AI RESEARCH
Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering
arXiv CS.LG
•
ArXi:2603.27417v1 Announce Type: new This paper presents a novel centroid-based heuristic algorithm, termed Kempe Swap K-Means, for constrained clustering under rigid must-link (ML) and cannot-link (CL) constraints. The algorithm employs a dual-phase iterative process: an assignment step that utilizes Kempe chain swaps to refine current clustering in the constrained solution space and a centroid update step that computes optimal cluster centroids. To enhance global search capabilities and avoid local optima, the framework incorporates controlled perturbations during the update phase.