南京大学学报（自然科学版）Issue(4)：772-780,9.DOI:10.13232/j.cnki.jnju.2015.04.015
基于 Markov 随机游走的谱聚类相似图构造方法
Similarity graph construction method based on Markov random walker for spectral clustering
摘要
Abstract
Spectral clustering is a clustering method based on graph theory.Similarity graph constructed on the data is the basis of spectral clustering and is one of the key factors which influence the performance of spectral clustering. The similarity graphs usually contain some error edges,which degrade the performance of spectral clustering. Therefore,how to reduce the error edges in similarity graph is an approach to improve the performance of spectral clustering.Currently,the model of Markov random walker has been widely used to measure the relations.In the paper,a similarity graph construction method is proposed based on Markov random walker for spectral clustering.In the proposed method,a Markov random walker(MRW)is defined on the common k-nearest-neighbors graph,and the high-order transition probabilities of the MRW are adopted to determine the k nearest neighbors.The neighbors in the proposed graph are more reliable because the high-order transition probabilities reflect the more complex relations among data.Experiments were performed on the synthetic and real datasets for performance evaluation and comparison.The results show that the graph obtained by our proposed method can reduce error edges effectively and better reflects the structure of the data compared to those of the state-of-the-art methods.It is also shown that the proposed graph can effectively improve the performance of spectral clustering.关键词
谱聚类/马尔可夫随机游走/近邻图/转移概率矩阵Key words
spectral clustering/Markov random walker/similarity graph/transition probabilities matrix分类
信息技术与安全科学引用本文复制引用
曹江中,陈佩,戴青云,凌永权..基于 Markov 随机游走的谱聚类相似图构造方法[J].南京大学学报（自然科学版）,2015,(4):772-780,9.基金项目
国家自然科学基金(61173083,61372173),中组部国家青年千人计划(400150019),广东省自然科学基金(2014A030310346),广东高校制造业知识产权大数据工程技术研究中心建设项目(501130144) （61173083,61372173）
