胡久松,刘宏立,颜 志,徐 琨

(湖南大学 电气与信息工程学院,湖南 长沙 410082)

仿射传播聚类算法(Affinity propagation clustering, APC)是Frey等人在science上提出的通过数据点之间相互传播消息来确定聚类的新方法[1-2]，文献[3]公开了其源码。由于APC算法可以在短时间内获得更低的误差聚类结果、不依赖于初值的选取、不需要相似矩阵必须对称等优点,已被广泛应用于众多领域,例如文献[2]将其应用于图像处理、基因识别和路线规划;文献[4]将其应用于文本聚类;文献[5-7]将其应用于数据流分类;文献[8]将其应用于室内定位中等。许多文献针对算法收敛速度和准确率方面,在仿射传播算法应用中进行了改进研究。文献[9]通过数据的约束对等先验知识调整相似度矩阵来提高APC聚类算法的性能。文献[10]通过采用可变度量来改善相似性矩阵,以此提高APC算法处理多种数据的能力。文献[11]将MapReduce与APC算法结合,加速了APC算法的收敛速度。文献[12]将分层聚类的思想引入APC聚类的过程中,提升了算法的准确性和收敛速度。文献[13]设计了一种新的聚类有效性指标来确定APC算法的最优聚类数。

这些研究的基础是建立在公开APC源码的基础上的，在公开源码中,阻尼因子是APC算法的一个重要参数，算法的收敛问题主要通过调整阻尼因子的值解决。在公开源码中,采用的是固定阻尼策略，若将阻尼因子设置成一个较小的值(0.5),则有可能导致算法因发生震荡而难以收敛。因此,通常通过将阻尼因子设置为一个较大的值(0.9)的策略来有效避免震荡,但是这样会减慢算法的收敛速度。……