Una revisión de los algoritmos de partición más comunes en el análisis de conglomerados: un estudio comparativo

• SUSANA A. LEIVA-VALDEBENITO ^[1] ; FRANCISCO J. TORRES-AVILÉS ^[1]
  1. [1] Universidad de Santiago de Chile

     Universidad de Santiago de Chile

     Santiago, Chile

     
• Localización: Revista Colombiana de Estadística, ISSN-e 2389-8976, ISSN 0120-1751, Vol. 33, Nº. 2, 2010, págs. 321-339
• Idioma: español
• Títulos paralelos:
  • A Review of the Most Common Partition Algorithms in Cluster Analysis: A Comparative Study
• Enlaces
  • Texto completo
• Resumen
  • español

    Este estudio está enfocado en comparar diversos métodos de partición del análisis de conglomerados, usualmente conocidos como métodos no jerárquicos. En este trabajo, se realizan estudios de simulación para comparar los resultados obtenidos al implementar los algoritmos k-medias, k-medianas, PAM y Clara cuando los datos son multivariados y de tipo continuo. Adicionalmente, se efectúa un estudio de simulación con el fin de comparar algoritmos de partición para datos cualitativos, confrontando la eficiencia de los algoritmos PAM y k-modas. La eficiencia de los algoritmos se compara usando el índice de Rand ajustado y la tasa de correcta clasificación. Finalmente, se aplican los algoritmos a bases de datos reales, las cuales poseen clases predefinidas.

  • English

    This study is oriented to compare several partition methods in the context of cluster analysis, which are also called non hierarchical methods. In this work, a simulation study is performed to compare the results obtained from the implementation of the algorithms k-means, k-medians, PAM and CLARA when continuous multivariate information is available. Additionally, a study of simulation is presented to compare partition algorithms qualitative information, comparing the efficiency of the PAM and k-modes algorithms. The efficiency of the algorithms is compared using the Adjusted Rand Index and the correct classification rate. Finally, the algorithms are applied to real databases with predefined classes.

• Referencias bibliográficas
  • Anderberg, M.. (1973). Cluster Analysis for Applications. Academic Press. New York.
  • Anderson, B.,Gross, D.,Musicant, D.,Ritz, A.,Smith, T.,Steinberg, L.. (2006). Adapting K-Medians to Generate Normalized Cluster Centers. 'Proceedings...
  • Andreopoulos, B.,An, A.,Wang, X.. (2006). Clustering Mixed Numerical and Low Quality Categorical Data: Significance Metrics on a Yeast Example....
  • Der, G.,Everitt, B. S.. (2006). Statistical Analysis of Medical Data using SAS. CRC Press. Boca Raton.
  • Gower, J. C.. (1971). 'A General Coefficient of Similarity and Some of its Properties'. Biometrics. 27. 623-637
  • Hae, P.,Chi, J.. (2009). 'A simple and Fast Algorithm for K-medoids Clustering'. Expert Systems with Applications. 36. 3336-3341
  • Han, J.,Kamber, M.,Tung, A. K. H.. (2001). 'Geographic Data Mining and Knowledge Discovery'. Taylor & Francis.
  • Hartigan, J.. (1975). Clustering Algorithms. John Wiley & Sons. Nueva York.
  • He, Z.,Deng, S.,Xu, X.. (2005). Improving K-modes Algorithm Considering Frequencies of Attribute Values in Mode. Springer Berlin - Heidelberg....
  • He, Z.,Xu, X.,Deng, S.. (2007). 'Attribute Value Weighting in K-Modes Clustering'. Computer Science e-Prints. 1. 1-15
  • Huang, Z.. (1998). 'Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values'. Data Mining and Knowledge...
  • Hubert, L.,Arabie, P.. (1985). 'Comparing Partitions'. Journal of Classification. 2. 193-218
  • Kamber, M.,Han, J.. (2006). Data Mining Concepts and Techniques. Morgan Kaufman Publishers. San Francisco.
  • Kaufman, L.,Rousseeuw, P.. (1987). 'Statistical Data Analysis Based on the L1 Norm and Related Methods'. North-Holland.
  • Kaufman, L.,Rousseeuw, P.. (1990). Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley and Sons. New York.
  • Leiva, S.. (2008). Algoritmos de partición en el análisis de conglomerados: un estudio comparativo.
  • MacQueen, J.. (1967). 'Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability'. Symposium on mathematics....
  • McGarigal, K.,Cushman, S.,Stafford, S.. (2000). Multivariate Statistics for Wildlife and Ecology Research. Springer Verlag. New York.
  • Ng, M. K.,Li, M. J.,Huang, J. Z.,Zengyou, H.. (2007). 'On the Impact of Dissimilarity Measure in k-Modes Clustering Algorithm'. ,...
  • Ng, R.,Han, J.. (1994). Efficient and Effective Clustering Methods for Spatial Data Mining. 'Proceeding of the 20t h International Conference...
  • Peña, D.. (2002). Análisis de datos multivariantes. McGraw-Hill. Madrid.
  • Quinn, G.,Keough, M.. (2002). Experimental Design and Data Analysis for Biologists. Cambridge University Press. Cambridge.
  • (2010). R Development Core Team, R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing. Vienna.
  • SAS Institute Inc.. (2008). SAS/STAT 9.2 User's Guide. SAS Publishing. Cary.
  • Velmurugan, T.,Santhanam, T.. (2010). 'Computational Complexity between K-Means and K-Medoids Clustering Algorithms for Normal and Uniform...