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 optimization method for the K-Means model. First, we establish that the K-Means minimization 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 coordinate 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 initialization 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.