谱聚类算法_马尔科夫聚类算法

由于作者是就声纹领域的说话人分割聚类这一子方向，结合社交网络中的马尔可夫聚类算法对谱聚类算法进行改进优化，以个人陈述的形式和大家分享一些小的想法，如果有逻辑或是理论上的错误，请阅读者评论指正，相互学习。

目录

1.谱聚类算法

1.1 图谱理论

1.1.1 图谱

以点和边构成类似于蛛网的网络，其中边是根据点之间关系而确定是否存在，可以利用方阵的形式来描述各个点之间的关系，即方阵，其中方阵作为线性算子，它的所有特征值的全体统称为方阵的谱，方阵的谱半径为最大的特征值。

1.1.2 无向权重图

对于一个图G，我们一般描述为G(V,E)。V为点集，E为边集。对于V中的任意两个点，可以有边连接，也可以没有边连接。我们定义权重wij为点vi和点vj之间的权重，且wij=wji。对于有边连接的两个点，wij>0；对于没有边连接的两个点，wij=0。对于图中的任意一个点vi，它的度di定义为 与它相连的所有边的权重之和，即：

利用每个点的度的定义，得到一个n×n的对角矩阵，n为数据集的点的数目。主对角线有值，对应第i行的第i个点的度数。

利用边的权重值，也可以得到一个n×n的矩阵W，第i行的第j个值对应我们的权重wij。

1.1.3 相似矩阵

对于构建相似矩阵，一般传统的做法是直接根据欧氏距离来获得对称矩阵，而针对谱聚类算法一般是直接通过余弦相似度来从角度来度量样本点的相似程度。但是真实的理论中是对权重矩阵定义了三种计算方法：
第一种：ϵ-邻近法，它设置了一个距离阈值ϵ，然后用欧式距离计算任意两点xi和xj的距离。也就是通过一个中间阈值来判定两点之间是否存在权重信息，如果没有，则为0，这样的定义有些草率。公式如下：

第二种：K邻近法。K邻近法，利用KNN算法遍历所有的样本点，取每个样本点最近的k个点作为近邻，只有这k个点的wij>0。但是这种方法会造成邻接矩阵W非对称（因为点i作为样本点，j是它k个近邻点中的一个；相反，i未必是样本点j的k个近邻中的一个），但后面的算法是需要对称的邻接矩阵。所以可以采取下面两种方法：

• 只要一个点在另一个点的k近邻中，则保留sij，公式如下：
  
• 只有两个点相互在各自的k近邻中，才保留siji，公式如下：
  

第三种：全连接法。相比前两种方法，第三种方法所有的点之间的权重值都大于0，因此称之为全连接法。可以选择不同的核函数来定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。最常用的是高斯核函数RBF，此时相似矩阵和邻接矩阵相同，公式如下：

其实我发现很多实验算法中已经将权重矩阵和相似矩阵看作一个东西，都是通过余弦相似度来求取。

1.1.4 拉普拉斯矩阵

拉普拉斯矩阵L=D−W，D即为我们第二节讲的度矩阵，它是一个对角矩阵。而W即为我们第二节讲的邻接矩阵，它可以由我们第三节的方法构建出。拉普拉斯矩阵有一些很好的性质如下：

• 拉普拉斯矩阵是对称矩阵，这可以由D和W都是对称矩阵而得。
• 由于拉普拉斯矩阵是对称矩阵，则它的所有的特征值都是实数。
• 对于任意的向量f,我们有
  对其推导如下：
• 拉普拉斯矩阵是半正定的，且对应的n个实数特征值都大于等于0，即0=λ1≤λ2≤…≤λn，且最小的特征值为0，这个由性质3很容易得出。

1.1.5 无向图切图

对于无向图G的切图，我们的目标是将图G(V,E)切成相互没有连接的k个子图，每个子图点的集合为：A1,A2,…Ak，它们满足Ai∩Aj=∅, 且A1∪A2∪…∪Ak=V.对于任意两个子图点的集合A,B，我们定义A和B之间的切图权重为：（对于所有点i∈A，j∈B，累加权重）

对于我们k个子图点的集合：A1,A2,…Ak，我们定义切图cut为：（即对每个子图，计算其余所有子图与其之间的权重，算了两遍，所以除以2）

那么如何切图可以让子图内的点权重和高，子图间的点权重和低呢？一个自然的想法就是最小化cut(A1,A2,…Ak)，但是可以发现，这种极小化的切图存在问题，如下图：

1.1.6 切图

（此部分请读者查看其余资料，本文重点不在切图上，因此不在这里叙述）

1.2 谱聚类算法的简单描述

谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。谱聚类可以理解为将高维空间的数据映射到低维，然后在低维空间用其它聚类算法（如KMeans）进行聚类。
谱聚类算法的伪代码如下：

