基于模拟退火的样本加权FCM算法

段林珊，刘培玉，谢方方

（1.山东师范大学 信息科学与工程学院，山东 济南250014；2.山东省分布式计算机软件新技术重点实验室，山东 济南250014）

0 引 言

聚类是人类最基本的认识活动之一，也是图像处理、模式识别、数据挖掘等众多研究领域的一项重要研究内容。所谓聚类，就是按照事物所具有的某些特征和属性，把具有相似特征和属性的事物聚集成同一类，属性特征差别大的另分一类，最终聚类结果使得各个类之间的属性和特性等相似度尽可能小，而聚类结果中已经聚好的类与类之间相似度尽可能大。聚类分析应用领域很广泛，近年来随着其不断发展，已经被卓有成效地应用在数据挖掘及分析、图像处理、模式识别等领域的聚类分析当中［1］。

传统的聚类分析，在进行聚类分类之时，会有一个明确的分类界限没有模糊性信息在其中，并且是按照事先设定好的原则和要求来将事物进行分类的，但在实际应用中，有大量的聚类问题在进行聚类分析的时候并没有完全明确的分类界限，即所谓的模棱两可，比如对移动客服回访满意程度进行评价，有非常满意、比较满意、满意、不满意等类别，诸如此类的事物，它们的特征和属性在进行分类时存在着一定的中介性和模糊不确定性，即事物之间没有明确的分类界限。

鉴于此类问题，模糊性理论由美国计算机与控制专家扎德教授提出来了，之后对于其研究迅速展开，并被应用于聚类问题，形成了模糊聚类分析方法。模糊聚类分析，就是用模糊理论对海量以及重要数据进行分析，建立样本属性类别的不确定性描述，已经被广泛并且有效地应用于海量数据挖掘、数据建模、模式识别、图像处理等重要领域 具有重要的理论与实际应用价值，完全可以比较客观地反映现实世界。随着各种应用的不断发展，由于模糊聚类算法具有广泛的适用性，因此对其研究与日俱增并取得了一定的理论成果和实践成效，其中，模糊C均值聚类［2，3］算法是目前的聚类算法当中应用领域最为广泛的，它是一种无导师即无监督学习的一种聚类算法，也是一种基于目标函数的聚类分析法［4］。已广泛应用于生命科学、医学、农业、目标识别、地理等领域。该算法针对聚类中心设定隶属度函数、目标函数和相关阈值，通过计算样本点对于各个聚类中心的隶属度函数自动对样本进行分类。

模糊C均值聚类 （FCM）算法具有应用范围广泛、使用方便、设计简单等优点，可以用于解决寻求全局最优解问题，但是它也存在不足之处：该算法无法自动确定初始聚类数，需要根据先验知识进行人为确定输入，并且在进行确定之时还没有明确的准则可以遵循，具有盲目性，这样，初始聚类数过大或过小都会影响算法产生聚类的效果；此外，传统的FCM算法忽略了不同样本分类贡献的不均衡性，把样本属性贡献视为等同的，因而可能会影响分类结果准确度。FCM的这些不足之处会使算法陷入局部最优，降低算法收敛速度。

针对上文提到的FCM的不足之处，国内外研究学者已经对其进行了相关的改进和研究，很多学者将进化理论中的思想运用到FCM中，以期得到全局最优。文献 ［5］运用人工免疫细胞模型来生成聚类初始值，文献 ［6］将遗传算法结合到FCM算法中解决局部最优问题，文献 ［7］运用粒子群优化算法解决此弊端。

本文利用模拟退火算法具有与初始值和初始状态无关以及全局最优的特点，运用模拟退火算法来确定FCM初始聚类数，并根据样本属性对分类贡献差异设定加权值，提出一种基于模拟退火算法的样本加权FCM算法 （SASWFCM），并经过实验验证了该算法的有效性和优越性。

1 模糊C均值聚类算法

模糊C均值聚类算法是根据隶属度大小来确定一个事物是否属于一个类别，与传统的没有明确分类界限的硬划分方法大不相同，它采用模糊隶属度来划分，具有比较可观的聚类效果。它是针对聚类中心设定隶属度函数、目标函数和相关阈值，通过计算样本点对于各个聚类中心的隶属度函数自动对样本进行分类。

