基于粒子群優(yōu)化的馬氏距離模糊聚類算法

祖志文，李 秦

(蘭州交通大學(xué) 數(shù)理學(xué)院，蘭州 730070)

0 引 言

模糊聚類是通過建立數(shù)據(jù)樣本對類別的不確定性進(jìn)行描述，表達(dá)樣本類屬的模糊性，該方法能夠更客觀地反應(yīng)現(xiàn)實世界，具有較強(qiáng)的聚類效果與數(shù)據(jù)表達(dá)能力。模糊c均值聚類算法(fuzzy c-means algorithm，F(xiàn)CM)是經(jīng)典的模糊聚類算法，馬氏距離的模糊聚類算法(fuzzy c-means algorithm based on Mahalanobis distance，M-FCM)是將FCM中的歐氏距離用馬氏距離替代，二者均是爬山迭代算法，對初始劃分都比較敏感，容易陷入局部極值點，將粒子群算法(particle swarm optimization，PSO)與模糊聚類算法結(jié)合可有效實現(xiàn)對模糊聚類算法的優(yōu)化。如文獻(xiàn)[1]將PSO算法和FCM相結(jié)合，提出了一種新的模糊聚類算法PSO-FCM。文獻(xiàn)[2]利用模糊系統(tǒng)對PSO算法進(jìn)行改進(jìn)后與FCM結(jié)合，實現(xiàn)全局最優(yōu)。文獻(xiàn)[3]設(shè)計結(jié)合類內(nèi)緊致性和類間分離度的適應(yīng)度函數(shù)改進(jìn)PSO算法，提出改進(jìn)的模糊聚類算法(Importance for fuzzy clustering algorithm based on particle swarm optimization，IFPSOFCM)。文獻(xiàn)[4]提出了2種將PSO算法與FCM算法混合的優(yōu)化算法來解決FCM算法的缺陷。文獻(xiàn)[5]提出了基于粒子群優(yōu)化的自適應(yīng)神經(jīng)模糊推理系統(tǒng)的信道均衡器。文獻(xiàn)[6]設(shè)計了一種利用局部空間信息和偏差校正的目標(biāo)函數(shù)進(jìn)行模糊熵聚類，再通過改進(jìn)的粒子群算法進(jìn)行優(yōu)化，使得算法具有新的適應(yīng)性能。

本文將基于粒子群算法對馬氏距離模糊聚類進(jìn)行優(yōu)化，構(gòu)造新的粒子適應(yīng)度函數(shù)，提出一種基于粒子群優(yōu)化的馬氏距離模糊聚類算法(Mahalanobis distance fuzzy clustering algorithm based on particle swarm optimization，DPSOM-FCM)。

1 基于馬氏距離的模糊聚類算法M-FCM

將FCM算法中的歐氏距離用馬氏距離代替，可以消除量綱不同對聚類分析的影響，排除變量之間相關(guān)性的干擾，便于處理復(fù)雜的多維數(shù)據(jù)[7]。

FCM算法的優(yōu)化目標(biāo)函數(shù)為

(1)

i=1,2,…,c;j=1,2,…,n)

(2)

最小化J，對ci,uij,Σi求偏導(dǎo)，令其結(jié)果為零可得

(i=1,2,…,c;j=1,2,…,n)

(3)

(4)

(5)

M-FCM算法描述如下。

初始化：給定聚類類別數(shù)c，2≤c≤n，n是數(shù)據(jù)個數(shù)，設(shè)定迭代閾值ε=1×10-5，取一般值m=2，初始化聚類中心矩陣C(0)，設(shè)置迭代計數(shù)器L=0。

步驟1用(3)式計算或更新隸屬度矩陣U(L)。

步驟2用(4)式更新聚類中心矩陣C(L+1)。

步驟3如果‖C(L)-C(L+1)‖<ε，則算法停止并輸出隸屬度矩陣U和聚類中心C，否則令L=L+1，轉(zhuǎn)向步驟1。其中，‖?‖為合適的矩陣范數(shù)。

2 粒子群算法(PSO)

粒子群算法PSO由Eberhart和Kennedy受鳥群覓食行為的啟發(fā)于1995年提出[8]。通常，粒子群算法的數(shù)學(xué)描述為：設(shè)在一個D維空間中，由N個粒子組成的種群X={S1,…,Si,…,SN}，其中，第i個粒子Si的位置為xi=(xi1,xi2,…,xiD)′，其速度為vi=(vi1,vi2,…,viD)′。它的個體極值為pb=(pi1,pi2,…,piD)′，種群的全局極值為pg=(pg1,pg2,…,pgD)′，為追隨當(dāng)前最優(yōu)粒子，粒子xi將按照(6)式、(7)式改變自己的速度和位置。粒子在解空間內(nèi)不斷跟蹤個體極值與全局極值進(jìn)行搜索，直到達(dá)到規(guī)定的迭代次數(shù)或滿足規(guī)定的誤差為止。

vij(t+1)=wvij(t)+c1r1(t)(pij(t)-xij(t))+c2r2(t)(pgi(t)-xij(t))

(6)

xij(t+1)=xij(t)+vij(t+1)

