Structured sparse K-means clustering via Laplacian smoothing

We propose a structured sparse K-means clustering algorithm that learns the cluster assignments and feature weights simultaneously. Compared to previous approaches, including K-means in MacQueen [28] and sparse K-means in Witten and Tibshirani [46], our method exploits the correlation information among features via the Laplacian smoothing technique, so as to achieve superior clustering accuracy. At the same time, the relevant features learned by our method are more structured, hence have better interpretability. The practical benefits of our method are demonstrated through extensive experiments on gene expression data and face images.