2001 ConstrainedKMeansClustering
Jump to navigation
Jump to search
- (Wagstaff et al., 2001) ⇒ Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schrödl. (2001). “Constrained K-means Clustering with Background Knowledge.” In: Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001).
Subject Headings: k-Means Clustering Algorithm, Background Knowledge, Constrained Clustering Algorithm.
Notes
- It proposes a variant of the k-Means Clustering Algorithm that incorporates Background Knowledge in the form of Instance-level Constraints.
- It demonstrates performance on six data sets.
Cited By
2004
- (Basu et al., 2004) ⇒ Sugato Basu, Mikhail Bilenko, and Raymond Mooney. (2004). “A Probabilistic Framework for Semi-Supervised Clustering.” In: Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2004).
2003
- (Xing, 2003) ⇒ Eric P. Xing, Andrew Y. Ng , Michael I. Jordan and Stuart Russell. (2003). “Distance Metric Learning, with Application to Clustering with Side-Information.” In: Advances in Neural Information Processing Systems 15.
Quotes
Abstract
Clustering is traditionally viewed as an unsupervised method for data analysis. However, in some cases information about the problem domain is available in addition to the data instances themselves. In this paper, we demonstrate how the popular k-means clustering algorithm can be pro tably modi ed to make use of this information. In experiments with artificial constraints on six data sets, we observe improvements in clustering accuracy. We also apply this method to the real-world problem of automatically detecting road lanes from GPS data and observe dramatic increases in performance.
References
- Bellot, P., & El-Beze, M. (1999). A clustering method for information retrieval (Technical Report IR-0199). Laboratoire d'Informatique d'Avignon, France.
- Bradley, P. S., Bennett, K. P., & Demiriz, A. (2000). Constrained k-means clustering (Technical Report MSR-TR-2000-65). Microsoft Research, Redmond, WA.
- Claire Cardie. (1993). A case-based approach to knowledge acquisition for domain-specific sentence analysis. Proceedings of the Eleventh National Conference on Artificial Intelligence (pp. 798{803). Washington, DC: AAAI Press / MIT Press.
- Ferligoj, A., & Batagelj, V. (1983). Some types of clustering with relational constraints. Psychometrika, 48, 541{552.
- Fisher, D. (1987). Knowledge acquisition via incremental conceptual clustering. Machine Learning, 2, 139{172.
- Gordon, A. D. (1973). Classification in the presence of constraints. Biometrics, 29, 821{827. Jain, A. K., & Dubes, R. C. (1988). Algorithms for clustering data. Prentice Hall.
- Lefkovitch, L. P. (1980). Conditional clustering. Biometrics, 36, 43{58.
- MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Symposium on Math, Statistics, and Probability (pp. 281{297). Berkeley, CA: University of California Press.
- Marroquin, J., & Girosi, F. (1993). Some extensions of the k-means algorithm for image segmentation and pattern recognition. AI Memo 1390). Massachusetts Institute of Technology, Cambridge, MA.
- Rand, W. M. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66, 846{850.
- Rogers, S., Pat Langley, and Wilson, C. (1999). Mining GPS data to augment road models. Proceedings of the Fifth International Conference on Knowledge Discovery and Data Mining (pp. 104{113). San Diego, CA: ACM Press.
- Schroedl, S., Wagsta, K., Rogers, S., Pat Langley, & Wilson, C. (2001). Mining GPS traces for map refi nement. (in preparation).
- Talavera, L., & Bejar, J. (1999). Integrating declarative knowledge in hierarchical clustering tasks. Proceedings of the International Symposium on Intelligent Data Analysis (pp. 211{222). Amsterdam, The Netherlands: Springer-Verlag.
- Thompson, K., & Pat Langley (1991). Concept formation in structured domains. In D. H. Fisher, Michael J. Pazzani and Pat Langley (Eds.), Concept formation: Knowledge and experience in unsupervised learning, 127{161. San Mateo, CA: Morgan Kaufmann.
- Wagstaff, K., & Cardie, C. (2000). Clustering with instance-level constraints. Proceedings of the Seventeenth International Conference on Machine Learning (pp. 1103{1110). Palo Alto, CA: Morgan Kaufmann.
,