(7)

(6)—(7)式中：j=1,2,…,D；i=1,2,…,N；N為種群規(guī)模；t為當(dāng)前進(jìn)化代數(shù)；w為1998年Eberhart和Shi引入到PSO算法速度項中的系數(shù)[9]，即慣性權(quán)重；r1,r2為分布于[0,1]的隨機(jī)數(shù)；c1,c2為加速系數(shù)[10]。

在粒子群算法中，粒子的優(yōu)劣好壞需要適應(yīng)度函數(shù)來進(jìn)行評價，根據(jù)適應(yīng)度函數(shù)值即適應(yīng)值尋找粒子的狀態(tài)極值，對粒子進(jìn)行選擇，優(yōu)勝劣汰，從而更新其他粒子的狀態(tài)。粒子的適應(yīng)值越大，即該粒子的質(zhì)量越好，越適應(yīng)目標(biāo)函數(shù)所定義的生存環(huán)境。

3 利用粒子群優(yōu)化馬氏距離模糊聚類算法

3.1 算法思想

如前所述，M-FCM算法由于使用梯度迭代法尋找最優(yōu)解，存在對初始值敏感和容易陷入局部最優(yōu)解的缺陷，為此將粒子群算法加入到M-FCM算法中。本文提出的基于粒子群優(yōu)化的馬氏距離模糊聚類算法的設(shè)計思想如下。

1)為尋找最優(yōu)聚類結(jié)果，即確定合理的聚類中心，選取聚類中心作為種群中的粒子，一個粒子表示一種聚類劃分的情況，粒子的每一維表示聚類一個簇的質(zhì)心，最優(yōu)聚類中心即最優(yōu)粒子。

2)對于粒子的評價，為使好的模糊聚類劃分使類內(nèi)樣本盡可能地緊湊、類與類之間盡可能地分離，并且模糊聚類劃分盡可能地清晰，本文從類內(nèi)緊致度、類間分離度與類間清晰度的角度綜合考慮，設(shè)計適應(yīng)度函數(shù)為

fitness(xi)=α·compact(U,C,Σi)+

(8)

(8)式中：α(0<α<1)為適應(yīng)度函數(shù)系數(shù)；(8)式等號右邊第1項為衡量目標(biāo)的類內(nèi)緊致度函數(shù)，第2項為衡量目標(biāo)的類間分離度函數(shù)，第3項為衡量目標(biāo)的類間清晰度函數(shù)。用目標(biāo)函數(shù)的均值來衡量類內(nèi)緊致度，目標(biāo)函數(shù)越小緊致度越佳。

(i=1,2,…,c;j=1,2,…,n)

(9)

用類間聚類中心的總距離來定義類間分離度，分離度大的數(shù)據(jù)傾向于不同的類別屬性，記Dik為群體最優(yōu)位置粒子的內(nèi)部距離，即最優(yōu)聚類中心距，當(dāng)separate(Si)越大時，類間分離程度越好。

(i,k=1,2,…,c)

(10)

把各個類內(nèi)最大模糊隸屬度值的均值作為衡量類間的清晰度

(i=1,2,…,c;j=1,2,…,n)，

(11)

當(dāng)definite(U)越小時，模糊聚類劃分結(jié)果越清晰。綜上，fitness(xi)的值越小，說明樣本集的類內(nèi)緊致程度越高、類間分離程度越大、類間清晰程度越明顯，即fitness(xi)的值越小，粒子越好。

另外，算法終止條件為以下2種情況：①最優(yōu)解對應(yīng)的目標(biāo)值保持不變或變動小于閾值ε；②迭代次數(shù)已達(dá)到設(shè)定的最大次數(shù)itermax。滿足任一種情況算法終止。

3.2 算法步驟

把基于粒子群優(yōu)化的馬氏距離模糊聚類算法記為DPSOM-FCM，算法具體步驟如下。

輸入：數(shù)據(jù)集、類別數(shù)。

1)算法參數(shù)設(shè)置，包括算法最大迭代次數(shù)itermax、最小閥值ε，模糊加權(quán)參數(shù)m，粒子種群大小N，粒子速度更新公式中的加速系數(shù)c1,c2及線性遞減的慣性權(quán)重參數(shù)wmax,wmin，適應(yīng)度函數(shù)系數(shù)α。

2)對粒子編碼，設(shè)置粒子的初始位置x0和初始速度v0，初始化模糊聚類的隸屬矩陣U0和聚類中心C0。

3)設(shè)置每個粒子的pb0,pg0，計算粒子的適應(yīng)值fitness0，并儲存。

4)進(jìn)行迭代，由M-FCM算法更新隸屬度矩陣U和聚類中心C。

5)計算慣性權(quán)重w。

6)更新每個粒子的速度和位置vi,xi。

7)計算每個粒子的pb,pg。

8)更新粒子的適應(yīng)值fitness，并儲存。

9)對于每個粒子，將其適應(yīng)度值與所經(jīng)歷過的最優(yōu)位置pb的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前的個體最優(yōu)位置。

10)對于每個粒子，將其適應(yīng)值與全局經(jīng)歷過的最優(yōu)位置pg的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前全局最優(yōu)位置。

