随机游走过程是平稳的吗(基于最短路径的随机游走的图聚类算法)

聚类是最常用的数据分析技术之一，已广泛应用于模式识别、数据挖掘和图像处理。聚类分析是将数据样本分成由相似的对图像组成的组的过程。每组称为一个聚类，每个聚类中数据对图像的相似度较大，而不同聚类中数据对图像的相似度较小。从机器学习的角度来看，搜索聚类是一个无监督学习的过程。大数据图由许多具有实际意义的数据对图像组成，两个数据对图像之间的相似关系可以用转化建模，现实世界中的许多系统都用网络图表示。比如，脸书上的朋友网络、生物学上的蛋白质互质网络、科学家合作网络以及网页之间的超链接都是常见的网络图模型。近年来，图聚类作为一种重要的分析方法，受到越来越多的关注。图聚类[1]主要是将图上的节点划分成一些子图，这样这些节点在类内有很强的联系，而类间的联系很弱。对图聚类不仅有助于可视化和发现层次结构[2]，而且有实际意义，如比如的社区发现[3-4]，离群点检测[5]等。此外，聚类结果也可以用于构建模块，这可以降低一些算法中的图或模块的复杂性[6-7]。谱分析方法已成功应用于解决数据聚类和图划分问题。谱聚类是一种基于图论的聚类分析方法。近年来，由于其高效、易实现和成熟的理论基础，谱聚类受到越来越多的关注，并被广泛应用于图像处理、计算机视觉、数据挖掘、机器学习等领域[8]。其基本思想是利用的的特征向量对的样本数据进行聚类，许多人对谱聚类算法进行了研究，其中经典算法有和弗里曼提出的PF算法、石和马利克提出的SM算法、吴和乔丹提出的算法以及梅拉提出的ms算法。谱聚类克服了传统聚类方法只能在凸球面数据集上工作，容易陷入局部最优解的局限性。它对任意数据集的聚类效果都是理想的，并且能够收敛到全局最优解。

提出了一种新的基于最短路径随机游走(DWSC)的高效图聚类算法。利用基于最短路径的局部随机游走模型，数据点之间的距离为转化作为随机游走的转移概率，相似矩阵由随机游走的转移概率构造。最后，用谱方法得到聚类结果。1相关工作

1.1谱聚类谱聚类算法的思想来源于谱图划分理论，谱聚类将聚类问题转化为无向图的多路径划分问题。谱方法属于基于优化的聚类方法，首次用于解决图的分割问题。谱方法有着坚实的数学理论基础，已经发展成为一种重要的聚类方法。该方法主要利用图的特征分解和拉普拉斯矩阵聚类。常见的图形分割标准如下。

(1)最小割规则[13]给定一个图G，构造它的划分的最简单和直接的方法是求解最小割问题。是定义的，是的补充.给定子集k的数量，对寻求作为最小化目标函数的划分问题：

当k=2时，最小割是一种简单有效的方法。然而，这种方法并不总能得到满意的划分，因为当k值不是2时，划分容易倾斜，即单个顶点从整个图中分离出来。显然，这不是期望的结果，聚类结果应该是由大量点组成的图。(2)比率削减规则[10]

Hagen和Kahng提出了比利割集准则，其中I类节点数为目标函数：比例割集准则通过引入类节点数作为类平衡条件，可以避免最小割集带来的划分倾斜问题，但运行速度较慢。

(3)归一化割准则[14]石和马利克根据谱图理论提出了双向划分的归一化割准则，它是I类中所有顶点的度之和，其目标函数为：

(4)最小最大割准则[15]丁提出了最小最大割准则，它既要求最小化又要求最大化，其目标函数为：

