基于相似性和距离及遗传模拟退火的自适应聚类算法*

张松兰 ，田 丽

（1.芜湖职业技术学院，安徽 芜湖 241006；2.中国科学技术大学，合肥 230026；3.安徽工程大学电气工程学院，安徽 芜湖 241000）

0 引言

在数据挖掘算法中，聚类是一种无监督学习方法，根据类内数据对象相似而类间数据对象相异的原则来归类给定的数据集合，实现聚类任务。聚类算法［1-2］主要有以下几种：1）基于划分的方法如K-means、最近邻算法、PAM算法等；2）基于密度的方法如DBSCAN；3）基于网格的方法如CLIQUE算法、STING算法、Wave-Cluster；4）基于层次的方法有自上向下的分裂聚类和自下向上的凝聚聚类算法两种。其中模糊C-均值聚类算法（Fuzzy C-Means algorithm，FCM）是应用最广泛的划分聚类算法。它在聚类算法中结合模糊数学，引入每个数据点对所有类中心的隶属度，通过优化目标函数实现对样本数据的分类。但模糊C-均值聚类是种局部搜索方法，其聚类结果受初始聚类中心选择的影响较大，如果不慎选择到异常点或噪声点，聚类过程收敛很慢会得到较差甚至错误的聚类结果。

针对FCM易陷入局部极小值的缺点，文献［3］在传统FCM算法中加入指数权值，并用两个数据集进行了验证，仿真结果说明其有效提高聚类效果并加快聚类过程。已有研究者将智能算法［4-5］引入FCM中进行全局搜索寻找最优解，文献［6］杨凯，蒋华伟将具有全局寻优的遗传算法与FCM相结合，利用遗传算法寻找到全局最优解的聚类中心，提高了算法的稳定性和有效性。文献［7-8］利用粒子群算法对初始聚类中心和FCM参数进行优化，并在人工数据集和标准UCI数据集上进行了验证。这些优化FCM的聚类算法都是从聚类的过程及初始聚类中心的角度进行寻优，但对聚类的另一个重要参数聚类数并未提及，本文在已有研究基础上将距离和数据点间的相关性度量引进聚类数目的确定中，并用遗传模拟退火优化FCM算法实现聚类过程的全局搜索，加快聚类收敛到全局解。

1 基于相似性和距离的聚类数确定

FCM算法中聚类中心的选取是建立在聚类数已知的基础上，而聚类数目和聚类中心［9］的确定是整个聚类过程的前提和关键，对聚类过程至关重要。聚类过程是将数据集中相似性大的数据聚集在一个类中，而将相异性大的数据分开来完成聚类的目的。聚类数目的确定方法有局部法和全局法［10］。局部法需要对不同类数据进行合并或拆分判断，聚类过程比较繁琐；而全局法据聚类指标和聚类结果人工确定聚类数，工作量受数据量影响大。本文结合两种方法采用一种基于相似度量和距离的确定方法，首先计算出数据点间的距离和相似矩阵，对数据进行预判断，最后根据性能指标是否达到要求确定最终聚类数，如果性能指标达到要求，则聚类过程结束。由于相似性和距离的计算大多文献已有描述，此处不再赘述。下面介绍算法：对于给定n个数据对象的数据集 X={x1，x2，…，xi，…，xn}，数据对象的属性个数为s。

1）由于数据属性差异可能很大，首先进行数据预处理，包括属性类别和标准化处理等；

2）进行数据集中数据对象的统计分析；

3）计算任意两个数据对象之间的距离dij（xi，xj）；

4）计算数据集中数据对象之间的相似性矩阵sim（xi，xj）；

5）根据统计结果预设距离阈值和相似度参数确定聚类数。

2 基于遗传模拟退火的模糊聚类算法

2.1 模糊C-均值聚类算法

设给定数据集为，X={x1，x2，…，xi，…，xn}，V={v1，v2，…，vi，…，vn}为 c 个类别的聚类中心，FCM 目标函数［11］为

式中，m为加权参数，取值范围是1≤m≤∞，dik为第i个数据对象到第k个聚类中心的距离，uik为第i个数据对象属于第k类的隶属度，uik∈［0，1］且满足条件

隶属度函数和聚类中心的计算公式如式（3）和式（4）所示。

FCM算法就是改变uik和vk，不断迭代使目标函数达到最小值。