11)如果全局最優(yōu)位置適應(yīng)值相對上次的改變量小于特定的最小閥值ε或達(dá)到最大迭代次數(shù)，則結(jié)束，否則轉(zhuǎn)向步驟4)。

輸出：最優(yōu)聚類中心及適應(yīng)值。

4 實驗結(jié)果與分析

為驗證本文提出的基于粒子群優(yōu)化的馬氏距離模糊聚類算法DPSOM-FCM的收斂性和聚類能力，采用來自UCI數(shù)據(jù)庫中的6個數(shù)據(jù)集進(jìn)行仿真實驗。實驗數(shù)據(jù)集的構(gòu)成介紹如表1所示。在各數(shù)據(jù)集上DPSOM-FCM算法的適應(yīng)值變化如圖1所示。將DPSOM-FCM算法與FCM，M-FCM算法及文獻(xiàn)[1]中PSO-FCM與文獻(xiàn)[3]中IFPSOFCM算法進(jìn)行聚類有效性和聚類準(zhǔn)確性對比分析，實驗結(jié)果如表2、表3所示。其中，選取的有效性指標(biāo)[3]為常用有效性指標(biāo)PC(partition coefficient)，MPC(my partition coefficient)，PE(partition entropy)，F(xiàn)S(Fukuyama and Sugeno)。

圖1 各數(shù)據(jù)集上DPSOM-FCM算法的適應(yīng)值變化Fig.1 Fitness function value changes of DPSOM-FCMalgorithm on each data set

數(shù)據(jù)集數(shù)據(jù)含量類別數(shù)屬性維數(shù)Iris15034Wine178313Glass21469Heart Disease270213Pima76828Car Evaluation172846

實驗環(huán)境為電腦系統(tǒng)Inter Pentium處理器，型號為 B960，頻率為2.20 GHz，4.00 GB內(nèi)存，運行均用Matlab語言實現(xiàn)。實驗參數(shù)設(shè)置為：N=20,c1=c2=m=2,wmax=0.9,wmin=0.4,α=0.6，算法最大迭代次數(shù)為100次，最小閥值為1×10-5，進(jìn)行重復(fù)聚類實驗20次，實驗結(jié)果取均值。

表2 5個算法的聚類有效性對比

續(xù)表2

表3 5個算法的聚類準(zhǔn)確性對比

續(xù)表3

實驗分析：由圖1可知，DPSOM-FCM算法在6個數(shù)據(jù)集上收斂且速度較快。由于有效性指標(biāo)PC與MPC越大、PE與FS越小,聚類越有效，故由表2得出DPSOM-FCM算法具有優(yōu)于其他算法的類間分離性和類內(nèi)緊湊性，可以證明在基于粒子群優(yōu)化的模糊聚類中，本文構(gòu)造的適應(yīng)度函數(shù)有助于算法尋找最優(yōu)聚類粒子。另一方面，由表3可知：①經(jīng)過粒子群優(yōu)化的PSO-FCM，IFPSOFCM和DPSOM-FCM算法聚類精度普遍高于未經(jīng)過優(yōu)化的FCM，M-FCM算法，即結(jié)合粒子群算法的模糊聚類具有全局尋優(yōu)性，聚類更加準(zhǔn)確，起到了對模糊聚類的優(yōu)化作用；②在Iris與Car Evaluation數(shù)據(jù)集上，F(xiàn)CM耗時最短，DPSOM-FCM耗時最長但精度高；在3組高維數(shù)據(jù)集Wine，Glass，Heart Disease上，PSO-FCM耗時最短但聚類精度不穩(wěn)定，DPSOM-FCM的聚類誤分個數(shù)明顯減少，且聚類精度高于PSO-FCM和IFPSOFCM算法；在類間相互交疊的數(shù)據(jù)集Pima上，M-FCM與DPSOM-FCM算法聚類精度都高于其他算法。這說明對于高維復(fù)雜數(shù)據(jù)集，基于粒子群算法以馬氏距離為度量的模糊聚類效果優(yōu)于以歐氏距離為度量的模糊聚類；③馬氏距離的計算復(fù)雜。由于本文提出的算法DPSOM-FCM比傳統(tǒng)模糊聚類算法加入了粒子群優(yōu)化步驟，所以DPSOM-FCM算法的運行速度不具優(yōu)勢，但仍在合理耗時內(nèi)。

5 結(jié)束語

通過對粒子群算法和馬氏距離模糊聚類算法的研究，構(gòu)造將類內(nèi)緊致度、類間分離度與類間清晰度結(jié)合的適應(yīng)度函數(shù)，本文提出了基于粒子群優(yōu)化的馬氏距離模糊聚類算法DPSOM-FCM。該算法用馬氏距離替換FCM算法的歐氏距離，同時結(jié)合了粒子群的全局優(yōu)化性能，經(jīng)過在6個數(shù)據(jù)集上，與FCM，M-FCM，PSO-FCM， IFPSOFCM算法的實驗對比分析，驗證了該算法的收斂性、有效性和聚類準(zhǔn)確性，具有全局優(yōu)化作用。