上面就是未标准化的谱聚类算法的描述。也就是先根据样本点计算相似度矩阵，然后计算度矩阵和拉普拉斯矩阵，接着计算拉普拉斯矩阵前k个特征值对应的特征向量，最后将这k个特征值对应的特征向量组成n*k的矩阵U，U的每一行成为一个新生成的样本点，对这些新生成的样本点进行k-means聚类，聚成k类，最后输出聚类的结果。这就是谱聚类算法的基本思想。相比较PCA降维中取前k大的特征值对应的特征向量，这里取得是前k小的特征值对应的特征向量。

1.3 谱聚类算法的优缺点

• 优点：只需要相似度矩阵，方便处理稀疏数据的聚类；使用了降维，处理高维数据效果比传统聚类方法好。
• 缺点：如果降维的幅度不够，效果和效率均不够好；严重依赖于相似度矩阵。同时传统谱聚类算法中通过余弦相似度来构建相似矩阵，没有完全描述数据样本之间的关系；此外该算法的复杂度很大，运行时间较慢。

2. 马尔可夫聚类算法

2.1 马尔可夫链概念

这里我们简单介绍一下马尔可夫链的概念，马尔科夫链是一种非常常见的统计随机过程，从文本到金融建模，都得到不错的应用价值，主要是由于马尔可夫链直观却容易理解，可以和很多算法进行结合来对实际数据进行建模操作。
以一个实际例子来介绍马尔可夫链。
假设有两种可能的天气状态：晴天或阴天，你随时都可以观测当前的天气状态且状态限定为晴天或阴天。现在你想预测明天的天气情况，你本能的会认为当天的天气会对明天的天气有一定的影响，因此，拥有智慧和才貌的你会收集并分析过去几年的天气数据，发现了一个规律——当天是阴天第二天是晴天的概率为0.25，由于天气限定为晴天或阴天，那么当天是阴天第二天也是阴天的概率为0.75。因此你可以基于当前的天气状态去预测未来几天的天气。
这一例子阐述了马尔科夫链的关键概念：马尔科夫链本质上是由满足马尔科夫性质的转移概率分布组成，下图为天气例子的转移概率：

马尔科夫的性质在于它的无记忆性，下一时刻的状态只与当前的状态相关。用数学公式描述为：

这个例子介绍了如何仅通过观察当天到下一天的转移来获得概率分布，这说明了马尔科夫的性质在于它的无记忆性。
马尔科夫的无记忆性通常使它们无法成功预测某些潜在会发生的趋势，比如马尔科夫链可能根据词频模仿作者的写作风格，但它无法产生具有深刻主题意义的文本，因为这种主题是基于更长的文本序列产生的，马尔科夫链只考虑当前的状态，不考虑之前状态的信息。

2.2 马尔可夫聚类算法

马尔可夫聚类算法是基于马尔可夫链的思想来构思，通过不断迭代随机游走状态下的概率转移矩阵，来改变状态矩阵中各个元素之间的紧凑关系，知道随机游走到指定的收敛状态，这也就是马尔可夫聚类中的扩展操作，具体过程如下：

• 扩展(Expansion)操作：通过状态概率矩阵行和列相乘实现各个元素之间的“随机游走”，不断迭代以达到状态稳定。
• 膨胀(Inflation)操作：主要是解决Expansion概率趋于同向的问题，具体的解释如下：
• 

马尔可夫聚类算法其实就是Expansion和Inflation交替进行的一种算法，Expansion操作负责将子图中的点联系更加紧凑，而Inflation则是不断弱化各点之间的联系，这样经过不断地迭代，使得矩阵中出现“聚集”现象，从而到达提前聚类的目的。

3.基于马尔可夫聚类的谱聚类算法（带有牵引因子）

3.1 算法介绍

其实这里用马尔可夫聚类算法就是对谱聚类中的相似矩阵进行“先聚类”，首先将相似矩阵转换为初始概率矩阵，然后通过扩展操作和膨胀操作不断迭代相似概率矩阵，知道矩阵的元素相对不在变化为止，紧接着就是谱聚类算法的步骤。

3.2 Traction牵引因子

马尔可夫聚类算法将相似矩阵中的相似度转换为概率值，通过Expansion和Inflation两个步骤交替进行，来强化相似矩阵中紧密的点，弱化了松散的点， 从而达到“聚集”的目的，但是Inflation中的幂次方使概率大小不一的点“强者越强，弱者越弱”，必然会让相似矩阵出现一个极端：原本不归属A类的点最后因为概率值的迭代不断增大，迫使其属于了A类，相反，原本归属B类的点最后不属于B类。考虑到马尔可夫链当前状态只由前一个状态决定，而对于聚类任务，初始状态的信息至关重要，因为初始样点的位置信息表明其归属类别的大致方向，基于此，本节提出一个新的概念：Traction牵引因子，公式如下：

以初始概率矩阵 与前端游走的状态概率矩阵 作为牵引来规范制约当前状态的概率信息，防止其游走到“错类”。（这里只给出一个概念，算是一个小想法吧！）

3.3 优化后的谱聚类算法