最优正则化参数的核FCM聚类算法

陈书文,覃 华,苏一丹

(广西大学 计算机与电子信息学院,南宁 530004)

1 引 言

模糊C均值(FCM)是一种常用的模糊聚类算法,已被广泛应用于图像处理、地质勘探、系统辨识等领域[1-5].FCM算法的核心思想是通过极小化目标函数求最优聚类中心,但FCM算法初始聚类中心的随机选取会导致算法的聚类不稳定,每次聚类结果不尽相同,聚类准确率低,此问题称为FCM的不适定性问题(ill-posed problem)[6,7].国内外学者针对此问题展开了研究,如Honda等采用熵的正则化概念优化FCM的模糊度[8].Chang等把稀疏正则化引入到FCM的目标函数中,提高了聚类准确率[9].Yin等用最大熵作为正则化项改进FCM,提高了聚类精度[10].Ahmed等用相邻空间信息作为自适应正则化项来改进FCM,提高了FCM算法的鲁棒性,图像分割的精度也有明显提升[11].徐再花等在FCM的目标函数中引入正则化项,提高了聚类的精度和稳定性[12].Miyamoto等用二次项的正则化方法提高FCM算法的鲁棒性[13].上述文献改进FCM的共同思路是:通过在FCM的目标函数中添加正则化项,改善FCM的不适定性;但正则化参数与数据集有关,取值不当会造成正则化项效果不佳,如何为数据集确定一个最优正则化参数值得深入研究.为此,本文提出一种最优正则化参数的核FCM聚类算法(Kernel FCM Clustering Algorithm based on Optimal Regularization Parameters based,ORP-KFCM),其核心思想是:首先给出含正则化项和正则化参数的核FCM模型;然后根据L曲线法寻优正则化参数的原理,用核FCM模型构造出一个病态线性系统,依据Tikhonov正则化理论,把解此病态线性系统的问题转化为一个最小化问题,从而导出正则化参数的迭代寻优公式;用相关的迭代公式设计新的核FCM算法;最后在UCI数据集上验证所提算法的可行性和有效性.

2 核FCM正则化参数的迭代公式

样本数据集X={x1,x2,…,xn},其中n是样本个数,数据样本xi∈Rs×1,s是样本的维度.将样本数据集划分为c类,传统FCM算法的模型为:

(1)

(1)式中vj(j=1,2,…,c)是聚类中心,vj∈Rs×1,V={v1,v2,…,vc}.uij为样本xi属于第j类的适合程度(隶属度),uij∈R;m是隶属度权重系数,‖·‖是范数计算.FCM聚类算法在迭代过程中通过不断地更新聚类中心V和隶属度矩阵U,直到获得最优聚类中心.

对模型(1)引入支持向量机的核距离和正则化项,得到正则化的核FCM模型为:

(2)

‖φ(xi)-φ(vj)‖2=K(xi,xi)+K(vj,vj)-2K(xi,vj)

(3)

其中K(·)是支持向量机中的核函数,利用它来提高FCM对非线性数据特征的辨识能力,本文所用高斯核函数为:

(4)

其中σ是高斯核参数.将(4)式代入(3)式,有:

‖φ(xi)-φ(vj)‖2=2-2K(xi,vj)

(5)

将(5)代入(2),得:

(6)

为了对模型(2)中的正则化参数α寻优,对模型(2)的优化问题构造一个拉格朗日函数为:

(7)

其中λi为拉格朗日因子.在(7)式中,λi、uij和vj为待定参数.为找到待定参数的最优值,分别对这些参数求一阶偏导数并令其为零.首先将(7)式对参数uij求一阶偏导数,得:

(8)

由(8)式推出uij的迭代更新表达式为:

(9)

其次,将(7)式对参数λi求一阶偏导数,得:

(10)

将(10)代入(9)式,得出λi的迭代更新表达式为:

(11)

