[关闭]
@chanvee 2014-06-18T12:28:45.000000Z 字数 1152 阅读 7347

The Markov Cluster Algorithm (MCL)

算法


MCL算法是一种快速可扩展的无监督聚类算法,它的思想非常简单,其核心包括两个内容:ExpansionInflation

算法基础


这个算法的基础是 随机游走马尔科夫链

随机游走 它是基于这样一个假设:当我们在划分社团的时候,我们会发现社团内部节点的连边会比较多,而社团与社团之间的连边相对较少。基于这个假设,假设我们从图中的某一个点开始“瞎转”,那么我们很可能就会在某一个社团里面转悠,而不是在社团间来回游荡,而随机游走的计算是通过马尔科夫链来实现的。

马尔科夫链 指的是给定一个随机序列,将来的状态只与现在的状态有关,而与过去的状态无关,满足这样的性质的离散序列就成为马尔科夫链,这也就是大名鼎鼎的马尔科夫“无后效性”,也就是说不管我以前犯了多少错做了多少坏事,只有我现在认真改正,好好学习,天天向上,将来还是有机会迎娶白富美,当上CEO,走向人生巅峰的。

算法核心


Expansion 这个步骤其实就是求前面提到的马尔科夫链的转移矩阵的极限分布。转移矩阵表示的就是在初识状态下,某个节点转移到另一个节点的概率所组成的矩阵。这里举一个例子,比如一个图中有1,2,3这3个节点,他们之间两两互相连接,不考虑权重,那么这个时候它的转系矩阵就是P=[0 0.5 0.5; 0.5 0 0.5; 0.5 0.5 0]了。而 expansion 这个步骤不断地对这个转移矩阵进行自乘直到它不再改变为止,这也就是求平稳分布的过程。而expansion的作用就是为了能够将图中不同的区域连接起来。

Infaltion 的思想也很简单。首先,我们先说inflation的目的是什么,它的目的是为了强邻居的连接更强,弱邻居的连接更弱,也就是让转系矩阵中概率大的概率更大,而小的更小。一种最直观的操作就是进行幂操作!比若说我对概率矩阵进行平方操作,(需要注意的是,这个操作与expansion的不同之处在于expansion是矩阵的乘法,而这里是分别对矩阵中的每一个元素进行平方操作),然后我们在将每一列归一化,这样就达到了上述目的。

算法流程


有了上述的算法基础和核心内容,我们就可以很轻松的给出MCL算法的流程步骤:

  1. 给定一个无向图(有权无权都可),以及expansion 和 inflation 的参数 e 和 r。
  2. 生成连接矩阵。
  3. 给每个节点添加自环(可选)。
  4. 归一化矩阵,得到转移矩阵。
  5. 对矩阵进行 expansion 操作。
  6. 对矩阵进行 inflation 操作。
  7. 重复 5 和 6 直至收敛。
  8. 根据最后得到的矩阵进行划分cluster。

参考文献


[1] PDF
[2] http://micans.org/mcl/
[3] Markdown原稿

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注