几种聚类的算法 - 图文(2)

0.020.0150.010.0050-0.005-0.01-0.015-0.020100200300400500600 结论：为了避免实验误差，增量R次后要对数据进行初始化，i.e. 用谱聚类的传统算法重新计算L等，在进行增量计算。实验数据对实验结果又有很大的影响，所以R的选择要具体问题具体分析。 二．Affinity propagation 聚类算法 Affinity Propagation (AP) 聚类是最近在Science杂志上提出的一种新的聚类算法。它根据N个数据点之间的相似度进行聚类,这些相似度可以是对称的,即两个数据点互相之间的相似度一样(如欧氏距离);也可以是不对称的,即两个数据点互相之间的相似度不等。这些相似度组成N×N的相似度矩阵S(其中N为有N个数据点)。AP算法不需要事先指定聚类数目,相反它将所有的数据点都作为潜在的聚类中心,称之为exemplar。 2.1Affinity propagation算法详细介绍 以S矩阵的对角线上的数值s (k, k)作为k点能否成为聚类中心的评判标准,这意味着该值越大,这个点成为聚类中心的可能性也就越大,这个值又称作参考度p ( preference) 。聚类的数量受到参考度p的影响,如果认为每个数据点都有可几种聚类的算法 | 2012/12/5 能作为聚类中心,那么p就应取相同的值。如果取输入的相似度的均值作为p的值,得到聚类数量是中等的。如果取最小值,得到类数较少的聚类。AP算法中传递两种类型的消息, (responsiblity)和(availability) 。r(i,k)表示从点i发送到候选聚类中心k的数值消息,反映k点是否适合作为i点的聚类中心。a(i,k)则从候选聚类中心k发送到i的数值消息,反映i点是否选择k作为其聚类中心。r (i, k)与a (i, k)越强,则k点作为聚类中心的可能性就越大,并且i点隶属于以k点为聚类中心的聚类的可能性也越大。AP算法通过迭代过程不断更新每一个点的吸 5 引度和归属度值,直到产生m个高质量的exemplar,同时将其余的数据点分配到相应的聚类中。 在这里介绍几个文中常出现的名词： exemplar：指的是聚类中心。 similarity：数据点i和点j的相似度记为S(i，j)。是指点j作为点i的聚类中心的相似度。一般使用欧氏距离来计算，如－|| (xi?xj)2?(yi?yj)2||。文中，所有点与点的相似度值全部取为负值。因为我们可以看到，相似度值越大说明点与点的距离越近，便于后面的比较计算。 preference：数据点i的参考度称为P(i)或S(i,i)。是指点i作为聚类中心的参考度。一般取S相似度值的中值。 Responsibility:R(i,k)用来描述点k适合作为数据点i的聚类中心的程度。 Availability:A(i,k)用来描述点i选择点k作为其聚类中心的适合程度。 两者的关系如下图： responsibility 数据点i availability 数据点k 图3. 数据点之间传递消息示意图 下面是R与A的计算公式： R(i,k)=S(i,k)-max{A(i,j)+S(i,j)}(j?{1,2,……,N,但j≠k}) (2)A(i,k)=min{0,R(k,k)+?{max(0,R(j,k))}} (j?{1,2,……,N,但j≠i且j≠k})j (3) R(k,k)=P(k)-max{A(k,j)+S(k,j)} (j?{1,2,……,N,但j≠k}) (4) 由上面的公式可以看出，当P(k)较大使得R(k, k)较大时, A(i, k) 也较大, 从而类代表k作为最终聚类中心的可能性较大; 同样, 当越多的P(i)较大时, 越多的类代表倾向于成为最终的聚类中心。 因此, 增大或减小P可以增加或减少AP输出的聚类数目。 Damping factor(阻尼系数):主要是起收敛作用的。文中讲述，每次迭代，吸引度Ri和归属度Ai要与上一次的Ri?1和Ai?1进行加权更新。公式如下： 几种聚类的算法 | 2012/12/5 6 Ri＝(1-lam) * Ri+lam * Ri?1 (5) Ai=(1-lam) * Ai+lam * Ai?1 (6) 其中，lam?[0.5,1)。 2.2AP算法的具体过程 AP算法的具体工作过程如下：先计算N个点之间的相似度值，将值放在S矩阵中，再选取P值(一般取S的中值)。设置一个最大迭代次数(文中设默认值为1000)，迭代过程开始后，计算每一次的R值和A值，根据R(k,k)+A(k,k)值来判断是否为聚类中心(文中指定当(R(k,k)+A(k,k))＞0时认为是一个聚类中心)，当迭代次数超过最大值( 即maxits值)或者当聚类中心连续多少次迭代不发生改变( 即convits值)时终止计算(文中设定连续50次迭代过程不发生改变是终止计算)。 三．K-MEANS算法简介 k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较低。簇的相似度是关于簇中对象的均值度量，可以看作簇的质心(centriod)或重心(center of gravity)。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.，其定义如下： ????|p?mi|2几种聚类的算法 | 2012/12/5 i?1p?Cik（1） 其中，E是数据集中所有对象的平方误差和，p是空间中的点，表示给定对象，mi是簇Ci的均值（p和mi都是多维的）。换句话说，对于每个簇中的每个对象，求对象到其簇中心距离的平方，然后求和。这个准则试图使生成的k个结果簇尽可能的紧凑和独立。 7 四．Affinity propagation算法与Kmeans算法比较 k-means算法对于离散和噪声数据比较敏感，对于初始聚类中心的选择很关键，因为初始聚类中心选择的好坏直接影响到聚类结果，而且这个算法要求进行聚类时输入聚类数目，这也可以说是对聚类算法的一种限制。不过，这种算法运行速度相对于AP算法要快一些，因此，对于那些小而且数据比较密集的数据集来说，这种聚类算法还是比较好的。 AP算法对于P值的选取比较关键，这个值的大小，直接影响都最后的聚类数量。值越大，生成的聚类数越多，反之如此。而且，那个阻尼系数(lam) 迭代也是很关键的。将AP算法运用于图像检索系统中来进行初始分类，我觉得挺有用的。这个想法还有待实现。 几种聚类的算法 | 2012/12/5 8