Back to search

University of Minnesota

Accommodating Positive and Negative Constraints in the K-Means Algorithm

Abstract

dc:description.abstract

K-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

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.

Chain of custody

source
Harvested from
University of Minnesota
Base URL
conservancy.umn.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Johnson, Emma. Accommodating Positive and Negative Constraints in the K-Means Algorithm. 2026. https://hdl.handle.net/11299/282252