AP聚类算法

最近在学习AP聚类算法,网上找了好多资料(http://blog.csdn.net/dreamd1987/article/details/8923035, http://www.doc88.com/p-239796915955.html, http://www.doc88.com/p-886680412462.html),对于AP的迭代公式都不太相同,后经过验证找到了正确的迭代公式,总结一下,以后备用:

算法原理

AP算法是一种根据数据对象之间的相似度自动进行聚类的方法,隶属于划分聚类方法的一种。数据对象之间的相似度根据不同的场景选择不同的衡量准则,如欧式距离,随相似准则的不同,数据对象之间的相似度可能是对称的,也可能是非对称的。这些相似度组成N*N(N为数据对象的数目)的相似矩阵S,利用该矩阵进行自动迭代计算。注:相似度矩阵应该是一个负值矩阵,即每个元素的值不能大于0,如果用欧式距离,那么取负值即可。

AP算法根据S对角线的数值最为某个点能否成为聚类中心的评判标准,该值越大,该点成为簇中心的可能性越大,对角线上的值称为参考度p。p的大小影响簇中心的数目,若认为每个数据对象都有可能作为簇中心,那么p就应该取相同的值(此时S对角线的值都为p),当然可以根据不同点成为簇中心的可能性大小,取不同的p值(此时S对角线上的值就会不同)。如果p等于S矩阵中所有元素的均值,那么得到的簇中心数目是中等的;如果取最小相似度,那么得到较少的聚类。

AP算法有两个重要的消息,Responsibility和Availability。R(i,k)描述了数据对象k适合作为数据对象i的聚类中心的程度,表示的是从i到k的消息;A(i,k)描述了数据对象i选择数据对象k作为其据聚类中心的适合程度,表示从k到i的消息。R(i,k)与A(i,k)越大,那么数据对象k就越有可能作为聚类的中心。AP算法就是不断迭代更新每一个数据对象的吸引度和归属度,直到迭代一定的次数,产生m个高质量的exemplar,同时将其余数据对象分配到相应的聚类中。

迭代公式:网上看到不同的版本,经过测试,公式如下:

(1)吸引度迭代公式

AP聚类算法

(2)归属度迭代公式:

AP聚类算法

当t为0时A(i,k)和R(i,k)为0.

整个AP算法的过程是先迭代R(i,k),利用迭代后的R再迭代A(i,k)。一次迭代包括R和A的迭代,每次迭代后,将R(k,k)+A(k,k)大于0的数据对象k作为簇中心。当迭代次数超过设置阈值时(如1000次)或者当聚类中心连续多少次迭代不发生改变时终止迭代(如50次)。

AP算法的迭代次数和聚类数目主要受到两个参数的影响。其中聚类数目主要受参考度p(该值为负值)的影响,该值越大,聚类数目越多。参数lamd称为阻尼系数,由公式可以看出,该值越小,那么R和A相比上一次迭代的R和A会发生较大的变化,迭代次数会减少。阻尼系数一般取值为(0,1)。

算法步骤:1)先计算数据对象之间的相似度,得到相似矩阵;2)不断迭代R和A,得到簇中心;3)根据簇中心划分数据对象。

优点:1)不需要像k-menas、k-medoids(如PAM、CLABA等)事先给出聚类数目;

缺点:1)AP算法需要事先计算每对数据对象之间的相似度,如果数据对象太多的话,内存放不下,若存在数据库,频繁访问数据库也需要时间。如果计算过程中实时计算相似度,那么计算量就上去了;2)AP算法的时间复杂度较高,一次迭代大概O(N3);3)聚类的好坏受到参考度和阻尼系数的影响。

 

例子:读入的文件内容为二维点:

数据对象编号\t X值\t Y值

1     0.1  0.1

2     0.3  0.1

3     0.3  0.3

4     0.1  0.3

5     0.2  0.2

6     0.5  0.5

7     0.7  0.5

8     0.7  0.7

9     0.5  0.7

10   0.6  0.6

聚类结果的簇中心为两个,分别为点(0.2,0.2)(簇编号为1)和(0.6,0.6)(簇编号为2)。

输出簇中心和聚类结果:

簇内变差:1.13137

数据对象编号\t所属的簇编号

1     1

2     1

3     1

4     1

5     1

6     2

7     2

8     2

9     2

10   2

AP聚类算法

上一篇:Join与子查询的对比


下一篇:PreparedStatement