¹Universidad de Santiago de Chile, Facultad de Ciencia, Departamento de Matemática y Ciencia de la Computación, Santiago, Chile. Estudiante de Ingeniería Estadística. Email: susanaleivav@gmail.com
²Universidad de Santiago de Chile, Facultad de Ciencia, Departamento de Matemática y Ciencia de la Computación, Santiago, Chile. Profesor asistente. Email: francisco.torres@usach.cl

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.

Palabras clave: algoritmos de conglomerados, medida de similaridad, simulación.

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.

Key words: Clustering algorithm, Similarity measure, Simulation.

Texto completo disponible en PDF

Referencias

1. Anderberg, M. (1973), Cluster Analysis for Applications, Academic Press, New York, United States.

2. Anderson, B., Gross, D., Musicant, D., Ritz, A., Smith, T. & Steinberg, L. (2006), Adapting K-Medians to Generate Normalized Cluster Centers, `Proceedings of the 2006 SIAM International Conference on Data Mining´, Bethesda, p. 165-175.

3. Andreopoulos, B., An, A. & Wang, X. (2006), Clustering Mixed Numerical and Low Quality Categorical Data: Significance Metrics on a Yeast Example, `ACM SIGMOD Workshop on Information Quality in Information Systems, IQIS 2005 Statistics Clustering Session´, Baltimore, p. 87-98.

4. Der, G. & Everitt, B. S. (2006), Statistical Analysis of Medical Data using SAS, CRC Press, Boca Raton, United States.

5. Gower, J. C. (1971), `A General Coefficient of Similarity and Some of its Properties´, Biometrics 27, 623-637.

6. Hae, P. & Chi, J. (2009), `A simple and Fast Algorithm for K-medoids Clustering´, Expert Systems with Applications 36, 3336-3341.

7. Han, J., Kamber, M. & Tung, A. K. H. (2001), Spatial Clustering Methods in Data Mining: A Survey, `Geographic Data Mining and Knowledge Discovery´, Taylor & Francis.

8. Hartigan, J. (1975), Clustering Algorithms, John Wiley & Sons, Nueva York, United States.

9. He, Z., Deng, S. & Xu, X. (2005), Improving K-modes Algorithm Considering Frequencies of Attribute Values in Mode, Vol. 3801 of Lecture Notes in Computer Science, Springer Berlin - Heidelberg, p. 157-162.

10. He, Z., Xu, X. & Deng, S. (2007), `Attribute Value Weighting in K-Modes Clustering´, Computer Science e-Prints 1, 1-15.

11. Huang, Z. (1998), `Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values´, Data Mining and Knowledge Discovery 2, 283-304.

12. Hubert, L. & Arabie, P. (1985), `Comparing Partitions´, Journal of Classification 2, 193-218.

13. Kamber, M. & Han, J. (2006), Data Mining Concepts and Techniques, Morgan Kaufman Publishers, San Francisco, United States.

14. Kaufman, L. & Rousseeuw, P. (1987), Clustering by Means of Medoids, `Statistical Data Analysis Based on the L₁ Norm and Related Methods´, North-Holland, p. 405-416.

15. Kaufman, L. & Rousseeuw, P. (1990), Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley and Sons, New York, United States.

16. Leiva, S. (2008), Algoritmos de partición en el análisis de conglomerados: un estudio comparativo, Trabajo de Grado, Universidad de Santiago de Chile, Chile.

17. MacQueen, J. (1967), Some Methods for classification and Analysis of Multivariate Observations, `Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability´, Vol. 1, Symposium on mathematics, , , p. 281-297.

18. McGarigal, K., Cushman, S. & Stafford, S. (2000), Multivariate Statistics for Wildlife and Ecology Research, Springer Verlag, New York, United States.

19. Ng, M. K., Li, M. J., Huang, J. Z. & Zengyou, H. (2007), `On the Impact of Dissimilarity Measure in k-Modes Clustering Algorithm´, , IEEE Transactions on Pattern Analysis and Machine Intelligence 29(3), 503-507.

20. Ng, R. & Han, J. (1994), Efficient and Effective Clustering Methods for Spatial Data Mining, `Proceeding of the 20^th International Conference on Very Large Databases´, p. 144-155.

21. Peña, D. (2002), Análisis de datos multivariantes, McGraw-Hill, Madrid, España.

22. Quinn, G. & Keough, M. (2002), Experimental Design and Data Analysis for Biologists, Cambridge University Press, Cambridge, UK.

23. R Development Core Team, (2010), R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing, Vienna, Austria. ISBN 3-900051-07-0. *http://www.R-project.org

24. SAS Institute Inc., (2008), SAS/STAT 9.2 User's Guide, SAS Publishing, Cary, Carolina del Norte.

25. Velmurugan, T. & Santhanam, T. (2010), `Computational Complexity between K-Means and K-Medoids Clustering Algorithms for Normal and Uniform Distributions of Data Points´, Journal of Computer Science 6(3), 363-368.

Este artículo se puede citar en LaTeX utilizando la siguiente referencia bibliográfica de BibTeX: