近邻传播聚类算法研究

李林阳，李高明，刘 祥，李 笑

（1.武警工程大学基础部，陕西 西安 710086；2.武警工程大学信息学院，陕西 西安 710086）

AP算法是基于距离的聚类算法，Frey等于2007年在《Science》上发表了一篇论文，首次提出了近邻传播聚类算法。该算法具有很多优点，比如聚类速度快、精确度高等，同时也存在一些问题。

1 AP算法存在的问题

（1）偏向参数的选择问题。偏向参数往往需要人工设置，然而事实上这种设置未必能找到最合理的聚类结果。因此考虑p值的自适应，避免人工设置的麻烦和因此导致的聚类结果的不合理，从而使算法更加便捷和准确，提升聚类性能。人工设置比较繁琐，若采用合适的策略，自适应调整阻尼因子，则可以加快算法收敛速度。

（2）相似度函数的选择问题。不同结构的数据其相似度函数的选择也不同，如对于球形数据，选择欧氏距离可以取得好的效果，但对于结构复杂的非球状簇，选择基于密度的相似度计算方法的效果会比较理想；对于多重尺度的数据，存在奇异数据的数据集，以及高维数据，欧氏距离不能准确刻画数据之间的距离。

（3）相似度函数的选择问题。不同结构的数据其相似度函数的选择也不同，对于多重尺度的数据，奇异数据，以及高维数据，欧氏距离不能准确反映数据之间的距离，且相似度矩阵会以根据维数的增加而呈几何倍数增长。

（4）其他问题。其他问题包括该算法的集成研究较少的问题，半监督的问题，对于大规模数据集，该算法的时间复杂度高的问题等。

2 AP算法发展现状

近邻传播聚类算法（Affinity Propagation Clustering Algorithm，AP）于2007年由Frey等 在《Science》杂志上第一次提出。作为一种有效的聚类算法，AP算法此后得到了较大发展。2008年，肖宇等 将半监督思想与近邻传播聚类算法结合在一起，详细介绍了近邻传播算法，根据成对约束先验信息提出了基于约束的半监督近邻传播聚类算法，该研究成果得到了广泛的认可，该文献一度被数百篇论文引用，证实了半监督AP算法的科学性和可行性。然而，该算法在聚类过程中存在相似度适用范围不够广泛、偏向参数和阻尼因子（也叫阻尼系数或者迭代因子）需要人工筛选、处理大规模复杂数据集时算法复杂度高、不适用于高维数据和多尺度数据等问题，针对以上问题，专家学者进行了一系列改进。

2.1 AP算法负欧氏距离的问题研究

董俊等 提出了可变相似性度量的方法，其基本思想是根据数据在观测空间中的流形分布规律，对不同分布的数据采取不同的处理策略；对于全局数据，采取函数变换策略对不同流形分布的数据对进行相似度的缩放，而对于局部数据，则采取映射的策略，搜索识别数据的不同流形分布并将其映射成超球形或超椭球形，再使用AP算法进行处理，从而提出了基于可变相似性度量的AP算法（AP-VSM），取得了良好的聚类效果。周世兵等 构造了样本聚类距离和样本离差聚类距离。邢艳等根据K-最近邻的内含提出了互近邻的概念，继而提出了互近邻一致性的定义并将其作为相似度度量的调整依据，最后提出了基于互近邻一致性的AP算法。同样采用最近邻概念和最近邻的传递性的还有苏亚然等 ，他们提出了近邻传播的快速扫描算法，优化搜索过程并尝试简化最近邻居的判定过程和计算过程，从而实现了更加快速的聚类。廖予良 通过分析路径相似度，提出了基于最短路径的聚类方法，用最短路径取代传统的欧氏距离，实现了对不同形状数据集的有效聚类。胡晨晓等 借助稀疏表示来作为样本数据的相似度度量，提出了基于稀疏表示的AP算法。张利 基于模糊函数提出了将距离贴近度引入相似度函数的算法，很好解决了奇异样本数据的量纲和过大过小值干扰问题，得到了良好的聚类结果。姬强 通过构造一个采用核低秩表示的优化问题，挖掘数据的低维度流形结构，从而构造出结构相似度，作为欧氏距离的替代相似度度量，一定程度上解决了复杂结构数据的内部结构不易识别和挖掘的问题。唐丹 采用改进的马氏距离来替代欧氏距离。赵昱 通过求解邻域半径得出邻域密度并最终计算出邻域相似度，作为近邻传播聚类算法的新的相似度度量，不仅提高了算法对复杂数据集的适应能力，也提高了算法的自适应特性。房骁 提出了量子近邻传播聚类算法，为解决高维数据的聚类问题，引进高斯核函数来构造相似度函数。

2.2 偏向参数的选择问题和阻尼因子的使用问题研究

有关学者也提出了一些解决方案。张利 针对偏向参数需要人工选择的问题，提出了基于布谷鸟优化算法的自适应寻找最优偏向参数的方法，提出了CS-SAP算法。周治平等 利用Silhouette聚类有效性指标来确定偏向参数。姬强 针对偏向参数难以调节的问题，提出了基于烟花爆炸智能优化算法的最佳偏向参数选择算法。覃华等 提出采用概率无向图模型来解决偏向参数的自适应问题。赵昱 采用聚类有效性指标和下降步幅相结合的方法，实现了偏向参数的自适应，提出了PGZC-AP算法，提高了算法的运行效率。房骁 采用量子智能优化算法对偏向参数进行优化，参数初始化阶段采用量子编码方法，参数的更新阶段使用旋转量子门，最后获得近优参数，将其代入算法运行过程，从而解决了偏向参数的筛选问题，提高了聚类精度，减少了迭代次数。郑凯月 采用布谷鸟优化算法对偏向参数和迭代因子同时进行优化，提高了算法的自适应性；还采用人工蜂群智能优化算法对偏向参数进行了自适应计算的优化。

2.3 近邻传播聚类算法的聚类有效性指标研究

周世兵等 采用近邻传播聚类算法作为聚类的研究对象，比较了6中聚类有效性指标，并改进了IGP指标作为最佳聚类数确定的方法。周世兵等 提出了BWP聚类有效性指标。

2.4 高维数据的聚类问题复杂的大数据集具有高复杂度的问题研究

多种不同类型的并行近邻传播聚类算法、一些与层级聚类相结合的近邻传播聚类算法以及多阶段近邻传播聚类算法等被相关专家学者分别提出。刘晓楠等 提出了专门针对大规模数据集的分层聚类方案，文章将原始数据集划分为多个较小的独立子集，对各个子集进行算法执行，得到每个子集的聚类中心，而后将得到的聚类中心集合再次进行算法执行，得到全部数据集的类代表点，最后用得到的全局类代表点实现原始数据集的划分，从而解决了大数据集聚类效率的优化问题。钱雪忠等 根据先验约束实现高维数据投影矩阵的获取，在低维空间中进行聚类，从而实现了高维空间数据的近邻传播聚类。其中，高维数据投影到低维数据时，要求原来的数据集结构不能改变。周治平等 同样提出了基于局部投影方法实现对复杂结构数据和高维数据的聚类，减少了信息冗余，保持了数据内部的结构。张利 使用熵权法和主成分分析法对高维数据进行降维，而后在低维空间中进行聚类。

3 结束语

AP算法还有较大的改进空间。可以与半监督方法结合。AP算法针对相似度的改进可以考虑与密度聚类的研究成果相结合，提高算法对于复杂结构数据的适应度，采用基于密度的近邻传播聚类算法。对于高维数据的处理还需要进一步加强。对AP算法聚类集成的研究比较少，可以进一步加强。