Simpósio de Pesquisa Operacional e Logística da Marinha - Publicação Online

Agosto 2016, vol.2, num.1 - XVIII Simpósio de Pesquisa Operacional & Logística da Marinha
Artigo Completo - Open Access Idioma principal | Segundo principal

UMA HEURÍSTICA BASEADA EM DENSIDADE PARA O PROBLEMA DE AGRUPAMENTO AUTOMÁTICO

UMA HEURÍSTICA BASEADA EM DENSIDADE PARA O PROBLEMA DE AGRUPAMENTO AUTOMÁTICO

Semaan, Gustavo Silva; Fadel, Augusto César; Brito, José André de Moura; Ochi, Luiz Satoru

Artigo Completo:

A análise de agrupamentos agrega vários métodos que visam identificar grupos dentro de um conjunto de dados. Este artigo apresenta novas heurísticas baseadas na metaheurística Busca Local Iterada para resolver o Problema de Agrupamento Automático, qual seja o problema de determinar o número ideal de grupos para uma base dados. Para tal, em uma das fases da aplicação desta heurística, foi utilizado o índice silhueta, que combina conceitos de coesão e separação e é considerado pelas heurísticas propostas para avaliar a qualidade das soluções. De acordo com os experimentos computacionais reportados neste trabalho, verifica-se que a nova heurística ILS-DBSCAN é muito eficiente no que concerne ao tempo de processamento e muito eficaz quanto à qualidade das soluções obtidas, quando comparado com outros métodos da literatura. Em geral, os resultados desta nova heurística foram superiores aos resultados relatados na literatura. Dessa maneira o ILS-DBSCAN apresenta-se como um algoritmo promissor para a resolução do problema abordado.

A análise de agrupamentos agrega vários métodos que visam identificar grupos dentro de um conjunto de dados. Este artigo apresenta novas heurísticas baseadas na metaheurística Busca Local Iterada para resolver o Problema de Agrupamento Automático, qual seja o problema de determinar o número ideal de grupos para uma base dados. Para tal, em uma das fases da aplicação desta heurística, foi utilizado o índice silhueta, que combina conceitos de coesão e separação e é considerado pelas heurísticas propostas para avaliar a qualidade das soluções. De acordo com os experimentos computacionais reportados neste trabalho, verifica-se que a nova heurística ILS-DBSCAN é muito eficiente no que concerne ao tempo de processamento e muito eficaz quanto à qualidade das soluções obtidas, quando comparado com outros métodos da literatura. Em geral, os resultados desta nova heurística foram superiores aos resultados relatados na literatura. Dessa maneira o ILS-DBSCAN apresenta-se como um algoritmo promissor para a resolução do problema abordado.

Download (PDF)

Palavras-chave:

DOI: 10.5151/marine-spolm2015-139822