由于相似矩阵的构造函数不同，特征向量矩阵不同，图划分标准不同，谱聚类算法也不同。佩罗娜和弗里曼[9]提出的粒子滤波算法是一种简单的谱聚类算法。对应于相似性矩阵中最大特征值的对的特征向量被用于聚集。对类似于对角矩阵块，对应于量中非零元素对的点属于一个类别，而对应于零元素对的点属于另一个类别。将师和马利克提出的SM算法[10]的目标函数定义为：将放宽到[-1，1]，并根据瑞利熵原理，将目标函数最小化的问题称为第二最小特征值问题。利用特征值计算相应的Fiedler特征向量，并根据启发式规则在向量中找到划分点，使得在该点获得的Ncut(A，b)值最小，Fiedler向量中大于该点值的被归类为一类，而小于该点值的被归类为另一类。该算法的效率明显优于粒子滤波算法。根据Scott等人[16]提出的SLH算法，利用对相似矩阵寻找对应于对，的前k个特征值的特征向量，构造特征向量矩阵V。对v的线矢量被归一化。如果Q(i，j)=1，这意味着顶点I和j属于同一个类。KVV[17]算法使用比例分割准则，并使用菲德勒向量来寻找分割点，就像SM算法一样。该算法能有效避免算法过度倾斜，但运算速度较慢。由于双向划分准则包含的特征向量较少，容易丢失一些有用的信息，算法不稳定。Ng等人提出了一种基于多路径划分准则的NJW算法[11]。该算法选取拉普拉斯矩阵前k个最大特征值对对应的特征向量构造特征向量，并将特征向量的行向量转化为单位向量。将一行矩阵中每作为一个数据点，利用k-means算法或其他简单的聚类算法得到聚类结果。Meila提出了一种基于马尔可夫链随机游走的聚类算法[12]。该算法利用随机游走构造一个相似矩阵，并利用对矩阵寻找前K个特征值对应的特征向量，对矩阵构造一个特征向量矩阵。以矩阵中每线为数据点，利用k-均值算法或其他简单的聚类算法得到聚类结果。

1.2基于最短路径的随机游走模型给出了一个无环无向图，其中和分别表示节点集和边集。在LRW[18]中，一个流浪者根据概率从一个节点游到任何相应的邻居节点。表示节点的度数。这样，可以获得邻接矩阵，即一步转移概率矩阵p。指示从一个节点到另一个节点的概率。如果两个节点直接相连，则值为；否则，它是0。同时，给出了序向量。指示从步骤节点到步骤节点的概率。初始转移向量表示该节点上漫游者的初始概率为1。节点之间的转移概率为

假设每个节点随机行走的步数是彼此之间的最短距离。也就是说，整个网络不必采用统一的最佳步数。此时，假设是从一个节点到另一个节点的概率。是从一个节点到另一个节点的最终概率。定义为节点和之间的最短距离。显然，当的值为零时，节点之间第一次接触的概率为。通过去近似获得的公式(8)是基于最短路径的局部随机行走模型ldrw[19]。其主要特点是将最短路径引入随机行走，并引入基于最短路径的初至概率的概念。

1.3基于随机游走的谱聚类图上的随机游走是一个从一个顶点跳到另一个顶点的随机过程，因此谱聚类的过程可以解释为试图找到一个图的划分，使得随机游走只发生在类内，而类间的对较少。美拉[12]提出移动平均线算法利用马尔可夫链中的随机游走来解释相似性，并计算转移概率矩阵的特征向量来构造聚类的向量空间。主要步骤如下：

(1)根据数据集构造相似性矩阵s和对角矩阵d；(2)计算转移概率矩阵；

(3)计算p的前几个特征值的对对应的特征向量，构造矩阵u；(4)将矩阵E中的每一行视为空间中的一个数据点，用k-means或其他经典的聚类算法对其进行聚类得到结果。

算法描述2本文提出的基于最短路径随机游走的图聚类算法(DWSC)通过节点间最短路径的随机游走构造相似矩阵，利用相似矩阵构造转移概率矩阵，并对其进行对特征分解，取对，前k个特征值的特征向量，对对n * k维的特征向量进行k均值运算，得到聚类结果。

2.1问题定义本文定义了一个无向图，其中顶点集是图的边集。相似性矩阵相似性，其中。对角矩阵对角线，其中。概率矩阵概率，其中对于矩阵概率的任何一行都有。

2.2实验步骤输入：无向图和聚类数；

(1)计算图的顶点之间的最短距离，构造距离矩阵距离；(2)利用LWRD算法计算顶点相似矩阵的相似度；

(3)计算对角矩阵对角线；(4)计算转移概率矩阵的概率；

(5)利用对概率进行特征分解，去除前k个特征值对对应的特征向量；(6)构造一个矩阵，其中它是中的第一列；

(7)将每一行特征视为一个顶点，用k-means对对的N个点进行聚类得到结果。