Busca por Similaridade usando o Gráfico de Interação NK

  • José Moraes Universidade de São Paulo
  • Renato Tinós Universidade de São Paulo

Resumo


Um método de busca por similaridade baseado no grafo de interação NK é proposto. O grafo de interação NK foi originalmente empregado para agrupamento e é construído com base na distância e densidade espacial dos objetos em um conjunto de dados. Duas variações do método são investigadas. Nas duas variações, k objetos são retornados visitando-se vértices do grafo de interação NK a partir do vértice inicial relacionado ao exemplo do conjunto de dados que está mais próximo do objeto a ser consultado. Em NK A, os k objetos relacionados a vértices com arestas incidentes ao vértice inicial são retornados. Em NK B, k vértices são visitados a partir do vértice inicial. O próximo vértice visitado é aquele com aresta incidente ao vértice atual e que está mais próximo do novo objeto a ser consultado. Os k objetos relacionados aos vértices visitados são retornados. Os algoritmos propostos são comparados entre si e com a busca por similaridade baseada apenas na distância. Os resultados experimentais indicam que os métodos propostos apresentam bom desempenho quando existem clusters com formas arbitrárias no conjunto de dados.

Palavras-chave: Busca por Similaridade, grafo de interação NK

Referências

AHA, D. W.; KIBLER, D. & ALBERT, M.K. (1991). “Instance-based learning algorithms”, Machine Learning, 6(1): 37-66.

CARPINETO, C. & ROMANO, G. (2012). "A survey of automatic query expansion in information retrieval", ACM Computing Surveys (CSUR), 44(1).

ESTER, M.; KRIEGEL, H.-P.; SANDER, J. & XU, X. (1996), “A density-based algorithm for discovering clusters in large spatial databases with noise”, In the Proc. of the 2nd ACM Int. Conf. Knowl. Discovery Data Min. (KDD), 226–231.

FRÄNTI, P. & SIERANOJA, S. (2018). “K-means properties on six clustering benchmark datasets”, Applied Intelligence, 48 (12), 4743-4759.

HRUSCHKA, E. R.; CAMPELLO, R. J. G. B.; FREITAS, A. A. & CARVALHO, A. C. P. L. F. (2009). “A survey of evolutionary algorithms for clustering”, IEEE Transactions on Systems, Man, and Cybernetics, Part C, 39(2): 133-155.

HSINCHUN, C.; CHIANG, R. H. L. & STOREY, V. C. (2012). "Business intelligence and analytics: from big data to big impact", MIS Quarterly, 36(4): 1165-1188.

RODRIGUEZ, A. & LAIO, A. (2014). “Clustering by fast search and find of density peaks,” Science, 344(6191): 1492–1496.

TINÓS, R.; ZHAO, L.; CHICANO, F. & WHITLEY, D. (2018). “NK hybrid genetic algorithm for clustering”, IEEE Transactions on Evolutionary Computation, 22(5): 748-761.

AHA, D. W.; KIBLER, D. & ALBERT, M.K. (1991). “Instance-based learning algorithms”, Machine Learning, 6(1): 37-66.

CARPINETO, C. & ROMANO, G. (2012). "A survey of automatic query expansion in information retrieval", ACM Computing Surveys (CSUR), 44(1).

ESTER, M.; KRIEGEL, H.-P.; SANDER, J. & XU, X. (1996), “A density-based algorithm for discovering clusters in large spatial databases with noise”, In the Proc. of the 2nd ACM Int. Conf. Knowl. Discovery Data Min. (KDD), 226–231.

FRÄNTI, P. & SIERANOJA, S. (2018). “K-means properties on six clustering benchmark datasets”, Applied Intelligence, 48 (12), 4743-4759.

HRUSCHKA, E. R.; CAMPELLO, R. J. G. B.; FREITAS, A. A. & CARVALHO, A. C. P. L. F. (2009). “A survey of evolutionary algorithms for clustering”, IEEE Transactions on Systems, Man, and Cybernetics, Part C, 39(2): 133-155.

HSINCHUN, C.; CHIANG, R. H. L. & STOREY, V. C. (2012). "Business intelligence and analytics: from big data to big impact", MIS Quarterly, 36(4): 1165-1188.

RODRIGUEZ, A. & LAIO, A. (2014). “Clustering by fast search and find of density peaks,” Science, 344(6191): 1492–1496.

TINÓS, R.; ZHAO, L.; CHICANO, F. & WHITLEY, D. (2018). “NK hybrid genetic algorithm for clustering”, IEEE Transactions on Evolutionary Computation, 22(5): 748-761.
Publicado
20/10/2020
MORAES, José; TINÓS, Renato. Busca por Similaridade usando o Gráfico de Interação NK. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 17. , 2020, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 222-233. ISSN 2763-9061. DOI: https://doi.org/10.5753/eniac.2020.12131.