Combining partitions by probabilistic label aggregation

ABSTRACT

Data clustering represents an important tool in exploratory data analysis. The lack of objective criteria render model selection as well as the identification of robust solutions particularly difficult. The use of a stability assessment and the combination of multiple clustering solutions represents an important ingredient to achieve the goal of finding useful partitions. In this work, we propose a novel way of combining multiple clustering solutions for both, hard and soft partitions: the approach is based on modeling the probability that two objects are grouped together. An efficient EM optimization strategy is employed in order to estimate the model parameters. Our proposal can also be extended in order to emphasize the signal more strongly by weighting individual base clustering solutions according to their consistency with the prediction for previously unseen objects. In addition to that, the probabilistic model supports an out-of-sample extension that (i) makes it possible to assign previously unseen objects to classes of the combined solution and (ii) renders the efficient aggregation of solutions possible. In this work, we also shed some light on the usefulness of such combination approaches. In the experimental result section, we demonstrate the competitive performance of our proposal in comparison with other recently proposed methods for combining multiple classifications of a finite data set.

REFERENCES

• 1: Sugato Basu , Mikhail Bilenko , Raymond J. Mooney, A probabilistic framework for semi-supervised clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014062]
• 2: S. Ben-David. A framework for statistical clustering with a constant time approximation algorithms for k-median clustering. In COLT, pages 415--426, 2004.
• 3: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Stat. Soc. B, 39(1):1--38, 1977.
• 6: I. Dhillon, Y. Guan, and B. Kulis. A unified view of kernel k-means, spectral clustering and graph partitioning. Technical report, University of Texas at Austin, 2005.
• 7: S. Dudoit and J. Fridlyand. Bagging to improve the accuracy of a clustering procedure. Bioinformatics, 19:1090--1099, 2003.
• 8: Bernd Fischer , Joachim M. Buhmann, Bagging for Path-Based Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.11, p.1411-1415, November 2003 [doi>10.1109/TPAMI.2003.1240115]
• 9: Ana L. N. Fred, Finding Consistent Clusters in Data Partitions, Proceedings of the Second International Workshop on Multiple Classifier Systems, p.309-318, July 02-04, 2001
• 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: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer series in statistics. Springer-Verlag New York, 2001.
• 12: Thomas Hofmann, Unsupervised learning by probabilistic latent semantic analysis, Machine Learning, v.42 n.1/2, p.177-196, Jan. 2001 [doi>10.1023/A:1007617005950]
• 13: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 14: E. T. Jaynes. Information theory and statistical mechanics, I and II. Physical Reviews, 106 and 108:620--630 and 171--190, 1957.
• 15: T. Lange, M. Braun, V. Roth, and J. Buhmann. Stability-based model selection. In Advances in Neural Information Processing Systems, volume 15, 2003.
• 16: M. H. C. Law, A. P. Topchy, and A. K. Jain. Multiobjective data clustering. In CVPR (2), pages 424--430, 2004.
• 17: D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In NIPS, volume 13, pages 556--562, 2000.
• 18: F. Leisch. Bagged clustering. Technical report, TU Wien, 1999.
• 19: B. Minaei-Bidgoli, A. P. Topchy, and W. F. Punch. A comparison of resampling methods for clustering ensembles. In IC-AI, pages 939--945, 2004.
• 20: Brian D. Ripley , N. L. Hjort, Pattern Recognition and Neural Networks, Cambridge University Press, New York, NY, 1995
• 21: Volker Roth , Julian Laub , Motoaki Kawanabe , Joachim M. Buhmann, Optimal Cluster Preserving Embedding of Nonmetric Proximity Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1540-1551, December 2003 [doi>10.1109/TPAMI.2003.1251147]
• 22: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 23: 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]
• 24: A. Topchy, A. Jain, and W. Punch. A mixture model for clustering ensembles. In Proc. SIAM Data Mining, pages 379--390, 2004.
• 25: 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
• 26: Alexander P. Topchy , Martin H. C. Law , Anil K. Jain , Ana L. Fred, Analysis of Consensus Partition in Cluster Ensemble, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.225-232, November 01-04, 2004

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
clustering, consensus partition, re-sampling