基于分层遗传的新聚类算法应用于数据分类

吴盛平 马永光 庄恒悦 赵魏 常志伟

摘 要：针对FCM（模糊C均值聚类算法）对初始聚类中心的选取敏感以及梯度法易收敛到鞍点，在此基础上提出了一种分层遗传算法（HGA）优化的核模糊C均值聚类算法（HGAKFCM）来提升聚类性能，首先用分层遗传算法（HGA）在全局筛选出高品质聚类中心以替代FCM的随机产生的聚类中心，再利用高斯径向核函数改变FCM中的距离函数并且重新定义目标函数，最终根据新参数进行迭代流程。在仿真实验中用两种数据集作为实验数据，利用FCM、HGAKFCM以及其他三种聚类算法进行聚类测试，结果显示HGAKFCM在一定程度上解决了FCM的缺陷，此外将新算法与另外三种性能不错的聚类算法在抗局部收敛能力，迭代次数和精度上比较，结果显示新算法具有良好的聚类性能。

关键词：模糊C均值聚类;核模糊C均值聚类;遗传算法;分层遗传;高斯核函数;聚类中心优化

1 概述

从古至今，聚类都是一个非常有价值的问题，从某种程度上来说，聚类就是按照一定的规律来对事物进行划分的过程。Dunn[1]和Bezdek[2]提出的模糊C均值聚类算法（FCM）是一种基于目标函数的聚类算法。但是FCM算法依然存在缺点，如对初始聚类中心敏感，容易收敛到局部极值等。

为了消除FCM算法的种种缺陷，学者们从不同的方面对FCM算法进行了改进。Chen S C[34]将核化技术引入模糊C均值算法中，利用核径向函数来替代FCM中的欧氏距离函数来重新定义目标函数，提出了核模糊C均值聚类算法（KFCM），经试验证明KFCM的聚类性能确实优于FCM，但是其算法依旧沿用FCM的随机化初始聚类中心，依然对初始聚类中心敏感。文传军[5]提出了粒子群高斯诱导核模糊C均值聚类算法，利用粒子群算法在整个全局解空间寻优，避免了梯度法的局部极值陷阱，提升了聚类性能。陈书文等[6]提出了一种最优正则化参数的核FCM算法，在KFCM的目标函数中引入正则化参数，并用L曲线法更新迭代公式，取得不错的效果，但并未解决局部收敛的问题。梁冰、徐华[7]提出了一种改进的人工蜂群与KFCM算法相结合的聚类算法，旨在解决初始聚类中心敏感和局部最优陷阱问题。

在上述研究的基础之上，提出了分层遗传优化的核模糊C均值聚类算法（HGAKFCM）。HGA算法更新的初始聚類中心的目的是在一定程度上消除FCM的初始聚类中心敏感的问题，并且HGA算法具有全局寻优的特点。

2 核化距离的模糊c均值聚类（KFCM）

KFCM算法是将核函数替代FCM中的欧式近距离，得到的优化的模糊c均值聚类算法，KFCM相比FCM具有更优的性能，能达到更佳的聚类效果，在此处引入的常用的径向函数——高斯核函数，形式如式（1）：

K（xj，ci）=e-‖xj-ci‖12δ2（1）

此时的目标函数可以写成：

JKFCM（uij，ci）=2·∑Nj=1∑ki=1umij（1-K（xj，ci））∑ki=1uij=1uij∈[0，1]（2）

再通过引入拉格朗日乘数因子，得到最终的划分矩阵和群类中心更新公式：

uij=（1-K（xj，ci））-1m-1∑kl=1（1-K（xl，ci））-1m-1（3）

ci=∑Nj=1umijK（xj，ci）xj∑Nj=1umijK（xj，ci）（4）

KFCM算法与FCM算法运行流程极为相似，都是根据划分矩阵和群类中心更新公式的不断更新来寻找极小值点，算法根据式（3）、（4）不断迭代循环更新隶属度矩阵直到找到最优聚类中心，然后去模糊化得出最终的聚类结果[8]。

3 HGAKFCM算法设计

HGAKFCM算法的思路是运用分层遗传算法对KFCM的初始聚类中心进行优化，旨在改善局部收敛和对初参数敏感问题。

3.1 分层遗传简述

遗传算法是根据生物进化理论提出的一种基于种群搜索的优化算法[9]，在传统的遗传算法中，交叉、变异、选择等遗传算子作用在整个群体上，有可能是各个个体在未达到最优点之前就停留在某一局部最优点，从而产生早熟现象。为克服早熟现象，引入遗传算法中利用并行遗传算方法的思想，将群体划分为一些子群体，各子群体按一定的模式分别进行独立进化。在适当的时候，某一些子群体之间交换一些信息，这样可以维持群体的多样性，从而达到抑制早熟现象的效果，称作分层遗传算法[1011]。

3.2 HGAKFCM流程

HGAKFCM算法分为两个循环，第一个是HGA循环，目的是找到KFCM的合适的初始聚类中心。第二个是主KFCM循环，根据HGA提供的聚类中心进行接下来的聚类。HGA循环的步骤：

第一步是初始化各项初参数。

第二步是设置计数器为零并随机产生n个初始种群。

第三步是定义高低层次计数器并计算其个体的适应度函数。

第四步判断是否满足适应度条件，若满足则解码输出聚类中心，若不满足则回到第三步直到满足适应度条件。KFCM循环与FCM极度相似，反复迭代，满足迭代结果后输出结果。

4 仿真实验

