Published

2010-07-01

UNA REVISIÓN DE LOS ALGORITMOS DE PARTICIÓN MÁS COMUNES EN EL ANÁLISIS DE CONGLOMERADOS: UN ESTUDIO COMPARATIVO

A REVIEW OF THE MOST COMMON PARTITION ALGORITHMS IN CLUSTER ANALYSIS: A COMPARATIVE STUDY

Keywords:

algoritmos de conglomerados, medida de similaridad, simulación (es)
Clustering algorithm, Similarity measure, Simulation (en)

Downloads

Authors

  • Susana A. Leiva-Valdebenito Universidad de Santiago de Chile
  • Francisco J. Torres-Avilés Universidad de Santiago de Chile
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.
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.

References

Abonyi, J. & Feil, B. (2007), Clustering Analysis for Data Mining and

System Identification, Birkhauser Verlag AG, Berlin, Germany.

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

Anderson, B., Gross, D., Musicant, D., Ritz, A., Smith, T. & Steinberg, L. (2006), Adapting K-Medians to Generate Normalized Cluster Centers, in 'Procee-dings of the 2006 SIAM International Conference on Data Mining', Bethesda, pp. 165-175.

Andreopoulos, B., An, A. & Wang, X. (2006), Clustering Mixed Numerical

and Low Quality Categorical Data: Significante Metrics on a Yeast Example, in `ACM SIGMOD Workshop on Information Quality in Information

Systems, IQIS 2005 Statistics Clustering Session', Baltimore, pp. 87-98.

Asuncion, A. & Newman, D. J. (2007), PCI machine learning repository'.

*http://www.ics.ucledu/—mleam/MLRepository-.html

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

Gower, J. C. (1971), 'A General Coefficient of Similarity and Some of its Proper-ties', 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), Spatial Clustering Methods in Data Mining: A Survey, in H. J. Miller & J. Han, eds, `Geographic Data Mining and Knowledge Discovery', Taylor & Francis.

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

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, pp. 157-162.

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 Discovery 2, 283-304.

Hubert, L Sc 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, United States.

Kaufman, L. & Rousseeuw, P. (1987), Clustering by Means of Medoids, in D. Y., ed., Statistical Data Analysis Based on the L1 Norm and Related Methods', North-Holland, pp. 405-416.

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

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.

MacQueen, J. (1967), Some Methods for classification and Analysis of

Multivariate Observations, in 'Proceedings of 5-th Berkeley Symposium on

Mathematical Statistics and Probability', Vol. 1, Sy-mposium on

mathematics, pp. 281-297.

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

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.

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

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

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

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

SAS Institute Inc. (2008), SAS/STAT 9.2 User's Guide, SAS Publishing,

Cary, Carolina del Norte.

Velmurugan, T. & Santhanam, T. (2010), `Computationa1 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.

Article abstract page views

481

Downloads

Download data is not yet available.

How to Cite

Leiva-Valdebenito, S. A., & Torres-Avilés, F. J. (2010). A REVIEW OF THE MOST COMMON PARTITION ALGORITHMS IN CLUSTER ANALYSIS: A COMPARATIVE STUDY. Revista Colombiana De Estadística, 33(2), 321-339. https://revistas.unal.edu.co/index.php/estad/article/view/29880

License

Copyright (c) 2010 Revista Colombiana de Estadística

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).