An Algebraic Approach to Constrained K-means Clustering

Hiroki Oohori; Kentaro Fukushima; Michio Yamamoto

stat.MEOct 10, 2026

An Algebraic Approach to Constrained K-means Clustering

Authors: Hiroki Oohori, Kentaro Fukushima, Michio Yamamoto

Organizations: Graduate School of Human Sciences, The University of Osaka, Osaka, Japan · Graduate School of Education, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan · Data Science and AI Innovation Research Promotion Center, Shiga University, Shiga, Japan

Abstract

Clustering is typically performed using only object features, although additional information about relationships between objects may be available and can be incorporated through constraints. Among these, pairwise constraints require two objects to belong to the same cluster or to different clusters. Several extensions of the k-means algorithm accommodate such constraints, but they sometimes fail to find a feasible assignment or incur high computational cost. Motivated by these limitations, we propose an algebraic approach to k-means clustering with pairwise constraints. The algorithm simplifies the constraints using Gröbner bases before optimization, improving the efficiency of cluster assignment. It can also detect whether the constraint set has a feasible assignment before optimization. Comparative experiments with existing algorithms showed that the proposed algorithm achieved comparable or better clustering quality at a lower computational cost, particularly when the numbers of constraints and clusters were small.

Figures & tables

Figure 1: Order dependence in COPK-means. Panel (a) is an illustration of the setting. There are two clusters with centroids

c_{1}

and

c_{2}

. The points of objects in feature space are

y_{1}

y_{2}

, and

y_{3}

, and a CL constraint is imposed between

1

and

2

and another between

2

and

3

. Panels (b), (c), and (d) illustrate the order dependence of COPK-means. Colors of points represent clusters to which objects are assigned, and the numbers in parentheses indicate the order in which the objects are assigned. In (b), COPK-means reaches the optimal assignment; in (c), it cannot assign object

2

; and in (d), it obtains another, nonoptimal assignment.

ID	age	operation year	positive nodes	survival status
1	57	61	30	2
2	59	62	35	2
3	60	65	23	2
4	30	65	0	1
5	33	60	0	1
6	34	60	0	1

Table 1: Extracted observations from the Haberman’s Survival dataset

Figure 2: Principal component analysis visualization of the extracted Haberman’s Survival data, with pairwise constraints overlaid. Blue solid lines represent must-link constraints, and red dashed lines represent cannot-link constraints. (a) Initial configuration. (b) Blocks obtained by merging objects connected through must-link constraints. The blocks, indicated by green ellipses, are

B_{1}=\{1,2,3\}

B_{2}=\{4,5,6\}

B_{3}=\{7\}

B_{4}=\{8\}

B_{5}=\{9\}

, and

B_{6}=\{10\}

. (c) Infeasible case.

Dataset ID	$k$	Features	Cluster size
BLOBS-2	2	2	5000/5000
BLOBS-3	3	2	3334/3333/3333
BLOBS-imbalance	2	2	1000/9000
moon-balance	2	2	5000/5000
moon-imbalance	2	2	1000/9000
XY-balance	2	2	5000/5000

Table 2: Datasets used in experiments

Figure 3: Scatter plots of the datasets, color-coded by class

Figure 4: Runtime and Correct Classification Rate (CCR) for the four algorithms (if no assignments are obtained, the corresponding points are omitted)

Number of constraints	2	3	imb	bal	imb	bal	imb	mushroom
	BLOBS			moon		XY
100	50	50	50	50	50	49	50	50
200	50	50	50	45	49	45	50	50
500	50	50	50	18	29	13	44	45
1000	50	50	50	0	7	2	25	23
2000	50	50	50	0	0	0	3	0

Table 3: Success sets of COPK-means (in 50 sets)

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Runtime and Correct Classification Rate (CCR) for BLOBS-imbalance

Figure 6: Runtime for infeasible settings (XY-balance)

	BLOBS-2		BLOBS-3
Number of constraints	Gröbner basis	Optimization	Gröbner basis	Optimization
100	4.08	7.46	4.10	77.57
200	4.10	12.41	4.70	151.72
500	4.16	25.78	7.44	351.86
1000	4.27	49.05	9.19	808.76
2000	6.91	96.25	16.55	7673.87

Appendix

Table 4: Runtime breakdown of the proposed algorithm: Gröbner basis computation and optimization (in seconds)

Figure 7: Runtime and Correct Classification Rate (CCR) for different numbers of initializations

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 342 papers

Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering
Mar 28, 2026Yuxuan Ren, Shijie DengClustering Semi-Supervised Learning
School of Industrial and Systems Engineering Georgia Institute of Technology, USA
Riemannian Difference-of-Convex Optimization for K-Means Clustering
Sep 28, 2026Meng Xu, Bo Jiang, Hanfu Zhang +2Riemannian Optimization Clustering
AMSS, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, Beijing, China · Ministry of Education Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing, China · Ministry of Education Key Laboratory of Mathematics and Information Networks, School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China +1
A Sub-4 Approximation for Fair $k$ -Means
Sep 7, 2026Kangke Cheng, Guanlin Mo, Shihong Song +1Clustering Group Fairness
University of Science and Technology of China, Hefei, China · School of Informatics, University of Edinburgh, Edinburgh, UK

Mar 28, 2026J/K move · Enter open · S save

Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering

Yuxuan Ren, Shijie Deng

School of Industrial and Systems Engineering Georgia Institute of Technology, USA

Clustering Semi-Supervised Learning

Open paper AskPDF arXiv

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. Empirical evaluations demonstrate that the proposed method achieves near-optimal partitions while maintaining high computational efficiency and scalability. The results indicate that Kempe Swap K-Means consistently outperforms state-of-the-art benchmarks in both clustering accuracy and algorithmic efficiency for large-scale datasets.

Abstract

Clustering

Explore similar work

Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering

Riemannian Difference-of-Convex Optimization for K-Means Clustering

A Sub-4 Approximation for Fair kkk-Means

A Sub-4 Approximation for Fair $k$ -Means