K-means clustering improved by new geometry based optimization method
Riemannian Difference-of-Convex Optimization for K-Means Clustering
Machine Learning
Summary
K-means is a common way for computers to group similar data points, but it can be hard to solve well when there are many groups. The authors study a new way to solve K-means by looking at it as a problem on curved spaces and using a special penalty method for constraints. They create a new algorithm called RADA-DC that tries to find good solutions efficiently, and they show it works better than popular methods like K-means++ on some tests. This approach is especially helpful when clustering many groups at once.
What this means in practice
- •For machine learning engineers: Cluster large datasets into many groups more accurately by using the proposed RADA-DC method.
- •For signal processing teams: Improve signal classification tasks by applying the new clustering algorithm to better group signal data points.
Authors
Meng Xu, Bo Jiang, Hanfu Zhang, Ya-Feng Liu, Anthony Man-Cho So
Abstract
K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an $ε$-Riemannian critical point within $O(ε^{-3})$ iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.