Abstract
Typical constrained clustering algorithms incorporate a set of must-link and cannot-link constraints into the clustering process. These instance level constraints specify relationships between pairs of data items and are generally derived by a domain expert. Generating these constraints is considered as a cumbersome and expensive task.
In this paper we describe an incremental constrained clustering framework to discover clusters using a decision theoretic approach. Our framework is novel since we provide an overall evaluation of the clustering in terms of quality in decision making and use this evaluation to “generate” instance level constraints. We do not assume any domain knowledge to start with. We show empirical validation of this approach on several test domains and show that we achieve better performance than a feature selection based approach.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Wagstaff, K., Cardie, C., Rogers, S., Schroedl, S.: Constrained K-means Clustering with Background Knowledge. In: 18th International Conference on Machine Learning (ICML), pp. 577–584. Morgan Kaufmann, San Francisco (2001)
Wagstaff, K., Cardie, C.: Clustering with instance-level constraints. In: 17th International Conference on Machine Learning (ICML), pp. 1103–1110. Morgan Kaufmann, Stanford (2000)
Davidson, I., Ravi, S.S., Ester, M.: Efficient incremental constrained clustering. In: 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 240–249. ACM, San Jose (2007)
Basu, S., Banerjee, A., Mooney, R.J.: Active Semi-Supervision for Pairwise Constrained Clustering. In: SIAM International Conference on Data Mining (SDM). SIAM, Florida (2004)
Eaton, E.: Clustering with Propagated Constraints. University of Maryland Baltimore County (2005)
Miller, G.A.: The Magical Number Seven, Plus or Minus Two: Some Limits on Our Capacity for Processing Information. Psychological Review 63, 81–97 (1965)
Kleinberg, J., Papadimitriou, C., Raghavan, P.: A Microeconomic View of Data Mining. Data Mining Knowledge Discovery 2, 311–324 (1998)
Swapna Raj, P., Ravindran, B.: Utility Driven Clustering. In: 23rd International Florida Artificial Intelligence Research Society Conference (FLAIRS). AAAI Press, Florida (2011)
Tasi, C.-Y., Chiu, C.-C.: A purchase-based market segmentation methodology. Expert System Applications 27, 265–276 (2004)
Cohn, D., Caruana, R., Mccallum, A.: Semi-supervised clustering with user feedback. Technical report (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Prabakara Raj, S.R., Ravindran, B. (2013). Incremental Constrained Clustering: A Decision Theoretic Approach. In: Li, J., et al. Trends and Applications in Knowledge Discovery and Data Mining. PAKDD 2013. Lecture Notes in Computer Science(), vol 7867. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40319-4_41
Download citation
DOI: https://doi.org/10.1007/978-3-642-40319-4_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40318-7
Online ISBN: 978-3-642-40319-4
eBook Packages: Computer ScienceComputer Science (R0)