抑制式模糊C均值聚类惩罚因子的改进

肖满生 肖哲

摘要：

针对传统模糊C均值（FCM）算法在聚类过程中存在收敛速度慢、对大数据处理实时性不强等问题，提出了一种基于惩罚因子的样本隶属度改进算法。首先分析抑制式模糊C均值（SFCM）聚类特点，研究惩罚因子对样本隶属度修正的触发条件，进而设计出基于惩罚因子的SFCM聚类隶属度动态修正算法。通过算法实现样本向“两极移动”，达到快速收敛之目的。理论分析与实验结果表明，在相同的初始化条件下，改进算法的执行时间效率比传统FCM算法提高约40%，比基于优化选择的SFCM（OSSFCM）算法提高10%，其聚类准确度与其他两种算法相比也有一定的提高。

关键词：

抑制式模糊C均值；惩罚因子；模糊隶属度；快速收敛

中图分类号：

TP391.4

文献标志码：A

Abstract：

Aiming at the problem of slow convergence and weak realtime processing of large data in general Fuzzy CMeans （FCM） algorithm， an improved method of penalty factor on sample membership was proposed. Firstly， the characteristics of Suppressed Fuzzy CMeans （SFCM） clustering were analyzed， and the trigger condition for adjusting sample membership by penalty factor was studied， and then the dynamic membership adjusting scheme of SFCM based on penalty factor was designed. By using the algorithm， the samples are “moved to the poles” to achieve the purpose of rapid convergence. Theoretical analysis and experimental result show that under the same initial condition， the execution time efficiency of the improved algorithm is increased by 40% and 10% respectively compared with the traditional FCM and OptimalSelectionbased SFCM （OSSFCM）， at the same time， the clustering accuracy is also improved.

英文关键词Key words：

Suppressed Fuzzy CMeans （SFCM）； penalty factor； fuzzy membership； fast convergence

0引言

基于目标函数的模糊C均值 （Fuzzy CMeans， FCM） 聚类在20世纪七八十年代由Dunn[1]提出、并由Bezdek等[2-3]完善和发展，它是一个带约束的非线性规划过程，通过迭代优化获得样本集的模糊划分或聚类。与传统的硬C均值（Hard CMeans， HCM）聚类算法相比，FCM聚类把HCM聚类的隶属度从{0，1}二值集合扩展到了[0，1]区间，从而把非此即彼的硬聚类推广到亦此亦彼的模糊聚类，建立了样本分属于各个类的不确定性程度，因此能更客观地反映现实世界。然而，FCM聚类的一个不可忽视的缺点是算法的收敛速度慢，特别是在处理大型复杂的数据集时，其实时性不强而失去应用价值。针对这个问题，本世纪初范九伦Fan等[4]提出了一种既能体现HCM聚类的快速性、又能反映FCM聚类准确性的抑制式模糊C均值（Suppressed Fuzzy CMeans， SFCM）聚类算法，该算法基于竞争学习思想[5]，在模糊聚类迭代优化求解过程中引入惩罚因子α，通过对样本的最大隶属度进行奖励的同时对其他隶属度进行抑制，使样本快速向最大隶属度对应的聚类原型靠近，从而达到快速收敛之目的。

