Traditional unsupervised clustering is often described as an "ill-posed" problem. As noted by Bouveyron et al., a single dataset can yield multiple mathematically valid partitions, many of which may be irrelevant to a specific real-world task. To bridge this gap, researchers have developed methods to steer algorithms using domain knowledge, transforming clustering from a purely discovery-driven process into a guided optimization task.
The Logic of Must-Link and Cannot-Link
The most influential framework for integrating background knowledge is the use of instance-level constraints, a concept introduced by Cardie et al.. Instead of requiring a full set of labels, a user provides simple pairwise rules:
- Must-link (ML) constraints specify that two data points must belong to the same cluster.
- Cannot-link (CL) constraints specify that two points must be kept apart.
These constraints act as a sparse scaffold. By enforcing these rules, Cardie et al. demonstrated that clustering becomes not only more accurate but also computationally faster, as the search space for valid partitions is significantly reduced. This approach allows experts to inject "common-sense" principles or known physical relationships that raw data features might not capture, as argued by desJardins.
Integrating Constraints into Spectral Methods
A major challenge in this field is how to mathematically embed these discrete "rules" into continuous optimization frameworks like spectral clustering. Standard spectral methods partition data by finding the eigenvectors of a graph Laplacian, but they lack a natural way to handle external requirements.
Cucuringu et al. addressed this by framing constrained clustering as a generalized eigenvalue problem. In their Fast-GE algorithm, constraints are not treated as secondary penalties but as a fundamental part of the objective function, represented by a second graph Laplacian. This allows the algorithm to recover complex geometries that unsupervised methods would miss. Further refinements by Jiang et al. provided the computational stability needed to apply these generalized spectral methods to large-scale datasets.
Other spectral approaches, such as CC++ proposed by Fabila Carrasco et al., utilize signed Laplacians. By treating "must-link" as positive edges and "cannot-link" as negative edges, the authors leverage the theory of signed graphs to ensure the resulting clusters respect the domain knowledge while remaining scalable. Similarly, Rangapuram et al. introduced COSC, which uses a continuous relaxation to guarantee that all constraints are satisfied even in massive datasets.
Optimization and Interpretability
Beyond spectral methods, researchers have explored how to make constrained clustering both globally optimal and human-readable. Cohen et al. and Shati et al. proposed using optimal decision trees for constrained clustering. By encoding the problem into a Maximum Satisfiability (MaxSAT) framework, the authors ensure that the resulting clusters are not only compliant with expert constraints but are also defined by simple, interpretable rules (e.g., "If Feature A > x, then Cluster 1").
For high-dimensional or noisy data, Cheng et al. formulated subspace clustering as a Quadratically Constrained Quadratic Program (QCQP). This allows for the integration of "priors"—such as the expected percentage of outliers or known point co-occurrences—directly into the mathematical objective, ensuring the model adheres to known physical constraints.
Broadening the Scope of Guidance
The definition of "guidance" has evolved beyond simple pairwise links. Stepp laid the groundwork for conceptual clustering, where data is fit into predefined slots based on hierarchies and rules rather than just numerical similarity. More recently, Stephan et al. introduced text-guided image clustering, where multi-modal models translate images into descriptive text. This allows users to steer the clustering process using natural language keywords, ensuring the resulting groups align with specific human intents rather than arbitrary pixel patterns.
Whether through logic-based constraints in causal discovery Sridhar et al. or physics-inspired spin-glass models for community detection Eaton et al., the central intuition remains the same: by providing a "nudge" through constraints, we transform clustering from an ambiguous mathematical exercise into a powerful tool for domain-specific insight.
Key Foundational Work
Clustering with Instance-Level Constraints (2000) — contributed 2 concept elements to this direction.
Refining Inductive Bias in Unsupervised Learning via Constraints (2000) — contributed 1 concept elements to this direction.
Concepts in Conceptual Clustering (1987) — contributed 1 concept elements to this direction.