基于免疫遗传算法的模糊C均值聚类算法应用研究

李鹏松，石 卓，刘 欣

(东北电力大学理学院，吉林吉林132012)

模糊聚类算法［1］是将模糊理论应用到硬聚类算法［2］中，为分析数据提供了模糊处理能力．模糊聚类算法给出每个样本和各个类之间存在某种隶属关系，把样本对于各类的隶属度由非0即1扩展到区间［0，1］，能更有效地对各类之间有交叉的数据集聚类．由于模糊聚类算法能更准确地描述模式间的不确定关系，成为近年来研究的热点．随着模糊聚类分析的不断发展，模糊聚类技术已获得了广泛的应用．在众多模糊聚类算法中，模糊C均值聚类算法应用最广泛，模糊C均值聚类算法是一种基于划分的聚类算法，它通过优化目标函数得到每个样本点对所有类中心的隶属度，从而决定样本点的类属以达到自动对样本数据进行分类的目的．它的思想就是使得被划分到同一类的对象之间相似度尽可能大，而不同类之间的相似度尽可能小．文献［3～6］分别将其应用在煤矿生产的回采工艺选择、油气识别、图像智能识别、非规则程序划分中，取得了较好的效果．

简单遗传算法［7］是一种随机搜索的全局优化算法，以一个种群中的所有个体为对象，利用随机化技术，在一个被编码的参数空间进行搜索，寻找最优解．免疫遗传算法将免疫算法和简单遗传算法各自的优点结合起来，既保留了简单遗传算法的搜索特性，又利用了免疫算法快速收敛于全局最优解的特性，在很大程度上避免了“早熟”(过早陷入局部最优)现象．文献［8～11］针对控制参数的选取、早熟收敛问题，对免疫遗传算法进行了改进．

目前，国内外大量学者将模糊聚类算法与简单遗传算法相结合进行研究，文献［12～15］分别针对传统数据关联算法存在计算量偏大或关联精度不高的问题、逆向工程中的点云数据区域分割问题，利用简单遗传算法的全局优化特征结合模糊聚类算法的局部搜索能力提高了算法的精度和效率．将免疫遗传算法和模糊聚类算法相结合的已有研究较少，本文提出了一种基于免疫遗传算法的模糊C均值聚类算法，充分发挥模糊聚类算法的局部搜索能力强、收敛速度快的特点，同时利用免疫遗传算法的全局优化特征和自适应特性，克服了模糊聚类算法迭代时容易陷入局部极小的缺陷，极大地提高算法的精度和效率．

本文主要关注以下2个问题:

(1)提出一种基于免疫遗传算法的模糊C均值聚类算法，采用免疫遗传算法对初始聚类中心进行优化，然后执行模糊C均值聚类算法．

(2)将本文算法应用于葡萄酒及鸢尾花数据集，得出分析结果，与基于简单遗传算法的模糊C均值聚类算法的分类结果进行比较，以说明本文算法的有效性．

1 基于免疫遗传算法的模糊C均值聚类算法流程图

基于免疫遗传算法的模糊C均值聚类算法的流程图，如图1所示．

2 结果分析及比较

目标函数，即算出每个个体模糊聚类的Jb值．Jb值越小，个体的适应度值越高．参数设定如表1所示．

表1 参数设定表

2．1 葡萄酒数据集分类结果分析及比较

选取葡萄酒数据集，数据个数为178，数据维数为12．将葡萄酒数据集聚为3类，在3类样本数据中分别画上不同记号．第1类标记为圆圈(o)、第2类标记为星号(*)、第3类标记为加号(+)．

(1)基于简单遗传算法的模糊C均值聚类算法实现．

算法迭代22次，得到的最优目标函数值Jb为1．791 9．每步迭代的目标函数值，如表2所示．最终分类结果，如图2所示．

图1 基于免疫遗传算法的模糊C均值聚类算法流程图

表2 基于简单遗传算法的模糊C均值聚类算法迭代22次目标函数值变化表

(2)基于免疫遗传算法的模糊C均值聚类算法实现．

算法迭代20次，得到的最优目标函数值Jb为1．7904．每步迭代的目标函数值，如表3所示．最终分类结果，如图3所示．

表3 基于免疫遗传算法的模糊C均值聚类算法迭代20次目标函数值变化表

基于免疫遗传算法的模糊C均值聚类算法的迭代次数及最优目标函数值均较基于简单遗传算法的模糊C均值聚类算法对应的数值小．事实上，基于免疫遗传算法的模糊C均值聚类算法迭代15次的目标函数值已经优于基于简单遗传算法的模糊C均值聚类算法的最优目标函数值．

图2 基于简单遗传算法的模糊C均值聚类算法对葡萄酒数据库聚类结果展示图

