Unsupervised clustering algorithms like $k$-means or spectral clustering typically group data based on a single assumption: that points close together in a feature space should belong to the same category. However, "similarity" is often subjective. A dataset of images might be clustered by color, by the objects depicted, or by artistic style, depending on the user's intent.
To bridge this gap between raw geometric distance and human semantics, researchers have developed a framework for semi-supervised clustering. Instead of requiring a full set of labels, this approach uses sparse "side information" in the form of pairwise instance-level constraints to guide the discovery of clusters.
The Language of Constraints
As Kiri Wagstaff and Claire Cardie established in Clustering with Instance-Level Constraints, human knowledge can be distilled into two simple rules:
- Must-Link (ML): Two specific data points must be assigned to the same cluster.
- Cannot-Link (CL): Two specific data points must not be assigned to the same cluster.
These constraints are significantly easier for humans to provide than exhaustive class labels. For example, in coreference resolution, a person can easily say whether two mentions refer to the same entity without needing to define every entity in a document. Similarly, in MOOC grading, a teacher can mark two different student answers as semantically equivalent, creating a must-link constraint that anchors the clustering of thousands of other responses.
Strategy 1: Warping the Metric Space
One of the most intuitive ways to satisfy these constraints is to change how the algorithm "sees" the distance between points. If two points have a must-link constraint but are far apart in the original feature space, we can "warp" the space to bring them closer together.
Mikhail Bilenko and researchers like Amaury Habrard utilize Metric Learning to achieve this. By learning a Mahalanobis distance metric, the algorithm adjusts the weights of different features so that must-link pairs are pulled together and cannot-link pairs are pushed apart. As Jiexi Yan demonstrates, this can be integrated directly into dictionary learning, ensuring that the underlying representation of the data is itself shaped by the provided constraints.
Strategy 2: Maximizing the Margin
Another approach adapts the "maximum margin" principle from Support Vector Machines (SVMs) to the unsupervised world. In Maximum Margin Clustering (MMC), Linli Xu and Dale Schuurmans treat cluster boundaries as hyperplanes that should maximize the distance (margin) between groups.
When pairwise constraints are introduced, they act as anchors for these boundaries. A must-link constraint forces the boundary to stay away from a specific pair, while a cannot-link constraint ensures the boundary passes between them. This formulation, further optimized by Jingchao Sun using bundle methods, allows the model to find the most robust partition that remains consistent with the known relationships.
Strategy 3: Propagating Constraints through Graphs
In many modern applications, data is represented as a graph or network. Here, constraints don't just affect the two points involved; they "flow" through the network to influence their neighbors.
Inmar E. Givoni and Brendan J. Frey adapted Affinity Propagation to incorporate these constraints directly into a message-passing framework. By modifying the "responsibility" and "availability" messages between nodes, a single must-link constraint can effectively pull an entire neighborhood into a specific cluster. This is particularly powerful in community detection, where network topology alone might be too noisy to reveal the true structure.
Active Learning and the Utility of Constraints
Not all constraints are created equal. Asking a user to link two points that the algorithm already knows belong together is a waste of effort. To solve this, researchers like Mrinmaya Sachan and Eric P. Xing use Active Learning to identify the most "informative" pairs—those where the model is most uncertain.
However, practitioners must be cautious. Hendrik Blockeel and Toon Van Craenendonck have shown that adding more constraints doesn't always improve performance. If the constraints are noisy or conflict with the natural density of the data, they can actually degrade the clustering quality. The goal is not just to satisfy the constraints, but to use them as a sparse skeleton upon which the rest of the data's structure can be reconstructed.