{ "id": "epmafmrbwp", "slug": "constrained-clustering", "title": "Constrained clustering", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_computation" }, { "id": "technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.ml_methods" }, { "id": "technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised" }, { "id": "technology.computing.ai.supervised_unsupervised.clustering", "label": "Clustering algorithms", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised.clustering" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "label": "Non-geographic · 1946 to 2000: Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t1946.technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.ml_methods" }, { "id": "geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.supervised_unsupervised" } ] } ], "excerpt": "Constrained clustering is a machine learning method that groups data while satisfying user-provided must-link and cannot-link constraints, named by Kiri Wagstaff and Claire Cardie in 2000.", "snippet": "Constrained clustering is a machine learning method that groups data while satisfying user-provided must-link and cannot-link constraints, named by Kiri Wagstaff and Claire Cardie in 2000.", "node": "technology.computing.ai.supervised_unsupervised.clustering", "markdown": "# Constrained clustering\n\nConstrained clustering is a machine learning method that groups data into clusters while satisfying user-provided pairwise constraints, so that the output reflects background knowledge rather than distance structure alone. The two standard constraint types are must-link, meaning two points must land in the same cluster, and cannot-link, meaning they must land in different clusters. Constraints may be enforced as hard requirements that can never be broken, or as soft preferences that may be violated at a cost. Compared with purely unsupervised clustering, this guidance steers the output toward a grouping the user actually wants, and it can also reduce runtime by pruning the search over partitions.[1](https://wkiri.com/research/papers/wagstaff-constraints-00.pdf)\n\n| Key fact | Detail |\n|---|---|\n| Constraint vocabulary | Must-link (same cluster) and cannot-link (different clusters), introduced with the name \"constrained clustering\" in 2000[1](https://wkiri.com/research/papers/wagstaff-constraints-00.pdf) |\n| Hard vs soft | Hard constraints must be satisfied; soft constraints can be violated to a variable extent[2](https://link.springer.com/article/10.1007/s10462-024-11103-8) |\n| Hard-enforcement failure mode | COP-K-means returns the empty partition if no legal cluster exists for a point[3](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf) |\n| Computational cost | Deciding whether a feasible partition exists is NP-complete[4](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf) |\n| Accuracy payoff | As few as 10-100 constraints raised accuracy on three of four early test datasets while lowering runtime[1](https://wkiri.com/research/papers/wagstaff-constraints-00.pdf) |\n| Modern scale | Integer-programming methods handle 60,000 objects, 100 clusters, and millions of cannot-link constraints[5](https://doi.org/10.1287/ijoc.2023.0419) |\n| First application | Lane finding for vehicles in GPS data[2](https://link.springer.com/article/10.1007/s10462-024-11103-8) |\n\n## How it works\n\nA constraint set consists of must-link pairs \\( C_{=} \\) and cannot-link pairs \\( C_{\\neq} \\), and the goal is a partition of \\( K \\) clusters that ideally satisfies every constraint in \\( C_{=} \\cup C_{\\neq} \\).[2](https://link.springer.com/article/10.1007/s10462-024-11103-8) Because must-link is transitive, practitioners take the transitive closure of the constraint set before clustering: if \\( d_i \\) must link to \\( d_j \\) and \\( d_j \\) cannot link to \\( d_k \\), then \\( d_i \\) cannot link to \\( d_k \\).[3](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf)\n\nMechanisms differ in how a constraint touches the objective. Hard enforcement, as in COP-K-means, restricts each assignment step: a point goes to its closest cluster unless doing so violates a constraint, in which case the algorithm walks down a sorted list of clusters until it finds a legal host.[3](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf) Penalty formulations such as PKM and CVQE instead allow a constraint to be ignored when satisfying it would substantially worsen the objective function, which gives better results than COP-K-means when constraints are noisy.[4](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf) Degree-of-belief formulations attach each constraint a real weight between 0 and 1, where 1 is a hard constraint; constrained spectral clustering can encode such beliefs and guarantees a user-specified lower bound on how well the constraints are satisfied.[6](https://www.cs.ucdavis.edu/~davidson/Publications/KDD10-DMKD12.pdf) • [7](https://people.eng.unimelb.edu.au/baileyj/papers/SDM16LCC.pdf)\n\nFeasibility is the structural limit on hard enforcement. Some constraint sets admit no feasible partition for any \\( K \\), for example a must-link and a cannot-link on the same pair, and feasibility can depend on \\( K \\): three mutual cannot-links \\( C_{\\neq}(x_1,x_2), C_{\\neq}(x_2,x_3), C_{\\neq}(x_1,x_3) \\) are satisfiable for \\( K = 3 \\) but not for \\( K = 2 \\). Determining whether a feasible solution exists is NP-complete, so iterative algorithms should not attempt to verify feasibility at every iteration; clustering under hard constraints is equivalent to coloring a cannot-link graph with \\( k \\) colors.[2](https://link.springer.com/article/10.1007/s10462-024-11103-8) • [4](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf) • [8](https://www.arxiv.org/pdf/2603.27417)\n\n## How it is done\n\nThe practitioner workflow has four stages. First, constraints are acquired: from labeled items, whose labels induce pairwise relations, or by querying an oracle that answers must-link or cannot-link for a nominated pair.[9](https://www.cs.utexas.edu/~ml/papers/semi-sdm-04.pdf) How the constraints are chosen matters as much as how many: space-level propagation generally needs less than half as many constraints as constrained k-means for a given accuracy,[10](https://people.eecs.berkeley.edu/~klein/papers/constrained_clustering-ICML_2002.pdf) actively selected constraints beat randomly generated ones,[4](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf) • [9](https://www.cs.utexas.edu/~ml/papers/semi-sdm-04.pdf) and active querying gives significant accuracy gains from a small supervision budget. Second, the constraint set is represented as a graph and closed under transitivity, collapsing must-link connected components into super-nodes, a step standard in exact solvers.[3](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf) • [8](https://www.arxiv.org/pdf/2603.27417) Third, the chosen algorithm runs. In COP-K-means the loop is: initialize \\( k \\) centers; assign each point to the closest cluster for which the violation check fails to trigger, returning the empty partition if no legal cluster exists; recompute centers as the means of assigned points; and iterate to convergence.[3](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf) Fourth, infeasibility is managed, for example by switching to a soft-constraint method.[4](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf)\n\n## Origin\n\nThe name constrained clustering and the must-link/cannot-link vocabulary appeared in \"Clustering with Instance-Level Constraints\" by Kiri L. Wagstaff and Claire Cardie in 2000, which also introduced the COP-COBWEB algorithm, a modified version of COBWEB that tends to satisfy all pairwise constraints.[1](https://wkiri.com/research/papers/wagstaff-constraints-00.pdf) • [11](https://germain-forestier.info/publis/guidedTour2020.pdf) The follow-up paper \"Constrained K-means Clustering with Background Knowledge\" by Kiri L. Wagstaff and colleagues in 2001 introduced COP-K-means.[3](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf) In 2002, Dan Klein, Sepandar Kamvar, and [Christopher D. Manning](https://www.edgepedia.org/christopher-d-manning) introduced space-level constraints, propagating pairwise relations across the feature space, after observing that the first two algorithms showed little improvement over their unsupervised counterparts when given very few constraints.[10](https://people.eecs.berkeley.edu/~klein/papers/constrained_clustering-ICML_2002.pdf) Later milestones include the Deep Constrained Clustering framework by Hongjing Zhang and colleagues (2021),[12](https://doi.org/10.1007/s10618-020-00734-4) the PCCC integer-programming algorithm by Philipp Baumann and Dorit S. Hochbaum (2024),[5](https://doi.org/10.1287/ijoc.2023.0419) and CODAC by Anri Patron and colleagues (2026).[13](https://doi.org/10.1007/s10618-026-01229-4)\n\n## Variants\n\n**Hard-constraint partitional methods.** COP-K-means is the canonical example; later heuristics such as ICOP-K-means and CLC-K-means were motivated by its infeasible intermediate solutions and sensitivity to data-point processing order.[8](https://www.arxiv.org/pdf/2603.27417)\n\n**Soft-constraint k-means.** PCK-means and MPCK-means treat constraints as soft penalties rather than inviolable rules.[2](https://link.springer.com/article/10.1007/s10462-024-11103-8) PKM and CVQE selectively ignore constraints that would badly damage the objective.[4](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf)\n\n**Spectral and exact methods.** Constrained spectral clustering encodes constraint confidence and bounds satisfaction from below;[6](https://www.cs.ucdavis.edu/~davidson/Publications/KDD10-DMKD12.pdf) a spectral-regularization variant scales with the number of objects and constraints and handles both constraint types in multi-class problems;[14](https://www.ee.columbia.edu/~zgli/papers/CVPR09_CCSR.pdf) and complex constraints built from logical combinations can be expressed as linear equalities and inequalities in a quadratic program, running up to 1000 times faster than the then state-of-the-art constrained spectral method for conjunctions.[15](https://people.cs.vt.edu/naren/papers/clust-complex-aaai13.pdf) PCCC uses integer programming for the assignment step and is unusual in mixing hard and confidence-weighted soft constraints in one model.[5](https://doi.org/10.1287/ijoc.2023.0419) Kempe Swap K-means borrows Kempe chain exchanges from graph coloring to preserve feasibility while improving assignments.[8](https://www.arxiv.org/pdf/2603.27417)\n\n**Deep methods.** The DCC framework learns a representation consistent with the constraints and handles standard together/apart constraints plus constraints from continuous values and high-level domain knowledge.[12](https://doi.org/10.1007/s10618-020-00734-4) SpherePair encodes constraints with an anchor-free angular loss bounded in \\( [0, \\pi] \\) and removes the need to know the number of clusters in advance.[16](https://proceedings.neurips.cc/paper_files/paper/2025/file/a9cae5b74cfc8f71c39a4e646db819c2-Paper-Conference.pdf) CODAC integrates actively selected constraints into [deep representation learning](https://www.edgepedia.org/deep-representation-learning).[13](https://doi.org/10.1007/s10618-026-01229-4)\n\n## Applications\n\nThe first application, in the 2001 COP-K-means paper, was lane finding for vehicles in GPS data.[2](https://link.springer.com/article/10.1007/s10462-024-11103-8) • [3](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf) By publication count, the largest field is text data analysis, where document clustering attracts the most work, followed by biological, image, and video data analysis.[2](https://link.springer.com/article/10.1007/s10462-024-11103-8)\n\n## Limitations and alternatives\n\nHard enforcement has three documented failure modes. Feasibility is NP-complete, so a greedy algorithm can paint itself into a corner; COP-K-means responds by returning the empty partition, and it can generate infeasible intermediate solutions and is sensitive to processing order.[4](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf) • [3](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf) • [8](https://www.arxiv.org/pdf/2603.27417) Randomly generated constraint sets can hurt: for a significant fraction of such sets, performance is worse than using no constraints at all, a negative effect that DCC mitigates by learning a representation satisfying the constraints while still clustering well.[12](https://doi.org/10.1007/s10618-020-00734-4) Noisy constraints favor soft methods such as PKM, CVQE,[4](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf) COP-RF,[17](https://xiatian-zhu.github.io/papers/TNNLS15/ZhuLoyGong_TNNLS2015.pdf) and PCCC's confidence weighting.[5](https://doi.org/10.1287/ijoc.2023.0419)\n\nThe nearest alternative branch is constrained distance metric learning, which learns a metric pulling must-link pairs together and maximizing cannot-link distance without directly producing a partition; the field splits into this branch and constrained partitional methods.[2](https://link.springer.com/article/10.1007/s10462-024-11103-8) Recent work automates constraint acquisition with LLMs, adding confidence thresholds and penalty mechanisms for inaccurate generated constraints.[18](https://ojs.aaai.org/index.php/AAAI/article/view/39379)\n\n## References\n\n1. [Clustering with Instance-level Constraints (Wagstaff & Cardie, ICML 2000)](https://wkiri.com/research/papers/wagstaff-constraints-00.pdf)\n2. [Semi-supervised constrained clustering: an in-depth overview, ranked taxonomy and future research directions (Artificial Intelligence Review, 2024)](https://link.springer.com/article/10.1007/s10462-024-11103-8)\n3. [Constrained K-means Clustering with Background Knowledge (Wagstaff, Cardie, Rogers, Schroedl, ICML 2001)](https://wkiri.com/research/papers/wagstaff-kmeans-01.pdf)\n4. [Intractability and Clustering with Constraints / Value, Cost, and Sharing (Davidson, ICML 2007)](https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf)\n5. [Philipp Baumann, Dorit S. Hochbaum (2024). An Algorithm for Clustering with Confidence-Based Must-Link and Cannot-Link Constraints. INFORMS journal on computing.](https://doi.org/10.1287/ijoc.2023.0419)\n6. [On Constrained Spectral Clustering and Its Applications (Davidson et al.)](https://www.cs.ucdavis.edu/~davidson/Publications/KDD10-DMKD12.pdf)\n7. [Lagrangian Constrained Clustering (SDM 2016)](https://people.eng.unimelb.edu.au/baileyj/papers/SDM16LCC.pdf)\n8. [Kempe Swap K-Means for constrained clustering under rigid must-link and cannot-link constraints (arXiv preprint)](https://www.arxiv.org/pdf/2603.27417)\n9. [Active Semi-Supervision for Pairwise Constrained Clustering (SDM 2004)](https://www.cs.utexas.edu/~ml/papers/semi-sdm-04.pdf)\n10. [From Instance-level Constraints to Space-level Constraints: Making the Most of Prior Knowledge in Data Clustering (Klein et al., ICML 2002)](https://people.eecs.berkeley.edu/~klein/papers/constrained_clustering-ICML_2002.pdf)\n11. [Constrained Clustering: Current and New Trends (guided tour survey, 2020)](https://germain-forestier.info/publis/guidedTour2020.pdf)\n12. [Hongjing Zhang and colleagues (2021). A framework for deep constrained clustering. Data Mining and Knowledge Discovery.](https://doi.org/10.1007/s10618-020-00734-4)\n13. [Anri Patron and colleagues (2026). CODAC: Constraint-based Deep Active Clustering. Data Mining and Knowledge Discovery.](https://doi.org/10.1007/s10618-026-01229-4)\n14. [Constrained Clustering via Spectral Regularization (CVPR 2009)](https://www.ee.columbia.edu/~zgli/papers/CVPR09_CCSR.pdf)\n15. [Clustering with Complex Constraints - Algorithms and Applications (AAAI 2013)](https://people.cs.vt.edu/naren/papers/clust-complex-aaai13.pdf)\n16. [Angular Constraint Embedding via SpherePair Loss for Constrained Clustering (NeurIPS 2025)](https://proceedings.neurips.cc/paper_files/paper/2025/file/a9cae5b74cfc8f71c39a4e646db819c2-Paper-Conference.pdf)\n17. [Constrained Clustering With Imperfect Oracles (COP-RF, TNNLS 2015)](https://xiatian-zhu.github.io/papers/TNNLS15/ZhuLoyGong_TNNLS2015.pdf)\n18. [Optimized Algorithms for Text Clustering with LLM-Generated Constraints (AAAI)](https://ojs.aaai.org/index.php/AAAI/article/view/39379)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Machine learning and neural computation › Machine learning methods › Supervised, unsupervised, and semi-supervised learning › Clustering algorithms*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.cs.ucdavis.edu/~davidson/Publications/ICML2007.pdf", "https://www.cs.ucdavis.edu/~davidson/Publications/KDD10-DMKD12.pdf", "https://www.cs.utexas.edu/~ml/papers/semi-sdm-04.pdf", "https://people.eecs.berkeley.edu/~klein/papers/constrained_clustering-ICML_2002.pdf", "https://www.ee.columbia.edu/~zgli/papers/CVPR09_CCSR.pdf" ], "url": "https://www.edgepedia.org/constrained-clustering", "markdown_url": "https://www.edgepedia.org/constrained-clustering.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Constrained clustering\", Edgepedia (EdgeChat), https://www.edgepedia.org/constrained-clustering. Edgepedia Community License 1.0.", "credit_md": "\"[Constrained clustering](https://www.edgepedia.org/constrained-clustering)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/constrained-clustering](https://www.edgepedia.org/constrained-clustering). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Constrained clustering\", Edgepedia (EdgeChat), https://www.edgepedia.org/constrained-clustering. Edgepedia Community License 1.0.", "speakable": "Constrained clustering is a machine learning method that groups data while satisfying user-provided must-link and cannot-link constraints, named by Kiri Wagstaff and Claire Cardie in 2000." }