Ian Davidson
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.
- {Ausiello et. al. 1999} Ausiello G., et. al., Complexity and Approximation, Springer, 1999. Google Scholar
Digital Library
- {Basu et. al. 2002} Basu S., Banerjee A. & Mooney R., "Semisupervised Learning by Seeding", ICML 2002. Google ScholarDigital Library
- {Basu et. al. 2004a} Basu S., Bilenko M. & Mooney R., "Active Semi-Supervision for Pairwise Constrained Clustering", SIAM Data Mining, 2002.Google Scholar
- {Basu et. al. 2004b} Basu S., Bilenko M. & Mooney R., "A Probabilistic Framework for Semi-Supervised Clustering", ACM KDD, 2004. Google ScholarDigital Library
- {Davidson and Ravi 2005} Davidson I. & Ravi S. S., "Clustering with Constraints: Feasibility Issues", SIAM Data Mining, 2005.Google Scholar
- {Feige and Kilian 1998} Feige U. & Kilian J., "Zero knowledge and the chromatic number", J. Computer and System Sciences, Vol. 57, 1998, pp. 187--199. Google ScholarDigital Library
- {Garey and Johnson 1979} Garey M. & Johnson D., Computers and Intractability, 1979.Google Scholar
- {Kleinberg 2002} Kleinberg J., "An Impossibility Theorem for Clustering", NIPS 2002, pp. 446--453.Google Scholar
- {Oliver et. al. 1996} Oliver J., Baxter R. & Wallace C., "Unsupervised Learning Using MML", ICML 1996.Google Scholar
- {Papadimitriou 1994} Papadimitriou C., Computational Complexity, Addison-Wesley, 1994.Google Scholar
- {Wagstaff and Cardie 2000} Wagstaff K. & Cardie C., "Clustering with Instance-Level Constraints", ICML, 2000. Google ScholarDigital Library
- {Wagstaff et. al. 2001} Wagstaff K., Cardie C, Rogers S. & Schroedl S., "Constrained k-means Clustering with Background Knowledge", ICML, 2001. Google ScholarDigital Library
- {Wagstaff 2002} Wagstaff K., Intelligent Clustering with Instance-Level Constraints, Ph.D. Dissertation, Cornell University, 2002. Google ScholarDigital Library
- {Xing et. al. 2003} Xing E., Ng A., Jordan M. & Russell S., "Distance Metric Learning, with Application to Clustering with Side-Information", NIPS, 2003.Google Scholar
- Intractability and clustering with constraints
Recommendations
Hierarchical Agglomerative Clustering with Ordering Constraints
WKDD '10: Proceedings of the 2010 Third International Conference on Knowledge Discovery and Data MiningMany previous researchers have converted background knowledge as constraints to obtain accurate clustering. These clustering methods are usually called constrained clustering. Previous ordering constraints are instance level non-hierarchical constraints,...
Clustering by Learning Constraints Priorities
ICDM '12: Proceedings of the 2012 IEEE 12th International Conference on Data MiningA method for creating a constrained clustering ensemble by learning the priorities of pair wise constraints is proposed in this paper. This method integrates multiple clusters produced by using a simple constrained K-means algorithm that we modify to ...
Agglomerative hierarchical clustering with constraints: theoretical and empirical results
ECMLPKDD'05: Proceedings of the 9th European Conference on European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in DatabasesWe explore the use of instance and cluster-level constraints with agglomerative hierarchical clustering. Though previous work has illustrated the benefits of using constraints for non-hierarchical clustering, their application to hierarchical clustering ...
Comments