利用Affinity Propagation优化K-means初始聚类：新策略与实验对比

本文主要探讨了如何利用近邻传播算法（Affinity Propagation，简称AP）来改进K-means聚类的初始化方法，从而提高K-means聚类的性能。作者朱岩、于剑和蔡燕在北京市交通大学计算机科学与技术系的研究表明，虽然K-means算法因其快速收敛速度而广受欢迎，但其对初始聚类中心（初始值）的依赖性是其显著的缺点。许多学者已经意识到这一点，并在文献中提出了多种K-means初始化策略。 K-means算法的基本原理是将数据集划分为k个簇，每个簇有一个质心，然后通过迭代过程不断调整质心位置，直到簇内数据点与其质心的距离平方和最小。然而，K-means的性能往往受初始聚类中心的影响很大，如果初始划分不合理，可能导致算法陷入局部最优解，无法达到全局最优。 Affinity Propagation算法则是一种自组织的聚类方法，它不需要预先指定聚类中心，而是通过计算样本间的相似度（称为亲和力）来自动选择代表每个簇的“示例”（exemplar），从而避免了对初始值的敏感性。这种方法在产生高质量的聚类结果方面表现良好，尤其是在处理复杂数据集时。 论文中提出的创新策略是结合K-means的快速收敛特性和Affinity Propagation的优秀聚类能力，即使用Affinity Propagation生成的簇示例作为K-means的初始聚类中心。实验结果显示，这种联合方法相较于原始的K-means和Affinity Propagation算法，能够显著降低平方误差，从而实现更优的聚类效果。这种方法不仅提高了聚类的精度，而且在实际应用中显示出更好的鲁棒性和效率。 这篇论文的核心贡献在于提出了一种新颖的K-means初始化策略，通过利用Affinity Propagation生成的簇示例来启动K-means算法，有效地改善了K-means对初始条件的依赖，为解决聚类问题提供了一个更为稳健且性能优越的方法。这不仅提升了聚类任务的准确性和稳定性，也为后续的聚类研究和实践提供了有价值的新思路。