arXiv preprint ·
An Algebraic Approach to Constrained K-means Clustering
- Published
- Source
- arXiv preprint, posted before peer review
- Published in
- arXiv
- DOI
- 10.48550/arxiv.2610.14932
- Original
- Read it at arXiv
- Cited by
- 0 works, as OpenAlex counts them
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Methodology
Copula Active Subspaces II: Error Decomposition, A Posteriori Estimation, and Sharpness of the Bounds
Imperfect Verifiers, Exact Targets: Inference-Time Scaling for Continuous Generation
Exploration strategies for Gaussian process bandit optimization with inference regret guarantees
Two-way Guidance: Simultaneous Learning of Summary Statistics for Generative Bayes
Locally adaptive step sizes for Hamiltonian Monte Carlo methods
Get the few papers worth your time in Methodology every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.