指定类数下仿射传播聚类的快速算法①

针对Science杂志上提出的仿射传播（Affinity propagation）聚类产生指定类数的聚类结果时效率较低的问题，提出了基于多网格策略的快速算法。该算法采用多网格搜索策略来减少调用仿射传播算法的次数，改进偏向参数的上界以缩小搜索范围。新方法大幅度地提高了仿射传播聚类在指定类数下的速度性能。实验结果表明新方法十分有效，在运行时间上比现有方法减少了22%－90%。

Fast Algorithm of Affinity Propagation Clustering under Given Number of Clusters

To enhance the low efficiency of producing the clustering result with given number of clusters by Affinity propagation clustering (AP), the fast multi-grid searching method is proposed. The proposed method uses multi-grid searching to reduce the calling times of AP, and improves the upper bound of preference parameter to reduce the searching scope, so that it can largely enhance the speed performance of AP under given number of clusters. The experimental results show that the proposed method is very effective and reduces the running time by 22%-90%, compared with the existing method.