Referências bibliográficas
  • [1] Aiex, R. M., Resende, M. G. C., and Ribeiro, C. C. (2007). TTT plots: a perl program to create time-to-target plots. Optimization Letters.
  • [2] Alves, V., R. Campello, & E. Hruschka (2006). Towards a fast evolutionary algorithm for clustering. In IEEE Congress on Evolutionary Computation, 2006, Vancouver, Canada, pp. 1776–1783.
  • [3] Banerjee, A. Validating clusters using the hopkins statistic. IEEE International Conference on Date of Conference, 2004.
  • [4] Baum, E.B. Iterated descent: A better algorithm for local search in combinatorial optimization problems. Technical report Caltech, Pasadena, CA. Manuscript, 1986.
  • [5] Campello, R. J. G. B., Hruschka, E. R., and Alves, V. S. (2009). On the efficiency of evolutionary fuzzy clustering. Journal of Heuristics 15, page 43-75.
  • [6] Cruz, M. D. O Problema de Clusterização Automática. Tese de Doutorado, UFRJ, Rio de Janeiro, 2010.
  • [7] Dias, C.R.; & Ochi, L.S.. Efficient Evolutionary Algorithms for the Clustering Problems in Directed Graphs. Proc. of the IEEE Congress on Evolutionary Computation (IEEECEC), 983-988. Canberra, Austrália, 2003.
  • [8] Ester, M., H.-P. Kriegel, J. Sander, & X. Xu (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD’96), pp. 226–231.
  • [9] Fisher, R. The use of multiple measurements in taxonomic problems. Annual Eugenics 7, 1936.
  • [10] Garai, G. & Chaudhuri, B. (2004), A novel genetic algorithm for automatic clustering, Pattern Recognition Letters, Ed. 25, pg. 173–187.
  • [11] Goldschimidt R.; Passos, E. Data Mining: um guia prático. Editora Campus, Rio de Janeiro: Elsevier, 2005.
  • [12] Hair, J.F, Black, W.C, Babin, B.J., Anderson, R.E. e Tatham, R.L. Análise Multivariada de Dados, Bookman, Sexta Edição, 2009.
  • [13] Han, J., e Kamber, M., Cluster Analysis. In: Morgan Kaufmann. Publishers (eds.), Data Mining: Concepts and Techniques, 2 ed., chapter 8, New York, USA, Academic Press, 2006.
  • [14] Hastie, t., Tibshirani, R., and Friedman, J. (2001). The elements of statistical learning. Data Mining, Inference, and prediction.
  • [15] Hruschka, E. R., Ebecken, N. F. F. A Genetic algorithm for cluster analysis. IEEE Transactions on Evolutionary Computation , 2001.
  • [16] Hruschka, E. R. & Ebecken, N. F. F. (2003). A genetic algorithm for cluster analysis. Intelligent Data Analysis 7 (1), 15–25.
  • [17] Hruschka, E. R., R. J. G. B. Campello, & L. N. de Castro (2004a). Evolutionary algorithms for clustering gene-expression data. In Proc. IEEE Int. Conf. on Data Mining, Brighton/England, pp. 403–406.
  • [18] Hruschka, E. R., R. J. G. B. Campello, & L. N. de Castro (2006). Evolving clusters in gene-expression data. Information Sciences 176 (13), 1898–1927.
  • [19] Johnson, R.; Wichern, D. Applied multivariate statistical analysis. 3.ed. New Jersey: Pretince-Hill, 2001. 642p.
  • [20] Kumar, V. ; Steinbach, M. ; Tan, P. N. Introdução ao Data Mining - Mineração De Dados. Ciência Moderna, 2009.
  • [21] Larose, D. T. Discovering Knowledge in Data, An Introduction to Data Mining. John Wiley & Sons, 2005.
  • [22] Larrañaga, Pedro; & Lozano, Jose A. Estimation of distribution algorithms: A new tool for evolutionary computation. Kluwer Academic Publishers, Boston, 2002.
  • [23] Lourenco, H. R., Martin, O. C., and Stuzle, T. (2010). Iterated local search: Framework and applications. In Glover, F. and Kochenberger, G., editors, Handbook of Metaheuristics, pages 363-397. Kluwer Academic Publishers.
  • [24] Ma, P. C. H., Chan, K. C. C., Yao, X., and Chiu, D. K. Y. (2006). An evolutionary clustering algorithm for gene expression microarray data analysis. Evolutionary Computations 10, page 296-314.
  • [25] Maulik, U. & Bandyopadhyay, S. (2000), Genetic Algorithm-based Clustering Technique, Pattern Recognition p.33,1455-1465.
  • [26] Macqueen, J. B. (1967). Some Methods for Classification and Analysis of MultiVariate Observations. Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. P. 281-297, V. 1.
  • [27] Maronna, R. and Jacovkis, P. M. Multivariate clustering procedures with variable metrics. Biometrics 30, 1974.
  • [28] Naldi, M. C. & A. C. P. L. F. Carvalho (2007). Clustering using genetic algorithm combining validation criteria. In Proceedings of the 15th European Symposium on Artificial Neural Networks, ESANN 2007, Volume 1. 2007.
  • [29] Naldi, C. N. Técnicas de Combinação para Agrupamento Centralizado e Distribuído de Dados. Tese de Doutorado, USP - São Carlos, 2011.
  • [30] Oliveira, C. EDACLUSTER: Um Algoritmo Evolucionário para Análise de Agrupamentos Baseados em Densidade e Grade, Dissertação (Mestrado em Engenharia Elétrica), Universidade Federal do Pará, 2007.
  • [31] Pakhira, M., S. B. and Maulik, U. (2005). A study of some fuzzy cluster validity indices, genetic clustering and application to pixel classification. Fuzzy Sets Systems 155, page 191-214.
  • [32] Pal, N. and Bezdek, J. (1995). On cluster validity for the fuzzy c-means model. IEEE Transactions of Fuzzy Systems 3, page 370-379.
  • [33] Rakesh, A., Johanners, G., Dimitrios, G. & Prabhakar, R. (1999). Automatic subspace clustering of high dimensional data for data mining applications. In: Proc. of the ACM SIGMOD, p.94-105.
  • [34] Reeves, C. R. Genetic algorithms. In Glover, F. and Kochenberger, G., editors, Handbook of Metaheuristics, Kluwer Academic Publishers. 2010.
  • [35] Rousseeuw, P. J. (1987). Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics 20, 53–65.
  • [36] Ruspini, E. H. Numerical methods for fuzzy clustering. Information Science, 1970.
  • [37] Semaan, G. S., Cruz, M.D., Brito, J. A. M., and Ochi, L. S. "Proposta de um método de classificação baseado em densidade para a determinação do número ideal de grupos em problemas de clusterização", Learning & Nonlinear Models v.10 n4, 2012.
  • [38] Semaan, G. S. Algoritmos para o Problema de Agrupamento Automático. Tese de Doutorado, Instituto de Computação, Universidade Federal Fluminense, 2013.
  • [39] Semaan, G. S. ; Vasconcelos, R. B. ; Brito, J. A. M. ; Ochi, L. S. Proposta de um Método Baseado em Densidade e Grade para o Problema de Agrupamento Automático. XVII Simpósio de Pesquisa Operacional e Logística da Marinha. Ed. Edgard Blücher, 2014.
  • [40] Semaan, G. S., Torres, C., Brito, J. A. M., Ochi, L. S. . Um Método Baseado em Combinação de Soluções com Coassociação para o Problema de Agrupamento Automático. Revista Brasileira de Estatística, v. 74, p. 43-68, 2013.
  • [41] Soares, S. S. R. F., Ochi, L. S. Um Algoritmo Evolutivo com Reconexão de Caminhos para o Problema de Clusterização Automática. in XII Latin Ibero American Congress on Operations Research, Proc. of the XII CLAIO, 2004.
  • [42] Soares, S. R. F. (2004b). Metaheurísticas para o problema de clusterização automática. Dissertação de mestrado, Universidade Federal Fluminense.
  • [43] Tseng, L. & . Yang, S.B. A genetic approach to the automatic clustering problem. Pattern Recognition 34, 2001.
  • [44] Wang et al., Wang, X., Qiu, W., Zamar, R. H. (2007). CLUES: A non-parametric clustering method based on local shrinking. Computational Statistics & Data Analysis 52, 2007.
Como citar:

Semaan, Gustavo Silva; Fadel, Augusto César; Brito, José André de Moura; Ochi, Luiz Satoru; "UMA HEURÍSTICA BASEADA EM DENSIDADE PARA O PROBLEMA DE AGRUPAMENTO AUTOMÁTICO", p-100-112. In: Anais do XVIII Simpósio de Pesquisa Operacinal & Logística da Marinha. São Paulo: Blucher, 2016.
ISSN 21756295, DOI 10.5151/marine-spolm2015-139822

últimos 30 dias

111
downloads

221
visualizações

999
indexações