[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]

Journal of Information Science and Engineering, Vol. 34 No. 1, pp. 289-305

Locality Sensitive K-means Clustering

1Department of Industrial Engineering and Management
2Department of Computer Science
National Chiao Tung University
Hsinchu, 300 Taiwan

3Department of Computer Science and Information Engineering
National Kaohsiung University of Applied Sciences
Kaohsiung, 807 Taiwan 

    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.

Keywords: unsupervised learning, clustering, locality sensitive clustering, dimensionality reduction, linear transformation

  Retrieve PDF document (JISE_201801_17.pdf)