数据挖掘知识

免费体验
当前位置: 首页 > 知识库 > 数据挖掘知识 >

聚类算法实践(3)——PCCA、SOM、Affinity Propagation

分享到:
时间:2013-10-14 22:09来源:谷歌推广seo网络知识 作者:谷歌优化怎么做
这篇日志是这个系列里算法部分的最后一篇,关注的是几个相对另类一点的聚类算法:PCCA、SOM和Affinity Propagation。PCCA是设计来专门用于马尔科夫模型的一种聚类算法;SOM是基于神经网络模型的自组织聚类。

      这篇日志是这个系列里算法部分的最后一篇,关注的是几个相对另类一点的聚类算法:PCCA、SOM和Affinity Propagation。PCCA是设计来专门用于马尔科夫模型的一种聚类算法;SOM是基于神经网络模型的自组织聚类;最后的Affinity Propagation则是在07年才在Science发表的一种较新颖的算法。

6、PCCA

      PCCA算法的全称是Perron Cluster Cluster Analysis,名称里有两个cluster是因为这样简写就可以和PCA区分开来(无语……)。PCCA并不是设计来处理传统的聚类问题的,而是专门用于得到马尔科夫链中的cluster。当然,对于一般的聚类问题,只要根据系统特点构造出一个概率转移矩阵,也可以使用PCCA算法。

       要解释马尔科夫模型中的cluster,让我们想象有一只跳蚤在了数据点间跳跃转移。它下一个时刻跳到特定数据点上的概率,只跟它当前落在哪个数据点上有关,这显然是一个经典的马尔可夫过程。再让我们假定,跳蚤在点与点之间的跃迁概率跟数据点的“距离”成反比。如果数据点可以分成几个分界明显的cluster,跳蚤大多数时间就只会在某个cluster内部的数据点间转移,在cluster之间的跳跃则相对罕见。

       先解释一下马尔科夫模型的一些性质。马尔科夫模型需要的是一个转移矩阵A,元素A(i,j)表示系统从状态i转移到状态j的概率。矩阵的每一列元素之和必须为1,这是因为转移概率总和必须为1。转移矩阵有一个本征值为1的本征矢量,对应着系统的稳态,亦即系统到达这个状态后,它在各个状态的概率分布就不会再发生变化。

       为了说明PCCA的原理,我们直接来考虑最为极端的情况,也就是系统由几个完全分离的cluster所构成。对于最为极端的情况,如果系统只能在cluster内部转移,而完全不会在cluster之间转移,那么转移矩阵A就会是分块矩阵的形式,比如下面的系统就可以分为两个完全不连通的cluster,如下面的矩阵。

      这样的一个矩阵存在着不止一个本征值为1的本征矢量,因为它的每个分块都可以看做一个转移矩阵,都会对应着一个稳态。比如对于上面的矩阵A,下面两个本征矢的本征值都为1。

      

      如果我们得到的矢量都是这样的理想形式,那么聚类就很简单了,只要得到本征值为1的全部本征矢,把对应的元素大于0的数据点归为一类就可以。十分可惜的是,由于这两个本征矢量是简并的,它们线性叠加产生的矢量也是矩阵的本征值为1的本征矢量,比如这个矢量:

      因此PCCA算法的思路,就是要从计算得到实际本征矢量,反推得到理想矢量,从而实现聚类。

       如果将计算得到的k个本征值为1的本征列矢量并排合并,成为一个N*k的矩阵,那么矩阵的每一行可以看成对应与数据点的一个坐标。对于理想本征矢(对应下图蓝色基矢),数据点都是落在坐标轴上(因为除了所属的cluster所对应的那个本征值,其余的维度都是0),比如下图的红色和黄色的数据点。但是由于实际得到的本征矢量是理想本征矢的线性叠加,所以基矢就发生了旋转(对应黑色基矢)。

      尽管如此,每个cluster的数据点落在一条直线上的性质并没有发生改变。现在的问题就变成了如何找到这些直线的方向。PCCA首先找到离原点最远的数据点,这个点相对于原点的矢量,就对应了一个理想本征矢。然后每一次都找与已知的理想矢量垂直(相对原点),而又离原点最远的数据点。只要找k次,就能找到所有的理想矢量。最后看数据点落在哪个方向上,就可以知道它们属于哪个cluster。实际情况下,矩阵并不会是完全的分块矩阵,所以除了第一个本征矢,其余本征矢量对应的本征值不会完全为1,而是接近于1。cluster之间的转移几率越小,这个算法的准确性自然越高。

聚类结果

       PCCA算法的一个优点就是,它可以根据本征值来直接得到cluster的数目,有多少个接近于1的本征值就应该分多少个cluster。当然这也是一个限制,聚类数目不能随意给定,完全由数据性质决定,如果cluster的分界不明显,那么可能聚类就完全无效。

       下面是PCCA对样品1的聚类结果。第一幅图是由算法自动判定聚类数目,正好为3,聚类十分成功;第二幅图是人为地要求分为4个cluster,结果算法就基本失效了。

聚类方法

