Improving clustering stability with combinatorial MRFs

ABSTRACT

As clustering methods are often sensitive to parameter tuning, obtaining stability in clustering results is an important task. In this work, we aim at improving clustering stability by attempting to diminish the influence of algorithmic inconsistencies and enhance the signal that comes from the data. We propose a mechanism that takes m clusterings as input and outputs m clusterings of comparable quality, which are in higher agreement with each other. We call our method the Clustering Agreement Process (CAP). To preserve the clustering quality, CAP uses the same optimization procedure as used in clustering. In particular, we study the stability problem of randomized clustering methods (which usually produce different results at each run). We focus on methods that are based on inference in a combinatorial Markov Random Field (or Comraf, for short) of a simple topology. We instantiate CAP as inference within a more complex, bipartite Comraf. We test the resulting system on four datasets, three of which are medium-sized text collections, while the fourth is a large-scale user/movie dataset. First, in all the four cases, our system significantly improves the clustering stability measured in terms of the macro-averaged Jaccard index. Second, in all the four cases our system managed to significantly improve clustering quality as well, achieving the state-of-the-art results. Third, our system significantly improves stability of consensus clustering built on top of the randomized clustering solutions.

REFERENCES

• 1: L. Badea. Clustering and metaclustering with nonnegative matrix decompositions. In Proceedings of ECML-16, pages 10--22, 2005.
• 2: Ron Bekkerman , Ran El-Yaniv , Andrew McCallum, Multi-way distributional clustering via pairwise interactions, Proceedings of the 22nd international conference on Machine learning, p.41-48, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102357]
• 3: R. Bekkerman and J. Jeon. Multi-modal clustering for multimedia collections. In Proceedings of CVPR'07, the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2007.
• 4: R. Bekkerman, M. Sahami, and E. Learned-Miller. Combinatorial Markov Random Fields. In Proceedings of ECML-17, 2006.
• 5: Ron Bekkerman , Martin Scholz, Data weaving: scaling up the state-of-the-art in data clustering, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458226]
• 6: S. Ben-David, U. von Luxburg, and D. Pál. A sober look at clustering stability. In Proceedings of COLT-19, pages 5--19, 2006.
• 7: A. Ben-Hur, A. Elisseeff, and I. Guyon. A stability based method for discovering structure in clustered data. Pacific Symposium on Biocomputing, pages 6--17, 2002.
• 8: J. Besag. Spatial interaction and statistical analysis of lattice systems. Journal of the Royal Statistical Society, 36(2):192--236, 1974.
• 9: J. Besag. On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, 48(3), 1986.
• 10: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 11: 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]
• 12: P. Jaccard. The distribution of flora in the alpine zone. New Phytologist, 11:37--50, 1912.
• 13: A. Kreiger and P. Green. A generalized rand-index method for consensus clustering of separate partitions of the same data base. Journal of Classification, 16:63--89, 1999.
• 14: Ludmila I. Kuncheva , Dmitry P. Vetrov, Evaluation of Stability of k-Means Cluster Ensembles with Respect to Random Initialization, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.11, p.1798-1808, November 2006 [doi>10.1109/TPAMI.2006.226]
• 15: Tilman Lange , Volker Roth , Mikio L. Braun , Joachim M. Buhmann, Stability-based validation of clustering solutions, Neural Computation, v.16 n.6, p.1299-1323, June 2004 [doi>10.1162/089976604773717621]
• 16: Erel Levine , Eytan Domany, Resampling Method for Unsupervised Estimation of Cluster Validity, Neural Computation, v.13 n.11, p.2573-2593, November 2001 [doi>10.1162/089976601753196030]
• 17: Nam Nguyen , Rich Caruana, Consensus Clusterings, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.607-612, October 28-31, 2007 [doi>10.1109/ICDM.2007.73]
• 18: Kunal Punera , Joydeep Ghosh, CONSENSUS-BASED ENSEMBLES OF SOFT CLUSTERINGS, Applied Artificial Intelligence, v.22 n.7-8, p.780-810, August 2008 [doi>10.1080/08839510802170546]
• 19: Vijay V. Raghavan , M. Y. L. Ip, Techniques for measuring the stability of clustering: a comparative study, Proceedings of the 5th annual ACM conference on Research and development in information retrieval, p.209-237, May 18-20, 1982, West Berlin, Germany
• 20: W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66(336):846--850, 1971.
• 21: Noam Slonim , Nir Friedman , Naftali Tishby, Multivariate information bottleneck, Neural Computation, v.18 n.8, p.1739-1789, August 2006 [doi>10.1162/neco.2006.18.8.1739]
• 22: 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]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms

Keywords:
clustering stability, combinatorial MRF, comraf