马尔可夫聚类算法（MCL）

港控/mmm° 2022-08-18 02:18 303阅读 0赞

# 1.基础 #

## 1.1Random Walks ##

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

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

## 1.2马尔可夫链（Markov Chain） ##

先看一个简单的例子：

![Center][]

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

![Center 1][]

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

![Center 2][]

然后，进行一下操作：

![Center 3][]

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

## 1.3加权图 ##

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

![Center 4][]

然后，进行列的标准化：

![Center 5][]

**注意：它不是对称的。**

# 2.MCL #

## 2.1Expansion ##

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

![Center 6][]

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

## 2.2Inflation ##

同样，先看例子：

![Center 7][]

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

![Center 8][]

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

## 2.3算法 ##

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

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

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

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

## 2.4算法实现 ##

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

import numpy as np
    
    def 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 = probabilityMat
            for i in range(power - 1):
                expandMat = np.dot(expandMat, probabilityMat)
            return expandMat
        expandMat = _expand(probabilityMat, power)
        
        #Inflate by taking inflation of the resulting 
        #matrix with parameter inflation. 
        def _inflate(expandMat, inflation):
            powerMat = expandMat
            for i in range(inflation - 1):
                powerMat = powerMat * expandMat
            inflateColumnSum = np.sum(powerMat, axis = 0)
            inflateMat = powerMat / inflateColumnSum
            return inflateMat
        inflateMat = _inflate(expandMat, inflation)
        
        for i in range(numIter):
            expand = _expand(inflateMat, power)
            inflateMat = _inflate(expand, inflation)
        print(inflateMat)
        
        
    if __name__ == "__main__":
        dimension = 4
        numIter = 2
        adjacencyMat = np.array([[1, 1, 1, 1],
                                 [1, 1, 0, 1],
                                 [1, 0, 1, 0],
                                 [1, 1, 0, 1]])
        markovCluster(adjacencyMat, dimension, numIter)

## 2.5收敛矩阵转换为聚簇 ##

为了找到聚簇，把所有的点分为两类：Attractor，聚集其他点；Vertex，被聚集的点。其中，Attractor所在的行必须至少有一个正值。每个Attractor聚集它所在行上有正值的点。然后，Attractor和被它聚集的点被分到一个聚簇。

![Center 9][]

如上图，则分为\{1,6,7,10\}，\{2,3,5\}，\{4,8,9,11,12\}三个聚簇。  
**一般来说，看行的正值点。**  
**注意：重叠簇**。所谓重叠簇，是指某个点被多个聚簇所共享。一般而言，重叠簇仅发生在特殊的对称图中：

*  当且仅当某些点等概率的分配到多个聚簇；
 *  当且仅当簇与簇是同构的。

![Center 10][]

## 2.6Inflation参数 ##

前面提到了Inflation参数会影响聚簇的粒度。下面有一组图进行说明，其中a是自循环的权值。

![Center 11][]

我把更详细的MLC英文原始文档放在：[http://download.csdn.net/detail/u010376788/9328693][http_download.csdn.net_detail_u010376788_9328693]，结合起来看效果会更好。

[Center]: /images/20220731/1b546e7b365848ae86ce07b58c0703e0.png
[Center 1]: /images/20220731/05d016250dfa4f648996e93d4bd00847.png
[Center 2]: /images/20220731/382a6b11d0a84c7caad8d3954068cb5b.png
[Center 3]: /images/20220731/7995081b53ae4ae59bc55d5c52196b9c.png
[Center 4]: /images/20220731/d75bc0d2f8a44aa5b7cf38ec6bd6ecdc.png
[Center 5]: /images/20220731/eccea78565e543dc92ff6e0ad79e2a13.png
[Center 6]: /images/20220731/df7219618b1449e89e0f03a8010dfab7.png
[Center 7]: /images/20220731/42bfe3e894a3481a9dc738d97aeb7342.png
[Center 8]: /images/20220731/fec294f65f684e5d85474ef83b973563.png
[Center 9]: /images/20220731/0908e499466740f981418f8d5db2b4f9.png
[Center 10]: /images/20220731/96a953e5f97944178c5f4a4c522acd7a.png
[Center 11]: /images/20220731/92d0fe73356a4664bc368c254279a2e9.png
[http_download.csdn.net_detail_u010376788_9328693]: http://download.csdn.net/detail/u010376788/9328693