Constrained K-means with General Pairwise and Cardinality Constraints

Adel Bibi, Baoyuan Wu, Bernard Ghanem

Introduction

Unsupervised clustering algorithms, such as the standard K-means, often struggle when data distributions do not align with their inherent assumptions—for instance, when clusters are not perfectly spherical or have significantly different densities. To overcome these limitations, "constrained clustering" incorporates prior knowledge to guide the algorithm toward more meaningful partitions.

Two primary categories of constraints are commonly used:

  1. Pairwise Constraints: Instance-level rules specifying that two data points must belong to the same cluster (must-link) or different clusters (cannot-link).
  2. Cardinality Constraints: Cluster-level rules that dictate the expected size or distribution of the clusters.

Historically, most algorithms have been designed to handle only one of these constraint types at a time. Attempting to combine them using heuristic methods often leads to instability or failure to find feasible solutions. This research introduces a unified, mathematically rigorous framework that integrates both constraint types simultaneously.

A Unified Optimization Framework

The core challenge in combining these constraints lies in the optimization. The authors formulate the problem starting with the integer programming version of K-means, where cardinality constraints are linear and pairwise constraints are quadratic. Because optimizing discrete binary variables with quadratic constraints is NP-hard, the researchers applied two key mathematical transformations:

  • Continuous Relaxation: They replaced strict binary constraints with the intersection of two continuous geometric spaces (an $\ell_2$-sphere and a bounding box).
  • Bi-linearization: Quadratic pairwise constraints were transformed into bi-linear constraints by introducing auxiliary variables.

This reformulated continuous problem is solved using the Alternating Direction Method of Multipliers (ADMM). This approach allows the algorithm to iteratively update variables and reliably converge to a feasible, optimal binary solution, regardless of the initial starting point.

Experimental Results and Synergy

The framework was tested on synthetic datasets (designed with varying densities) and real-world benchmarks from the UCI Machine Learning Repository (e.g., Wine, Iris, Breast Cancer).

Key Findings

  • Synergy of Constraints: The experiments demonstrated that utilizing both pairwise and cardinality constraints jointly (referred to as $\ell_p$Km-Mix) significantly outperforms using either type in isolation. On certain datasets, the Adjusted Random Index (ARI) improved by up to 40% compared to single-constraint models.
  • Zero Violations: Unlike "soft-constraint" methods that treat rules as penalties, this formulation treats them as "hard" constraints. The algorithm consistently achieves zero violations for both pairwise and cardinality rules.
  • Robustness: The ADMM-based method proved highly stable, avoiding the common pitfall of getting trapped in unfeasible solutions due to poor random initialization.
Visualization of cluster assignments showing zero violations for cardinality (CardV), must-link (MLV), and cannot-link (CLV) constraints.

Across classical metrics like Mirkin's and Huber's indices, the proposed method outperformed state-of-the-art constrained models by 2% to 5%. On imbalanced synthetic data where standard K-means failed (ARI ~34%), this framework achieved near-perfect recovery (ARI ~99.5%).

Conclusion and Future Work

While the current ADMM framework is computationally intensive for very large datasets—due to a complexity of $O(n^3k^3)$—it provides a robust and mathematically sound solution for medium-sized benchmarks. Future research aims to integrate this optimization framework into deep clustering architectures. By combining neural network feature learning with strict constraint enforcement, the researchers hope to unlock new possibilities in complex fields like medical imaging and bioinformatics.

Summary updated

Abstract

We study constrained clustering, where constraints guide the clustering process. In existing works, two categories of constraints have been widely explored, namely pairwise and cardinality constraints. Pairwise constraints enforce the cluster labels of two instances to be the same (must-link constraints) or different (cannot-link constraints). Cardinality constraints encourage cluster sizes to satisfy a user-specified distribution. Most existing constrained clustering models can only utilize one category of constraints at a time. We enforce the above two categories into a unified clustering model starting with the integer program formulation of the standard K-means. As the two categories provide different useful information, utilizing both allow for better clustering performance. However, the optimization is difficult due to the binary and quadratic constraints in the unified formulation. To solve this, we utilize two techniques: equivalently replacing the binary constraints by the intersection of two continuous constraints; the other is transforming the quadratic constraints into bi-linear constraints by introducing extra variables. We derive an equivalent continuous reformulation with simple constraints, which can be efficiently solved by Alternating Direction Method of Multipliers. Extensive experiments on both synthetic and real data demonstrate when: (1) utilizing a single category of constraint, the proposed model is superior to or competitive with SOTA constrained clustering models, and (2) utilizing both categories of constraints jointly, the proposed model shows better performance than the case of the single category. The experiments show that the proposed method exploits the constraints to achieve perfect clustering performance with improved clustering to 2%-5% in classical clustering metrics, e.g. Adjusted Random, Mirkin's, and Huber's, indices outerperfomring other methods.
BibTeX
@article{bibi2023constrained,
  author = {Adel Bibi and Baoyuan Wu and Bernard Ghanem},
  title = {{Constrained K-means with General Pairwise and Cardinality Constraints}},
  journal = {IEEE Access},
  year = {2023},
  doi = {10.1109/access.2023.3236608},
}
Figure