文献 ［8］中对模糊C均值聚类算法有一个详细的描述，算法具体过程如下：假设一个样本空间为X＝｛x1，x2，……xn｝，将此样本空间X分成m类，m需是大于1的一个正整数 ，隶属度函数用一个模糊矩阵来表示，矩阵中u＝（uij），uij为第i个样本属于第j类的隶属度大小。为此定义

其中，第j个聚类的中心点用cj来表示，xi－cj称为样本xi到某一个聚类中心cj的欧式距离。从式 （1）可以分析出，如果样本点xi到第j个聚类中心的距离越近，则相对应的那个隶属度就越小，即uij越小。其中＝1，i＝1，2，3……n，j＝1，2，……m 。FCM 的目标函数F（U，c）定义为

其中b称为一个模糊度指数，随着它的数值的增大，整个聚类的模糊性就越大。从式 （2）可以看出，xi－cj如果越小，则uij就会越小，则目标函数值F就会越小。FCM聚类算法执行过程中，需要对聚类中心值进行多次尝试性修改，每一次修改后进行计算对应的目标函数值F（U，c），直至最终达到满意的聚类效果。因此，FCM算法可以称之为是一个不断优化迭代目标函数F（U，c），寻找最佳目标函数值的一个过程。在算法中需要不断修改聚类中心值，所以定义聚类中心点函数如下

根据以上描述内容，确定模糊C均值聚类算法的迭代过程如下：

步骤1 事先设定模糊度数b和一个聚类类数的初始值。

步骤2 随机性地产生m个聚类中心，其中0代表此时算法的迭代次数是0。

步骤3 根据式 （1）和每一次迭代产生的聚类中心函数来计算目标函数，再根据每一次迭代产生的隶属度函数uij，进一步更新聚类中心函数cj的值，反复进行步骤3算法过程，直至目标函数达到最终理想的目标函数最小值，或者等目标函数值达到低于预先给定的较小的一个阈值ε时再停止算法执行。

从上述算法描述可以看出，传统的模糊C均值聚类算法，设定初始簇的数目也就是聚类个数和确定模糊指数之时，并没有一个合理明确的准则可以遵循，而是需要人为或者专家根据先验知识来输入初始值，然后算法继续执行。这样处理，不可避免地会造成各种误差，会使算法收敛度和准确度受到影响，甚至使算法陷入局部最优。

同时，上述算法描述中目标函数和聚类中心函数在处理各种样本各维属性特征或者数据属性时并无区别，即将样本各属性特征或者数据属性对最终聚类结果的贡献程度视为等同的，这样处理，可能会夸大某些孤立点或者噪声数据对分类的作用，也会缩小对某些重要属性的贡献，也会导致聚类准确度有所下降。

2 基于模拟退火的样本加权FCM算法

2.1 基于模拟退火的FCM算法

模拟退火算法［9－11］是一种很好的求解大规模组合优化问题的算法，基于求解全局最优问题与物理固体退火具有相似性，该算法参数设计上采用的是物理领域的参数，假设温度T时粒子趋于平衡的概率是e－ΔE／（kT），其中，k是波尔兹曼常数，内能改变量用ΔE来表示，E代表温度T时刻的内能，该算法基于Metropolis准则，可以进行控制温度由高到低的过程，

模拟退火算法原型进行演变应用在实际问题当中时，把内能变量E模拟为求解问题当中的目标函数值f，在实际问题当中找到一个变量来对应原型当中的控制参数，即温度T，按照上述方法和过程，就可以运用模拟退火算法来解决各种大小规模的组合优化问题：在算法开始迭代时，事先确定一个初始解、确定一个控制参数的初始值记为T，然后对每一次迭代过程的当前状态解进行随机扰动，以产生一个新的解，然后计算这两次迭代最终的目标函数差值，根据此差值与预先设定的很小的阈值比较情况，再判断是否接受该新解，这样逐次进行迭代计算分析，并逐步衰减控制参数T的值，直到满足算法终止条件，再输出当前状态解为问题所寻求的最优解。

