{ "id": "ep98nq46ye", "slug": "semi-supervised-clustering", "title": "Semi-supervised 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.semi_supervised_learning", "label": "Semi-supervised and weakly supervised learning", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.supervised_unsupervised.semi_supervised_learning" } ], "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" } ] }, { "id": "geo.nongeo.t2001.technology.computing.ai.supervised_unsupervised", "label": "Non-geographic · 2001 to 2020: Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.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.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology" }, { "id": "geo.nongeo.t2001.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing" }, { "id": "geo.nongeo.t2001.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai" }, { "id": "geo.nongeo.t2001.technology.computing.ai.ml_computation", "label": "Machine learning and neural computation", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.ml_computation" }, { "id": "geo.nongeo.t2001.technology.computing.ai.ml_methods", "label": "Machine learning methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.ml_methods" }, { "id": "geo.nongeo.t2001.technology.computing.ai.supervised_unsupervised", "label": "Supervised, unsupervised, and semi-supervised learning", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.supervised_unsupervised" } ] } ], "excerpt": "Semi-supervised clustering is a machine learning method that groups data using must-link and cannot-link constraints or labeled seeds; canonical algorithms include COP-K-Means, seeded k-means, and MPCK-Means.", "snippet": "Semi-supervised clustering is a machine learning method that groups data using must-link and cannot-link constraints or labeled seeds; canonical algorithms include COP-K-Means, seeded k-means, and MPCK-Means.", "node": "technology.computing.ai.supervised_unsupervised.semi_supervised_learning", "markdown": "# Semi-supervised clustering\n\nSemi-supervised clustering is a machine learning method that groups data into clusters using a large unlabeled set plus limited supervision, most often pairwise must-link and cannot-link constraints or a small number of labeled seed points, to steer the grouping toward a desired partition. The output is a partition of the data into K clusters that, ideally, satisfies every constraint in the union of the must-link and cannot-link sets.[1](https://link.springer.com/article/10.1007/s10462-024-11103-8)\n\n| Key fact | Detail |\n|---|---|\n| Supervision consumed | Pairwise must-link constraints (two points share a cluster), cannot-link constraints (they must not), or labeled seed points used to initialize clusters[1](https://link.springer.com/article/10.1007/s10462-024-11103-8) • [2](https://mlanthology.org/icml/2002/basu2002icml-semi/) |\n| Output | A partition of K clusters; hard-constraint methods require returned solutions to satisfy every constraint, but they may fail or return no solution when the constraint set is infeasible or a feasible assignment cannot be found[1](https://link.springer.com/article/10.1007/s10462-024-11103-8) • [3](https://arxiv.org/pdf/2111.15571v2.pdf) |\n| Two mechanism families | Constraint-based approaches modify the clustering algorithm or objective; metric-based approaches learn a distance measure from the constraints[4](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf) |\n| Canonical algorithms | COP-K-Means, seeded k-means (2002), PCK-Means and MPCK-Means, HMRF-K-Means[3](https://arxiv.org/pdf/2111.15571v2.pdf) • [2](https://mlanthology.org/icml/2002/basu2002icml-semi/) • [4](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf) • [5](https://www.cs.utexas.edu/~ml/papers/semi-kdd-04.pdf) |\n| Runtime cost | COP-K-Means runs in \\( O(n \\cdot k \\cdot c \\cdot t) \\) versus \\( O(n \\cdot k \\cdot t) \\) for k-means, where c counts constraints, so more constraints mean more computation[6](https://www.jstage.jst.go.jp/article/transinf/E100.D/6/E100.D_2016EDP7201/_pdf/-char/en) |\n| Known risk | Adding constraints lowered clustering performance in 45% of the runs in one systematic evaluation[7](https://ceur-ws.org/Vol-1455/paper-05.pdf) |\n\n## How it works\n\nA must-link constraint \\(C_{=}(x_i, x_j)\\) says two instances must land in the same cluster; a cannot-link constraint says they must not.[1](https://link.springer.com/article/10.1007/s10462-024-11103-8) Hard constraints must be satisfied exactly, while soft constraints may be violated to a variable extent, a distinction formalized by Davidson and Basu.[1](https://link.springer.com/article/10.1007/s10462-024-11103-8)\n\nThe two mechanism families alter the clustering differently.Constraint-based methods change the algorithm or its objective so that supervision pulls the partition toward the desired grouping; metric-based methods train a distance measure so that must-linked pairs become close and cannot-linked pairs far apart.[4](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf) • [5](https://www.cs.utexas.edu/~ml/papers/semi-kdd-04.pdf) In the pairwise constrained k-means formulation, the objective is the sum of squared distances from each point to its centroid plus a penalty cost for each violated constraint, with separate penalty weights for the must-link set M and the cannot-link set C:[4](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf)\n\n\\[ J_{\\mathrm{PCK\\text{-}Means}} = \\sum_{x_i \\in X} \\|x_i - \\mu_{l_i}\\|^2 + \\sum_{(x_i, x_j) \\in M} w_{ij}\\,[l_i \\neq l_j] + \\sum_{(x_i, x_j) \\in C} \\bar{w}_{ij}\\,[l_i = l_j] \\]\n\nwhere \\(\\mu_{l_i}\\) is the centroid of the cluster assigned to \\(x_i\\) and \\(w_{ij}\\) is the violation cost. MPCK-Means extends this by learning a weight matrix \\(A_{l_i}\\) per cluster, minimizing dispersion under the learned metric while penalizing violations:[4](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf)\n\n\\[ J_{\\mathrm{combined}} = \\sum_{x_i \\in X} \\|x_i - \\mu_{l_i}\\|^2_{A_{l_i}} - \\log(\\det(A_{l_i})) \\]\n\nBecause the metric is learned from the constraints, the distance function itself warps to respect the supervision rather than the assignment rule alone.[5](https://www.cs.utexas.edu/~ml/papers/semi-kdd-04.pdf)\n\n## How it is done\n\nCOP-K-Means, the canonical hard-constraint algorithm, adapts classic k-means with the essential change in the cluster-assignment step: in each iteration it tries to assign each observation to the nearest center so that no constraint is violated.[3](https://arxiv.org/pdf/2111.15571v2.pdf) • [8](https://www.wkiri.com/research/papers/wagstaff-const-kdid-06.pdf) It greedily enforces the constraints without backtracking, so it has no optimality guarantee and can fail to return a solution even when a feasible assignment exists.[3](https://arxiv.org/pdf/2111.15571v2.pdf)\n\nSeeded k-means, introduced by Sugato Basu, Arindam Banerjee, and Raymond J. Mooney (2002), instead uses labeled data to generate initial seed clusters, while their related constrained k-means approach derives pairwise constraints from the labels; the variants can be viewed as instances of the EM algorithm and outperformed random seeding and COP-KMeans in their experiments.[2](https://mlanthology.org/icml/2002/basu2002icml-semi/)\n\nMPCK-Means (Sugato Basu, Mikhail Bilenko, and Raymond J. Mooney, ICML 2004) unifies the constraint-based and metric-based lines: it performs distance-metric training with each clustering iteration using both unlabeled data and pairwise constraints, learns an individual metric per cluster so clusters of different shapes are possible, and, unlike earlier hard-constraint methods, allows constraint violation when that yields a more cohesive clustering, which makes it less vulnerable to noisy supervision.[4](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf) The probabilistic HMRF-K-Means algorithm works in three supervised stages: initializing centroids from neighborhoods induced by the constraints, constraint-sensitive assignment that minimizes distortion while violating as few constraints as possible, and iterative re-estimation of the distortion measure during clustering; using supervision in all three stages gave substantial improvements in its experiments on text documents.[5](https://www.cs.utexas.edu/~ml/papers/semi-kdd-04.pdf)\n\n## Origin\n\nConstrained Clustering introduced instance-level constraints and the first algorithm of the line, COP-COBWEB; Wagstaff, Cardie, Seth Rogers, and Stefan Schrödl followed with COP-K-Means in 2001.[1](https://link.springer.com/article/10.1007/s10462-024-11103-8) • [9](https://wkiri.com/research/papers/wagstaff-constraints-00.pdf) The first application was lane finding for vehicles in GPS data.[1](https://link.springer.com/article/10.1007/s10462-024-11103-8) Basu, Banerjee, and Mooney added the seeding approach in 2002,[2](https://mlanthology.org/icml/2002/basu2002icml-semi/) • [1](https://link.springer.com/article/10.1007/s10462-024-11103-8) while the MPCK-Means paper itself is the ICML 2004 publication.[4](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf) The same review credits Davidson and Ravi with the first hierarchical approaches (2005), and Basu, Davidson, and Wagstaff with the first book on [constrained clustering](https://www.edgepedia.org/constrained-clustering) (2008).[1](https://link.springer.com/article/10.1007/s10462-024-11103-8)\n\n## Variants\n\nBeyond the partition-based core, reviews organize the literature into hierarchical-based, density-based, graph-based, neural network-based, NMF-based, and random subspace technique-based semi-supervised clustering.[10](https://www.sciencedirect.com/science/article/pii/S0020025523002840) Spectral variants handle non-globular clusters that k-means cannot; most early semi-supervised spectral algorithms addressed only two-class problems, motivating k-way formulations using pairwise constraints.[11](https://pdfs.semanticscholar.org/ee2f/1ef5466a230e981e221acd050b27904c451a.pdf) The HMRF probabilistic framework accepts a broad range of distortion measures, including Bregman divergences such as squared [Euclidean distance](https://www.edgepedia.org/euclidean-distance) and KL divergence, and directional measures such as cosine distance.[12](https://www.cs.utexas.edu/~ml/papers/semi-bkchapter-06.pdf) Deep constrained clustering encodes standard together/apart constraints plus triplet constraints from continuous side information, instance difficulty constraints, and cluster-level balancing constraints, learning a representation consistent with the constraints end to end.[13](https://ar5iv.labs.arxiv.org/html/1901.10061) Structural entropy methods (SSE, December 2023) unify pairwise and label constraints in a relation graph with positive weights for must-link and negative for cannot-link, supporting both partitioning and hierarchical clustering.[14](https://arxiv.org/html/2312.10917)\n\n## Applications\n\nDocument and text clustering is the field with the largest number of publications, followed by biological data and image and video analysis.[1](https://link.springer.com/article/10.1007/s10462-024-11103-8) The probabilistic framework was validated on text documents,[5](https://www.cs.utexas.edu/~ml/papers/semi-kdd-04.pdf) and structural entropy methods have been demonstrated on single-cell RNA-seq [cell clustering](https://www.edgepedia.org/cell-clustering).[14](https://arxiv.org/html/2312.10917) Constraints are attractive because pairwise relations are easier to collect from experts than full labels.[11](https://pdfs.semanticscholar.org/ee2f/1ef5466a230e981e221acd050b27904c451a.pdf) Acquisition options include selecting constraints from existing labeled instances (ConstraintSelector),[15](https://link.springer.com/chapter/10.1007/978-3-642-14264-2_16) active selection of constraint queries in a pairwise constrained clustering framework,[16](https://epubs.siam.org/doi/10.1137/1.9781611972740.31) and large language models used as pairwise constraint pseudo-oracles, where LLM pseudo-labeled constraints fed to PCKMeans beat the state of the art on OPIEC59k.[17](https://arxiv.org/pdf/2307.00524)\n\n## Limitations and alternatives\n\nConstraints can hurt. Even constraint sets generated from true labels can decrease accuracy when predicting those very labels.[1](https://link.springer.com/article/10.1007/s10462-024-11103-8) In one systematic evaluation, performance decreased when constraints were added in 45% of the considered runs, and no single semi-supervised algorithm outperformed all others across datasets and constraint sets.[7](https://ceur-ws.org/Vol-1455/paper-05.pdf) On UCI benchmarks, COP-KMeans and constrained EM do not always beat their unsupervised counterparts.[6](https://www.jstage.jst.go.jp/article/transinf/E100.D/6/E100.D_2016EDP7201/_pdf/-char/en) Seeding with a small number of constraints has an immediate positive effect with diminishing returns, but metric learning from few constraints is unreliable and needs a substantial number to estimate its parameters accurately.[4](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf) Erroneous must-link constraints are more harmful than erroneous cannot-link constraints, because must-link errors propagate through the transitivity of \"same class\" while cannot-link errors act only as regularization.[18](https://arxiv.org/pdf/2001.06720v1.pdf) [Ad hoc](https://www.edgepedia.org/ad-hoc) constraint handling and soft penalty factors lack a probabilistic interpretation and may fail under noisy, scarce supervision; soft penalties also depend heavily on parameter choices.[19](https://ar5iv.labs.arxiv.org/html/2104.02146) Computationally, COP-KMeans costs \\( O(n \\cdot k \\cdot c \\cdot t) \\) against \\( O(n \\cdot k \\cdot t) \\) for k-means,[6](https://www.jstage.jst.go.jp/article/transinf/E100.D/6/E100.D_2016EDP7201/_pdf/-char/en) and relaxed spectral formulations require a full-rank eigendecomposition taking \\( O(n^{3}) \\).[13](https://ar5iv.labs.arxiv.org/html/1901.10061)\n\nAlternatives address these weaknesses in different ways. Exact branch-and-cut with SDP relaxation solves semi-supervised minimum sum-of-squares clustering with hard constraints optimally for instances up to \\( n = 801 \\) points with \\( n/2 \\) constraints, with cannot-link constraints the most challenging.[3](https://arxiv.org/pdf/2111.15571v2.pdf) A confidence-based constraint algorithm scales to 60,000 objects, 100 clusters, and millions of cannot-link constraints.[20](https://arxiv.org/pdf/2212.14437v3.pdf) End-to-end deep clustering overcomes the negative effects of individual constraint sets by learning a constraint-consistent representation,[13](https://ar5iv.labs.arxiv.org/html/1901.10061) and a 2025 constraint self-learning framework iteratively derives new constraints from local neighbor structures in a discriminant feature space, outperforming eight competitors including MPCK-Means.[21](https://www.mdpi.com/2227-7390/13/9/1535)\n\n## References\n\n1. [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)\n2. [Semi-Supervised Clustering by Seeding (Basu, Banerjee, Mooney, ICML 2002)](https://mlanthology.org/icml/2002/basu2002icml-semi/)\n3. [An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering](https://arxiv.org/pdf/2111.15571v2.pdf)\n4. [Integrating Constraints and Metric Learning in Semi-Supervised Clustering (Basu, Bilenko, Mooney, ICML 2004)](https://www.cs.utexas.edu/~ml/papers/semi-icml-04.pdf)\n5. [A Probabilistic Framework for Semi-Supervised Clustering (KDD 2004)](https://www.cs.utexas.edu/~ml/papers/semi-kdd-04.pdf)\n6. [Semi-Supervised Clustering Based on Exemplars Constraints](https://www.jstage.jst.go.jp/article/transinf/E100.D/6/E100.D_2016EDP7201/_pdf/-char/en)\n7. [Limitations of Using Constraint Set Utility in Semi-Supervised Clustering](https://ceur-ws.org/Vol-1455/paper-05.pdf)\n8. [Value, Cost, and Sharing: Open Issues in Constrained Clustering (Wagstaff)](https://www.wkiri.com/research/papers/wagstaff-const-kdid-06.pdf)\n9. [Clustering with Instance-level Constraints (COP-COBWEB)](https://wkiri.com/research/papers/wagstaff-constraints-00.pdf)\n10. [A review on semi-supervised clustering (Information Sciences)](https://www.sciencedirect.com/science/article/pii/S0020025523002840)\n11. [Semi-supervised K-way Spectral Clustering Using Pairwise Constraints](https://pdfs.semanticscholar.org/ee2f/1ef5466a230e981e221acd050b27904c451a.pdf)\n12. [Probabilistic Semi-Supervised Clustering (book chapter, HMRF-based model)](https://www.cs.utexas.edu/~ml/papers/semi-bkchapter-06.pdf)\n13. [A Framework for Deep Constrained Clustering - Algorithms and Advances](https://ar5iv.labs.arxiv.org/html/1901.10061)\n14. [Semi-Supervised Clustering via Structural Entropy with Different Constraints](https://arxiv.org/html/2312.10917)\n15. [Automated Constraint Selection for Semi-supervised Clustering Algorithm (Springer chapter)](https://link.springer.com/chapter/10.1007/978-3-642-14264-2_16)\n16. [Active Semi-Supervision for Pairwise Constrained Clustering (SDM 2004)](https://epubs.siam.org/doi/10.1137/1.9781611972740.31)\n17. [Large Language Models Enable Few-Shot Clustering (NEC; arXiv 2307.00524, 2023)](https://arxiv.org/pdf/2307.00524)\n18. [A Classification-Based Approach to Semi-Supervised Clustering with Pairwise Constraints (S3C2)](https://arxiv.org/pdf/2001.06720v1.pdf)\n19. [Semi-Supervised Clustering with Inaccurate Pairwise Annotations](https://ar5iv.labs.arxiv.org/html/2104.02146)\n20. [An algorithm for clustering with confidence-based must-link and cannot-link constraints (PCCC)](https://arxiv.org/pdf/2212.14437v3.pdf)\n21. [Semi-Supervised Clustering via Constraints Self-Learning (Mathematics, MDPI, 2025)](https://www.mdpi.com/2227-7390/13/9/1535)\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 › Semi-supervised and weakly supervised learning*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Oct 15, 2026 · Last review: Sep 30, 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.utexas.edu/~ml/papers/semi-icml-04.pdf", "https://www.cs.utexas.edu/~ml/papers/semi-kdd-04.pdf", "https://www.cs.utexas.edu/~ml/papers/semi-bkchapter-06.pdf" ], "url": "https://www.edgepedia.org/semi-supervised-clustering", "markdown_url": "https://www.edgepedia.org/semi-supervised-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": "\"Semi-supervised clustering\", Edgepedia (EdgeChat), https://www.edgepedia.org/semi-supervised-clustering. Edgepedia Community License 1.0.", "credit_md": "\"[Semi-supervised clustering](https://www.edgepedia.org/semi-supervised-clustering)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/semi-supervised-clustering](https://www.edgepedia.org/semi-supervised-clustering). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Semi-supervised clustering\", Edgepedia (EdgeChat), https://www.edgepedia.org/semi-supervised-clustering. Edgepedia Community License 1.0.", "speakable": "Semi-supervised clustering is a machine learning method that groups data using must-link and cannot-link constraints or labeled seeds; canonical algorithms include COP-K-Means, seeded k-means, and MPCK-Means." }