Modified Dunn’s cluster validity index based on graph theory

• Autorzy: Ilc N.

Warianty tytułu

PL

Zmodyfikowany indeks oceny klastrów Dunna oparty na teorii grafów

• Języki publikacji: EN

Abstrakty

EN

Clustering methods serve as common tools for efficient data analysis in many fields of science. The essential, yet often neglected, step in the cluster analysis is validation of the clustering results. This paper presents a novel cluster validity index, which is the modification of the well-known Dunn’s index. Our proposal is based on its generalization considering the shortest paths between data points in the Gabriel graph. The experiments show that the proposed index can be successfully applied in the validation of the partitions, even when they contain complex-shaped clusters.

PL

Klasteryzacja danych jest często wykorzystywanym narzędziem analizy w wielu dziedzinach nauki. W pracy zaprezentowano nowy indeks oceny klastrów. Zaproponowane podejście jest uogólnieniem indeksu Dunna, bazującym na poszukiwaniu najkrótszej drogi pomiędzy punktami w grafie Gabriela. Przeprowadzone eksperymenty potwierdzają, że proponowany indeks może być stosowany do oceny podziałów zbiorów danych, nawet jeśli zawierają one klastry o skomplikowanych kształtach.

Słowa kluczowe

EN

cluster analysis; cluster validation; Dunn’s index; Gabriel graph

PL

analiza klasterów; ocena klastrów; indeks Dunna; graf Gabriela

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2012
• Tom: R. 88, nr 2
• Strony: 126--131
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Ilc N.

• Faculty of Computer and Information Science, University of Ljubljana, Tržaška 25, 1000 Ljubljana,

Bibliografia

• [1] Bishop C.M., Pattern Recognition and Machine Learning, Springer, 2006
• [2] Xu R., Wunsch II D., Survey of clustering algorithms, IEEE Transactions on Neural Networks, 16 (2005), 645–678
• [3] Handl J.,Knowles J., Kell D.B., Computational cluster validation in post-genomic data analysis, Bioinformatics, 21 (2005), 3201–3212
• [4] Halkidi M., Batistakis Y., Vazirgiannis M., On Clustering Validation Techniques, Journal of Intelligent Information Systems, 17 (2001), 107–145
• [5] Dunn J.C., A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters, Journal of Cybernetics, 3 (1973), 32–57
• [6] Pal N.R., Biswas J., Cluster validation using graph theoretic concepts, Pattern Recognition, 30 (1997), 847–857
• [7] Bezdek J., Pal N., Some new indexes of cluster validity, IEEE Transactions on Systems, Man, and Cybernetics, 28 (1998), 301–315
• [8] Shi J., Malik J., Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22 (2000), 888–905
• [9] Handl J., Knowles J., Exploiting the Trade-off –The Benefits of Multiple Objectives in Data Clustering. In: Coello Coello C., Hernández Aguirre A., Zitzler E., editors, Evolutionary Multi- Criterion Optimization, vol. 3410 of LNCS, Springer Berlin / Heidelberg, 2005, 547–560
• [10] Gabriel K.R., Sokal R.R., A New Statistical Approach to Geographic Variation Analysis, Systematic Zoology, 18 (1969), No. 3, 259–278
• [11] Matula D.W., Sokal R.R., Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane, Geographical Analysis, 12 (1980), 205– 222
• [12] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to algorithms, MIT Press, 2001
• [13] Ilc N., Artificial datasets for clustering, URL: http://laspp. fri.uni-lj.si/nejci/data/, 2011
• [14] Kuncheva L.I., Clustering data, URL: http://pages. bangor.ac.uk/~mas00a/activities/artificial_ data.htm, 2011
• [15] Frank A., Asuncion A., UCI Machine Learning Repository, URL: http://archive.ics.uci.edu/ml/, 2010
• [16] Vega-Pons S., Correa-Morris J., Ruiz-Shulcloper J., Weighted partition consensus via kernels, Pattern Recognition, 43 (2010), 2712–2724
• [17] Gurrutxaga I., Muguerza J., Arbelaitz O., Pérez J.M., Martín J.I., Towards a standard methodology to evaluate internal cluster validity indices, Pattern Recognition Letters, 32 (2011), 505–515
• [18] Meila M., Comparing clusterings – an information based distance, Journal of Multivariate Analysis, 98 (2007), 873–895
• [19] Strehl A., Ghosh J., Cluster Ensembles – A Knowledge Reuse Framework for Combining Multiple Partitions, Journal of Machine Learning Research, 3 (2002), 583–617