Locality-preserving L1-graph and its application in clustering
Shuchu Han, Hao Huang, Hong Ying Qin, Dantong Yu · 2015
Constructing a good graph to represent data structures is critical for many important machine learning tasks such as clustering and classification. Recently, a nonparameteric graph construction method called L1-graph is proposed with claimed advantages on sparsity, robustness to data noise and datum-adaptive neighborhood. However, it suffers a lot from the loss of locality and the instability of performance. In this paper, we propose a Locality-Preserving L1- graph (LOP-L1), which preserves higher local-connections and at the same time maintains sparsity. Besides, compared with L1-graph and the succeeding regularization-based techniques, our LOP-L1 requires less amount of running time in the scalability test. We evaluate the effectiveness of LOP-L1 by applying it to clustering application, which confirms that the proposed algorithm outperforms related methods.