Effects of Constraint Quality and Distribution on Semi-Supervised Clustering Performance

Semi-supervised clustering enhances traditional clustering algorithms by leveraging prior knowledge, such as class labels or pairwise constraints, to improve clustering quality. Despite numerous proposed methods, the effects of constraint set quality and distribution—particularly imbalanced or erroneous constraints—remain poorly understood. This paper investigates these issues through systematic simulations, evaluating six state-of-the-art semi-supervised clustering algorithms under imbalanced or incorrect constraint conditions. Experiments on multiple real-world and synthetic benchmark datasets reveal that must-link constraints generally provide greater benefit than cannot-link constraints, while relying solely on cannot-link constraints may reduce performance. Furthermore, incorrect constraints—especially erroneous must-link constraints—can significantly degrade clustering performance. These findings underscore the critical importance of carefully designing constraint sets to achieve reliable and effective semi-supervised clustering, providing clear guidance on the conditions under which different algorithmic approaches perform best.