最優正則化參數的核FCM聚類算法

2018-07-27 03:28:24陳書文蘇一丹

小型微型計算機系統 2018年7期

陳書文,覃華,蘇一丹

(廣西大學計算機與電子信息學院,南寧 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的不適定性,并且該方法對數據集具有自適應性,能應用于更廣泛的場合.