Busca por Similaridade usando o Gráfico de Interação NK
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.
Referências
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.
