并行近邻传播半监督聚类算法：时间效率提升与实验验证

本文主要探讨了"论文研究-近邻传播半监督聚类算法的并行计算"这一主题，针对传统聚类方法存在的问题，尤其是Semi-supervised Affinity Propagation (SAP)算法在处理大规模数据集时效率较低的问题。SAP算法原本基于近邻传播的思想，通过利用成对点约束信息调整相似度矩阵，旨在找到理想的类代表点，但其时间复杂度较高，达到O(n^3)，对于大数据集的处理显得效率低下。 AP算法的核心是利用相似度矩阵来表示数据点间的两类信息：代表矩阵(r(i,k))和适选矩阵(a(i,k))。r(i,k)反映xk作为xi的类代表点的证据积累，而a(i,k)则体现xi倾向于选择xk作为类代表。然而，这些计算密集型操作导致算法在大规模数据集上的运行时间显著增加。 为解决这个问题，本文提出了一种并行计算方法PSAP（Parallel SAP），它旨在优化SAP算法，降低其时间复杂度。PSAP通过将计算任务分解到多个处理器或并行计算单元上，有效地分摊了计算负担。实验结果显示，PSAP算法的运行时间相比SAP算法大幅缩短，大约为其运行时间的1/8至1/4，这意味着在同样的聚类效果下，PSAP能够显著提升大规模数据集的处理速度。 PSAP的实现包括约束转换过程，以及对原始SAP算法的并行化策略。这种方法不仅提高了算法的性能，还减少了对初始类代表点选择的依赖，从而提高了聚类结果的稳定性。这篇论文不仅提升了聚类算法的效率，也为半监督聚类问题提供了一种有效的并行计算解决方案，对于处理大规模数据集的实时性需求具有实际应用价值。