然而，文献[4]提出的SFCM算法在实际应用中又发现了几个问题亟待解决：一是惩罚因子α的确定问题，包括α是动态取值还是固定取值、α的取值范围、取值方法等；二是样本在什么情況下其隶属度需要修正，包括奖励或抑制，即当样本的最大隶属度为0.5左右时，或样本对任何类的隶属度近似相等，这时对隶属度的奖励或抑制也就失去了意义。针对这些问题，目前众多专家学者都在进行研究，且取得了一系列的研究成果[6-18]，如关于惩罚因子α的设计问题，台湾学者杨敏生教授及其学生等通过深入研究，给出了SFCM算法中惩罚因子α的柯西型指数固定选择公式[8-9]，并在磁共振图像（Magnetic Resonance Image， MRI）分割中进行了实验，该方法对模糊聚类收敛速度有所改进，但效果不明显；罗马尼亚和匈牙利学者Szilgyi等[6-7，12] 基于竞争学习思想，提出了7种α因子的固定设计函数，并在测试过程中与传统FCM算法进行了比较，但他们并没有给出α函数设计的理论依据和推导过程，也没有给出其设计的物理意义；Lan等[10]和兰红等[18]综合图像像素的空间信息，通过在图像聚类分割中动态设置惩罚因子来提高聚类收敛速度，对大型图像处理有一定的实际意义，但该方法仅限于灰度图像，对其他样本聚类没有意义。关于何时样本隶属度需要调整的问题，Zhao等[11]提出了一种基于图像像素灰度值的加权排名来选择样本隶属度的抑制策略，即排名靠前的样本隶属度需要修正、靠后的不修正；黄建军等[16]则在SFCM算法中引入一个抑制门限，只有超过门限值的样本最大隶属度才得以修正，其他则不修正。但这两种方法又引入了新的问题，包括排名靠前的合理比例、抑制门限值的具体选择等。此外，人们还提出了惩罚因子的其他问题与选择方法，如国内学者Li等[14]给出的基于模糊偏差的选择方法，韩国学者Nyma等[13]提出的含有模糊加权指数m的惩罚因子选取方法，孟加拉国学者Saad等[15]基于图像清晰度的抑制率选择公式等。这些方法大部分是从具体应用出发，给出了惩罚因子α的经验值，但没有合理的推导过程和依据，不具备通用性；部分只考虑了单一因素，没有综合考虑惩罚因子的设计对其他参数设置的影响，甚至惩罚因子的引入破坏了其他模糊聚类参数，使聚类有效性并没有得到实质性的提高[19]。

针对上述问题，本文在国内外研究的基础上，提出了一种SFCM聚类惩罚因子α的改进方法，综合不同样本特点来设计惩罚函数，实现模糊隶属度的动态调整；同时也给出了惩罚因子α的自动触发方法，即样本隶属度何时需要修正，从而达到SFCM聚类快速收敛之目的。

1.1通用SFCM聚类算法

SFCM聚类算法由范九伦（J. L. Fan）Fan等[4]于2003年提出，其的基本思想是基于惩罚对手的竞争机制，即假定样本对离它最近的聚类原型（具有最大隶属度）的吸引力最大，因而在每次优化迭代过程中对其隶属度进行奖励，来进一步提高样本对该聚类原型的吸引力而减小对其他聚类原型的吸引力，达到提高收敛速度之目的，同时也保证了良好的聚类精度。在SFCM迭代过程中，由于每次迭代都对隶属度进行修正，而每次修正后再求解得到的目标函数值不一定等于修正前的值，因而SFCM聚类不能使目标函数值最小化，其隶属度值的修正只能在传统模糊聚类中极小化目标函数值后所得到的隶属度的基础上进行。

1.2惩罚因子的改进

惩罚因子α在聚类中起着重要作用。但如何合理选取α值，使得算法在实际应用过程中既能保证良好的聚类精度，又能获得较快的收敛速度，上述SFCM算法中并没有具体给出，虽然目前诸多学者在此方面有过相关研究，但都存在一定的局限性（如引言中所述）；另外，一个样本（如噪声），它相对各聚类中心的隶属度基本相等，或者它对各类的隶属度都小于或等于0.5，这时如采用上述SFCM算法人为地奖励其最大隶属度，而抑制其他隶属度，使该样本强制性向“两极”运动，显然没有意义。因此，本文提出了一种惩罚因子α的改进方法，以期较好解决上述问题。

设lij表示样本xi到聚类中心vj的距离，uw为修正前样本xi对各聚类中心的最大隶属度，lw为对应的距离，根据“强者更强、弱者更弱、两极运动、中间保持”的竞争机制，惩罚因子定义为：

α=uw（1-lw/∑cj=1lij）2（6）

理论分析：在模糊聚类中，样本隶属度的大小与样本所在的位置有关，因此用于隶属度修正的惩罚因子也应当与样本的距离lij 有关。

