2007年,美国学者Frey在《Science》发表题为“Clustering by Passing Messages Between Data Points”的一篇文章,即近邻传播聚类算法(Affinity Propagation,AP),此算法一经提出,不断有学者对其进行研究。基于该算法的优势,越来越多的专家学者对其进行改进并应用到实际生活中。尽管如此,传统的AP算法仍然存在三个问题:(1)传统的AP算法的重要参数——偏向参数和阻尼系数,需要手动调节,使算法时间成本增加,也会导致算法准确度降低;(2)传统的AP算法在对凸集和结构清晰的超球形数据聚类时,可以得到合理的结果,但当处理结构复杂的大规模数据集时,则难以获得准确的聚类结果;(3)传统的AP算法采用欧式距离作为相似度,而欧式距离无法准确反映数据间的相似性;针对以上三点不足,本文提出了三种优化AP算法的方法,如何对以上三个问题进行优化,本文提出了三种优化AP的算法,分别从优化参数、设计相似度函数和处理大数据集聚类三个方面进行改进并详细介绍改进的思想及流程。1.针对难以设置近邻传播聚类算法的偏向参数这一问题,本文提出了一种新的算法—ABC-SAP聚类算法,即基于人工蜂群的半监督近邻传播聚类算法(Semi-supervised Affinity Propagation Based on Artificial Bee Colony,ABC-SAP)。该算法将人工蜂群算法和近邻传播算法相融合,利用半监督思想调整相似度矩阵,将引领蜂引入到算法迭代过程,因其寻优能力强,可以双向搜索偏向参数空间以取得最优值。通过UCI大数据集进行测试,ABC-SAP算法可以有效地调整偏向参数值,使其更加合理,进而使得聚类质量得到改进。2.鉴于近邻传播聚类算法对海量复杂的大数据集处理效果不理想,提出基于大规模数据集的近邻传播算法(Affinity Propagation Clustering Algorithm Based on Large Scale Data Set,LSDS-AP)。该算法在确定聚类中心距离时采用结构相似度计算,然后引入密度峰值聚类算法对所有聚类中心再次聚类,使其达到最佳聚类结果。3.AP算法在聚类过程中需要偏向参数以及阻尼系数作为聚类指引,提出一种新的算法—基于自适应步长的布谷鸟近邻传播算法(An Adaptive Step Size Cuckoo Search-based Affinity Propagation Clustering Algorithm,ASCS-AP)。基于布谷鸟算法寻优能力强的特点,本文将布谷鸟算法应用到AP算法中,用以找到最佳的偏向参数值和阻尼系数值。同时,在Silhouette值的指导下,输出近似全局最优解。在仿真实验中表明,本文提出的ABC-SAP算法可以有效提高传统AP算法的性能以及收敛效率。4.为拓展研究的应用领域,本文将ABC-SAP算法和ASCS-AP算法应用到对农村居民家庭平均每月支出数据的聚类中。经验证,新算法的聚类结果与真实的分类基本一致,说明新算法在实际应用中可以发挥价值,为国民经济分析提供了依据。