On combining multiple clusterings

ABSTRACT

Many problems can be reduced to the problem of combining multiple clusterings. In this paper, we first summarize different application scenarios of combining multiple clusterings and provide a new perspective of viewing the problem as a categorical clustering problem. We then show the connections between various consensus and clustering criteria and discuss the complexity results of the problem. Finally we propose a new method to determine the final clustering. Experiments on kinship terms and clustering popular music from heterogeneous feature sets show the effectiveness of combining multiple clusterings.

REFERENCES

• 1: Arabie, P., Carroll, J. D., & Desarbo, W. (1987). Three-way scaling and clustering. Newbury Park, CA: Sage publications.
• 2: Shlomo Argamon , Marin Šarić , Sterling S. Stein, Style mining of electronic messages for multiple authorship discrimination: first results, 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.956805]
• 3: Eric Bauer , Ron Kohavi, An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants, Machine Learning, v.36 n.1-2, p.105-139, July-August 1999 [doi>10.1023/A:1007515423169]
• 4: Eric Brill, Some advances in transformation-based part of speech tagging, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.722-727, October 1994, Seattle, Washington, United States
• 5: Brucker, P. (1977). On the complexity of clustering problems. Optimization and Operations Research (pp. 45--54). Springer-Verlag.
• 6: Cohen, J. (1960). A coefficient of agreement for nominal scales. Educational and Psychological Measurement, 20, 37--46.
• 7: David, A., & Panchanathan, S. (2000). Wavelet-histogram method for face recognition. Journal of Electronic Imaging, 9, 217--225.
• 8: Day, W. H. E. (1986). Foreword: Comparison and consensus of classifications. Journal of Classification, 3, 183--185.
• 9: Duran, B. S., & Odell, P. L. Cluster analysis: a survey. New York, NY: Springer.
• 10: B. S. Everitt, Introduction to optimization methods and their application in statistics, Chapman & Hall, Ltd., London, UK, 1987
• 11: Ferligoj, A. (1992). Direct multicriteria clustering algorithm. Journal of Classification, 9, 43--61.
• 12: Ferligoj, A., & Batagelj, V. (1983). Some types of clustering with relational constraints. Psychometrika, 48, 541--552.
• 13: Fern, X. Z., & Brodley, C. E. (2003). Random projection for high dimensional data clustering: A cluster ensemble approach. Proceedings of the Twentieth International Conference on Machine Learning(ICML 2003) (pp. 186--193). Morgan Kaufmann Publishers.
• 14: Golub, G. H., & Loan, C. F. V. (1991). Matrix computations. The Johns Hopkins University Press.
• 15: Goodman, L. A., & Kruskal, W. H. (1954). Measures of associations for cross classification. Journal of the American Statistical Association, 49, 732--764.
• 16: Gordan, A. D., & Vichi, M. (1998). Partitions of partitions. journal of classification, 15, 265--285.
• 17: Gordan, A. D., & Vichi, M. (2002). Obtaining partitions of a set of hard or fuzzy partitions. Classification, Clustering and Data Analysis: recent advances and applications (pp. 75--79). Springer.
• 18: Hubert, L. J., & Arabie, P. (1985). Comparing partitions. journal of classification, 2, 193--218.
• 19: Hubert, L. J., & Baker, F. B. (1978). Evaluating the conformity of sociometric measurements. Psychometrika, 43, 31--41.
• 20: Hillol Kargupta , Weiyun Huang , Krishnamoorthy Sivakumar , Erik Johnson, Distributed clustering using collective principal component analysis, Knowledge and Information Systems, v.3 n.4, p.422-448, November 2001 [doi>10.1007/PL00011677]
• 21: Katz, L., & Powell, J. H. (1953). A proposed index of the conformity of one sociometric measurement to another. Psychometrika, 18, 249--256.
• 22: Kaufman, L., & Rousseeuw, P. J. (1990). Finding groups in data: An introduction to cluster analysis. John Wiley.
• 23: Tao Li , Sheng Ma , Mitsunori Ogihara, Document clustering via adaptive subspace iteration, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009031]
• 24: Tao Li , Mitsunori Ogihara, Music artist style identification by semi-supervised learning from both lyrics and content, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027612]
• 25: Tao Li , Mitsunori Ogihara , Qi Li, A comparative study on content-based music genre classification, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860487]
• 26: Li, T., Zhu, S., & Ogihara, M. (2003b). Algorithms for clustering high dimensional and distributed data. Intelligent Data Analysis Journal, 7. 305--326.
• 27: Messatfa, H. (1992). An algorithm to maximize the agreement. Journal of Classification, 9, 5--15.
• 28: Boris Mirkin, Reinterpreting the Category Utility Function, Machine Learning, v.45 n.2, p.219-228, November 2001 [doi>10.1023/A:1010924920739]
• 29: Roger Mitton, Spelling checkers,spelling correctors and the misspellings of poor spellers, Information Processing and Management: an International Journal, v.23 n.5, p.495-505, Sept. 1987 [doi>10.1016/0306-4573(87)90116-6]
• 30: Stefano Monti , Pablo Tamayo , Jill Mesirov , Todd Golub, Consensus Clustering: A Resampling-Based Method for Class Discovery and Visualization of Gene Expression Microarray Data, Machine Learning, v.52 n.1-2, p.91-118, July-August 2003 [doi>10.1023/A:1023949509487]
• 31: Bernard M. Moret, The Theory of Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 32: P.W. Ellis, D., Whitman, B., Berenzweig, A., & Lawrence, S. (2002). The quest for ground truth in musical artist similarity. Proceedings of 3rd International Conference on Music Information Retrieval (pp. 170--177).
• 33: Rosenberg, S., & Kim, M. P. (1975). The method of sorting as a data gathering procedure in multivariate research. Multivariate Behavioral Research, 10, 489--502.
• 34: Efstathios Stamatatos , George Kokkinakis , Nikos Fakotakis, Automatic text categorization in terms of genre and author, Computational Linguistics, v.26 n.4, p.471-495, December 2000 [doi>10.1162/089120100750105920]
• 35: 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
• 36: Tweedie, F. J., & Baayen, R. H. (1998). How variable may a constant be? Measure of lexical richness in perspective. Computers and the Humanities, 32, 323--352.
• 37: Tzanetakis, G., & Cook, P. (2002). Musical genre classification of audio signals. IEEE Transactions on Speech and Audio Processing, 10.
• 38: Vichi, M. (1999). One-mode classification of a three-way data matrix. journal of classification, 16, 27--44.
• 39: Zhao, Y., & Karypis, G. (2001). Criterion functions for document clustering: Experiments and analysis (Technical Report). Department of Computer Science, University of Minnesota.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Experimentation, Theory

Keywords:
categorical, combining, multiple clusterings