An Algebraic Approach to Constrained K-means Clustering

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.

Riemannian Difference-of-Convex Optimization for K-Means Clustering
Meng Xu, Bo Jiang, Hanfu Zhang +2
arXiv28 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Robust K-means Clustering using the Density Power Divergence Measure
Anirban Mondal, Paromita Banerjee, Abhijit Mandal
arXiv30 Aug 2026PreprintCC BY-NC-SA 4.0Full textStatisticsarXiv
Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering
Yordan P. Raykov, Max A. Little
arXiv24 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
Invariant means, coset correct means and the Hahn-Banach Theorem
Armando Martino, Motiejus Valiunas
arXiv28 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Analysis & PDEsarXiv
Mostow-Type Decompositions and Geometric Means for Symmetric Cones
Khalid Koufany, Yongdo Lim
HAL30 Jul 2026PreprintLicence not statedGeneral mathematicsHAL

Cite

BibTeX RIS

BibTeX

@misc{oohori2026algebraic,
  title = {{An Algebraic Approach to Constrained K-means Clustering}},
  author = {Hiroki Oohori and Kentaro Fukushima and Michio Yamamoto},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.14932},
  eprint = {2610.14932},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.14932},
}

RIS

TY  - UNPB
TI  - An Algebraic Approach to Constrained K-means Clustering
AU  - Hiroki Oohori
AU  - Kentaro Fukushima
AU  - Michio Yamamoto
PY  - 2026
DA  - 2026/10/10
PB  - arXiv
DO  - 10.48550/arxiv.2610.14932
UR  - https://arxiv.org/abs/2610.14932
AB  - 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.
ER  -

Abstract

Related

Cite