1）当样本的最大隶属度uw（设其所在的类为p）一定时，此时lw也为定值，相对于其他聚类中心（非p），如果lij（j≠p）越大，即样本越远离该聚类中心，式（6）中α值越小，根据式（5）中的条件，其修正后的uij越小，即抑制程度越大；反之，其抑制程度越小。

2）当uw很大时，因lij（lij=lw， j=p）较小（即样本离该聚类中心很近），式（6）中α值则较大，根据式（5），修正后最大隶属度变化量为：（1-α+αuw）-uw=（1-α）（1-uw）>0，从此可以看出，由于α和uw都很大，修正后的隶属度增加不多，但uw已经足够大，再明显增加已没有意义。且uw越大，修正后的隶属度增加得越少，反之亦然。

3）由于0

结合这些分析，可以实现SFCM算法中样本隶属度根据其特点动态调整，实现样本较好分离，这样既能保证聚类的质量，又提高了聚类的收敛速度。

另外，一个噪声样本，由于它不属于任何类，因此它对各类的隶属度都很小，这样的样本，采用SFCM算法强制其靠近某类而远离其他类的意义不大；同样，如果样本的最大隶属度值不超过0.5，即：uw≤0.5，采用SFCM算法的意义也不大，因此，惩罚因子α的约束条件为：

uij-1c∑cj=1uij>σ； i， j或uw>0.5（7）

其中：c为聚类数目，σ为一设定值。式（7）表明，如果样本隶属度与其对各类的平均隶属度之差小于某一设定值或其最大隶属度小于0.5，则该样本的隶属度无需修正，反之则修正。

算法描述：

步骤1对于給定样本集X={x1，x2，…，xn}，设其初始聚类中心V（t）={v1，v2，…，vc}，c为聚类数，迭代次数t的初始值为0，最大迭代次数为T，聚类终止条件值为ε，模糊加权指数m。

步骤2基于传统FCM聚类的求解过程，根据式（2）计算样本隶属度u（t）ij （i = 1，2，…，n， j = 1，2，…，c）。

步骤3根据式（4），找出样本xi（i=1，…，n）对于各类的最大隶属度uip，并求出样本xi对于各类的平均隶属度：1c∑cj=1uij。

步骤4如果隶属度满足式（7）（此时uip即式（7）中的uw），式（7）中的σ为一定值（如σ=0.05），则用式（6）计算SFCM算法中的惩罚因子α，并将α值代入式（5）对xi隶属度进行修正；如果样本的隶属度不满足式（7），则α=1，代入式（5）后，隶属度保持原值，不修正。

步骤5根据式（3），利用修正后的隶属度，计算各类的聚类中心V（t+1）。

步骤6判断是否终止迭代，如果V（t+1）-V（t）<ε，或者t≥T，则迭代终止，输出V（t+1）；否则，t=t+1，转到步骤2，继续进行。

从上面的实现过程可以看出，在迭代过程中，相对于传统FCM聚类，样本将以更快速度向隶属度大的聚类中心“靠近”，同时也以较快的速度“远离”其他聚类中心，从而实现快速聚类，且不同的样本，其惩罚因子会随着聚类中心对它的“吸引力”大小不同而动态改变。另外，如果xi是噪声样本，则它相对于所有聚类的隶属度都很小，且各隶属度值也相差不大，根据式（7）可知，惩罚因子不起作用，其聚类过程等同于传统FCM算法。

3实验结果分析

为验证本文改进方法的有效性，本研究以图像聚类分割

