最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 马尔科夫聚类算法

     聚类算法分为两类:向量聚类和图聚类,而马尔科夫就是属于图聚类算法。

    Random Walks:

    一个图中,如果有好几个聚类,聚类中的线比较密集,而聚类之间的线比较少,那么从一个点开始随机行走,那么我们更可能待在同一个聚类中,所以这就是马尔科夫聚类算法的中心思想:通过Random Walks,我们可以发现流在哪里汇聚,这样我们就可以发现聚类了。Random Walks 是通过“Markov Chains”计算出来的。

    Markov Chains:

    如图,我们可以发现,从节点一,我们有33%的概率到达节点 2,3,4,到达节点5 6 7 的概率为0,同理从节点2出发有25%的概率到达1 3 4 5,根据这样的思想,我们可以得到以下矩阵A:

      然后下一步操作就是

    A*A=D;

    D*A=C;

    C*A….

    直到收敛。

    矩阵A的数值我们还可以根据节点间的距离来改变,通过距离来判断两个节点的亲疏关系,例子如下:

    然后添加自循环(即把a[i,i]的值变为1)。

    MCL

    Expansion

    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收敛矩阵转换为聚簇
    为了找到聚簇,把所有的点分为两类:Attractor,聚集其他点;Vertex,被聚集的点。其中,Attractor所在的行必须至少有一个正值。每个Attractor聚集它所在行上有正值的点。然后,Attractor和被它聚集的点被分到一个聚簇。

    如上图,则分为{1,6,7,10},{2,3,5},{4,8,9,11,12}三个聚簇。一般来说,看行的正值点。
    注意:重叠簇。所谓重叠簇,是指某个点被多个聚簇所共享。

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

    2.6Inflation参数

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 马尔科夫聚类算法

    发表评论

    • 52会员总数(位)
    • 320资源总数(个)
    • 25本周发布(个)
    • 3 今日发布(个)
    • 333稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情