将(11)式代入(9)式,得隶属度的迭代更新表达式为:

(12)

最后,将(7)式对参数vj求一阶偏导数,得:

(13)

由(13)得聚类中心vj的迭代更新表达式为:

(14)

(14)式的vj与(12)式的隶属度uij有关,而uij与正则化参数α有关.因此,要提高FCM聚类算法的稳定性和聚类精度,需对正则化参数α寻优.

用L曲线法寻优正则化参数的思想可用图1描述[15].Ay=b是一个线性系统,其中y是变量,A是病态的系数矩阵,A的秩不确定;用Tikhonov正则化理论解此线性系统,可将其转化为一个最小化问题[15]:

(15)

其中正则化参数α≥0.用L曲线法寻找α最优值的过程,就是在不同的α值下,以log(‖Ay-b‖2)为横坐标,log(‖y‖2)为纵坐标,拟合一条单调下降的曲线,在曲线拐角处的α值,就是能平衡‖Ay-b‖2和‖y‖2两项的最优正则化参数值.

图1 L曲线法寻优正则化参数Fig.1 L-curve method for finding regularized parameters

为能用L曲线法获取(2)式核FCM的最优正则化参数α,令:

(16)

(17)

(18)

(19)

(20)

其中ρ′、θ′、ρ″、θ″分别是ρ(α)、θ(α)对正则化参数α的一阶、二阶偏导数,具体计算方法见文献[14,15].对(20)式求曲率函数的极大值,得到最优正则化参数α的迭代表达式为:

(21)

3 最优正则化参数的核FCM算法流程

本文所提最优正则化参数的核FCM算法流程如下:

输入:数据集X={x1,x2,…,xn}.

输出:数据集的聚类结果和划分聚类中心.

Step1.初始化聚类中心,随机选取c个数据点构成初始聚类中心V(0);

Step2.数据预处理,采用高斯滤波方法去除数据集的噪音;

Step3.构造循环,迭代以下子步骤:

Step 3.1.用式(22)计算模糊隶属度uij;

(22)

Step 3.2.用式(23)计算并更新聚类中心vj;

(23)

Step 3.3.用式(24)计算并更新正则化参数α(l+1);

(24)

Step 3.4.判断算法是否收敛.若已达到最大迭代次数或最近两次的隶属度矩阵的范数值小于阈值,则迭代结束,转Step 4;否则转至Step 3.1.

Step4.Step 3循环结束后,获得最优聚类中心,输出聚类结果及聚类中心的信息.

上述算法步骤中的若干要点说明如下:

3.1 Step 1步骤中参数初始化

算法的参数初始化设置如下:权重系数m一般设为2,初始迭代次数t= 0,正则化参数初值α(0)=1,聚类数目c、允许误差ε以及最大迭代次数T要根据数据集的类型进行适当设置.

3.2 Step 2步骤中的高斯算子

原始数据集X中可能包含噪声点,在聚类过程中会造成算法误判,影响聚类的效果.本文采用高斯滤波方法过滤数据集的噪音,高斯滤波函数为:

(25)

其中,σ是高斯算子参数.在高斯分布下导入样本数据X,根据高斯分布概率密度函数确定样本点的权重,根据各样本的权重,确定最终参与聚类的数据样本并归一化.

3.3 Step 3步骤中的迭代过程说明

Step 3是算法的核心部分.每一次循环都要先计算出各数据点属于上一轮更新的聚类中心的隶属情况,通过上一轮更新的正则化参数α1来修正隶属度uij,隶属度越大,表明该数据点属于该聚类中心所在类别的机会越大;式(23)更新计算出聚类中心V;式(24)更新计算正则化参数α.通过不断迭代更新(U,V),当目标函数达到最小值时,此时正则化参数α达到最优,所获得的聚类中心V是最优的.

3.4 算法时间复杂度分析