及UCI数据库[20]中的相关数据集聚类划分两方面来进行实验。其中图像实验分别采用了标准测试图像以及人造含噪声的图像作为实验对象。实验环境：PC Intel Pentium CPU G3220@3.00GHz（双核），RAM 4GB，Windows 7操作系统、Matlab 7.0。同时，为了评价改进方法的聚类效果，实验中采用了传统FCM算法（General Fuzzy CMeans， GFCM）以及文献[11]中所提出的最新基于优化选择的抑制式模糊C均值聚类算法（OptimalSelectionbased Suppressed Fuzzy CMeans， OSSFCM）进行对比实验。OSSFCM方法在聚类过程中通过对最大隶属度排序，只有当样本最大隶属度超过某一门限值（如排在最前面的61.8%，黄金分割点），惩罚因子才起作用，大量的实验及应用证明，OSSFCM算法是目前最有说服力的SFCM方法之一，因此用来作为对比实验较为合适。另外，为了描述方便，本文所提出基于惩罚因子改进的抑制式模糊C均值算法简称IαSFCM（Improved the factor α in Suppressed Fuzzy CMeans）。实验中主要评价指标包括：1）运行时间（Runtime），指完成聚类迭代所需的时间，包括惩罚因子α的计算时间等，单位为s（second），但不包括图像重建等后续处理时间。2）分割精度（Segmentation Accuracy， SA），定义为：在标准测试图像聚类分割中，正确分割的像素占图像总像素的百分比；在人造样本图像中则为迭代终止后的聚类中心与原始（正确）的聚类中心的重合度，用1-vj′-vjmaxni=1（xi-vj）表示，其中vj′-vj表示算法执行后聚类中心与原始中心的距离，maxni=1（xi-vj）表示各样本与vj的最大距离，它是一个重要的图像质量评价指标。3）聚类准确度（Clustering Accuracy， CA），指正确聚类的样本数与样本集中样本总数之比。需要说明的是，FCM算法在聚类过程中对初始值的选取极为敏感，即选择不同的初始聚类中心对聚类结果（包括运行时间、分割精度及聚类准确度等）有很大影响，因此，本文在实验过程中，为了能正确比较三种算法的聚类效果，选择了同一初始聚类中心分别对三种算法进行聚类实验，至于初始聚类中心如何选取，包括自适应选取方法等问题，目前国内外已研究出了很多方法，可参考其他文献，限于篇幅，本文不再一一详述。

3.1图像聚类分割实验

采用2个图像分别进行实验，一个是标准测试图像Lena，大小为156×156像素，256级灰度，如图1（a）所示；另一个是在干净无噪声的人造样本数据集组成的图上，加上30个均匀分布的噪声点像素构成的图像，如图2（a）、（b）所示，它由一大两小三个样本子集构成（图2（a）中3个黑粗点为原始类中心，为了突出实验效果特别标出，实际不存在），其主要参数如表1所示。实验分别采用传统的GFCM、OSSFCM以及本文的IαSFCM算法進行聚类分割，每种算法各进行50次聚类取平均值，其中迭代终止阈值（两次迭代间聚类中心之差）ε=0.001，OSSFCM算法中的惩罚因子α取常规值0.5，惩罚因子α起作用分界点γ=0.618（黄金分割点，即按隶属度值大小排序，前61.8%的隶属度可用惩罚因子修正），IαSFCM中约束条件即式（7）中σ为0.01。三种算法对上述两图像聚类分割的效果如图1（b）～（d）与图2（c）所示。图3（c）中黑粗点代表原始聚类中心、“◇”代表采用经典GFCM算法聚类后得到的3个聚类中心、“（”代表采用OSSFCM算法得到的聚类中心，“*”代表采用本文IαSFCM算法得到的聚类中心，三种算法对上述两图实验测得的运行时间（Runtime）及分割精度（SA）如表2所示。

从图1（b）～（d）及表2中Lena数据可以看出，在Lena图像聚类分割实验时，三种算法的实现效果差别不大，但在运行时间上，IαSFCM算法比其他两种方法要短，GFCM运行时间最长，表明IαSFCM方法确实能提高收敛速度；同样，对比图2（c）及表2中人造样本重合度SA值的可以看出，在有噪声点存在的情况下，本文所提出的IαSFCM算法其聚类中心与原始中心的重合度最高、相应的SA值也最大，另从表2中人造样本的runtime也可以看出，IαSFCM算法运行时间比经典GFCM算法更短，与OSSFCM相比其运行时间几乎相等，这是因为在本文算法中设置的α因子约束条件对噪声样本隶属度不起作用。

