Cluster ensembles
Wiley Interdisciplinary Reviews Data Mining and Knowledge DiscoveryPublished 2 May 2011
Joydeep Ghosh, Ayan Acharya
Citations186
SJR quartileQ1
SJR score2.20
SNIP4.05
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 variety of algorithms that have been proposed to address the cluster ensemble problem are described, organizing them in conceptual categories that bring out the common threads and lessons learnt while simultaneously highlighting unique features of individual approaches.
Abstract
Abstract Cluster ensembles combine multiple clusterings of a set of objects into a single consolidated clustering, often referred to as the consensus solution. Consensus clustering can be used to generate more robust and stable clustering results compared to a single clustering approach, perform distributed computing under privacy or sharing constraints, or reuse existing knowledge. This paper describes a variety of algorithms that have been proposed to address the cluster ensemble problem, organizing them in conceptual categories that bring out the common threads and lessons learnt while simultaneously highlighting unique features of individual approaches. © 2011 John Wiley & Sons, Inc. WIREs Data Mining Knowl Discov 2011 1 305–315 DOI: 10.1002/widm.32 This article is categorized under: Technologies > Structure Discovery and Clustering
Keywords
Computer SciencePhysics and Astronomy
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.
SIAM Journal on Scientific ComputingA Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
5,588 Citations1998George Karypis, Vipin Kumar
This work presents a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of theSize of the final partition obtained after multilevel refinement, and presents a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening.
Algorithms for Non-negative Matrix Factorization
5,463 Citations2000Daniel D. Lee, H. Sebastian Seung
Two different multiplicative algorithms for non-negative matrix factorization are analyzed and one algorithm can be shown to minimize the conventional least squares error while the other minimizes the generalized Kullback-Leibler divergence.
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.
ComputerChameleon: hierarchical clustering using dynamic modeling
2,102 Citations1999George Karypis, Eui-Hong Han +1 more
Chameleon's key feature is that it accounts for both interconnectivity and closeness in identifying the most similar pair of clusters, which is important for dealing with highly variable clusters.
Clustering with Bregman Divergences
1,536 Citations2004Arindam Banerjee, Srujana Merugu +2 more
This paper proposes and analyzes parametric hard and soft clustering algorithms based on a large class of distortion functions known as Bregman divergences, and shows that there is a bijection between regular exponential families and a largeclass of BRegman diverGences, that is called regular Breg man divergence.
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/153244303321897735
1,127 Citations2000
This paper introduces the problem of combining multiple partitionings of a set of objects into a single consolidated clustering without accessing the features or algorithms that determined these partitionings and proposes three effective and efficient techniques for obtaining high-quality combiners (consensus functions).
ACM Transactions on Knowledge Discovery from DataClustering aggregation
816 Citations2007Aristides Gionis, Heikki Mannila +1 more
This work gives a formal statement of the clustering-aggregation problem, an extensive empirical evaluation demonstrating the usefulness of the problem and of the solutions, and suggests a number of algorithms to improve the robustness of clusterings.
Multilevel hypergraph partitioning
718 Citations1997George Karypis, Rajat Aggarwal +2 more
The experiments show that the multilevel hypergraph partitioning algorithm produces high quality partitioning in relatively small amount of time and outperforms other schemes (in hyperedge cut) quite consistently with larger margins.
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.
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.
Journal of the Operational Research SocietyMathematical Classification and Clustering
565 Citations1997Boris Mirkin
Solving cluster ensemble problems by bipartite graph partitioning
564 Citations2004Xiaoli Z. Fern, Carla E. Brodley
A new reduction method is introduced that constructs a bipartite graph from a given cluster ensemble that retains all of the information provided by a given ensemble, allowing the similarities among instances and the similarity among clusters to be considered collectively in forming the final clustering.
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.
Combining Artificial Neural Nets: Ensemble and Modular Multi-Net Systems
489 Citations1999Amanda Sharkey
This volume, written by leading researchers, presents methods of combining neural nets to improve their performance and suggests ways to improve the quality of these nets.
Nonconvex optimization and its applicationsMathematical Classification and Clustering
452 Citations1996Boris Mirkin
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.
Consensus Clusterings
257 Citations2007Nam Hoang Nguyen, Rich Caruana
An iterative EM-like method is found that is remarkably effective for combining multiple clusterings without access to the underlying features of the data and produces clusterings that are as good as, and often better than, these other methods.
MIT Press eBooksAdvances in Distributed and Parallel Knowledge Discovery
233 Citations2000Hillol Kargupta, Philip K. Chan
This book presents introductions to DKD and PKD, extensive reviews of the field, and state-of-the-art techniques that address the problem of extracting interesting associations, classifiers, clusters, and other patterns from data.
IEEE Transactions on Pattern Analysis and Machine IntelligenceCumulative Voting Consensus Method for Partitions with Variable Number of Clusters
232 Citations2007Hanan Ayad, Mohamed S. Kamel
This paper proposes new consensus clustering algorithms with linear computational complexity in n and introduces the idea of cumulative voting as a solution for the problem of cluster label alignment, where unlike the common one-to-one voting scheme, a probabilistic mapping is computed.
Solving Consensus and Semi-supervised Clustering Problems Using Nonnegative Matrix Factorization
212 Citations2007Tao Li, Chris Ding +1 more
This paper shows how consensus and semi-supervised clustering can be formulated within the framework of nonnegative matrix factorization (NMF), and shows that this framework yields NMF-based algorithms that are provably correct and provably convergent.
BioinformaticsAn ensemble framework for clustering protein–protein interaction networks
204 Citations2007Sitaram Asur, Duygu Ucar +1 more
An ensemble clustering framework designed to reduce the dimensionality of the consensus problem and yield informative clusters, and facilitate soft clustering by discovering multiple functional associations for proteins is proposed.
Correlation clustering
179 Citations2003Nikhil Bansal, Avrim Blum +1 more
Society for Industrial and Applied Mathematics eBooksConsensus Clustering Algorithms: Comparison and Refinement
158 Citations2008Andrey Goder, Vladimir Filkov
A refined consensus clustering heuristic is developed for the occasions when the given clusterings may be too disparate, and their consensus may not be representative of any one of them, and it is shown that in practice the refined consensus clusterings can be much superior to the general consensus clustings.
Analysis of Consensus Partition in Cluster Ensemble
156 Citations2005A. Topchy, M.H.C. Law +2 more
This paper provides a rigorous justification for the use of cluster ensemble based on a stochastic partition generation model related to re-labeling and consensus function with plurality voting and studies the property of the "mean" partition of an ensemble with respect to a metric on the space of all possible partitions.
Genome biologyConsensus clustering and functional interpretation of gene-expression data
146 Citations2004Stephen Swift, Allan Tucker +5 more
This work introduces consensus clustering, which allowed the identification of novel genes regulated by NFκB and the unfolded protein response in certain B-cell lymphomas.
Weighted Consensus Clustering
142 Citations2008Tao Li, Chris Ding
Theoretically, it is shown that a reformulation of the wellknown L1 regularization LASSO problem is equivalent to the weight optimization of the weighted consensus clustering, and thus the approach provides sparse solutions which may resolve the difficult situation when the input clusterings diverge significantly.
Automatic malware categorization using cluster ensemble
110 Citations2010Yanfang Ye, Tao Li +2 more
An Automatic Malware Categorization System (AMCS) for automatically grouping malware samples into families that share some common characteristics using a cluster ensemble by aggregating the clustering solutions generated by different base clustering algorithms is developed.
Pattern RecognitionA scalable framework for cluster ensembles
97 Citations2008Prodip Hore, Lawrence Hall +1 more
It is shown that the centroid-based ensemble merging algorithms presented here generate partitions of quality comparable to the best label vector approach or clustering all the data at once, while providing very large speedups.
Pattern RecognitionAn aggregated clustering approach using multi-ant colonies algorithms
95 Citations2006Yan Yang, Mohamed S. Kamel
Experimental evaluation shows that the average performance of the aggregated multi-ant colonies algorithms outperforms that of the single ant-based clustering algorithm and the popular K-means algorithm.
Information FusionA cluster ensemble method for clustering categorical data
89 Citations2004Zengyou He, Xiaofei Xu +1 more
Experimental results on real datasets show that CE based clustering method is competitive with existing CDC algorithms with respect to clustering accuracy.
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.
Expert Systems with ApplicationsExternal validation measures for K-means clustering: A data distribution perspective
74 Citations2008Junjie Wu, Jian Chen +2 more
It is demonstrated that only three measures, namely the variation of information (VI), the van Dongen criterion (VD) and the Mirkin metric (M), can detect the negative uniform effect of K-means in the clustering results.
Lecture notes in computer scienceA Scalable Approach to Balanced, High-Dimensional Clustering of Market-Baskets
68 Citations2000Alexander L. Strehl, Joydeep Ghosh
Opossum, a novel similarity-based clustering approach based on constrained, weighted graph-partitioning, built on top of Metis, a well-known and highly efficient graphpartitioning algorithm, inherits the scalable and easily parallelizeable attributes of the latter algorithm.
Weighted Clustering Ensembles
65 Citations2006Muna Al‐Razgan, Carlotta Domeniconi
A mechanism which leverages the ensemble framework to bootstrap informative constraints directly from the data and from the various clusterings, without intervention from the user is introduced and three new consensus functions for ensembles of subspace clusterings are introduced.
Lecture notes in computer scienceHeterogeneous Clustering Ensemble Method for Combining Different Cluster Results
52 Citations2006Hye-Sung Yoon, Sunyoung Ahn +3 more
A novel heterogeneous clustering ensemble scheme that uses a genetic algorithm to generate high quality and robust clustering results with characteristics of bio-data and is founded on the concept of using the evolutionary processes to select the most commonly-inherited characteristics.
Bayesian Cluster Ensembles
42 Citations2009Hongjun Wang, Hanhuai Shan +1 more
A distributed learning framework for heterogeneous data sources
34 Citations2005Srujana Merugu, Joydeep Ghosh
This framework decouples data privacy issues from knowledge integration issues by requiring the individual sites to share only privacy-safe probabilistic models of the local data, which are then integrated to obtain a global Probabilistic model based on the union of the features available at all the sites.
Lecture notes in computer scienceNonparametric Bayesian Clustering Ensembles
27 Citations2010Pu Wang, Carlotta Domeniconi +1 more
A nonparametric Bayesian clustering ensemble (NBCE) method, which can discover the number of clusters in the consensus clustering.
Generalized cluster aggregation
23 Citations2009Fei Wang, Xin Wang +1 more
A unified framework to solve the clustering aggregation problem, where the aggregated clustering result is obtained by minimizing the (weighted) sum of the Bregman divergence between it and all the input clusterings is proposed.
Feature diversity in cluster ensembles for robust document clustering
16 Citations2006Xavier Sevillano, Germán Cobo +2 more
A strategy based on feature diversity and cluster ensembles is presented, which is robust to near-optimal model order selection and able to detect constructive interactions between different document representations in the test bed.
Consensus Clustering for Detection of Overlapping Clusters in Microarray Data
12 Citations2006Meghana Deodhar, Joydeep Ghosh
This paper extends a popular model selection approach called X-means (Pelleg and Moore, 2000) to detect the inherent number of overlapping clusters in the data to take advantage of the fact that results obtained by applying different clustering algorithms to the same dataset could be different.
AP-Based Consensus Clustering for Gene Expression Time Series
6 Citations2010Tai‐Yu Chiu, Ting-Chieh Hsu +1 more
This work proposes an unsupervised approach for analyzing gene time-series datasets that combines Affinity Propagation and the spirit of consensus clustering-- extracting multiple partitions from different time intervals.
Journal of Experimental BiologySTEM CELLS: THE CONTROVERSY CONTINUES
1 Citations2005Julie Ghosh
Stem cells - cells that can divide to self-renew and can also differentiate into a number of different cell types - have been very much in the public eye over the last few years.