Locality Sensitive K-means Clustering

Chien-Liang Liu, Wen Hoar Hsaio, Tao Hsing Chang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This study considers clustering and dimensionality reduction simultaneously to devise an unsupervised clustering algorithm called locality sensitive K-means (LS-Kmeans). 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 . 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 K1 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.

Original languageEnglish
Pages (from-to)289-305
Number of pages17
JournalJournal of Information Science and Engineering
Issue number1
StatePublished - 1 Jan 2018


  • Clustering
  • Dimensionality reduction
  • Linear transformation
  • Locality sensitive clustering
  • Unsupervised learning


Dive into the research topics of 'Locality Sensitive K-means Clustering'. Together they form a unique fingerprint.

Cite this