3.2UCI数据集实验

本实验采用来自UCI样本库[20]的6个样本数据集Iris、Seeds、BreastCancer、Soybean、Segment以及Yeats进行实验，各数据集的基本组成如表3所示。实验方法同3.1节，即分别采用经典GFCM算法、优化选择算法OSSFCM与本文IαSFCM算法对上述6个样本集进行聚类实验，每种算法各进行50次取平均值，相关算法中的参数设置不变，本实验主要对两个聚类指标进行测定，一个是聚类的运行时间Runtime，另一个是聚类准确度和CA进行测定，各算法在实验中所得的结果如表4所示。

从表4可以看出，对于聚类准确度指标CA，三种算法对6个样本集聚类所得到的值相差不大，且其准确度都很高，表明三种算法都能很好地对真实数据集实现聚类划分；但从运行时间指标Runtime上来看，三种算法中，经典GFCM算法远大于其他两种算法，IαSFCM算法在聚类过程中，除了样本集Iris与Segment聚类，其运行时间略长于OSSFCM算法外，其他4类样本的运行时间IαSFCM比OSSFCM算法都要少。

从上述两个实验可以看出，本文提出的改进惩罚因子的SFCM算法在聚类过程中，在保证聚类质量的前提下，其运行时间更短，能更好地满足那些实时性要求很高的样本集处理，特别在含有噪声点的图像样本的聚类分割中，其具有更大的优势。

4結语

本文基于竞争学习思想，利用样本与聚类中心的关系，改进了SFCM算法中的惩罚因子，便于样本在聚类过程中根据自身特点进行隶属度的动态修正，实现快速聚类；同时在修正过程中，通过设置惩罚因子的约束条件，避免了包括噪声样本在内的隶属度较小的样本在聚类中的过度修正。多次实验结果表明，本文提出的改进惩罚因子的SFCM聚类算法在保证聚类质量的前提下，其算法的执行速度比经典的FCM算法快得多，比其他SFCM算法聚类的有效性也有较大的提高。本文的主要创新点在于：一是改进SFCM算法的惩罚因子，实现模糊隶属度在竞争修正过程中根据样本自身特点的动态调整，即怎么抑制的问题；二是给出了α参数起作用的触发条件，提出何时样本的隶属度需要抑制修正。需要指出的是，本文所提出的惩罚参数对隶属度进行修正后，其迭代终止后目标函数值是否达到最小，是否同经典FCM算法一样也会收敛到局部极值点，这些问题有待进一步研究论证。

参考文献：

[1]

DUNN J C. Wellseparated clusters and the optimal fuzzy partitions [J]. Journal of Cybernet， 1974， 4（1）： 95-104.

[2]

BEZDEK J C. Pattern Recognition with Fuzzy Objective Function Algorithms [M]. Norwell， MA： Kluwer Academic Publishers， 1981： 34-41.

[3]

BEZDEK J C， KELLER J， KRISNAPURAM R， et al. Fuzzy Models and Algorithms for Pattern Recognition and Image Processing [M]. New York： Springer， 1999： 65-69.

[4]

FAN J L， ZHEN W Z， XIE W X. Suppressed fuzzy cmeans clustering algorithm [J]. Pattern Recognition Letters， 2003， 24（9/10）： 1607-1612.

[5]

张锋，赵杰煜，朱绍军. 可区分惩罚控制竞争学习算法[J].模式识别与人工智能，2014，27（5）：426-434.（ZHANG F， ZHAO J Y， ZHU S J. Discriminative rival penalization controlled competitive learning algorithm [J]. Pattern Recognition and Artificial Intelligence， 2014， 27（5）： 426-434.）

[6]

SZILGYI L， SZILGYI S M. Generalization rules for the suppressed fuzzy cmeans clustering algorithm [J/OL]. Neurocomputing， （20140415）[20140426]. http：//www. Science direct. com/science/article/ pci/s09252312140011263.