聚类方法

       PCCA是除了Chameleon算法外,对样品2聚类结果最好的一个算法。不过它并不能正确地判断出cluster的数目,总共划分出了7个cluster,这里显示了前5个。

聚类方法

       PCCA可以自动判定cluster数目,而且也能得到非凸型的cluster,还可以适用于概率转移矩阵的聚类,看上去确实是一个性能比较好的聚类算法。不过,PCCA对数据的性质特征有比较强的预设,当数据性质偏离理想状况较远时,算法的稳定性有待考验。

7、SOM

      之所以尝试SOM聚类,主要是因为这是基于神经网络的一种算法,而神经网络本身又是机器学习中的一个重要方法,所以就自己实践一下体会体会。

       所谓SOM指的是Kohonen提出的竞争网络,全称是self-organizing map。这个算法有着非常多的改进和变种,在网络的拓扑结构、节点之间的反馈方式等方面各有不同。更一般地说,SOM应该是一个降维算法,它可以将高维的数据投影到节点平面上,实现高维数据可视化,然后也可以继续根据降维之后的数据再进行聚类,google seo,就像谱聚类一样。不过,因为这里仅仅是个人的算法尝试,所以我就使用最简单的方式,直接使用SOM进行聚类。

       竞争网络,顾名思义就是网络节点相互竞争。对于每一个输入的数据点,网络节点都要进行竞争,最后只有一个节点获胜。获胜节点会根据赢得的数据点进行演化,变得与这个数据点更匹配。如果数据可以明显地分为多个cluster,节点变得跟某个cluster内的数据点更为匹配,一般而言就会跟其它cluster不太匹配,这样其它节点就会赢得了其它cluster的数据点。如此反复学习,每个节点就会变得只跟特定的一个cluster匹配,这样就完成了数据点的聚类。

       SOM需要输入数据点的坐标矩阵,对应的,每个网络节点也有一个坐标,初始时刻随机赋值。每次输入一个数据点,与这个数据距离最近的节点获胜,获胜点的坐标向着这个数据点的方向偏移。聪明的看官们肯定发现了,这个简单化的SOM算法跟K-means算法思路基本一致,确实一些文章也提到,在节点数目偏少的情况下SOM的结果就类似于K-means。

聚类结果

       SOM的聚类结果确实跟K-means比较类似,不过当聚类数目取为4时,经常也能正确的结果,而不会聚成4个cluster,这个跟学习时间以及节点的初始值有关。这应该是因为SOM的学习方式与K-means直接求平均不同。至于对样品2的聚类,SOM也跟K-means类似,就不贴出来了。

聚类方法

聚类方法

       这个SOM聚类只是个人试水,并不能真正代表SOM聚类的最佳效果,仅作参考。

8、Affinity Propagation

       Affinity Propagation(简称AP)是一个比较新的算法,在07年发表在Science上面,可见肯定是有一些独到之处的。

       个人认为,AP算法的具体实现步骤没有很直观的物理意义,大致上就是一个网络自动演化的过程,实现起来也并不复杂。感兴趣的童鞋可以直接到算法作者的,上面也提供了各个版本的实现程序,可以直接拿来使用。

        

这里我就不详细地叙述算法的实现步骤了,只是介绍一下这个算法的一些特点。

1)AP只要求输入数据点之间相似性矩阵,而且还不需要是对称阵。从这个角度来说,适用范围非常大。

2)AP算法的核心是对于每个cluster找到一个代表数据点exemplar,使得cluster内其它数据点到这个点的距离平方和最小。这是AP算法的一个很大的优点,因为它不仅能完成聚类,还可以给出这个类别的代表。很多时候我们聚类也就是为了找出代表而已。

3)AP算法不能直接知道聚类的数目,它不仅不能判定合适的聚类数目,甚至在聚类完成前,用户都不知道这次会聚出多少个cluster来,只能自己慢慢调整参数,多次尝试……

       AP算法的目标函数跟K-means类似,不过中心点不是平均值,而是真实的一个数据点。其实这个算法可以说是K-centers的一个高效实现,但归根到底得到的也就是K-centers最佳情况下的结果而已,跟K-means也类似,都是大小接近的凸型cluster,所以我就不贴结果了。可以说,当你想得到K-centers的结果时,AP算法是你的最佳选择,但如果你的目标不在于此,那就不要用这个方法了。

( )

(整理:英文推广TuiGuang123.com)
分享到:
------分隔线----------------------------

联系信息

 

 地址:深圳南山保利广场B区二层51#

 手机:18123763721,400-879-3881

 微信:18123763721

 联络:费先生、雁狸

 办公:9:00~22:00

 网址:http://www.tuiguang123.com

银行账户

 

银行:招商银行深圳水榭花都支行

户名:深圳市亿推信息技术有限公司

帐号:7559 2777 4410 601

重点方案

 

国外媒体发稿

社交媒体KOL

区块链海外推

英文外链推广

跨境电商特惠

微信咨询

 

COPYRIGHT·深圳市亿推信息技术有限公司 版权所有 粤ICP备17150804号-2