基于萤火虫算法的近邻传播聚类研究

◆马翩翩 张新刚 梁晶晶

基于萤火虫算法的近邻传播聚类研究

◆马翩翩 张新刚 梁晶晶

（南阳师范学院计算机与信息技术学院 河南 473061）

针对近邻传播聚类（AP）中偏向参数和阻尼因子对聚类效果的影响，将偏向参数和阻尼因子作为萤火虫算法中的亮度和吸引度，通过群体智能算法在搜索空间中寻找偏向参数和阻尼因子，从而提高AP算法的聚类质量。实验表明，该算法能提高聚类质量。

近邻传播；偏向参数；阻尼因子；萤火虫算法

聚类算法属于机器学习中的无监督学习，寻找数据内在特征的一种划分过程。近邻传播聚类算法是BJ Frey和D Dueck在2007年提出的近年来发展较快聚类算法[1]。该算法在聚类过程将所有的数据点作为潜在簇中心，通过消息传递确定最终簇中心，在数据流聚类、图像处理、文本聚类、基因序列等领域都有广泛的应用。但是该算法的最终聚类结果受偏向参数的影响，若偏向参数取值过大，则最终划分的簇的个数偏多；若偏向参数取值过少，则最终划分的簇的个数偏少。针对偏向参数对聚类结果影响的问题，不同的学者从不同的角度进行了改进：为了克服设定的偏向参数和阻尼系数对聚类结果的影响，文献[2]设计了一种根据数据结构自动调整参数的核函数，对核空间中的数据集进行近邻传播聚类；文献[3]提出了将偏向参数和阻尼系数作为粒子群算法中的粒子，使用粒子群算法对系数寻优，从而提高聚类质量；文献[4]通过改进的布谷鸟搜索对偏向参数和阻尼系数进行调整，从而提高聚类效果；文献[5]通过对数据集构建概率图模型，分析数据集的概率密度，并将其注入偏向参数进而进行近邻传播聚类。本文则使用萤火虫群体智能优化算法来对近邻传播聚类算法中的偏向参数和阻尼因子寻优，进而提高聚类质量。

1 近邻传播聚类算法

近邻传播聚类算法是基于中心点的聚类算法。聚类中首先需要构建任意点与点之间的相似度矩阵，默认为负的欧式距离，即（，）=-||x-x||2| ；其中自身与自身的相似性（，）定义为偏向参数，参数会影响最终簇个数。

其次近邻传播聚类算法的聚类过程是通过点与点之间的消息传递来实现的。传递的信息有两类，吸引度（，）和归属度（，）。（，）代表的是通过和其他点的比较，数据点作为数据点的程度，具体如公式（1）所示；（，）代表的是数据点选择数据点作为簇中心的程度，具体如公式（3）所示。

当=时，

当=

最后对于任意数据点，找到满足（，）+（，）最大化值的点。如果=，则点为簇中心；如果≠时，则表示点属于簇中心的成员。同时消息传递过程中对消息进行阻尼以防止出现振荡，每个消息都被设置为和前一次迭代的乘积加上1-乘以新的更新值。具体如下所示：

最终根据所确定的簇中心将数据集划分为个不相交的簇{l|l=1，2，…，} 其中’∩’≠=且=∪l=1使簇内距离最小，具体如公式（7）所示。

2 萤火虫算法

萤火虫算法是Xin-She Yang于2008年根据自然界中萤火虫的活动所提出来的一种群体智能优化算法[6]。自然界中萤火虫主要借助于亮光进行活动，光亮较强的萤火虫吸引光亮较弱的萤火虫；但是随着距离的靠近，萤火虫相对吸引力降低，在优化算法中，用目标函数值代表亮光强度。

定义1 相对荧光亮度

其中（x）表示为第x萤火虫的光亮程度，即聚类的目标函数值。

定义2 吸引度

其中0表示最大吸引度，r表示萤火虫和萤火虫的距离。

定义3 位置更新

其中x和x分别表示萤火虫和和在空间中的两个位置；表示的是步长因子；ε代表的是随机数；x代表的是更新后的位置。

3 近邻传播聚类算法的改进

近邻传播聚类的改进是（FAAP）是一种基于萤火虫算法的改进，将参数和阻尼因子看作是萤火虫算法中的相对荧光亮度和吸引度，同时根据式（10）不断调整偏向参数和阻尼因子的值，然后进行近邻传播聚类，最终确定最优的聚类结果。基于FA的AP算法具体过程如下：

（1）加载数据集同时对数据进行归一化处理。

（2）在偏向参数空间和阻尼因子中随机选择组和值，最大迭代次数为max。

（3）依据欧式距离和偏向参数建立相似度矩阵。

