Entropy Regularized Power k-Means Clustering
This work addresses a fundamental limitation in clustering algorithms for data analysis, offering a theoretically justified and scalable solution that is incremental over prior power k-means.
The paper tackles the problem of k-means clustering getting stuck in local minima and failing in high dimensions by introducing entropy regularization to learn feature relevance during annealing, resulting in significant improvements over existing methods while maintaining computational efficiency.
Despite its well-known shortcomings, $k$-means remains one of the most widely used approaches to data clustering. Current research continues to tackle its flaws while attempting to preserve its simplicity. Recently, the \textit{power $k$-means} algorithm was proposed to avoid trapping in local minima by annealing through a family of smoother surfaces. However, the approach lacks theoretical justification and fails in high dimensions when many features are irrelevant. This paper addresses these issues by introducing \textit{entropy regularization} to learn feature relevance while annealing. We prove consistency of the proposed approach and derive a scalable majorization-minimization algorithm that enjoys closed-form updates and convergence guarantees. In particular, our method retains the same computational complexity of $k$-means and power $k$-means, but yields significant improvements over both. Its merits are thoroughly assessed on a suite of real and synthetic data experiments.