Locality Sensitive K-means Clustering

Abstract

This study considers clustering and dimensionality reduction simultaneously to devise an unsupervised clustering algorithm called locality sensitive K-means (LS-K means). The goal is to find a linear transformation to project data points into a lower dimensional space, so that clustering can perform well in the new space. We design a novel objective function for LS-Kmeans to achieve the goal, and further show that the proposed method can be reformulated as a matrix trace minimization with constraints problem. The original optimization problem becomes a generalized eigenvalue problem when relaxing the optimization problem of LS-Kmeans by allowing the indicator entries to take arbitrary values in R. This paper also shows that the continuous solutions for the transformed cluster membership indicator vectors of LS-Kmeans are located in the subspace spanned by the first K-1 eigenvectors. In the experiments, we use two synthetic datasets to show that the proposed method can cluster non-linearly separable data points. Besides, the experimental results of eight real datasets indicate that the proposed algorithm can generally outperform other alternatives.