A novel method for optimizing spectral rotation embedding K-means with coordinate descent

Lloyd's heuristic K-Means, one of the most widely used clustering methods, plays a vital role in a variety of downstream tasks in machine learning owing to its simplicity. However, Lloyd's heuristic sometimes performs poorly in finding the local minimum and is heavily influenced by the initial points. To address these issues, we propose a novel opti-mization method for the K-Means model. First, we establish that the K-Means minimiza-tion problem can be reformulated as a trace maximization problem, which can be seen as a unified view of spectral clustering. Then, we relax the constraint of the scaled cluster matrix and implement an improved spectral rotation to bring the cluster matrix infinitely close to the binary indicator matrix. To this end, an efficient and redundancy-free coordi-nate descent (CD) method is used to optimize the spectral rotation. Extensive experiments including a hybrid test on several different datasets showed that the proposed algorithm achieved better local objective values compared to Lloyd's heuristic under different initial-ization strategies (random or K-Means++). In the hybrid test, the proposed algorithm could further decrease the convergence value of the objective function obtained by Lloyd's heuristic; conversely, Lloyd's heuristic did not work. Moreover, statistical hypothesis and comparison tests further validated the superiority of the proposed algorithm.(c) 2022 Elsevier Inc. All rights reserved.

Automated summary

In this study, we propose a novel optimization method for the K-Means model that improves the clustering performance by introducing an improved spectral rotation. The experiments demonstrate the effectiveness of the proposed algorithm.