Robust Self-Tuning Sparse Subspace Clustering

Sparse subspace clustering (SSC) is an effective approach to cluster high-dimensional data. However, how to adaptively select the number of clusters/eigenvectors for different data sets, especially when the data are corrupted by noise, is a big challenge in SSC and also an open problem in field of data mining. In this paper, considering the fact that the eigenvectors are robust to noise, we develop a self-adaptive search method to select cluster number for SSC by exploiting the cluster-separation information from eigenvectors. Our method solves the problem by identifying the cluster centers over eigenvectors. We first design a new density based metric, called centrality coefficient gap, to measure such separation information, and estimate the cluster centers by maximizing the gap. After getting the cluster centers, it is straightforward to group the remaining points into respective clusters which contain their nearest neighbors with higher density. This leads to a new clustering algorithm in which the final randomly initialized k-means stage in traditional SSC is eliminated. We theoretically verify the correctness of the proposed method on noise-free data. Extensive experiments on synthetic and real-world data corrupted by noise demonstrate the robustness and effectiveness of the proposed method comparing to the well-established competitors.