• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Spectral Clustering with Sparse Graph Construction Based on Markov Random Walk

Vol. 9, No.7, July 31, 2015
10.3837/tiis.2015.07.013, Download Paper (Free):

Abstract

Spectral clustering has become one of the most popular clustering approaches in recent years. Similarity graph constructed on the data is one of the key factors that influence the performance of spectral clustering. However, the similarity graphs constructed by existing methods usually contain some unreliable edges. To construct reliable similarity graph for spectral clustering, an efficient method based on Markov random walk (MRW) is proposed in this paper. In the proposed method, the MRW model is defined on the raw k-NN graph and the neighbors of each sample are determined by the probability of the MRW. Since the high order transition probabilities carry complex relationships among data, the neighbors in the graph determined by our proposed method are more reliable than those of the existing methods. Experiments are performed on the synthetic and real-world datasets for performance evaluation and comparison. The results show that the graph obtained by our proposed method reflects the structure of the data better than those of the state-of-the-art methods and can effectively improve the performance of spectral clustering.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Jiangzhong Cao, Pei Chen, Bingo Wing-Kuen Ling, Zhijing Yang and Qingyun Dai, "Spectral Clustering with Sparse Graph Construction Based on Markov Random Walk," KSII Transactions on Internet and Information Systems, vol. 9, no. 7, pp. 2568-2584, 2015. DOI: 10.3837/tiis.2015.07.013

[ACM Style]
Cao, J., Chen, P., Ling, B. W., Yang, Z., and Dai, Q. 2015. Spectral Clustering with Sparse Graph Construction Based on Markov Random Walk. KSII Transactions on Internet and Information Systems, 9, 7, (2015), 2568-2584. DOI: 10.3837/tiis.2015.07.013