最近在学习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）吸引度迭代公式
（2）归属度迭代公式：
当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