基于粒子群優化的馬氏距離模糊聚類算法

祖志文，李 秦

(蘭州交通大學 數理學院，蘭州 730070)

0 引 言

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

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

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

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

FCM算法的優化目標函數為

(1)

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

(2)

最小化J，對ci,uij,Σi求偏導，令其結果為零可得

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

(3)

(4)

(5)

M-FCM算法描述如下。

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

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

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

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

2 粒子群算法(PSO)

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

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為種群規模；t為當前進化代數；w為1998年Eberhart和Shi引入到PSO算法速度項中的系數[9]，即慣性權重；r1,r2為分布于[0,1]的隨機數；c1,c2為加速系數[10]。

在粒子群算法中，粒子的優劣好壞需要適應度函數來進行評價，根據適應度函數值即適應值尋找粒子的狀態極值，對粒子進行選擇，優勝劣汰，從而更新其他粒子的狀態。粒子的適應值越大，即該粒子的質量越好，越適應目標函數所定義的生存環境。

3 利用粒子群優化馬氏距離模糊聚類算法

3.1 算法思想

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

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

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

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

(8)

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

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

(9)

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

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

(10)

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

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

(11)

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

另外，算法終止條件為以下2種情況：①最優解對應的目標值保持不變或變動小于閾值ε；②迭代次數已達到設定的最大次數itermax。滿足任一種情況算法終止。

3.2 算法步驟

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

輸入：數據集、類別數。

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

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

3)設置每個粒子的pb0,pg0，計算粒子的適應值fitness0，并儲存。

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

5)計算慣性權重w。

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

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

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

9)對于每個粒子，將其適應度值與所經歷過的最優位置pb的適應值進行比較，若較好，則將其作為當前的個體最優位置。

10)對于每個粒子，將其適應值與全局經歷過的最優位置pg的適應值進行比較，若較好，則將其作為當前全局最優位置。

11)如果全局最優位置適應值相對上次的改變量小于特定的最小閥值ε或達到最大迭代次數，則結束，否則轉向步驟4)。

輸出：最優聚類中心及適應值。

4 實驗結果與分析

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

圖1 各數據集上DPSOM-FCM算法的適應值變化Fig.1 Fitness function value changes of DPSOM-FCMalgorithm on each data set

數據集數據含量類別數屬性維數Iris15034Wine178313Glass21469Heart Disease270213Pima76828Car Evaluation172846

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

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

續表2

表3 5個算法的聚類準確性對比

續表3

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

5 結束語

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