Intractability and clustering with constraints

ABSTRACT

Clustering with constraints is a developing area of machine learning. Various papers have used constraints to enforce particular clusterings, seed clustering algorithms and even learn distance functions which are then used for clustering. We present intractability results for some constraint combinations and illustrate both formally and experimentally the implications of these results for using constraints with clustering.

REFERENCES

• 1: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 2: Sugato Basu , Arindam Banerjee , Raymond J. Mooney, Semi-supervised Clustering by Seeding, Proceedings of the Nineteenth International Conference on Machine Learning, p.27-34, July 08-12, 2002
• 3: {Basu et. al. 2004a} Basu S., Bilenko M. & Mooney R., "Active Semi-Supervision for Pairwise Constrained Clustering", SIAM Data Mining, 2002.
• 4: 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]
• 5: {Davidson and Ravi 2005} Davidson I. & Ravi S. S., "Clustering with Constraints: Feasibility Issues", SIAM Data Mining, 2005.
• 6: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
• 7: {Garey and Johnson 1979} Garey M. & Johnson D., Computers and Intractability, 1979.
• 8: {Kleinberg 2002} Kleinberg J., "An Impossibility Theorem for Clustering", NIPS 2002, pp. 446--453.
• 9: {Oliver et. al. 1996} Oliver J., Baxter R. & Wallace C., "Unsupervised Learning Using MML", ICML 1996.
• 10: {Papadimitriou 1994} Papadimitriou C., Computational Complexity, Addison-Wesley, 1994.
• 11: Kiri Wagstaff , Claire Cardie, Clustering with Instance-level Constraints, Proceedings of the Seventeenth International Conference on Machine Learning, p.1103-1110, June 29-July 02, 2000
• 12: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 13: Kiri Lou Wagstaff , Claire Cardie, Intelligent clustering with instance-level constraints, Cornell University, Ithaca, NY, 2002
• 14: {Xing et. al. 2003} Xing E., Ng A., Jordan M. & Russell S., "Distance Metric Learning, with Application to Clustering with Side-Information", NIPS, 2003.