Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 29 September 2006
Ludmila I. Kuncheva, Dmitry Vetrov
Citations315
SJR quartileQ1
SJR score3.91
SNIP5.99
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
A new combined stability index is proposed to be the sum of the pairwise individual and ensemble stabilities to correlate better with the ensemble accuracy, following the hypothesis that a point of stability of a clustering algorithm corresponds to a structure found in the data.
Abstract
Many clustering algorithms, including cluster ensembles, rely on a random component. Stability of the results across different runs is considered to be an asset of the algorithm. The cluster ensembles considered here are based on k-means clusterers. Each clusterer is assigned a random target number of clusters, k and is started from a random initialization. Here, we use 10 artificial and 10 real data sets to study ensemble stability with respect to random k, and random initialization. The data sets were chosen to have a small number of clusters (two to seven) and a moderate number of data points (up to a few hundred). Pairwise stability is defined as the adjusted Rand index between pairs of clusterers in the ensemble, averaged across all pairs. Nonpairwise stability is defined as the entropy of the consensus matrix of the ensemble. An experimental comparison with the stability of the standard k-means algorithm was carried out for k from 2 to 20. The results revealed that ensembles are generally more stable, markedly so for larger k. To establish whether stability can serve as a cluster validity index, we first looked at the relationship between stability and accuracy with respect to the number of clusters, k. We found that such a relationship strongly depends on the data set, varying from almost perfect positive correlation (0.97, for the glass data) to almost perfect negative correlation (-0.93, for the crabs data). We propose a new combined stability index to be the sum of the pairwise individual and ensemble stabilities. This index was found to correlate better with the ensemble accuracy. Following the hypothesis that a point of stability of a clustering algorithm corresponds to a structure found in the data, we used the stability measures to pick the number of clusters. The combined stability index gave best results.
Keywords
Computer SciencePhysics and Astronomy
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
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.
Cambridge University Press eBooksPattern Recognition and Neural Networks
6,468 Citations1996B. D. Ripley
Journal of the American Statistical AssociationObjective Criteria for the Evaluation of Clustering Methods
5,815 Citations1971Telmo Menezes
Journal of the Royal Statistical Society Series A (General)Pattern Classification and Scene Analysis.
3,240 Citations1974Mairi Clarke, Richard O. Duda +1 more
Machine LearningConsensus Clustering: A Resampling-Based Method for Class Discovery and Visualization of Gene Expression Microarray Data
2,181 Citations2003Stefano Monti, Pablo Tamayo +2 more
A new methodology of class discovery and clustering validation tailored to the task of analyzing gene expression data is presented, and in conjunction with resampling techniques, it provides for a method to represent the consensus across multiple runs of a clustering algorithm and to assess the stability of the discovered clusters.
Journal of the American Statistical AssociationObjective Criteria for the Evaluation of Clustering Methods
1,841 Citations1971William Rand
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.
IEEE Transactions on Pattern Analysis and Machine IntelligenceCombining multiple clusterings using evidence accumulation
1,167 Citations2005Ana Fred, Anil K. Jain
A theoretical framework for the analysis of the proposed clustering combination strategy and its evaluation is developed, based on the concept of mutual information between data partitions, for extracting a consistent clustering, given the various partitions in a clustering ensemble.
Applied Physics Letters10.1162/153244302760200704
696 Citations2000
It is shown how to use notions of stability for learning algorithms to derive generalization error bounds based on the empirical error and the leave-one-out error to apply to SVM for regression and classification.
Random projection for high dimensional data clustering: a cluster ensemble approach
582 Citations2003Xiaoli Z. Fern, Carla E. Brodley
Empirical results show that the proposed approach achieves better and more robust clustering performance compared to not only single runs of random projection/clustering but also clustering with PCA, a traditional data reduction method for high dimensional data.
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.
Neural ComputationStability-Based Validation of Clustering Solutions
528 Citations2004Tilman Lange, Volker Röth +2 more
A measure of cluster stability is introduced to assess the validity of a cluster model and its suitability as a general validation tool for clustering solutions in real-world problems.
BioinformaticsBagging to improve the accuracy of a clustering procedure
526 Citations2003Sandrine Dudoit, Jane Fridlyand
Two new resampling methods, inspired from bagging in prediction, are proposed to improve and assess the accuracy of a given clustering procedure to solve the problem of accurate partitioning of tumor samples into clusters.
Data clustering using evidence accumulation
513 Citations2003Ana Fred, Anil K. Jain
Results on both synthetic and real data show the ability of the K-means method to identify arbitrary shaped clusters in multidimensional data.
MPG.PuRe (Max Planck Society)Stability and Generalization
495 Citations2001Bousquet, O., Elisseeff, A.
A Mixture Model for Clustering Ensembles
383 Citations2004A. Topchy, Anil K. Jain +1 more
A probabilistic model of consensus using a finite mixture of multinomial distributions in a space of clusterings is offered and a combined partition is found as a solution to the corresponding maximum likelihood problem using the EM algorithm.
Combining multiple weak clusterings
346 Citations2004A. Topchy, Anil K. Jain +1 more
This work introduces a unified representation for multiple clusterings and forms the corresponding categorical clustering problem, and shows that the consensus function is related to the classical intra-class variance criterion using the generalized mutual information definition.
Robust data clustering
337 Citations2003L.N.F. Ana, Anil K. Jain
It is shown that the proposed technique attempts to optimize the mutual information based criteria, although the optimality is not ensured in all situations, and experimental results show the ability of the technique to identify clusters with arbitrary shapes and sizes.
Lecture notes in computer scienceFinding Consistent Clusters in Data Partitions
300 Citations2001Ana Fred
This paper addresses the problem of finding consistent clusters in data partitions, proposing the analysis of the most common associations performed in a majority voting scheme, and evaluating the proposed methodology in the context of k-means clustering, a new clustering algorithm being presented.
Using diversity in cluster ensembles
273 Citations2005Ludmila I. Kuncheva, Stefan Hadjitodorov
A variant of the generic ensemble method where the number of overproduced clusters is chosen randomly for every ensemble member (partition) is proposed and it is shown that this approach increases the spread of the diversity within the ensemble thereby leading to a better match with the known cluster labels.
Neural ComputationResampling Method for Unsupervised Estimation of Cluster Validity
271 Citations2001Erel Levine, Eytan Domany
A figure of merit that measures the stability of clustering solutions against resampling is introduced, and the applicability of the method for validation of results obtained by clustering analysis of data for higher-dimensional data, including gene microarray expression data.
Information FusionModerate diversity for better cluster ensembles
222 Citations2005Stefan Hadjitodorov, Ludmila I. Kuncheva +1 more
The results suggest that selection by median diversity is no worse and in some cases is better than building and holding on to one ensemble.
IEEE Transactions on Pattern Analysis and Machine IntelligenceBagging for path-based clustering
209 Citations2003Bernd Fischer, Joachim M. Buhmann
A resampling scheme for clustering with similarity to bootstrap aggregation (bagging) is presented to improve the quality of path-based clustering, a data clustering method that can extract elongated structures from data in a noise robust way.
Ensembles of partitions via data resampling
136 Citations2004Behrouz Minaei‐Bidgoli, A. Topchy +1 more
A data resampling approach for building cluster ensembles that are both robust and stable is proposed, and the effectiveness of a bootstrapping technique in conjunction with several combination algorithms is investigated.
COMPSTATA Resampling Approach to Cluster Validation
127 Citations2002Volker Röth, Tilman Lange +2 more
This work presents an empirical estimator for the theoretically derived stability index, based on imitating independent sample-sets by way of resampling, and demonstrates that the proposed validation principle is highly suited for model selection.
Lecture notes in computer scienceMulticlassifier Systems: Back to the Future
116 Citations2002Joydeep Ghosh
This article argues that the current understanding of ensemble-type multiclassifier systems is now quite mature and exhorts the reader to consider a broader set of models and situations for further progress.
Stability of Randomized Learning Algorithms
94 Citations2005André Elisseeff, Theodoros Evgeniou +1 more
The formal definitions of stability for randomized algorithms are given and non-asymptotic bounds on the difference between the empirical and expected error as well as the leave-one-out and expectederror of such algorithms that depend on their random stability are proved.
Lecture notes in computer scienceFinding Natural Clusters Using Multi-clusterer Combiner Based on Shared Nearest Neighbors
91 Citations2003Hanan Ayad, Mohamed S. Kamel
Preliminary experiments show promising results, and comparison with a recent study justifies the combiner's suitability to the pre-defined problem domain.
Ensemble clustering in medical diagnostics
79 Citations2004Derek Greene, Alexey Tsymbal +2 more
The potential of applying ensemble clustering techniques with a focus on the area of medical diagnostics is examined and it is shown that diversity among ensemble members is necessary, but not sufficient to yield an improved solution without the selection of an appropriate integration method.
Asia-Pacific Bioinformatics ConferenceCluster ensemble and its applications in gene expression analysis
76 Citations2004Xiaohua Hu, Illhoi Yoo
A cluster ensemble framework for gene expression analysis to generate high quality and robust clustering results and experiment results indicate that cluster ensemble approach yields better clusteringResults than the single best clustering algorithm on both synthetic data set and yeast gene expression data set.
Journal of Machine Learning ResearchStability of Randomized Learning Algorithms
56 Citations2005ElisseeffAndré, EvgeniouTheodoros +1 more
Pattern Recognition LettersROC curves and video analysis optimization in intestinal capsule endoscopy
52 Citations2006Fernando Vilariño, Ludmila I. Kuncheva +1 more
The results reinforce the claims from recent literature that classifier ensemble methods specifically designed for imbalanced problems have substantial advantages over simple classifiers and standard classifier ensembles.
An Ensemble Method for Clustering
41 Citations2003Andreas Weingessel, Evgenia Dimitriadou +1 more
This work presents a methodology for combining ensembles of partitions obtained by clustering, discusses the properties of such combination strategies and relate them to the task of assessing partition “aggrement”.