Weighted cluster ensembles: Methods and analysis

ABSTRACT

Cluster ensembles offer a solution to challenges inherent to clustering arising from its ill-posed nature. Cluster ensembles can provide robust and stable solutions by leveraging the consensus across multiple clustering results, while averaging out emergent spurious structures that arise due to the various biases to which each participating algorithm is tuned. In this article, we address the problem of combining multiple weighted clusters that belong to different subspaces of the input space. We leverage the diversity of the input clusterings in order to generate a consensus partition that is superior to the participating ones. Since we are dealing with weighted clusters, our consensus functions make use of the weight vectors associated with the clusters. We demonstrate the effectiveness of our techniques by running experiments with several real datasets, including high-dimensional text data. Furthermore, we investigate in depth the issue of diversity and accuracy for our ensemble methods. Our analysis and experimental results show that the proposed techniques are capable of producing a partition that is as good as or better than the best individual clustering.

REFERENCES

• 1: Al-Razgan, M. and Domeniconi, C. 2006. Weighted clustering ensembles. In Proceedings of the SIAM International Conference on Data Mining. 258--269.
• 2: Asuncion, A. and Newman, D. 2007. UCI Machine Learning Repository. http://www.ics.uci.edu/~mlearn/MLR/epository.html.
• 3: Ayad, H. and Kamel, M. 2003. Finding natural clusters using multi-clusterer combiner based on shared nearest neighbors. In Proceedings of the International Workshop on Multiple Classifier Systems. 166--175.
• 4: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 5: Carlotta Domeniconi , Dimitrios Gunopulos , Sheng Ma , Bojun Yan , Muna Al-Razgan , Dimitris Papadopoulos, Locally adaptive metrics for clustering high dimensional data, Data Mining and Knowledge Discovery, v.14 n.1, p.63-97, February 2007 [doi>10.1007/s10618-006-0060-8]
• 6: Domeniconi, C., Papadopoulos, D., Gunopulos, D., and Ma, S. 2004. Subspace clustering of high-dimensional data. In Proceedings of the SIAM International Conference on Data Mining. 517--520.
• 7: Dudoit, S. and Fridlyand, J. 2003. Bagging to improve the accuracy of a clustering procedure. Bioinformatics 19, 9, 1090--1099.
• 8: Fern, X. and Brodley, C. 2003. Random projection for high-dimensional data clustering: A cluster ensemble approach. In Proceedings of the International Conference on Machine Learning. 63--74.
• 9: Xiaoli Zhang Fern , Carla E. Brodley, Solving cluster ensemble problems by bipartite graph partitioning, Proceedings of the twenty-first international conference on Machine learning, p.36, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015414]
• 10: Data Clustering Using Evidence Accumulation, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 4, p.40276, August 11-15, 2002
• 11: Ana L. N. Fred , Anil K. Jain, Combining Multiple Clusterings Using Evidence Accumulation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.6, p.835-850, June 2005 [doi>10.1109/TPAMI.2005.113]
• 12: David Gondek , Thomas Hofmann, Non-redundant clustering with conditional ensembles, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081882]
• 13: Derek Greene , Alexey Tsymbal , Nadia Bolshakova , Padraig Cunningham, Ensemble Clustering in Medical Diagnostics, Proceedings of the 17th IEEE Symposium on Computer-Based Medical Systems, p.576, June 24-25, 2004 [doi>10.1109/CBMS.2004.40]
• 14: Stefan T. Hadjitodorov , Ludmila I. Kuncheva , Ludmila P. Todorova, Moderate diversity for better cluster ensembles, Information Fusion, v.7 n.3, p.264-275, September, 2006 [doi>10.1016/j.inffus.2005.01.008]
• 15: Integration of Cluster Ensemble and Text Summarization for Gene Expression Analysis, Proceedings of the 4th IEEE Symposium on Bioinformatics and Bioengineering, p.251, May 19-21, 2004
• 16: Ning Kang , Carlotta Domeniconi , Daniel Barbara, Categorization and Keyword Identification of Unlabeled Documents, Proceedings of the Fifth IEEE International Conference on Data Mining, p.677-680, November 27-30, 2005 [doi>10.1109/ICDM.2005.39]
• 17: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 18: Kullback, S. and Leibler, R. A. 1951. On information and sufficiency. Annals Math. Statist. 22, 1, 79--86.
• 19: Kuncheva, L. and Hadjitodorov, S. 2004. Using diversity in cluster ensembles. In Proceedings of the IEEE International Conference on Systems, Man and Cybernetics. Vol. 2. 1214--1219.
• 20: Kuncheva, L. I., Hadjitodorov, S. T., and Todorova, L. P. 2006. Experimental comparison of cluster ensemble methods. In Proceedings of the International Conference on Information Fusion. 1--7.
• 21: Mangasarian, O. L. and Wolberg, W. H. 1990. Cancer diagnosis via linear programming. SIAM News 23, 5, 1--18.
• 22: Minaei-Bidgoli, B., Topchy, A., and Punch, W. 2004. A comparison of resampling methods for clustering ensembles. In Proceedings of the International Conference on Machine Learning: Models, Technologies and Applications. 939--945.
• 23: Ng, A. Y., Jordan, M. I., and Weiss, Y. 2002. On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems. Vol. 14. 849--856.
• 24: Lance Parsons , Ehtesham Haque , Huan Liu, Subspace clustering for high dimensional data: a review, ACM SIGKDD Explorations Newsletter, v.6 n.1, p.90-105, June 2004 [doi>10.1145/1007730.1007731]
• 25: Pekalska, E. 2005. The dissimilariy representations in pattern recognition. concepts, theory and applications. Ph.D. thesis, Delft University of Technology, Delft.
• 26: Punera, K. and Ghosh, J. 2007. Soft cluster ensembles. In Advances in Fuzzy Clustering and its Applications, J. V. de Oliveira and W. Pedrycz, Eds. John Wiley & Sons, Ltd., 69--90.
• 27: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003 [doi>10.1162/153244303321897735]
• 28: Alexander Topchy , Anil K. Jain , William Punch, Combining Multiple Weak Clusterings, Proceedings of the Third IEEE International Conference on Data Mining, p.331, November 19-22, 2003
• 29: Topchy, A., Jain, A., and Punch, W. 2004. A mixture model for clustering ensembles. In Proceedings of the SIAM International Conference on Data Mining. 379--390.
• 30: Alexander Topchy , Anil K. Jain , William Punch, Clustering Ensembles: Models of Consensus and Weak Partitions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.12, p.1866-1881, December 2005 [doi>10.1109/TPAMI.2005.237]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Cluster ensembles, accuracy and diversity measures, consensus functions, data mining, subspace clustering, text data