上述算法中的Step 1运行的时间复杂度是O(c);Step 2对数据预处理的时间复杂度是O(n);Step 3.1的时间复杂度是O(nt),其中t是该算法的迭代次数;Step 3.2的时间复杂度是O(n2t);Step 3.3的时间复杂度是O(n3t);Step 3.4的时间复杂度是O(t).Step 4的时间复杂度是O(c).综上分析,最优正则化参数的核FCM聚类算法的时间复杂度为O(c+n+nt+n2t+n3t+t+c)=O((n3+n2+n)t+n+c).由此可见,本文算法具有多项式时间的计算复杂度.

4 仿真实验与分析

4.1 实验环境

实验所用PC机硬件为:CPU Intel(R) Pentium(R) G640,主频2.8GHz;内存8GB.在Windows 7 x64平台上用Matlab R2017a实现算法.

表1是UCI测试数据集列表,高维的数据集有wine和glass,低维的数据集有Habermans(Haber)、Threecircles(Tcircles)、Spiral、Iris、User knowledge modeling(User)、Aggregation(Aggre).

表1 测试数据集

Table 1 Testing datasets

数据集名称样本总数维度类别数Haber30632Tcircles29923Spiral31223Iris15043Wine178133User40354Glass21496Aggre78827

4.2 聚类效果的评价方法

为评价所提算法的聚类效果,本文采用聚类准确率(Precision,P)和召回率(Recall,R)两个准则作为评价指标.准确率的计算公式为:

(26)

其中N是样本总数,W是聚类错误数.准确率越高,则聚类的效果越好.

召回率的计算公式为:

(27)

其中,ni是正确聚类到第i类的样本数,Ni是数据集中第i类所属样本的总数.

4.3 实验结果与分析

将本文所提算法与MATLAB R2017a工具箱自带FCM(记为FCM2017)相比较,FCM2017是传统FCM算法的最新改进版,具有较好的聚类性能.

因FCM算法存在不适定性问题,每次运算所获的聚类精度不尽相同.为评估算法的稳定性,将两种算法各运行30次,表2给出两种算法30次运行的最差聚类精度、最好聚类精度;精度偏差=(最好精度-最差精度),精度偏差值越小,表明该算法越稳定;精度偏差倍数=FCM2017精度偏差/ORP-KFCM精度偏差.由表2可知,FCM2017 的平均精度偏差比ORP-KFCM高5.8倍,本文算法的稳定性更好.例如,在Haber数据集上,FCM2017的精度偏差为12.72%,而ORP-KFCM的精度偏差为2.44%,FCM2017的精度偏差是ORP-KFCM的5.21倍.尤其在Iris和Wine两数据集上,本文算法的精度偏差均为0,即:30次运算的聚类精度完全相同,算法表现出高度的稳定性;而FCM2017的精度偏差分别是10.69%和17.71%,算法稳定性明显差于本文算法;因本文算法在该两数据集上精度偏差为0,故表2相应的精度偏差倍数栏中用符号“-”表示此时分母为零.表2的实验结果表明:在测试集上,本文算法的聚类稳定性均优于FCM2017算法,本文引入L曲线寻优正则化参数是可行的.

表2 两种算法聚类稳定性的比较

Table 2 Comparison of clustering stability of two algorithms

数据集算法最差精度(%)最好精度(%)精度偏差(%)精度偏差倍数HaberFCM201744．7457．4612．72ORP⁃KFCM64．7967．232．445．21TcirclesFCM201733．6542．899．24ORP⁃KFCM54．5655．721．167．97SpiralFCM201731．2536．545．29ORP⁃KFCM48．3749．621．254．23IrisFCM201783．8694．5510．69ORP⁃KFCM96．0596．050—WineFCM201767．8385．5417．71ORP⁃KFCM91．2691．260—UserFCM201742．0350．318．28ORP⁃KFCM63．1664．030．879．52GlassFCM201740．7245．514．79ORP⁃KFCM54．4256．311．862．58AggreFCM201759．0970．7511．66ORP⁃KFCM74．1876．202．025．77