模拟退火算法是基于金属退火的机理而建立起来的一种随机算法，它能够通过控制温度的变化过程来实现大范围的粗略搜索与局部的精细搜索［12］。它是近年来发展起来的一种新的随机搜索方法，与传统随机搜索策略相比而言，它具有很多优势：第一，它在算法过程中是对每一次迭代当前状态解进行随机扰动来产生新解，并以一定的概率接受或者舍弃新解，同时模拟退火算法利用实际物理固体退火过程的自然机理进行随机搜索。这样在迭代过程中使得目标函数值变 “好”，由于模拟退火算法是在整个解的邻域范围内取值的随机性，可以避免使算法陷入局部最优解而最终获得全局最优解，使得获得全局最优解的可能性增大。第二，模拟退火算法输入输出的耦合程度较低。在利用该算法求解优化问题时，求得的最优解与算法的初始值和迭代次数无关。此外，模拟退火算法是一种具有较好的收敛性的全局优化算法，已被理论上证明，该算法收敛于全局最优解的概率可以达到 “1”［13］。

基于模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点，是用来解决大规模组合优化问题通用而又行之有效的算法之一，已经被广泛应用于大量需要优化的场合，比如决策控制、神经网络、机器学习等算法中的局部最优问题都用到了模拟退火算法。模糊C均值聚类算法实际可以看作是一个优化问题，也可以采用模拟退火算法对其进行优化。模糊C均值聚类算法需要人为根据先验知识输入初始聚类数，这样会导致结果陷入局部最优，使最终聚类效果受影响。鉴于此，本文采用模拟退火算法来求得FCM算法初始的聚类类数，改进算法的局限性，从而使算法跳出局部最优解，达到全局最优解。用模拟退火算法确定FCM聚类算法初始聚类数的具体步骤描述如下：

步骤1 假定初始目标函数值为F，FCM算法在进行聚类初始时对其聚类数目赋予一个初始解为S，每一个目标函数值F值的迭代次数记为P；

步骤2 对于r＝1，2……r，P每迭代一次都按照步骤（3）～步骤 （6）顺序执行一次；

步骤3 对每一次迭代过程中产生的解S进行随机扰动处理，产生的新的状态解记为S′；

步骤4 用当前解S作为FCM算法中的初始聚类数生成聚类中心；

步骤5 定义目标函数为

式中：vi、vj——第i类第j类的聚类中心。计算增量Δf′＝f（S′）－f（S）；

步骤6 若Δf′＞0，则将S′作为当前状态下的新解，否则 就 以e（－Δf′／F）大 小 的 概 率 接 受 S′ 作 为 当 前 状 态 下得新解；

步骤7 如果两次迭代过程中目标函数差值小于预先设定的阈值，即满足了最终算法的终止条件，则将当前状态下得解输出作为问题最终的最优解，算法结束。

2.2 样本加权FCM算法

传统的FCM算法在进行聚类分析时，把每一个样本的各种属性特征对最终聚类结果的贡献视为等同的或者均匀的，而这在实际应用中是有很大的局限性的。因为实际生活中样本各维属性特征对聚类贡献不可能等同。

传统FCM聚类算法这样处理，必然会导致有些重要的样本属性特征结构就很难被发现，另外样本中的噪声点以及孤立点对分类的贡献就被夸大化了。

为解决此问题，本文拟对FCM聚类算法中目标函数和聚类中心函数根据样本属 性特征对分类贡献程度进行合理加权处理，尽可能使得算法在分类准确数和准确度上有更大的提高。

受热力学中熵定义的启发，它是表示信息的无序度，熵值越大，信息越有效。在这里定义类似于熵的一个量Ei来衡量uij即第i个样本属于第j类的隶属度的有效度。定义权重wi来表示第i个样本点对聚类数据评价的影响和贡献程度

其中定义FCM目标函数为

聚类中心函数变为

式 （7）和式 （8）是进行加权处理后的目标函数和聚类中心函数，将其应用于FCM聚类算法中。

2.3 基于模拟退火的样本加权FCM算法

模糊C均值聚类算法初始聚类数需要人为根据先验知识确定的问题通过使用模拟退火算法来确定一个最优解，改进了算法，避免算法陷入局部最优。

对于样本或者数据的属性特征对分类贡献存在差异的问题，本文对其进行加权处理应用于模糊C均值聚类算法中。

基于模拟退火的样本加权FCM算法 （SASWFCM）的步骤描述如下：

