马尔可夫聚类算法（MCL）

本文主要是介绍马尔可夫聚类算法（MCL），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.基础

1.1Random Walks

在图中，通过Random Walks处理，可以找到数据在哪里聚集，或者聚簇在哪。

图中的Random Walks是使用马尔可夫链计算求出。

1.2马尔可夫链（Markov Chain）

先看一个简单的例子：

第一步，结点1的Random Walker有33%的概率到达结点2、3和4，且有0%的概率到达结点5、6和7。
对于结点2，有25%的概率到达结点1、3、4和5，且有0%的概率到达6和7。
由此可以得到一个过渡矩阵（transition matrix）或者称为概率矩阵（probability matrix）：

注意：矩阵的每一列之和是1。
再看一个简单的例子：

然后，进行一下操作：

到此，Markov Chain的定义可以描述为：
Markov Chain指变量X1、X2、X3等的一个状态序列（在上述的例子中，是一个概率矩阵），它给出当前状态、历史状态和未来状态，并且状态之间彼此独立。
每一步的概率仅仅依赖于当前的概率。一个Random Walk是一个使用过渡概率矩阵的Markov Chain的例子。

1.3加权图

对于加权图而言，要转换成概率矩阵，需要进行列的标准化（即每个值除以所在列的所有值之和）。
看一个简单的例子：

然后，进行列的标准化：

注意：它不是对称的。

2.MCL

2.1Expansion

但是，上面的例子有一个问题。就是对于奇数长度的简单，进行奇数次幂的扩大获得的值有很大的影响。同样，对于偶数也有影响。
要解决这个问题，需要对每个节点添加一条自循环的边。通过添加一条长度为1的路径，在计算矩阵的奇数次幂时，这个问题就不在发生。

而对于Markov Chain求幂的运算就称为“Expansion”。

2.2Inflation

同样，先看例子：

上面的变换，即求Inflation的平方运算。由此可以看出，Inflation操作就是：求矩阵中每个元素的n次幂，然后求出的结果除以所在列的所有元素之和。
标准的定义是这样的：

Inflation操作的职责是增大或减小当前概率（增大当前大概率，减小当前小概率）。同时，Inflation的参数r影响聚簇的粒度。

2.3算法

在MCL中，下面两个处理过程交替的重复执行：

Expansion（计算Markov Chain过渡矩阵的幂）
Inflation

Expansion操作的职责是让流连接图的不同区域。
Inflation操作的职责是同时增大和减小当前概率。
算法实现步骤：

输入一个无向图，Expansion的幂e和Inflation的参数r，
创建邻接矩阵，
对每个结点添加自循环（可选的），
标准化矩阵（每个元素除以所在列的所有元素之和），
计算矩阵的第e次幂，
用参数r对求得的矩阵进行Inflation处理，
重复第5步和第6步，直到状态稳定不变（收敛），
把最终结果矩阵转换成聚簇。

2.4算法实现

在进行大数据处理的时候，我们可以根据上一次和下一次结果矩阵是否相等来停止运算，但更常见更易操作的方法是采用迭代次数来控制。（另外，由于Python Numpy的矩阵没有四舍五入或进1制，用all()方法比较就不太理想，所以代码采用迭代方式）。如下：

import numpy as npdef markovCluster(adjacencyMat, dimension, numIter, power = 2, inflation = 2):columnSum = np.sum(adjacencyMat, axis = 0)probabilityMat = adjacencyMat / columnSum#Expand by taking the e^th power of the matrix.def _expand(probabilityMat, power):expandMat = probabilityMatfor i in range(power - 1):expandMat = np.dot(expandMat, probabilityMat)return expandMatexpandMat = _expand(probabilityMat, power)#Inflate by taking inflation of the resulting #matrix with parameter inflation. def _inflate(expandMat, inflation):powerMat = expandMatfor i in range(inflation - 1):powerMat = powerMat * expandMatinflateColumnSum = np.sum(powerMat, axis = 0)inflateMat = powerMat / inflateColumnSumreturn inflateMatinflateMat = _inflate(expandMat, inflation)for i in range(numIter):expand = _expand(inflateMat, power)inflateMat = _inflate(expand, inflation)print(inflateMat)if __name__ == "__main__":dimension = 4numIter = 2adjacencyMat = np.array([[1, 1, 1, 1],[1, 1, 0, 1],[1, 0, 1, 0],[1, 1, 0, 1]])markovCluster(adjacencyMat, dimension, numIter)