PCA-guided search for K-means

• Based on the relationship between PCA and K-means we propose a novel initialization method for K-means clustering.
• The initialization method has two steps and is easy to implement.
• We compare the proposed method with previous standard methods.
• The proposed method is effective and always provides the best solution.

K-means is undoubtedly the most widely used partitional clustering algorithm. Unfortunately, due to the non-convexity of the model formulations, expectation-maximization (EM) type algorithms converge to different local optima with different initializations. Recent discoveries have identified that the global solution of K-means cluster centroids lies in the principal component analysis (PCA) subspace. Based on this insight, we propose PCA-guided effective search for K-means. Because the PCA subspace is much smaller than the original space, searching in the PCA subspace is both more effective and efficient. Extensive experiments on four real world data sets and systematic comparison with previous algorithms demonstrate that our proposed method outperforms the rest as it makes the K-means more effective.