马 杰，杨 磊，徐 建

（1江苏师范大学 智慧教育学院（计算机科学与技术学院），江苏 徐州221116；2中国矿业大学徐海学院 计算机系，江苏 徐州221008）

0 引 言

本文算法不是一个独立的聚类算法，是用来辅助其它聚类算法更好、更有效地聚类的辅助算法。与其它聚类算法结合使用，能有效地改善聚类算法的聚类效果。

1 问题的提出

有些算法聚类的结果与自然分类有出入，有些算法对某些情况不能正确的分类。比如：Affinity Propagation（AP）聚类算法，是基于数据点间的“信息传递”的一种聚类算法。算法的基本思想是：将全部样本看作网络节点，通过网络中各条边的消息传递 计算出各样本的聚类中心。聚类过程中，共有两种消息在各节点间传递，分别是吸引度（responsibility）和归属度（availability）。通过在点之间不断地传递信息，最终选出代表元以完成聚类。AP算法通过迭代过程不断更新每一个点的吸引度和归属度值，直到产生m个高质量的Exemplar（类似于质心），同时将其余的数据点分配到相应的聚类中。其特点如下：

（1）不需要制定最终聚类个数。

（2）将已有数据点作为最终的聚类中心，而不是新生成聚类中心。

（3）模型对数据的初始值不敏感，多次执行AP聚类算法，得到的结果是完全一样的，即不需要进行随机选取初值步骤。

（4）对初始相似度矩阵数据的对称性没有要求。

（5）与k中心聚类方法相比，其结果的平方差误差较小，相比于K-means算法，鲁棒性强、准确度较高，但算法复杂度高、运算消耗时间多。

在实际的使用中，AP有两个重要参数：preference（定义聚类数量）和damping factor（控制算法的收敛效果）。……