0 引言

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

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

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

1 SFCM聚类算法惩罚因子的改进 1.1 通用SFCM聚类算法

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

设X={x_i, i=1, 2, …, n}为样本集，n为X中的样本数目；V={v_j, j=1, 2, …, c}为聚类中心矩阵，c为聚类数目；U={u_ij, i=1, 2, …, n; j=1, 2, …, c}为模糊隶属度矩阵，表示X中第i个样本x_i对第j个聚类原型的隶属度，它满足以下约束条件：$u_{ij} \in \left[ {0,1} \right];\sum\limits_{i = 1}^c {{u_{ij}} = 1,\forall i;0 < \sum\limits_{i = 1}^n {{u_{ij}} < n,} } \forall j$。FCM聚类的目标函数为：

${J_m}{\rm{ = }}\sum\limits_{j = 1}^c {\sum\limits_{i = 1}^n {u_{ij}^md_{ij}^2} } $

(1)

其中:m∈[1, +∞)为模糊加权指数，d_ij=‖x_i－v_j‖为样本x_i到聚类中心v_j的欧几里得距离。通过拉格朗日(Lagrange)乘子法最小化目标函数，可得模糊隶属度和聚类中心：

${u_{ij}} = {\left[ {\sum\limits_{k = 1}^c {{{\left( {{d_{ij}}/{d_{ij}}} \right)}^{\frac{2}{{m - 1}}}}} } \right]^{ - 1}}$

(2)

${v_j} = \left( {\sum\limits_{i = 1}^n {u_{ij}^m{x_i}} } \right)/\left( {\sum\limits_{i = 1}^n {u_{ij}^m} } \right)$

(3)

由于FCM的收敛速度慢，难以满足现实需求，因此，抑制式SFCM算法在式(2)之后引入一个隶属度惩罚因子来完成对u_ij的修正，即：

对每一个样本x_i，设它对第p个聚类中心的隶属度最大，记为：

${u_{ip}} = \mathop {{\rm{max}}}\limits_{1 \le j \le c} \left\{ {{u_{ij}}} \right\}$

(4)

根据FCM的约束条件$\sum\limits_{j = 1}^c {{u_{ij}} = 1,\forall i} $，设计一个惩罚因子α(0≤α≤1)，得：

$\begin{array}{l} {u_{ip}} = 1 - \alpha \sum\limits_{j = 1,j \ne p}^c {{u_{ij}} = 1 - \alpha \left( {\sum\limits_{j = 1}^c {{u_{ij}} - {u_{ip}}} } \right) = 1 - } \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\alpha \left( {1 - {u_{ip}}} \right) = 1 - \alpha + \alpha {u_{ip}};\;\;\;{u_{ij}} = \alpha {u_{ij}},i \ne p \end{array}$

(5)

惩罚因子也叫抑制因子，是一个非常重要的参数，用来控制隶属度的修正程度。当α=0时，由式(5)可知：u_ip=1，u_ij=0(i≠p)，SFCM变为HCM；当α=1时，u_ip=u_ip，u_ij=u_ij(i≠p)，隶属度不修正，SFCM仍为传统FCM算法；当0 < α < 1时，最大隶属度u_ip增大(1－u_ip)(1－α)，而其他隶属度则减少(1－α)u_ij，从这里可以看到，引入惩罚因子后，最大隶属度增大，而其他隶属度减小，且α值越小，其抑制程度越大，导致样本x_i对第p类的聚类中心吸引力增强，而对其他聚类中心的吸引力降低，即样本向“两极”移动，从而达到了样本向聚类中心快速收敛之目的。

1.2 惩罚因子的改进

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

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

$\alpha = {u_w}{\left( {1 - {l_w}/\sum\limits_{j = 1}^c {{l_{ij}}} } \right)^2}$

(6)

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

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

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

3)由于0 < u_w≤1，当u_w→1时，其样本与聚类中心的距离l_w→0；当u_w→0，l_w→∞ (此种情况仅供理论分析，实际上不存在，因最大隶属度不可能趋近0)，因此$1 - {l_m}/\sum\limits_{j = 1}^c {{l_{ij}}} $值也在[0, 1]区间内，故式(6)中0 < α≤1，即式(6)是收敛的。

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

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

$\left| {{u_{ij}} - \frac{1}{c}\sum\limits_{j = 1}^c {{u_{ij}}} } \right| > \sigma ;\forall i,j或{u_w} > 0.5$

(7)

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

2 改进α因子的SFCM算法实现

改进惩罚因子α的SFCM聚类算法具体描述如下：

步骤1   对于给定样本集X={x₁, x₂, …, x_n}，设其初始聚类中心V^(t)={v₁, v₂, …, v_c}，c为聚类数，迭代次数t的初始值为0，最大迭代次数为T，聚类终止条件值为ε，模糊加权指数m。

步骤2   基于传统FCM聚类的求解过程，根据式(2)计算样本隶属度u_ij^(t)(i=1, 2, …, n, j=1, 2, …, c)。

步骤3   根据式(4)，找出样本x_i(i=1, …, n)对于各类的最大隶属度u_ip，并求出样本x_i对于各类的平均隶属度：$\frac{1}{c}\sum\limits_{j = 1}^c {{u_{ij}}} $。

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

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

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

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

3 实验结果分析

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

3.1 图像聚类分割实验

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

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

3.2 UCI数据集实验

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

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

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

4 结语

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