Solving cluster ensemble problems by bipartite graph partitioning

ABSTRACT

A critical problem in cluster ensemble research is how to combine multiple clusterings to yield a final superior clustering result. Leveraging advanced graph partitioning techniques, we solve this problem by reducing it to a graph partitioning problem. We introduce a new reduction method that constructs a bipartite graph from a given cluster ensemble. The resulting graph models both instances and clusters of the ensemble simultaneously as vertices in the graph. Our approach retains all of the information provided by a given ensemble, allowing the similarity among instances and the similarity among clusters to be considered collectively in forming the final clustering. Further, the resulting graph partitioning problem can be solved efficiently. We empirically evaluate the proposed approach against two commonly used graph formulations and show that it is more robust and achieves comparable or better performance in comparison to its competitors.

REFERENCES

• 1: Bach, F. R., & Jordan, M. I. (2004). Learning spectral clustering. NIPS 16.
• 2: Blake, C. L., & Merz, C. J. (1998). UCI repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 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: 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]
• 6: Evgenia Dimitriadou , Andreas Weingessel , Kurt Hornik, Voting-Merging: An Ensemble Method for Clustering, Proceedings of the International Conference on Artificial Neural Networks, p.217-224, August 21-25, 2001
• 7: Dudoit, S., & Fridlyand, J. (2003). Bagging to improve the accuracy of a clustering procedure. Bioinformatics, 19.
• 8: Dy, J. G., Brodley, C. E., Kak, A., Shyu, C., & Broderick, L. S. (1999). The customized-queries approach to CBIR using EM. CVPR.
• 9: Fern, X. Z., & Brodley, C. E. (2003). Random projection for high dimensional data clustering: A cluster ensemble approach. ICML.
• 10: Fjallstrom, P. (1998). Algorithms for graph partitioning: A survey. Linkoping Electronic Articles in Computer and Information Science, 3.
• 11: Fred, A. L. N., & Jain, A. K. (2002). Data clustering using evidence accumulation. ICPR.
• 12: Hagen, L., & Kahng, A. (1992). New spectral methods for ratio cut partitioning and clustering. IEEE transaction on CAD, 11, 1074--1085.
• 13: 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]
• 14: 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]
• 15: Ng, A., Jordan, M., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. NIPS 14.
• 16: 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]
• 17: Noam Slonim , Naftali Tishby, Document clustering using word clusters via the information bottleneck method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.208-215, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345578]
• 18: 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]
• 19: 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
• 20: Topchy, A., Jain, A. K., & Punch, W. (2004). A mixture model for clustering ensembles. Proc. of SIAM Conf. on Data Mining.