基于最短路径的随机游走的图聚类算法.docVIP

基于最短路径的随机游走的图聚类算法 　　摘要：现实世界中的许多系统都以网络图形式存在，并且近年来图聚类作为一种重要的分析手段已经得到越来越多的关注。在众多图聚类算法中，谱图聚类算法以其高效性、易于实现以及坚实的理论基础等特性已经得到越来越多的关注。本文提出一种基于最短路径的随机游走的谱图聚类算法。该算法利用基于最短路径的局部随机游走模型将数据点之间的距离转化为随机游走的转移概率，通过随机游走的转移概率构造相似矩阵，最后利用谱方法得到聚类结果。实验结果表明，使用本文所提出的聚类方法可以有效提高聚类效果。 　　关键字：随机游走；图聚类；最短距离；谱聚类 　　中图分类号：TP311文献标识码：A文章编号：2095-2163（2015）06- 　　Abstract：There are many systems exiting in the form of network in the real world. And the graph clustering as an important analysis method has gained more and more attention in recent years. The spectral graph clustering algorithm is more popular because of its high efficiency， easy to implement and solid theory foundation. This paper proposes a Graph Clustering Algorithm based on Random Walk Model of the Shortest Path. This algorithm uses the random walk model based on the shortest path to transfer the distance between two data points to the transition probability， and structures the similarity matrix by the transition probability. Then the paper gets the result by using the spectral clustering algorithm. The experimental results show that using the presented clustering method can effectively improve the clustering effect. 　　Keywords： Random Walk； Graph Clustering； Shortest Distance； Spectral Clustering 　　0引言 　　聚类是最常用的数据分析技术之一，已经被广泛地应用到模式识别、数据挖掘和图像处理等领域。聚类分析是一个将数据样本划分为由相似对象组成的分组的过程。每一个组称为一个簇，每个簇中的数据对象的相似度大，而不同簇中的对象相似度小。从机器学习的角度来看，有哪些信誉好的足球投注网站簇就是一个无监督学习的过程。大数据图有很多内部具有实际意义的数据对象组成，两个数据对象间的相似关系可以转化成图模型。现实世界中的许多系统都是由网络图形来进行表示的，比如Facebook上的朋友关系网、生物上的蛋白质互质网络、科学家合著网络以及网页之间的超链接都是常见的网络图模型。近年来图聚类作为一种重要的分析手段已经得到越来越多的关注。图聚类[1]主要是将图上的节点划分为一些子图，使得这些节点在类内具有较强的连接而类间的连接则相对较弱。图聚类不仅有助于可视化和发现层次结构[2]，还具有实际的意义，比如社区发现[3-4]、孤立点检测[5]等，此外聚类的结果也可以用来构建模块，使得在一些算法中可以降低图或模块的复杂度[6-7]。 　　谱分析方法已经成功地运用在解决数据聚类和图划分的问题方面。谱聚类是一种基于图论的聚类分析方法，近几年，由于谱聚类的高效性、易于实现以及成熟的理论基础等特性已经得到越来越多的关注，并被广泛应用在图像处理、计算机视觉、数据挖掘、机器学习等领域[8]。其基本思想是通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。关于谱聚类算法已经有很多人做了研究，其中经典的算法有Perona和Freeman提出的PF算法[9]、Shi和Malik提出的SM算法[10]、Ng和Jordan等人提出的NJW算法[11]以及Meila提出的MS算法[12]等。谱聚类克服了传统聚类方法仅