（4）根据公式（1）、（2）、（3）、（4）、（5）、（6）执行近邻传播聚类。

（5）判断是否达到聚类结束条件，如不结束则返回步骤（4）中。

（6）计算每组偏向参数p和阻尼因子的聚类结果

（7）根据目标函数值和式（8）、（9）（10）进行移动。

（8）判断是否达到结束条件，否则转回（3）。

在步骤（2）中参数的搜索空间在文献[7]得知的下限为=1-2，1为聚类结果只有1个簇的时候的净相似度值，2为聚类结果簇为2的净相似度值。具体公式（11）、（12）所知。在文献[8]中可以得因此的上限取值为/2。阻尼因子的搜索范围为[0.5，1]。

4 实验与分析

4.1 数据源

数据源采用的是验证机器学习的标准数据库UCI。具体如表1所示。

表1 数据集

4.2 实验环境

实验环境中硬件为Intel（R） Core（TM）i7；内存为4G；软件依赖于Windows7操作系统，MATLAB R2012a。

4.3 实验方法

实验最大迭代次数为5000，连续收敛次数为50。将本文算法与原AP算法、自适应AAP从簇的个数准确率、芮氏指标、时间等方面对聚类结果进行评估。

准确率是指聚类结果中正确的样本数占总样本数的比例。为最终簇的个数，L为第个簇中正确聚类的样本数，该度量为聚类的直观展示。

（2）Rand指数（）

指数将聚类样本中的结果和外界簇划分进行对比而得到的一种结果测评。表示属于同一个簇被划分到相同的簇中的样本数；表示在聚类簇C中隶属于同一簇但在参考划分中属于不簇的样本数；表示在聚类结果中属于不同簇但在参考簇中于同一簇的样本数；表示在度量中不属于同一簇且在参考簇中也不属于同一簇的样本数。

表2 簇个数

在近邻传播聚类过程中，因为值得设定导致最终簇的数量偏多。从表2可知AP、AAP算法中产生的簇数目偏多，而FAAP因为通过萤火虫算法寻找合适的参数值所以产生适当个数的簇。

表3 聚类正确率ACC

由表3可知在ACC指标上FAAP算法相比较AP、AAP算法有一定的提升。如在Iris、Glass、Wine、Zoo据集中，FAAP算法相比较于AP算法分别提升了40.12%、37.36%、96.33%、8.9%；相较于APP算法分别提升了97.19%、29.11%、1.08倍、8.9%。

表4 聚类RI指数

由表4可知在RI指标上FAAP算法相比较AP、AAP算法有一定的提升。如在Iris、Glass、Wine、Zoo据集中，FAAP算法相比较于AP算法分别提升了9.73%、24.94%、10.47%、16.54%；相较于APP算法分别提升了20.33%、27.75%、10.73%、16.53%。

表5 聚类运行时间

由表5可知，本文算法的时间效率优于算法AP、AAP。在数据集Iris、Glass、Wine、Zoo上，FAAP算法的运算速率较AP算法分别提升了是5.5倍、3.5倍、1.64倍、3.13倍；较AAP算法也有一定程度的提升。

5 总结

本文主要是通过在偏向参数p和阻尼因子的取值范围内使用萤火虫群体智能算法FA来寻找最优参数，同时和已有的算法AP、AAP进行了对比试验，该算法在聚类质量和聚类效率上有一定的提高，但是该算法在复杂数据集上还有一定的局限性，下一步将结合特征提取工程来提高聚类质量。

[1]Frey B J，Dueck D. Clustering by passing messages between data points[J]. Science， 2007， 315（5814）：972-976.

[2]付迎丁，兰巨龙.基于核自适应的近邻传播聚类算法[J]. 计算机应用研究，2012，29（5）.

[3]谢文斌，童楠，王忠秋，等. 基于粒子群的近邻传播算法[J].计算机系统应用，2014，23（3）：103-107.

[4]Jia B，Yu B，Wu Q，et al. Adaptive affinity propagation method based on improved cuckoo search[J]. Knowledge-Based Systems，2016：111.

[5]覃华，詹娟娟，苏一丹.基于概率无向图模型的近邻传播聚类算法[J].控制与决策，2017（10）.

[6]Yang X S. Firefly Algorithms for Multimodal Optimization[J]. Mathematics，2009，5792：169-178.

[7]Yu J，Cheng Q. The upper bound of the optimal number of clusters in fuzzy clustering[J]. Science in China. Series F， 2001，44（2）：119-125.

[8]王开军，张军英，李丹，等.自适应仿射传播聚类[J].自动化学报，2007，33（12）：1242-1246.

河南省科技攻关项目（182102210114）；南阳师范学院校级科研项目（2019QN020）。