为了验证HGAKFCM聚类算法的有效性，选取了来自UCI机器学习数据库的两种真实数据集进行测试，分别为Iris（鸢尾花卉数据集）、Pageblocks（页块分类数据集）。数据集的详细数据如表1所示。

实验结果及分析。通过HGA=FCM算法和FCM、FCS、KFCM、GAFCM四种算法进行比较，通过对UCI四种数据集用以上五种聚类算法进行聚类，每种算法运行20次。

FCM存在的容易陷入局部收敛的问题是直接表现为目标函数的最终值都会收敛到一个较大的数值，理想的目标函数是趋近于0的正数，在这里选取目标函数迭代曲线的最终值的大小来评估陷入局部收斂的程度，数值越小则表明在抵抗局部收敛的能力越强。图1、图2，分别为Iris、Pageblocks两种经典数据集在运行五种聚类算法的目标函数值的收敛曲线，其横坐标为迭代次数，纵坐标为目标函数值的对数。

首先，FCM与改进后的算法HGAKFCM的收敛曲线进行对比，可以通过图2直观地了解到HGAKFCM的目标函数收敛值大幅度小于FCM，这就可以得到新算法的抗局部收敛能力相较于FCM有很大提升。此外，再将新算法HGAKFCM与性能不错的三种经典算法（分别为FCS模糊子空间聚类、KFCM核模糊C均值、FCM遗传算法优化的模糊C均值）进行对比，四种算法的目标函数收敛值大小排序如下：

（1）在Iris数据集中：GAFCM>FCS>KFCM>HGAKFCM。

（2）在Pageblocks数据集中：GAFCM>KFCM>FCS>HGAKFCM。HGA算法在Iris和Pageblocks数据集中与其他三种算法排序最小，而目标函数收敛值越小，其抗局部收敛能力就越强，新算法在这四种数据集的抵抗局部收敛能力良好。

FCM算法的初始聚类中心敏感会导致各种聚类性能指标的不同程度的下降，最直接地反映在迭代次数和精度方面，新算法用分层遗传来优化初始聚类中心得到较为优质的初始聚类中心，在此选取聚类到最终结果所需的迭代次数和精度作为衡量指标，迭代次数越小和精度越高则表示新算法较好地解决了FCM初始聚类中心敏感这个问题。表2是两个数据集在测试五种聚类算法20次的迭代次数和精度数据。

HGAKFCM算法与FCM算法在迭代次数上进行了三个小方面的对比，分别是在20次实验中的最多迭代次数，最少迭代次数以及平均迭代次数，可以明显看出HGAFCM在迭代次数少于FCM，究其深层原因，HGAFCM算法用分层遗传多次迭代筛选出更加合适的初始聚类中心，从而让算法的主循环的迭代次数明显减少。在精度方面，HGAKFCM算法在两种数据集测试20次的平均精度依次为：0.9141、0.9005。FCM算法则为：0.8933、0.3573，通过对比，新算法HGAKFCM相较于FCM算法有很大的精度提升。此外，将新算法与FCS、GAFCM、KFCM三种算法在精度和迭代次数上进行对比，如表2所示，在精度上，对比四种数据集上的精度测试，HGAKFCM皆不同程度地优于其他三种算法，在迭代次数上，新算法在四种数据集上的平均迭代次数分别为：5.1、17.8，均小于其他三种算法。

结语

提出的HGAKFCM算法用分层遗传优化初始聚类中心，得到合适的初始聚类中心后，用高斯径向函数替代FCM的距离函数得到新的目标函数，通过新的目标函数进行迭代完成聚类，通过仿真实验与FCM算法对比，在一定程度上解决了FCM的局部收敛和初始聚类中心敏感问题。另外，将新算法与经典的三种聚类算法在抗局部收敛能力、迭代次数和精度三个方面进行实验比较，结果显示新算法拥有不错的性能。

参考文献：

[1]Bezdek James C.，Ehrlich Robert，Full William.FCM：The fuzzy cmeans clustering algorithm[J].Pergamon，1984，10：23.

[2]J.C.Dunn.A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact WellSeparated Clusters[J].Cybernetics and Systems，1973，3（3）：3257.

[3]Zhang D Q，Chen S C.Fuzzy clustering using kernel method[C]// International Conference on Control & Automation.IEEE，2003.

[4]Zhang D Q，Chen S C.A novel kernelized fuzzy Cmeans algorithm with application in medical image segmentation[J].Artificial Intelligence in Medicine，2004，32（1）：3750.

[5]文传军，詹永照.粒子群高斯诱导核模糊C均值聚类算法[J].科学技术与工程，2018，18（08）：7884.

[6]陈书文，覃华，苏一丹.最优正则化参数的核FCM聚类算法[J].小型微型计算机系统，2018，39（07）：15371541.

[7]梁冰，徐华.基于改进人工蜂群的核模糊聚类算法[J].计算机应用，2017，37（09）：26002604.

[8]刘奕麟，安建成.优化的核模糊C均值聚类算法[J].微电子学与计算机，2018，35（02）：7983.

[9]崔庆磊.基于多目标分层遗传算法的溢流粒度软测量[D].大连理工大学，2015.

[10]刘树荣.基于分层遗传算法的测试数据自动生成方法研究[D].北京理工大学，2015.

[11]牟威.分层遗传算法在图像模板匹配中的应用[D].北京邮电大学，2011.

作者简介：吴盛平（1996— ），男，汉族，安徽枞阳人，硕士，研究方向：模式识别。