An Algorithm for Clustering with Confidence-Based Must-Link and Cannot-Link Constraints

Philipp Baumann () and Dorit S. Hochbaum ()
Additional contact information
Philipp Baumann: Department of Business Administration, University of Bern, 3012 Bern, Switzerland
Dorit S. Hochbaum: Industrial Engineering and Operations Research Department, University of California, Berkeley, California 94720

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 1044-1068

Abstract: We study here the semisupervised k -clustering problem where information is available on whether pairs of objects are in the same or different clusters. This information is available either with certainty or with a limited level of confidence. We introduce the pair-wise confidence constraints clustering (PCCC) algorithm, which iteratively assigns objects to clusters while accounting for the information provided on the pairs of objects. Our algorithm uses integer programming for the assignment of objects, which allows us to include relationships as hard constraints that are guaranteed to be satisfied or as soft constraints that can be violated subject to a penalty. This flexibility distinguishes our algorithm from the state of the art, in which all pair-wise constraints are considered hard or all are considered soft. We developed an enhanced multistart approach and a model-size reduction technique for the integer program that contribute to the effectiveness and efficiency of the algorithm. Unlike existing algorithms, our algorithm scales to large-scale instances with up to 60,000 objects, 100 clusters, and millions of cannot-link constraints (which are the most challenging constraints to incorporate). We compare the PCCC algorithm with state-of-the-art approaches in an extensive computational study. Even though the PCCC algorithm is more general than the state-of-the-art approaches in its applicability, it outperforms the state-of-the-art approaches on instances with all hard or all soft constraints in terms of both run time and various metrics of solution quality. The code of the PCCC algorithm is publicly available on GitHub.

Keywords: machine learning; semisupervised learning; must-link and cannot-link constraints; confidence levels; integer programming; constrained clustering (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0419 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:4:p:1044-1068

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().