Clustering aggregation

ABSTRACT

We consider the following problem: given a set of clusterings, find a single clustering that agrees as much as possible with the input clusterings. This problem, clustering aggregation, appears naturally in various contexts. For example, clustering categorical data is an instance of the clustering aggregation problem; each categorical attribute can be viewed as a clustering of the input rows where rows are grouped together if they take the same value on that attribute. Clustering aggregation can also be used as a metaclustering method to improve the robustness of clustering by combining the output of multiple algorithms. Furthermore, the problem formulation does not require a priori information about the number of clusters; it is naturally determined by the optimization function.

In this article, we give a formal statement of the clustering aggregation problem, and we propose a number of algorithms. Our algorithms make use of the connection between clustering aggregation and the problem of correlation clustering. Although the problems we consider are NP-hard, for several of our methods, we provide theoretical guarantees on the quality of the solutions. Our work provides the best deterministic approximation algorithm for the variation of the correlation clustering problem we consider. We also show how sampling can be used to scale the algorithms for large datasets. We give an extensive empirical evaluation demonstrating the usefulness of the problem and of the solutions.

REFERENCES

• 1: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 2: Andritsos, P., Tsaparas, P., Miller, R. J., and Sevcik, K. C. 2004. LIMBO: Scalable clustering of categorical data. In Proceedings of the International Conference on Extending Database Technology (EDBT). 123--146.
• 3: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Machine Learning, v.56 n.1-3, p.89-113 [doi>10.1023/B:MACH.0000033116.57574.95]
• 4: Barthelemy, J.-P. and Leclerc, B. 1995. The median procedure for partitions. DIMACS Series in Discrete Mathematics, 3--34.
• 5: Blake, C. L. and Merz, C. J. 1998. UCI repository of machine learning databases.
• 6: Constantinos Boulis , Mari Ostendorf, Combining multiple clustering systems, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.63-74, September 20-24, 2004, Pisa, Italy
• 7: Moses Charikar , Venkatesan Guruswami , Anthony Wirth, Clustering with Qualitative Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.524, October 11-14, 2003
• 8: Cristofor, D. and Simovici, D. A. 2001. An information-theoretical approach to genetic algorithms for clustering. Tech. rep. TR-01-02, UMass, Boston, MA.
• 9: Erik D. Demaine , Dotan Emanuel , Amos Fiat , Nicole Immorlica, Correlation clustering in general weighted graphs, Theoretical Computer Science, v.361 n.2, p.172-187, 1 September 2006 [doi>10.1016/j.tcs.2006.05.008]
• 10: Deza, M. and Laurent, M. 1997. Geometry of Cuts and Metrics. Springer-Verlag.
• 11: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 12: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 13: Fern, X. Z. and Brodley, C. E. 2003. Random projection for high dimensional data clustering: A cluster ensemble approach. In Proceedings of the International Conference on Machine Learning (ICML). 186--193.
• 14: Filkov, V. and Skiena, S. 2004. Integrating microarray data by consensus clustering. Int. J. AI Tools 13, 4, 863--880.
• 15: 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
• 16: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems, v.25 n.5, p.345-366, July 2000 [doi>10.1016/S0306-4379(00)00022-3]
• 17: Hamerly, G. and Elkan, C. 2003. Learning the k in k-means. In Advances in Neural Information Processing Systems (NIPS).
• 18: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 19: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 20: Hochbaum, D. and Shmoys, D. 1985. A best possible heuristic for the k-center problem. Mathem. Operat. Resea., 180--184.
• 21: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 22: Taneli Mielikäinen , Evimaria Terzi , Panayiotis Tsaparas, Aggregating time partitions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150442]
• 23: Schwarz, G. 1978. Estimating Dimension of a Model. Ann. Statis. 6, 461--464.
• 24: Padhraic Smyth, Model selection for probabilistic clustering using cross-validatedlikelihood, Statistics and Computing, v.10 n.1, p.63-72, January 2000 [doi>10.1023/A:1008940618127]
• 25: 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
• 26: Chaitanya Swamy, Correlation Clustering: maximizing agreements via semidefinite programming, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 27: Topchy, A., Jain, A. K., and Punch, W. 2004. A mixture model of clustering ensembles. In Proceedings of the SIAM International Conference on Data Mining (SDM). 379--390.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
Data clustering, clustering aggregation, clustering categorical data, correlation clustering