步骤1 利用模拟退火算法按照3.1中所描述的步骤确定FCM算法中初始聚类数，初始化聚类中心、权重指数wi和阈值ε，t＝0。

步骤2 根据式 （1）计算第i个样本在第j个聚类中的隶属度函数uij。

步骤3 根据式 （8）更新聚类中心，记录t时刻的隶属度，t＝t＋1。

步骤4 根据式 （7）更新目标函数值F（U，c），如果相对于上次的目标函数值改变量小于阈值ε，则算法停止，否则转到步骤3。

该算法中阈值ε需要事先确定为很小很小的正整数。

3 实验分析

为验证本文提出的SASWFCM算法的有效性，实验采用UCI数据集作为测试对象，在Matlab实验环境下进行相关实验分析，对传统FCM算法、普通样本加权FCM算法以及本文提出的基于模拟退火的样本加权模糊－C均值聚类算法在聚类准确数和聚类准确度上进行了比较。实验结果表明本文提出的SASWFCM算法在聚类准确数和准确率上比传统FCM算法及普通样本加权FCM聚类算法都要高，具有更好的效果。

3.1 UCI数据集描述

本文是采用 UCI数据集中的Diabetes、Horse colic、Glass数据集来进行算法性能的比较。数据源信息见表1。

表1 数据源信息

3.2 UCI数据集上的实验性能比较

表2给出了在UCI的3个数据集上，模糊C－均值（fuzzy C－means，FCM）聚类算法［14］，普通样本加权 FCM聚类算法以及SASWFCM算法在聚类准确数目方面效果对比情况。

表2 FCM、样本加权FCM、SASWFCM聚类准确数比较

从表2实验结果可以看出，SASWFCM算法较之FCM以及普通样本加权FCM算法，聚类准确数目更多一些。在Diabetes数据集上SASWFCM算法的准确数531比传统FCM算法多很多，与普通样本加权FCM算法基本等同高出一点点。在Horse colic、Glass上情况也类似。

表3给出了在UCI的3个数据集上，模糊C－均值（fuzzy C－means，FCM）聚类算法，普通样本加权FCM聚类算法以及SASWFCM算法聚类准确度效果对比情况。

表3 FCM、样本加权FCM、SASWFCM聚类准确度比较

从表3实验数据可以看出本文提出的SASWFCM算法在聚类准确度方面较之FCM算法和普通样本加权FCM算法都有所提高，具有实际应用价值。

4 结束语

本文以模糊C均值聚类算法为研究背景，利用模拟退火算法实现简单、求最优解可靠性高的优点，来解决FCM初始聚类数需要根据先验知识人为确定的不足。根据不同样本对聚类贡献不等的情况，对FCM算法中目标函数和聚类中心函数进行相应合理加权处理，提出一种基于模拟退火的样本加权FCM算法 （SASWFCM）。通过相关实验分析表明该算法能够避免人为确定初始聚类数带来的误差，不会使算法陷入局部最优，且在样本正确聚类数和正确聚类度方面较传统FCM以及普通样本加权FCM算法具有一定的优越性，是一种有效地具有实际价值的聚类算法。

：

［1］LIU Qiang，XIA Shixiong，ZHOU Yong，et al.Fuzzy clustering algorithm using two methods ［J］.Application Research of Computers，2011，28 （12）：4437－4438 （in Chinese）.［刘强，夏士熊，周勇，等.基于两种加权方式的模糊聚类算法［J］.计算机应用研究，2011，28 （12）：4437－4438.］

［2］GUAN Qing，DENG Zhaohong，WANG Shitong.Improved fuzzy C－means clustering algorithm ［J］.Computer Engineering and Applications，2011，47 （10）：27－29 （in Chinese）. ［关庆，邓赵红，王士同.改进的模糊C均值聚类算法 ［J］.计算机工程与应用，2011，47 （10）：27－29.］

［3］ZENG Shan，TONG Xiaojun，SANG Nong，et al.Study of multi－prototype fuzzy C－means clustering algorithm using correspondence analysis ［J］.Huazhong University of Science and Technology （Natural Science Edition），2012，40 （2）：107－111（in Chinese）.［曾山，同小军，桑农，等.基于对应分析的冗余模糊C均值聚类算法研究 ［J］.华中科技大学学报 （自然科学版），2012，40 （2）：107－111.］

