An extensive comparative study of cluster validity indices
Pattern RecognitionPublished 9 August 2012
Olatz Arbelaitz, Ibai Gurrutxaga, Javier Muguerza, Jesús M. Pérez, Iñigo Perona
Citations1,309
SJR quartileQ1
SJR score2.06
SNIP2.67
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The results of an experimental work that compares 30 cluster validity indices in many different environments with different characteristics can serve as a guideline for selecting the most suitable index for each possible application and provide a deep insight into the performance differences between the currently available indices.
Abstract
The validation of the results obtained by clustering algorithms is a fundamental part of the clustering process. The most used approaches for cluster validation are based on internal cluster validity indices. Although many indices have been proposed, there is no recent extensive comparative study of their performance. In this paper we show the results of an experimental work that compares 30 cluster validity indices in many different environments with different characteristics. These results can serve as a guideline for selecting the most suitable index for each possible application and provide a deep insight into the performance differences between the currently available indices.
Keywords
Computer ScienceAgricultural and Biological SciencesPhysics and Astronomy
Journal of Computational and Applied MathematicsSilhouettes: A graphical aid to the interpretation and validation of cluster analysis
20,741 Citations1987Peter J. Rousseeuw
A new graphical display is proposed for partitioning techniques, where each cluster is represented by a so-called silhouette, which is based on the comparison of its tightness and separation, and provides an evaluation of clustering validity.
Statistical Comparisons of Classifiers over Multiple Data Sets
11,198 Citations2006Janez Demšar
A set of simple, yet safe and robust non-parametric tests for statistical comparisons of classifiers is recommended: the Wilcoxon signed ranks test for comparison of two classifiers and the Friedman test with the corresponding post-hoc tests for comparisons of more classifiers over multiple data sets.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Cluster Separation Measure
8,543 Citations1979David L. Davies, Donald W. Bouldin
A measure is presented which indicates the similarity of clusters which are assumed to have a data density which is a decreasing function of distance from a vector characteristic of the cluster which can be used to infer the appropriateness of data partitions.
Journal of ClassificationComparing partitions
7,714 Citations1985Lawrence J. Hubert, Phipps Arabie
A measure based on the comparison of object triples having the advantage of a probabilistic interpretation in addition to being corrected for chance is proposed and bounded between ±1.5 and ±2.5.
Communications in StatisticsA dendrite method for cluster analysis
6,686 Citations1974T. Calinski, J. Harabasz
A method for identifying clusters of points in a multidimensional Euclidean space is described and its application to taxonomy considered and an informal indicator of the "best number" of clusters is suggested.
Journal of CyberneticsA Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters
6,548 Citations1973J. C. Dunn
Two fuzzy versions of the k-means optimal, least squared error partitioning problem are formulated for finite subsets X of a general inner product space; in both cases, the extremizing solutions are shown to be fixed points of a certain operator T on the class of fuzzy, k-partitions of X, and simple iteration of T provides an algorithm which has the descent property relative to the least squarederror criterion function.
PsychometrikaAn Examination of Procedures for Determining the Number of Clusters in a Data Set
3,870 Citations1985Glenn W. Milligan, Martha C. Cooper
A Monte Carlo evaluation of 30 procedures for determining the number of clusters was conducted on artificial data sets which contained either 2, 3, 4, or 5 distinct nonoverlapping clusters to provide a variety of clustering solutions.
Neural ComputationApproximate Statistical Tests for Comparing Supervised Classification Learning Algorithms
3,654 Citations1998Thomas G. Dietterich
This article reviews five approximate statistical tests for determining whether one learning algorithm outperforms another on a particular learning task and measures the power (ability to detect algorithm differences when they do exist) of these tests.
Journal of Intelligent Information SystemsOn Clustering Validation Techniques
2,655 Citations2001Maria Halkidi, Yannis Batistakis +1 more
The fundamental concepts of clustering are introduced while it surveys the widely known clustering algorithms in a comparative way and the issues that are under-addressed by the recent algorithms are illustrated.
IEEE Transactions on Pattern Analysis and Machine IntelligencePerformance evaluation of some clustering algorithms and validity indices
1,388 Citations2002Ujjwal Maulik, Sanghamitra Bandyopadhyay
This article evaluates the performance of three clustering algorithms, hard K-Means, single linkage, and a simulated annealing (SA) based technique, in conjunction with four cluster validity indices, namely Davies-Bouldin index, Dunn's index, Calinski-Harabasz index, andA recently developed index I.
An Extension on "Statistical Comparisons of Classifiers over Multiple Data Sets" for all Pairwise Comparisons
1,299 Citations2008Salvador García, Francisco Herrera
The paper correctly introduces the basic procedures and some of the most advanced ones when comparing a control method, but it does not deal with some advanced topics in depth.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Some new indexes of cluster validity
1,142 Citations1998James C. Bezdek, Nikhil R. Pal
Journal of the American Statistical AssociationFinding the Number of Clusters in a Dataset
819 Citations2003Catherine A. Sugar, Gareth James
A simple, yet powerful nonparametric method for choosing the number of clusters based on distortion, a quantity that measures the average distance, per dimension, between each observation and its closest cluster center, is developed.
Lecture notes in computer scienceComparing Clusterings by the Variation of Information
599 Citations2003Marina Meilă
This paper proposes an information theoretic criterion for comparing two partitions, or clusterings, of the same data set, called variation of information (VI), which is positive, symmetric and obeys the triangle inequality.
A stability based method for discovering structure in clustered data
540 Citations2001Asa Ben‐Hur, André Elisseeff +1 more
The method can be used with any clustering algorithm and provides a means of rationally defining an optimum number of clusters, and can also detect the lack of structure in data.
Clustering validity assessment: finding the optimal partitioning of a data set
428 Citations2002Maria Halkidi, Michalis Vazirgiannis
A clustering validity procedure, which evaluates the results of clustering algorithms on data sets and defines a validity index, S Dbw, based on well-defined clustering criteria enabling the selection of optimal input parameter values for a clustering algorithm that result in the best partitioning of a data set.
Pattern Analysis and ApplicationsA new cluster validity measure and its application to image compression
328 Citations2004Chien-Hsing Chou, Mu‐Chun Su +1 more
This paper proposes a new validity measure that can deal with the edge degradation in vector quantisation of image compression and proposes a modified K-means algorithm that can assign more cluster centres to areas with low densities of data.
CERN Document Server (European Organization for Nuclear Research)Clustering for Data Mining: A Data Recovery Approach
298 Citations2005Boris Mirkin
PsychometrikaAn Examination of Indexes for Determining the Number of Clusters in Binary Data Sets
293 Citations2002Evgenia Dimitriadou, Sara Dolničar +1 more
This simulation includes 162 binary data sets that are clustered by two different algorithms and lead to recommendations on the number of clusters for each index under consideration, and focuses on high-dimensional empirical binary data.
Advances in information securityApplications of Data Mining in Computer Security
271 Citations2002Daniel Barbará, Sushil Jajodia
Modern Intrusion Detection, Data Mining, and Degrees of Attack Guilt, and Degrees of Attack Guilt are discussed.
Pattern Recognition LettersNew indices for cluster validity assessment
267 Citations2005Minho Kim, R. S. Ramakrishna
This paper presents an analysis of design principles implicitly used in defining cluster validity indices and reviews a variety of existing clusters validity indices in the light of these principles, and proposes six new indices.
Knowledge and Information SystemsCharacterization and evaluation of similarity measures for pairs of clusterings
248 Citations2008Darius Pfitzner, Richard Leibbrandt +1 more
A paradigm apparatus for the evaluation of clustering comparison techniques is introduced and the proposal of a novel clustering similarity measure, the Measure of Concordance, is proposed, showing that only MoC, Powers’s measure, Lopez and Rajski's measure and various forms of Normalised Mutual Information exhibit the desired behaviour under each of the test scenarios.
Journal of the American Statistical AssociationMeasuring the Power of Hierarchical Cluster Analysis
247 Citations1975Frank B. Baker, Lawrence J. Hubert
The results indicate that the power of a particular hierarchical clustering procedure is a function of the type of partition.
Pattern RecognitionModel-based evaluation of clustering validation measures
236 Citations2006Marcel Brun, Chao Sima +5 more
It is concluded that one should not put much faith in a validity score unless there is evidence, either in terms of sufficient data for model estimation or prior model knowledge, that a validity measure is well-correlated to the error rate of the clustering algorithm.
Pattern RecognitionHow many clusters are best? - An experiment
230 Citations1987Richard C. Dubes
The modified Hubert index, proposed here for the first time, is shown to perform better than the Davies-Bouldin index under all experimental conditions and demonstrates the difficulty inherent in estimating the number of clusters.
Journal of ClassificationComparing resemblance measures
176 Citations1995Vladimir Batagelj, Matevž Bren
In the paper some types of equivalences over resemblance measures and some basic results about them are given, and standard association coefficients between binary vectors are compared both theoretically and computationally.
IEEE Transactions on Knowledge and Data EngineeringA Point Symmetry-Based Clustering Technique for Automatic Evolution of Clusters
174 Citations2008Sanghamitra Bandyopadhyay, Sriparna Saha
A new symmetry-based genetic clustering algorithm is proposed which automatically evolves the number of clusters as well as the proper partitioning from a data set using a newly proposed PS-based cluster validity index, sym-index, as a measure of the validity of the corresponding partitioning.
Pattern RecognitionCluster validation using graph theoretic concepts
165 Citations1997Nikhil R. Pal, Jayabrata Biswas
The generalized Dunn's index and the Davies-Bouldin index for cluster validation using graph structures, such as GG, RNG and MST are generalized and superiority over some existing cluster validity indices is established.
Pattern RecognitionBootstrap technique in cluster analysis
147 Citations1987Anil K. Jain, J.V. Moreau
A method to estimate the number of clusters in a data set E, using the bootstrap technique, which involves the generation of several “fake” data sets by sampling patterns with replacement in E (bootstrapping).
Chapman & Hall/CRC eBooksClustering For Data Mining: A Data Recovery Approach (Chapman & Hall/Crc Computer Science)
135 Citations2005Boris Mirkin
The surgical principles applied with the aid of two cotton pads, gravity assist, and lateral horizontal head position, and without continuous use of brain retractors in the third ventricular lesion in the transcallosal interhemispheric approach are safe and secure in preventing perioperative brain edema or early postoperative neurological complications.
Lecture notes in computer scienceA Bounded Index for Cluster Validity
123 Citations2007Sandro Saitta, Benny Raphael +1 more
A new bounded index for cluster validity, called the score function (SF), is introduced, based on standard cluster properties, and is shown to work well on multi-dimensional data sets and is able to accommodate unique and sub-cluster cases.
Clustering: science or art?
120 Citations2011Ulrike von Luxburg, Robert C. Williamson +1 more
It is argued that it will be useful to build a "taxonomy of clustering problems" to identify clustering applications which can be treated in a unified way and that such an effort will be more fruitful than attempting the impossible--developing "optimal" domain-independent clustering algorithms or even classifying clusteringgorithms in terms of how they work.
Pattern Recognition LettersValidity index for clusters of different sizes and densities
118 Citations2010Krista Rizman Žalik, Borut Žalik
Two cluster validity indices are proposed for efficient validation of partitions containing clusters that widely differ in sizes and densities, each based on a compactness measure and a separation measure.
Pattern Recognition LettersA density-based cluster validity approach using multi-representatives
118 Citations2008Maria Halkidi, Michalis Vazirgiannis
A cluster validity index, CDbw, is proposed which assesses the compactness and separation of clusters defined by a clustering algorithm and enables the selection of the input parameter values that lead an algorithm to the best possible partitioning of the data set.
Pattern RecognitionSEP/COP: An efficient method to find the best partition in hierarchical clustering based on a new cluster validity index
100 Citations2010Ibai Gurrutxaga, Iñaki Albisua +5 more
SEP, a new method that efficiently searches in an extended partition set called SEP/COP is proposed and a new cluster validity index, COP, is proposed, since many of the commonly used indices cannot be used with SEP.
Soft ComputingA geometric approach to cluster validity for normal mixtures
98 Citations1997James C. Bezdek, Wei Li +2 more
Viewing mixture decomposition as probabilistic clustering as opposed to parametric estimation enables both fuzzy and crisp measures of cluster validity for this problem, and uses the expectation-maximization algorithm to find clusters in the data.
Pattern Recognition LettersTowards a standard methodology to evaluate internal cluster validity indices
84 Citations2010Ibai Gurrutxaga, Javier Muguerza +3 more
This work compared 7 internal cluster validity indices with both methodologies and concluded that the results obtained with the proposed methodology are more representative of the actual capabilities of the compared indices.
IEEE Transactions on Systems Man and Cybernetics Part C (Applications and Reviews)Performance Evaluation of Some Symmetry-Based Cluster Validity Indexes
36 Citations2009Sriparna Saha, Sanghamitra Bandyopadhyay
It is empirically established that incorporation of the property of symmetry significantly improves the capabilities of these indexes in identifying the appropriate number of clusters.
Pattern RecognitionNormality-based validation for crisp clustering
36 Citations2009Luis F. Lago-Fernández, Fernando Corbacho
A new validity index for crisp clustering that is based on the average normality of the clusters that provides better results than other indices, both with respect to the prediction of the correct number of clusters and to the similarity among the real clusters and those inferred.
Journal of the American Statistical AssociationClustering for Data Mining: A Data Recovery Approach
26 Citations2006Samuel E. Buttrey
As an advanced text in a specialty that is not even represented in many departments of statistics and biostatistics, I doubt the book will make many appearances in the “required course texts” part of the bookstore and I suspect this excellent book will be used most often by specialists in design.