表3是在8个测试数据集上,两种算法聚类效果的比较.由表3可知,ORP-KFCM算法的平均准确率和平均召回率比FCM2017分别提高了30.25%和33.22%.例如,在高维的Wine数据集上,ORP-KFCM的聚类准确率是91.26%,比FCM2017提高了28.83%;ORP-KFCM的召回率是91.75%,比FCM2017提高了42.42%.在低维的Spiral数据集上,ORP-KFCM的准确率是48.47%,比FCM2017提高了42.73%;ORP-KFCM的召回率是45.31%,比FCM2017提高了30.46%.表3实验结果表明:在测试集上,本文算法的准确率和召回率均优于FCM2017,本文用L曲线法寻优正则化参数还能有效地提高核FCM的聚类效果.

下页图2是本文算法在8个测试集上拟合的L曲线图及所得的最优正则化参数值.由图2可看出,不同的数据集,其L曲线形状不完全相同,但都是单调下降;并且各数据集的最优正则化参数也不相同,例如,Haber数据集的最优正则化参数是1.325e-07,而Aggre数据集的是1.0082e-01.图2说明了两点:一是最优正则化参数与数据集相关,二是本文用L曲线法寻优正则化参数时具有数据集自适应性,这意味着本文算法能应用于更广泛的场合.

表3 两种算法聚类效果的比较

Table 3 Comparison of clustering results of two algorithms

数据集指标FCM2017(%)ORP⁃KFCM(%)指标提高百分比(%)HaberPR50．2550．3266．8065．6832．9430．52TcirclesPR36．4736．8354．8762．1350．4568．69SpiralPR33．9634．7448．4745．3142．7330．46IrisPR90．2889．3396．0596．006．397．47WinePR70．8464．4291．2691．7528．8342．42UserPR49．0248．8763．9366．8030．4236．69GlassPR42．8748．3355．6761．3529．8626．94AggrePR62．3962．9274．8477．7319．9622．58

表4 不同正则化参数值对核FCM聚类精度的影响

Table 4 Influence of different regularized parameter values on Cluster FCM Clustering Accuracy

数据集 正则化参数10．10．010．0010．0001L曲线法Haber(%)51．5051．0250．0650．2350．2366．80Tcircle(%)39．5540．6736．4936．8348．6654．87Spiral(%)35．7436．7340．3236．1735．5348．47Iris(%)91．3491．6592．3393．5995．3496．06Wine(%)74．1979．3285．4688．2190．7191．26User(%)49．5952．3058．3055．6053．5063．93Glass(%)43．5645．2847．8649．6550．2355．67Aggre(%)65．3672．8268．4766．7362．3974．84

表4是在不同正则化参数值下,模型(2)核FCM聚类精度的比较.由表4可知,正则化参数取值不当,会影响核FCM的聚类精度,例如,对于Glass数据集,用L曲线法寻优正则化参数α后,核FCM聚类精度为55.67%;而当α取值为0.0001、0.001、0.01、0.1、1时,核FCM的聚类精度均低于55.67%.表4的实验结果说明:对核FCM的正则化参数寻优是必要的.

5 结 论

针对传统FCM聚类算法存在的不适定性问题,本文提出用L曲线法寻优核FCM的正则化参数.在UCI数据集上的实验结果表明,优化后的正则化参数能有效地提高核FCM算法的稳定性,算法的聚类精度亦有所改善,由此得到两个结论:一是核FCM算法的正则化参数与数据集有关,并非一个固定不变的数值,需要根据数据集而定;二是本文用L曲线法寻优核FCM正则化参数是可行的,能有效地抑制FCM的不适定性,并且该方法对数据集具有自适应性,能应用于更广泛的场合.

图2 各测试集的L曲线图及其最优正则化参数值Fig.2 L-curve and the optimal regularization parameter values of each test set