［4］HE Zhenghong，LEI Yingjie.Reaearch on intuitionistic fuzzy C－means clustering algorithm ［J］.Control and Decision，2011，26 （6）：847－850 （in Chinese）. ［贺正洪，雷英杰.直觉模糊C均值聚类算法研究 ［J］.控制与决策，2011，26（6）：847－850.］

［5］WANG Wei，WANG Lei，LI Yuxiang.Fuzzy clustering algorithm based on artificial immune cell model ［J］.Computering Engineering，2011，37 （5）：13－15 （in Chinese）. ［王伟，王磊，李玉祥.基于人工免疫细胞模型的模糊聚类算法 ［J］.计算机工程，2011，37 （5）：13－15.］

［6］HUANG Minming，LIN Bogang.Fuzzy clustering method based on genetic algorithm in intrusion detection study ［J］.Journal on Communications，2009，30 （11A）：140－145 （in Chinese）.［黄敏明，林柏钢.基于遗传算法的模糊聚类入侵检测研究 ［J］.通信学报，2009，30 （11A）：140－145.］

［7］PU Pengbo，WANG Ge，LIU Tai’an.Research of improved fuzzy C－means algorithm based on particle swarm optimization［J］.Computer Engineering and Design，2008，29 （16）：4277－4299 （in Chinese）. ［蒲蓬勃，王鸽，刘太安.基于粒子群优化的模糊C－均值聚类改进算法 ［J］.计算机工程与设计，2008，29 （16）：4277－4279.］

［8］LIU Kunpeng，LUO Ke.Improved fuzzy C－means clustering algorithm ［J］.Computer Engineering and Applications，2009，45（21）：97－98 （in Chinese）.［刘坤朋，罗可.改进的模糊 C均值聚类算法 ［J］.计算机工程与应用，2009，45 （21）：97－98.］

［9］ZHU Jingwei，RUI Ting，JIANG Xinsheng，et al.Simulated annealing ant colony algorithm for QAP ［J］.Computer Engineering and Applications，2011，47 （14）：34－36 （in Chinese）.［朱 经纬，芮挺，蒋新胜，等.模拟退火蚁群算法求解二次分配问题［J］.计算机工程与应用，2011，47 （14）：34－36.］

［10］ZHU Haodong，ZHONG Yong.An improved simulated annealing algorithm ［J］.Computer Technology and Development，2009，19 （6）：32－35 （in Chinese）. ［朱颢东，钟勇.一种改进的模拟退火算法 ［J］.计算机技术与发展，2009，19 （6）：32－35.］

［11］LI Fangfang，WANG Jing.A best clustering scheme based on simulated annealing algorithm in wireless sensor networks［J］.Chinese Journal of Sensors and Actuatorsl，2011，24（6）：900－904 （in Chinese）.［李芳芳，王靖.一种基于模拟退火算法的无线传感器网络最优簇类求解方案 ［J］.传感技术学报，2011，24 （6）：900－904.］

［12］LI Zhengwei，TAN Guojun.Research and application of improved simulated annealing genetic strategy ［J］.Computer Engineering and Applications，2010，46 （4）：245－248 （in Chinese）.［李政伟，谭国俊.改进的退火遗传优化策略应用 研 究 ［J］. 计 算 机 工 程 与 应 用，2010，46 （4）：245－248.］

［13］LIU Jia，LIU Lina，LI Jing，et al.Research of improved artificial fish swarm algorithm based on simulated annealing algorithm ［J］.Computer Simulation，2010，28 （10）：195－198（in Chinese）.［刘佳，刘丽娜，李靖，等.基于模拟退火算法的改进人工鱼群算法 ［J］.计算机仿真，2010，28（10）：195－198.］

［14］ZHANG Guosuo， ZHOU Chuangming， LEI Yingjie.Improved FCM clustering algorithm and its application in intrusion detection ［J］.Computer Applications，2009，29（5）：1336－1338 （in Chinese）. ［张国锁，周创明，雷英杰.改进FCM聚类算法及其在入侵检测中的应用 ［J］.计算机应用，2009，29 （5）：1336－1338.］