HAPPIER CONSTRAINED CLUSTERING: EXPLOITING PAIRWISE HINTS

Constrained clustering incorporates domain knowledge through pairwise must-link and cannot-link constraints and can substantially improve unsupervised clustering. However, these constraints turn the assignment step of k-means into a combinatorial problem and, when treated only as feasibility conditions, leave much of their geometric information unexploited. We introduce HAPPIER, a weighted hard-constrained k-means framework that quantifies the geometric agreement between feasible assignments and their centers and uses this information to guide point weighting and solution selection. We establish that the fixed-center assignment relaxation is integral for two clusters under mere feasibility of the constraints, and for more than two clusters under acyclic constraint graphs. Consequently, each assignment step admits a globally optimal binary solution obtainable through linear programming, yielding a direct and tractable algorithm. Extensive experiments across diverse datasets, constraint budgets, and noise regimes demonstrate that HAPPIER robustly and consistently outperforms competitive constrained clustering methods in recovering the ground-truth cluster structure. These results confirm the value of exploiting the geometric information encoded by pairwise constraints to improve clustering quality.