2.2 遗传模拟退火算法

2.2.1 模拟退火算法

模拟退火算法是根据固体加热和冷却过程中分子运动状态由无序变为有序的过程，在每个温度都达到平衡态，最后在常温时达到基态，内能变为最小。在实际问题中通过将内能表示为目标函数值，控制参数用温度表示，从而抽象出一种优化算法。

模拟退火算法步骤：1）选定初始化状态S0，设定初始温度T，循环变量i=0；2）设T=Ti，计算当前温度所处能量较低的状态S；3）按照一定的方式降温到Ti+1，循环变量i=i+1；4）检查终止条件，若满足转到步骤5），否则返回步骤2）；5）输出最优解。

2.2.2 遗传算法

遗传算法是一种借鉴生物界“适者生存”现象发展起来的全局优化方法，通过对多个个体组成的种群进行选择、交叉和变异操作逐步逼近最优解。选择操作据适应度大小将父代群体中的优秀个体保存到下一代，有利于提高计算效率；交叉操作配对的两个个体之间交换遗传物质，变异操作则是对遗传物质的变化，这两种操作都会产生新个体防止算法收敛至局部解。

1）编码方法及初始种群

遗传算法中编码方式［12-13］有二进制编码和浮点数编码，优化目标有聚类中心和聚类数。本文采用基于聚类中心的二进制编码实现c个聚类中心的优化，每个变量使用10位二进制编码。将各个类别的中心编码为染色体，每条染色体由c个聚类中心组成，重复构建多条染色体组成初始种群，染色体的条数即为种群大小。

2）选择算子

选择算子采用随机遍历抽样方法，根据个体适应度之间大小关系进行选择，每次随机从几个个体中选取适应度最高的一个个体遗传到下一代群体中，从而保留上一代中优秀的遗传物质部分，由于是随机选择扩大了下一代个体的搜索范围。

3）交叉算子

交叉算子有单点交叉、多点交叉、均匀交叉和算术交叉几种。多点交叉可能会破坏群体中好的模式，算术交叉用于浮点数编码方式。本文交叉操作采用单点交叉，在个体编码串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。

4）变异算子

变异算子有基本位变异、均匀变异、非均匀变异、边界变异、高斯近似变异。均匀变异适用于遗传算法的初级运行阶段，边界变异用于最优点位于或接近于可行解的边界时的情况。高斯变异主要搜索局部区域。因此，本文采用基本位变异。对个体编码串中以变异概率［14］、随机指定的某一位或某几位基因座上的值作变异运算。

5）适应度函数

对于FCM算法，其最优聚类结果对应目标函数的最小值，即聚类效果越好，则目标函数越小，而此时适应度应越大。此处，个体的适应度函数使用FCM算法的目标函数Jb。

综上所述，得到本文算法的流程图［15］如图1所示。首先调用基于相似度量和距离的聚类数程序获取聚类数，然后运行遗传模拟退火算法优化FCM的聚类中心，完成聚类过程。如果运行结果达不到性能要求，返回重新更新聚类数程序，直到聚类结束。

3 仿真实验

3.1 人工数据集

本文以人工数据集和标准UCI两类数据集进行实验验证，以实验结果来分析算法性能。其中两个人工数据集为不带噪声的两类无交叉的随机数据和带噪声的两类无交叉的随机数据。人工数据集如图2所示，仿真结果表明两个数据集能得到两个准确的聚类簇，其中带噪声的数据集由于在聚类数确定程序中采用的是基于距离和相似度的方法，两个噪声点距右上方的簇距离较近，将其归类到附近的第2类中。

3.2 标准数据集

标准UCI数据集采用通用的iris数据集，该数据集样本共150个，每类均为50个，属性数为4，3类样本的平均中心分别为（5.006 0 3.418 0 1.464 0 0.244 0）；（5.936 0 2.770 0 4.260 0 1.326 0）；（6.570 6 2.970 6 5.523 5 2.011 8）。分别采用 FCM和本文算法两种方法进行仿真实验，结果如下页表1和表2所示。

