MR-SAP: MapReduce实现的半监督近邻传播聚类算法

"一种基于MapReduce的半监督近邻传播算法" 本文主要探讨了一种改进的聚类算法，即基于MapReduce的半监督近邻传播（MR-SAP）算法，用于解决传统近邻传播（Affinity Propagation, AP）算法存在的高时间复杂度和对结构松散数据聚类效果不佳的问题。近邻传播算法是一种无中心的非参数聚类方法，它通过消息传递机制寻找数据点之间的相似性，并据此形成簇。然而，AP算法在大规模数据集上的运行效率较低，且对于结构不紧密的数据集，其聚类效果可能不尽如人意。 为了解决这些问题，该研究提出将MapReduce并行计算框架应用到AP算法中，实现半监督学习。在MR-SAP算法中，首先在各个数据节点上并行运行AP算法，计算得到局部聚类中心和每个中心成为全局聚类中心的决策系数。这一步骤大大提升了计算效率，同时降低了单个节点的计算压力。接下来，通过对这些局部聚类中心进行整合，利用决策系数确定全局的AP聚类过程，其中初始参考度的选择依据这些决策系数。这种方法使得算法能更好地处理大规模和结构松散的数据。 为了评估聚类效果并引导算法优化，研究者引入了IGP（类内比例）这一聚类评价指标。IGP用于衡量同一类别内部数据点的相似性和类间数据点的差异，通过比较不同聚类结果的IGP值，可以指导算法向最优解方向调整。实验结果显示，MR-SAP算法在处理不同规模和类型的数据集时，不仅具有良好的计算效率和扩展性，而且聚类精度也得到了显著提高。 此外，文章指出该工作得到了国家自然科学青年基金的资助，由冯兴杰教授和王文超硕士研究生共同完成，他们分别在数据库及数据仓库、智能信息处理理论与技术，以及数据挖掘和大数据技术领域有所专长。文章最后提供了中图分类号、文献标志码和文章编号，便于后续引用和检索。 MR-SAP算法是针对AP算法的优化，它利用MapReduce的并行处理能力提升聚类效率，并通过半监督学习和IGP评价指标改善了对结构松散数据的聚类性能。这项研究对于大数据环境下的聚类任务具有重要的实践价值和理论意义。