Constrained and Semi-Supervised Clustering

Twenty road segments of GPS traces, one algorithm, two runs. With must-link and cannot-link pairs enforced it averaged 98.6% on the Rand index. Without them, 58.0% on exactly the same segments. On that task the supervision was not breaking ties. It was carrying the result. The same literature reports the opposite outcome as well, from a paper one of the same authors co-wrote: constraint sets that “can actually decrease algorithm performance”.

Limited supervision can focus structure on a real task. It can also turn an unsupervised system into a brittle reflection of sparse, biased judgments. A fully satisfied constraint set does not tell you which of the two you are holding.

Guidance can restrict assignments, initialize groups, or reshape the distance itself. Those are not three settings of one dial. Xing and colleagues measured the gap in 2002. On a synthetic three-dimensional two-class set, K-means scored 0.4975 accuracy, and constrained K-means, enforcing the supplied pairs as hard constraints, scored 0.5060. Hand those same pairs to a Mahalanobis metric instead, learn the metric, cluster under it, and the result was accuracy 1. Their second example ran 0.4993, 0.5701 and 1. They state the reading plainly: “As shown by the accuracy scores given in the figure, both K-means and constrained K-means failed to find good clusterings. But by first learning a distance metric and then clustering according to that metric, we easily find the correct clustering separating the true clusters from each other.”

The difference is reach. A hard constraint moves the pair it names. A learned metric moves every point near that pair. Davidson and Ravi restate the finding — “The results of Xing and collaborators ... showed that learning a distance function from constraints and then using this distance function to cluster the data and not enforcing the constraints produced better results than just enforcing the constraints” — and then supply the counter-case. It is the same reach running the wrong way. Set k below the number of labels the constraints came from, and “the vast majority of constraints will effectively be ignored in the final clustering and ... the learnt distance function generally performs worse than the Euclidean distance function”.

The mechanisms differ in how they handle contradiction and uncertainty. For hard constraints that difference is a proved result rather than a caution. Davidson and Ravi asked the feasibility question in 2007: does any partition satisfy the given relations at all? Under must-link constraints alone the question is cheap, a transitive-closure computation in O(n+m). Add cannot-link and it stops being cheap. “The feasibility problem for clustering under ML constraints is in P while clustering under CL only and ML and CL is NP-complete, as can be shown by a reduction from graph coloring”. An unrelated group of five restates it: “It is NP-complete even only to determine whether an instance of the CL-constrained clustering problem is feasible”, obtained “via a reduction from the k-coloring problem”.

Repair is no easier than detection. Fixing an infeasible clustering is NP-complete as well, and no ρ-approximation exists for deleting the minimum number of constraints to restore feasibility. A few failures are trivial to spot: ML(a,b) together with CL(a,b), or CL(a,b), CL(b,c) and CL(a,c) with k ≤ 2. In general, though, the contradiction check a hard-constraint pipeline needs is exactly the problem those theorems call intractable. Soft penalties and learned metrics are not softer standards. They are ways of not having to answer that question exactly.

Treat annotation, consistency, fitting, and validation as separate stages. Two of those stages have published protocols and measured comparisons behind them, not advice.

Step 2, sampling. How the pairs are chosen matters as much as how many there are. In 2004 Basu and colleagues selected pairs with a two-phase Explore/Consolidate scheme built on farthest-first traversal, and compared it against randomly drawn pairs. The data sets were News-sim3 (300 documents, 3,225 dimensions), News-diff3 (300 documents), News-all20 (2,000 documents, 16,089 dimensions), a 400-document Classic3 subset and Iris (150 points). Learning curves ran out to 1,000 pairwise constraints — 5,000 for News-all20 — under 10-fold cross-validation. The result: “For the active algorithms, we consistently get significant improvements over the non-active algorithms, for all datasets we have considered.” On News-all20 the unstable opening of the curve is behind them after roughly the first 20 queries. The COBRA authors summarize the same finding — “Basu et al. [2004a] introduce a strategy to select the most informative constraints, prior to performing a single run of a constraint-based clustering algorithm. They show that active constraint selection can improve clustering performance” — while noting that in practice queried pairs “are often selected randomly”.

Steps 3 and 5, consistency and held-out validation. These are one problem seen twice, because pairwise constraints generate other constraints. COBRA is built on exactly that property: “constraint transitivity and entailment ... two properties that allow deriving additional constraints from a given set of constraints”. Pourrajabi and colleagues show what it does to a naive split: “For example, suppose a training fold contains the constraints must-link(A,B) and cannot-link(B,C). If the test fold contains the constraint cannot-link(A,C), this is information that was, implicitly, already available during the clustering process even though only the explicit constraints in the training folds were given.” Splitting a constraint set at random therefore “can lead to significantly underestimating the true classification error”. Their fix is structural: cut the constraint graph so that the folds are genuinely non-overlapping. The entailment that leaks across your split is the same entailment that makes A–B–C contradictions possible. That is why step 3 and step 5 share a piece of code.

Pairwise guidance can conflict locally, globally, or through missing coverage. The region nobody constrained is where the worst outcome sits. In 2017 Chierichetti and colleagues clustered three UCI data sets: Diabetes (1,000 records, balancing gender), Bank marketing (1,000 records, marital status) and 1994 Census/Adult (600 records, gender). Here is what the classical objectives did with an attribute no one had constrained: “Observe that the balance of the solutions produced by the classical algorithms is very low, and in four out of the six cases, the balance is 0 for larger values of k, meaning that the optimal solution has monochromatic clusters.” The Bank k-median instance produced three monochromatic clusters from k = 12 onward. Imposing balance ≥ 0.5 through fairlets restored it, and the paper prices the repair: “the balance comes with a corresponding increase in cost”. In 2019 Backurs and five colleagues re-ran fair clustering on the same three data sets, reporting fair k-median cost at k = 20 of 4,149 on Diabetes and 2.41×10⁷ on Census, against roughly 9,909 and 3.65×10⁷ for the 2017 method.

Constraints can make groups more relevant to a domain. They also reduce the claim that the result emerged from data alone. On the lane-finding task the constraints were most of the answer — 98.6% against 58.0% — and a result that dependent on human judgment has to be reported as such. That is not a weakness when it is documented honestly.

Preserve the constraint source, reviewer disagreement, coverage, and version. Record how the held-out set was cut, since a random split of a constraint graph is not a split. The final cluster model is inseparable from that human evidence.