APC算法
1 算法提出：Frey B J, Dueck D. Clustering by passing messagesbetween data points. Science, 2007, 315(5814):972?976.
2 AP算法详细介绍：
1) 已知数据集X?{X1,X2,?XN}，采用欧氏距离得到相似矩阵SN?N，任意两点之间的
相似度为两点距离平方的负数，即：s(i,k)??xi?xk上适合作为数据点Xi的类代表点.
AP算法为每个数据点k设定其偏向参数s(k,k)的值，s(k,k)的值越大，相应的点k被选中作为类代表点的可能性也就越大.
2) AP算法初始假设所有数据点被选中成为类代表点的可能性相同，即设定所有
2，表示数据点Xk在多大程度
s(k,k)?p?0为相同值p.同样p值的大小也影响到最终得到聚类的类的个数，AP算
法可以通过改变p值来寻找合适的类的数目 (实验结果说明，一般情况下，增大p值可以增加类的个数，减小p值可以减少类的个数)，这是此算法中的一个重要参数.
3) AP算法引入了两个重要的信息量参数，分别是responsibility 和availability,代表矩阵
R?[r(i,k)]N?N和适选矩阵A?[a(i,k)]N?N
AP算法的迭代过程就是这两个信息量交替更新的过程，两个信息量代表了不同的竞争目
的.
r(i,k)是从点Xi指向点Xk，它代表点Xk积累的证据，用来表示Xk适合作为Xi的类
代表点的代表程度.
a(i,k)是从点Xk指向点Xi，它代表点Xi积累的证据，用来表示Xi选择Xk作为类代
表点的合适程度.
对于任意数据点Xi，计算所有数据点的代表程度r(i,k)和合适程度a(i,k)之和，则Xi的类代表点为Xk:argmin(a(i,k)?r(i,k)).
kAP算法的核心步骤为两个信息量的交替更新过程，更新公式如下:
r(i,k)?s(i,k)?max{a(i,k?)?s(i,k?)}
k??k?min{0,r(k,k)??max{0,r(i?,k)}}?i??ia(i,k)????max{0,r(i?,k)}i?k?i??ii?k
AP 算法在信息更新这一步引入了一个重要参数，称为阻尼系数（Damping factor），主要起收敛作用。每次迭代,r(i,k)和a(i,k)的更新结果都是由当前迭代过程中更新的值和上一步迭代的结果加权得到。设当前迭代次数为t，加权公式为：
rt(i,k)?(1??)?(s(i,k)?max{at?1(i,k?)?s(i,k?)})???rt?1(i,k)（1）
k??k?(1??)?(min{0,rt(k,k)??max{0,rt(i?,k)}})???at?1(i,k)?i??iat(i,k)??tt?1?(1??)?(?max{0,r(i?,k)})???a(i,k)i?ki??i?4) AP算法程序的基本步骤:
i?k（2）
Step1 初始化:求解相似度矩阵SN?N.N为数据点的个数，设定相似度矩阵对角线元素
s(k,k)?p?0为一相同值.初始化availabilities和responsibilities为0,即：r(i,k)?a(i,k)?0
Step2 迭代过程:
① 信息量availabilities和responsibilities根据迭代公式(l)，(2)进行更新；
② 所有数据点求和信息量availabilities和responsibilities,找到每个点的类中心点； ③ 判断信息迭代过程是否满足停止条件:超过某一迭代最大数目;信息改变量低于某一固
定阈值;选择的类中心在连续几步迭代过程中保持稳定满足其中一个停止条件即可. Step3 判断得到的类中心的个数是否满足要求，如果不满足，则改变p值，重复进行程序直至聚类个数满足要求为止，输出最终聚类结果.
affinity propagation clustering
