改进的AP聚类算法研究

The Improved Algorithm for Affinity Propagation

AP聚类算法是Frey和Dueck在2007年提出的一个先进的聚类方法.该算法具有较传统聚类算法更好的聚类性能,已被成功地应用于计算机科学的研究领域.为了获得高质量的聚类集,原始AP算法的迭代是在全部数据点之间交流信息,直到收敛.由于这种算法在计算数据时需要占用二次CPU时间,不适用于大规模的数据集,因此,本文在AP算法的基础上提出了一种有效的聚类算法.该算法在迭代时可修剪不必要的信息,且在计算消息收敛的同时确定迭代集群,并对算法进行了实验,证明算法是有效的.

Affinity Propagation is a advanced clustering method proposed by Frey and Dueck in 2007. It has been successfully applied to broad areas of computer science research because it has much better clustering performance than traditional clustering methods. In order to obtain high quality sets of clusters, the original Affinity Propagation algorithm iteratively exchanges messages between all pairs of data points until convergence. This algorithm does not scale for large datasets because it requires quadratic CPU time to compute the messages. This paper proposes an ef- ficient Affinity Propagation algorithm. The algorithm in the iterative pruning unnecessary exchange information, and when calculating the convergence pruning news value, determine the iteration of the cluster . Experimental evalua- tions demonstrate the effectiveness of our algorithm.