图3 基于免疫遗传算法的模糊C均值聚类算法对葡萄酒数据库聚类结果展示图

2．2 鸢尾花数据集分类结果分析及比较

选取鸢尾花数据集，数据个数为150，数据维数为5．将鸢尾花数据集聚为3类，在3类样本数据中分别画上不同记号．第1类标记为圆圈(o)、第2类标记为星号(*)、第3类标记为加号(+)．

(1)基于简单遗传算法的模糊C均值聚类算法实现．

算法迭代14次，得到的最优目标函数值为Jb=0．014 877．每步迭代的目标函数值，如表4所示．最终分类结果，如图4所示．

表4 基于简单遗传算法的模糊C均值聚类算法迭代14次目标函数值变化表

(2)基于免疫遗传算法的模糊C均值聚类算法实现．

算法迭代12次，得到的最优目标函数值为Jb=0．014 845．每步迭代的目标函数值，如表5所示．最终分类结果，如图5所示．

基于免疫遗传算法的模糊C均值聚类算法的迭代次数及最优目标函数值均较基于简单遗传算法的模糊C均值聚类算法对应的数值小．事实上，基于免疫遗传算法的模糊C均值聚类算法迭代10次的目标函数值已经优于基于简单遗传算法的模糊C均值聚类算法的最优目标函数值．

图4 基于简单遗传算法的模糊C均值聚类算法对鸢尾花数据集聚类结果

图5 基于免疫遗传算法的模糊C均值聚类算法对鸢尾花数据库聚类结果

3 结 论

将模糊C均值聚类算法和免疫遗传算法相结合，能更有效地提高算法的效率，使获得全局最优解的可能性增大，克服了现有算法迭代时容易陷入局部极小的缺陷．将本文算法应用于葡萄酒和鸢尾花数据集，说明算法的有效性，实现对葡萄酒及鸢尾花数据集更客观的分类．

当数据量较大时，免疫遗传算法的优越性更加明显．其主要原因是基于免疫遗传算法的模糊C均值聚类算法在处理大规模数据时，更加容易收敛到局部最优解．

［1］ 邓冠男，宋莲莲．真域贴近模糊推理算法［J］．东北电力大学学报，2015，35(5):63－70．

［2］ 邓冠男．聚类分析中的相似度研究［J］．东北电力大学学报，2013，33(1/2):156－161．

［3］ 孙臣良，侯旭江，宛洪顺．基于模糊C－聚类分析的回采工艺选择及MATLAB实现［J］．世界科技研究与发展，2012，34(1):58－61．

［4］ 李铁军，贺建，凌立苏，等．油气识别的模糊聚类与遗传神经网络技术［J］．大庆石油地质与开发，2014，33(2):31－34．

［5］ 胡建平，李玲，谢琪，等．一种新的航拍玻璃绝缘子图像分割方法［J］．东北电力大学学报，2018，38(2):87－92．

［6］ 李远成，阴培培，赵银亮．基于模糊聚类的推测多线程划分算法［J］．计算机学报，2014，37(3):580－592．

［7］ 汪民乐．遗传算法的收敛性研究［J］．计算技术与自动化，2015，34(1):58－62．

［8］ S．Prakash，D．P．Vidyarthi．A hybrid immune genetic algorithm for scheduling in computational grid［J］．Int．J．of Bio－Inspired Computation，2014，6(6):397－408．

［9］ J．A．M．Rodríguez，F．C．M．Alanís．Binocular self－calibration performed via adaptive genetic algorithm based on laser line imaging［J］．Journal of Modern Optics，2016，63(13):1219－1232．

［10］郭惠勇，李正良．免疫遗传算法在结构损伤识别中的应用与改进［J］．土木建筑与环境工程，2012，34(2):7－26．

［11］姜萍，王培光，郝靖宇．自抗扰控制器参数的免疫遗传优化及应用［J］．控制工程，2012，19(2):286－289．

［12］ S．Wikaisuksakul．A multi－objective genetic algorithm with fuzzy c－means for automatic data clustering［J］．Applied Soft Computing Journal，2014，24:679－691．

［13］ D．D．Nguyen，L．T．Ngo，J．Watada．A genetic type－2 fuzzy C－means clustering approach to M－FISH segmentation［J］．Journal of Intelligent＆Fuzzy Systems，2014，27(6):3111－3122．

［14］胡傲，冯新喜，王冬旭，等．遗传模糊聚类算法在数据关联中的应用［J］．电光与控制，2010，17(3):30－34．

［15］李海伦，黎荣，丁国富，等．应用遗传模糊聚类实现点云数据区域分割［J］．计算机应用研究，2012，29(5):1974－1976．