SZILGYI L， SZILGYI S M. Generalization rules for the suppressed fuzzy cmeans clustering algorithm [J]. Neurocomputing， 2014， 139（5223）： 298-309.

[7]

SZILGYI L， SZILGYI S M， BENYZ. Analytical and numerical evaluation of the suppressed fuzzy cmeans algorithm： a study on the competition in cmeans clustering models [J]. Soft Computing， 2010， 14（5）： 495-505.

[8]

HUNG W L， YANG M S， CHEN D H. Parameter selection for suppressed fuzzy cmeans with an application to MRI segmentation [J]. Pattern Recognition Letters， 2006， 27（5）： 424-438.

[9]

HUNG W L， CHEN D H， YANG M S. Suppressed fuzzysoft learning vector quantization for MRI segmentation [J]. Artificial Intelligence in Medicine， 2011， 52（1）： 33-43.

[10]

LAN H， JIN S B . An improved suppressed FCM algorithm for image segmentation [J]. Advanced Materials Research， 2013，712/713/714/715： 2349-2353.

[11]

ZHAO F， FAN J， LIU H. Optimalselectionbased suppressed fuzzy cmeans clustering algorithm with selftuning non local spatial information for image segmentation [J] . Expert System with Applications， 2014， 41（9）： 4083-4093.

[12]

SZILGYI L， SZILGYI S M， KISS C. A generalized approach to the suppressed fuzzy cmeans algorithm [M]// TORRA V， NARUKAWA Y， DAUMAS M. Modeling Decisions for Artificial Intelligence， LNCS 6408， Berlin： Springer， 2010： 140-151.

[13]

NYMA A， KANG M， KWON Y K， et al. A hybrid technique for medical image segmentation [J]. Journal of Biomedicine and Biotechnology， 2012， 2012（4）：213-219.

[14]

LI Y， LI G. Fast fuzzy cmeans clustering algorithm with spatial constraints for image segmentation [J]. Advances in Neural Network Research and Applications， Lecture Notes in Electrical Engineering， 2010，（67）：431-438.

LI Y， LI G. Fast fuzzy cmeans clustering algorithm with spatial constraints for image segmentation [C]// Advances in Neural Network Research and Applications， Lecture Notes in Electrical Engineering 67. Berlin： Springer， 2010： 431-438.

[15]

SAAD M F， ALIMI A M. Improved modified suppressed fuzzy cmeans [C]// Proceedings of the 2010 2nd International Conference on Image Processing Theory Tools and Applications. Piscataway， NJ： IEEE， 2010： 313-318.

[16]

黃建军，谢维信.半抑制式模糊C均值聚类算法[J].中国体视学与图像分析，2004，9（2）：109-113.（HANG J J， XIE W X. Halfsuppressed fuzzy cmeans clustering algorithm [J]. Chinese Journal of Stereology and Image Analysis， 2004， 9（2）： 109-113.）

[17]

TSAI H S， HUNG W L， YANG M S. A robust kernelbased fuzzy cmeans algorithm by incorporating suppressed and magnified membership for MRI image segmentation [C]// Proceedings of the 4th International Conference of Artificial Intelligence and Computational Intelligence， LNCS 7530. Berlin： Springer， 2012： 744-754.

[18]

兰红，闵乐泉.结合邻域信息的改进抑制式FCM图像分割方法[J].电视技术，2013，37（17）：17-21.（LAN H， MIN L Q. Improved suppressed FCM algorithm for image segmentation based on neighborhood information [J]. Video Engineering， 2013， 37（17）： 17-21.）

[19]

范九伦.抑制式模糊C均值聚类研究综述[J].西安邮电大学学报，2014，19（3）：1-5.（FAN J L. A brief overview on suppressed fuzzy Cmeans clustering [J]. Journal of Xian University of Posts and Telecommunications， 2014， 19（3）： 1-5.）

[20]

BACHE K， LICHMAN M. UCI machine learning repository [EB/OL]. [20151119].