从表1看出FCM算法随着迭代次数的增加，聚类中心逐渐趋于稳定，目标函数值由3次迭代的71.954 2降到12次迭代的29.114 1，开始阶段收敛较快，后期收敛较慢。而对本文算法在3次迭代时为29.116 9，5次迭代运算时为29.110 4，从聚类中心来看，3次迭代的聚类中心与5次迭代的聚类中心也较为接近，稍有差别在于遗传算法中交叉和变异产生新个体对聚类中心产生比较小的影响，但从全局角度来看仿真结果的稳定性比较好，在迭代次数较小的情况下达到全局最优，说明了本文算法具有较强的全局收敛性能。

表1 两种算法聚类结果比较

表2 两种算法聚类结果比较

从表2结果来看FCM在迭代次数为3时，聚类的准确率为76.84%，准确率较低，随着迭代次数的增加，聚类中心趋于稳定，准确率逐渐提高。而本文提出的算法中在迭代次数为3时即达到90%，准确率比较高，与标准数据集相比较，第1类数据对象聚类完全正确，其相似度均在0.95以上，出现误分的数据对象主要在第2类和第3类间有少量数据存在重叠，这从第1节中相似性度量中也可看出（由于相似矩阵比较大，前文中未给出此矩阵）。

4 结论

本文以人工数据集和标准数据集为实验数据，所用数据量不是太大，对于大数据集应用本算法时相似矩阵比较大，计算耗时量较大。本文中的数据均为同属性的数据，如果数据集中有不同属性的数据首先要进行数据预处理。本文对FCM算法聚类数需事先确定的问题采用了基于距离和相似性度量的方法，避免了逐个试算聚类数而产生大量的工作量和计算时间问题，对FCM聚类中心随机选择产生聚类结果不稳问题，采用遗传模拟退火算法对标准UCI数据集进行仿真搜索聚类中心，加快了搜索过程，充分发挥了遗传算法的快速全局搜索性能和模拟退火算法的局部搜索能力。

［1］汪中，刘贵全，陈恩红.一种优化初始中心点的K-means算法［J］.模式识别与人工智能，2009，22（2）：299-304.

［2］李家成，苏一丹，覃华，等.基于遗传算法的K调和均值聚类算法［J］.计算机技术与发展，2013，23（9）：55-58.

［3］TANG C L，WANG S G，XU W.New fuzzy c-means clustering model based on the data weighted approach［J］.Data&Knowledge Engineering，2010，69：881-890.

［4］WONG A K C，LI G C L.Simultaneous pattern and data clustering for pattern cluster analysis［J］.IEEE Transaction on Knowledge and Data Engineering，2008，20：911-923.

［5］KUMAR M，VERMA S，SINGH P P.Data clustering in sensor networks using ART［C］//Wireless Communication and Sensor Networks（WCSN08），2009：51-56.

［6］杨凯，蒋华伟.模糊C均值聚类图像分割的改进遗传算法研究［J］.计算机工程与应用，2009，45（33）：179-182.

［7］王纵虎，刘志镜，陈东辉.基于粒子群优化的模糊C-均值聚类算法研究［J］.计算机科学，2012，39（9）：166-169.

［8］蒲蓬勃，王鸽，刘太安.基于粒子群优化的模糊C-均值聚类改进算法 ［J］.计算机工程与设计，2008，29（16）：4277-4279.

［9］王泽，张宏军，张睿，等.基于遗传算法与密度及距离计算的 聚 类 方 法 ［J］. 计 算 机 应 用 ，2015，35（11）：3243-3246，3251.

［10］何宏，谭永红.一种基于动态遗传算法的聚类新方法［J］.电子学报，2012，40（2）：254-259.

［11］刘庆华，周帏，何仁，等.基于优化模糊C均值聚类算法的路面不平度识别［J］.农业工程学报，2014，30（22）：195-200.

［12］何东晓，周栩，王佐，等.复杂网络社区挖掘—基于聚类融 合 的 遗 传 算 法 ［J］.自 动 化 学 报 ，2010，36（8）：1160-1170.

［13］赖玉霞，刘建平，杨国兴.基于遗传算法的K均值聚类分析［J］.计算机工程，2008，34（20）：200-202.

［14］黄毅成，杨洪耕.改进遗传K均值算法在负荷特性分类的应用［J］. 电力系统及其自动化学报，2014，26（7）：70-75.

［15］李泓泽，郭森，王宝.基于遗传改进蚁群聚类算法的电力客户价值评价［J］.电网技术，2012，36（12）：256-261.