mustlink

Must-link is a pairwise constraint used in constrained clustering to indicate that two data points should be assigned to the same cluster. It is paired with cannot-link constraints, which require that two points be placed in different clusters. Must-link constraints are typically supplied by domain knowledge or derived from prior observations, and are treated as hard constraints by many algorithms but can be modeled as soft or probabilistic in some approaches.

Transitivity is a common property: if A must-link B and B must-link C, then A must-link C, which can simplify constraint propagation. In some methods this transitivity is enforced, in others it is not strictly required.

Must-link constraints are used in algorithms such as constrained k-means (e.g., COP-KMeans), constrained spectral clustering and other semi-supervised clustering methods. They influence initialization, distance calculations, and cluster assignments to ensure must-linked points are co-clustered. They help incorporate domain knowledge and can improve clustering quality when constraints are accurate.

Limitations include sensitivity to noisy or contradictory constraints, the potential to bias results if constraints are scarce or incorrect, and the need to handle partial or uncertain constraints. The concept originated in early 2000s literature on constrained clustering, notably Wagstaff, Cardie, Rogers, and Scholz's Constrained K-Means work, which popularized the framework.