University of Minnesota
Accommodating Positive and Negative Constraints in the K-Means Algorithm
Abstract
dc:description.abstractK-Means is one of the most widely used clustering algorithms, but its standard form is an unsupervised method that assumes no prior information about relationships among observations. In practice, partial knowledge may exist in the form of constraints: some observations should be grouped together through positive constraints, while others should be kept apart by negative constraints. This thesis develops and implements a semi-supervised extension of K-Means that accommodates both types of hard constraints. Positive constraints are handled through block formation, while negative constraints are represented using graph-based structures that determine feasible cluster assignments. The resulting method, implemented in the R package ssKmeans with a C backend, preserves the iterative structure and within-cluster sum of squares objective of classical K-Means while incorporating prior information into the membership update.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Johnson, Emma
Subjects
dc:subject × 12- Hard Constraints
- K-Means Algorithm
- Model-Based Clustering
- Negative Constraints
- Positive Constraints
- Semi-Supervised Clustering
- Master of Science in Mathematical Sciences
- Department of Mathematics and Statistics
- Swenson College of Science and Engineering
- University of Minnesota Duluth
- Plan As (thesis-based master's degrees)
- Master of Science
Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Citation
- Johnson, Emma. (2026). Accommodating Positive and Negative Constraints in the K-Means Algorithm. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/282252.