nips nips2012 nips2012-68 nips2012-68-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nan Li, Longin J. Latecki
Abstract: We formulate clustering aggregation as a special instance of Maximum-Weight Independent Set (MWIS) problem. For a given dataset, an attributed graph is constructed from the union of the input clusterings generated by different underlying clustering algorithms with different parameters. The vertices, which represent the distinct clusters, are weighted by an internal index measuring both cohesion and separation. The edges connect the vertices whose corresponding clusters overlap. Intuitively, an optimal aggregated clustering can be obtained by selecting an optimal subset of non-overlapping clusters partitioning the dataset together. We formalize this intuition as the MWIS problem on the attributed graph, i.e., finding the heaviest subset of mutually non-adjacent vertices. This MWIS problem exhibits a special structure. Since the clusters of each input clustering form a partition of the dataset, the vertices corresponding to each clustering form a maximal independent set (MIS) in the attributed graph. We propose a variant of simulated annealing method that takes advantage of this special structure. Our algorithm starts from each MIS, which is close to a distinct local optimum of the MWIS problem, and utilizes a local search heuristic to explore its neighborhood in order to find the MWIS. Extensive experiments on many challenging datasets show that: 1. our approach to clustering aggregation automatically decides the optimal number of clusters; 2. it does not require any parameter tuning for the underlying clustering algorithms; 3. it can combine the advantages of different underlying clustering algorithms to achieve superior performance; 4. it is robust against moderate or even bad input clusterings. 1
[1] Gionis, A. & Mannila, H. & Tsaparas, P. (2005) ”Clustering aggregation”. Proceedings of the 21st ICDE
[2] Strehl, A. & Ghosh, J. (2003) ”Cluster ensembles—a knowledge reuse framework for combining multiple partitions”. The Journal of Machine Learning Research (3):583-617.
[3] Brendel, W. & Todorovic, S. (2010) ”Segmentation as maximum-weight independent set”. Neural Information Processing Systems
[4] Fisher, R.A. (1936) ”The use of multiple measurements in taxonomic problems”. Annual Eugenics (7) Part II: 179-188
[5] Alimoglu, F. & Alpaydin, E. (1996) ”Methods of Combining Multiple Classifiers Based on Different Representations for Pen-based Handwriting Recognition”. Proceedings of the Fifth Turkish Artificial Intelligence and Artificial Neural Networks Symposium (TAINN 96)
[6] Franti, P. & Virmajoki, O. (2006) ”Iterative shrinking method for clustering problems”. Pattern Recognition 39 (5), 761-765
[7] Lloyd, S. P. (1982) ”Least squares quantization in PCM”. IEEE Transactions on Information Theory 28 (2): 129-137
[8] Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu (1996) ”A density-based algorithm for discovering clusters in large spatial databases with noise”. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96)
[9] Fred, A.L.N. & Jain, A.K. (2002) ”Data clustering using evidence accumulation”. Proceedings of the International Conference on Pattern Recognition(ICPR) 276-280
[10] Kirkpatrick, S. & Gelatt, C. D. & Vecchi, M. P. (1983). ”Optimization by Simulated Annealing”. Science 220 (4598): 671C680
[11] Vikas Singh & Lopamudra Mukherjee & Jiming Peng & Jinhui Xu (2008) ”Ensemble Clustering using Semidefinite Programming”. Advances in Neural Information Processing Systems 20: 1353–1360
[12] Nguyen, N. & Caruana, R. (2007) ”Consensus clusterings”. IEEE International Conference on Data Mining ICDM 2007 607–612
[13] X. Z. Fern & C. E. Brodley (2004) ”Solving cluster ensemble problems by bipartite graph partitioning”. Proc. of International Conference on Machine Learning page 36
[14] Topchy, A. & Jain, A.K. & Punch, W. (2003) ”Combining multiple weak clusterings”. IEEE International Conference on Data Mining, ICDM 2003 331–338 9