基于分层遗传的新聚类算法应用于数据分类
来源:用户上传
作者:吴盛平 马永光 庄恒悦 赵魏 常志伟
摘要：针对FCM（模糊C均值聚类算法）对初始聚类中心的选取敏感以及梯度法易收敛到鞍点，在此基础上提出了一种分层遗传算法（HGA）优化的核模糊C均值聚类算法（HGAKFCM）来提升聚类性能，首先用分层遗传算法（HGA）在全局筛选出高品质聚类中心以替代FCM的随机产生的聚类中心，再利用高斯径向核函数改变FCM中的距离函数并且重新定义目标函数，最终根据新参数进行迭代流程。在仿真实验中用两种数据集作为实验数据，利用FCM、HGAKFCM以及其他三种聚类算法进行聚类测试，结果显示HGAKFCM在一定程度上解决了FCM的缺陷，此外将新算法与另外三种性能不错的聚类算法在抗局部收敛能力，迭代次数和精度上比较，结果显示新算法具有良好的聚类性能。
关键词：模糊C均值聚类;核模糊C均值聚类;遗传算法;分层遗传;高斯核函数;聚类中心优化
1概述
从古至今，聚类都是一个非常有价值的问题，从某种程度上来说，聚类就是按照一定的规律来对事物进行划分的过程。Dunn[1]和Bezdek[2]提出的模糊C均值聚类算法（FCM）是一种基于目标函数的聚类算法。但是FCM算法依然存在缺点，如对初始聚类中心敏感，容易收敛到局部极值等。
为了消除FCM算法的种种缺陷，学者们从不同的方面对FCM算法进行了改进。ChenSC[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]。
3HGAKFCM算法设计
HGAKFCM算法的思路是运用分层遗传算法对KFCM的初始聚类中心进行优化，旨在改善局部收敛和对初参数敏感问题。
3.1分层遗传简述
遗传算法是根据生物进化理论提出的一种基于种群搜索的优化算法[9]，在传统的遗传算法中，交叉、变异、选择等遗传算子作用在整个群体上，有可能是各个个体在未达到最优点之前就停留在某一局部最优点，从而产生早熟现象。为克服早熟现象，引入遗传算法中利用并行遗传算方法的思想，将群体划分为一些子群体，各子群体按一定的模式分别进行独立进化。在适当的时候，某一些子群体之间交换一些信息，这样可以维持群体的多样性，从而达到抑制早熟现象的效果，称作分层遗传算法[1011]。
3.2HGAKFCM流程
HGAKFCM算法分为两个循环，第一个是HGA循环，目的是找到KFCM的合适的初始聚类中心。第二个是主KFCM循环，根据HGA提供的聚类中心进行接下来的聚类。HGA循环的步骤：
第一步是初始化各项初参数。
第二步是设置计数器为零并随机产生n个初始种群。
第三步是定义高低层次计数器并计算其个体的适应度函数。
第四步判断是否满足适应度条件，若满足则解码输出聚类中心，若不满足则回到第三步直到满足适应度条件。KFCM循环与FCM极度相似，反复迭代，满足迭代结果后输出结果。
4仿真实验
为了验证HGAKFCM聚类算法的有效性，选取了来自UCI机器学习数据库的两种真实数据集进行测试，分别为Iris（鸢尾花卉数据集）、Pageblocks（页块分类数据集）。数据集的详细数据如表1所示。
转载注明来源:https://www.xzbu.com/1/view-15424546.htm
