基于粒子群優化的模糊C均值聚類算法*

王宇鋼

(遼寧工業大學 機械工程與自動化學院，遼寧 錦州 121000)

0 引言

隨著大數據、云計算等技術的迅猛發展，聚類分析已成為數據挖掘的主要研究手段之一。為符合人類的認知，研究員將模糊集理論引入聚類分析中，提出了模糊C均值聚類算法(Fuzzy C-means Clustering Algorithm，FCM)。經典FCM 算法由于是一種局部最優搜索算法，存在對初始聚類中心敏感、易于陷入局部最優解的缺陷，限制了算法的應用[1-2]。因此，學者嘗試通過各種智能算法對經典FCM 算法進行改進。粒子群優化算法(Particle Swarm Optimization, PSO)作為群體智能算法的代表，依靠個體之間的簡單交互作用在群體內自組織搜索，具有很強的學習能力和適應性[3]。一些學者利用PSO算法克服傳統FCM算法的缺陷，將PSO算法與FCM算法融合已成為近年來的研究熱點[4]。

文獻[5]針對FCM算法用于高維數據樣本聚類時效果較差的不足，提出一種基于粒子群的FCM聚類算法。該算法在滿足FCM算法對隸屬度限制條件的前提下，根據樣本與聚類中心間距離重新分布了隸屬度，并通過比較樣本與各聚類中心距離加速最優粒子收斂。文獻[6]對初始聚類中心和模糊加權指數進行粒子編碼，通過粒子群優化算法搜索最優的適應度值及模糊加權指數，經人工數據集與UCI數據集實驗，證明該方法比傳統的FCM算法和粒子群聚類算法的聚類準確性和穩定性都有提高。文獻[7]將基于直覺模糊的粒子群算法(IFPSO)和FCM算法混合，利用猶豫度屬性參數尋找目標函數與聚類中心的相似性，對高維數據集進行聚類分析取得較好效果。文獻[8]提出一種基于慣性指數權重的粒子群聚類算法(ACL-PSO)。將改進的PSO算法與FCM算法相結合，改善FCM算法易于陷入局部最優解的缺陷，對UCI數據庫中標準數據集進行測試，結果顯示了該算法的有效性。

為克服FCM算法缺陷，提高聚類質量，本文對基本粒子群聚類算法進行改進，并與FCM算法結合，提出了一種改進的粒子群優化模糊C均值聚類算法(Improved Fuzzy C-mean Clustering Algorithm Based on Particle Swarm Optimization，IFCM-PSO)。首先通過選擇合理的粒子初始化空間，降低對初始聚類中心的敏感度，提高收斂速度；其次通過優化參數粒子運動最大速度以及引入環形拓撲結構的鄰域，解決粒子群聚類算法易早熟收斂的缺陷。選取UCI 數據庫中3 個真實數據集IRIS、WINE和Breast Cancer Wisconsin (BCW)進行仿真實驗，以驗證該算法的有效性。

1 模糊C均值聚類算法(FCM)

分為L個類簇的數據樣本集合X={x1,x2,…,xn}∈Rp，n為樣本個數，p為樣本空間維數，L介于2～n之間。FCM算法采用誤差平方和函數作為目標函數，其定義式為：

隸屬度uij應滿足約束條件：

FCM算法是以誤差平方和為準則函數的一種逐點迭代聚類算法。通過式(2)和式(3)迭代計算隸屬度矩陣U和聚類中心V，使目標函數J(U，V)的取值不斷減小。當準則函數會聚時，獲得數據樣本的最終聚類結果，即模糊劃分后的隸屬度矩陣U和聚類中心V。

2 基本粒子群聚類算法

2.1 粒子群優化算法

在粒子群優化算法中，每個粒子si抽象為一個個體，種群就是由這些粒子構成的，所求問題的解就是粒子在空間中的最優位置。在每次迭代計算過程中，根據所有粒子的適應值評價每個粒子的極值當前最優位置pi和群體全局最優位置g。依靠兩個位置極值，粒子更新其移動速度和位置，直至收斂到空間位置的最優解。

目前普遍采用的粒子速度和位移更新形式為：

vi=ωvi+c1r1(pi-si)+c2r2(g-si)

(5)

si=si+vi

(6)

其中，c1、c2為學習因子，一般取c1=c2；r1、r2是[0，1]之間的隨機數；w為慣性權重，取值限定在[wmin，wmax]之間。在迭代過程中，慣性權重通常采用線性遞減方式由最大值變為最小值，即：

w=wmax-iter×(wmax-wmin)/itertotle

(7)

其中，iter為當前迭代次數，itertotle為最大迭代次數。

2.2 FCM-PSO算法

為了實現傳統聚類方法缺陷的突破，研究人員嘗試將粒子群優化算法與傳統聚類算法相結合，通過PSO算法的全局尋優能力和分布式隨機搜索特性解決傳統聚類算法易陷入局部最優和對初值敏感的問題。將聚類作為一種優化問題實現對數據集的近似最優劃分。基本粒子群聚類算法的流程如下：

(1)給定聚類的數目，初始化聚類中心矩陣，并賦值給各個粒子，隨機產生粒子的初始速度。

(2)對每個粒子計算隸屬度，更新所有的聚類中心，計算各個粒子的適應值，更新個體極值。

(3)根據各個粒于的個體極值，找出全局極值和全局極值位置。

(4)根據粒子群優化算法的速度公式更新粒子的速度，并把它限制在最大速度內。

(5)根據粒子群優化算法的位置公式更新粒子的位置。

(6)若不滿足終止條件，返回步驟(2)繼續迭代計算；若滿足終止條件，則輸出最優粒子的位置即最優分類中心矩陣。

目前，將FCM算法與PSO算法相融合的聚類算法(Fuzzy C-Mean Clustering Algorithm Based on Particle Swarm Optimization，FCM-PSO)已成為基本粒子群聚類算法的一種主要研究形式[9]。該方法將每個粒子表示為一種聚類中心的選取方式，應用FCM算法的目標函數計算各粒子的適應值，作為對應聚類中心聚類效果的評判依據，算法收斂后輸出粒子的全局最優位置，即最優聚類中心。

3 改進的粒子群優化模糊C均值聚類算法

3.1 粒子群聚類算法的改進

(1)PSO算法通常將粒子初始值均勻分布于[0，1]之間，而非在粒子的最優解的附近空間，這將使粒子搜尋最優解的迭代時間增加，聚類的效果變差[10]。本文將樣本聚類中心作為種群個體，因此粒子的最優解空間即為樣本的分布空間。將粒子的初始位置隨機分布于取值范圍[Xmin，Xmax]，Xmin、Xmax分別為樣本每維最小值和最大值組成的向量。這樣初始化的粒子在接近最優解的搜索空間開始進化運算，可有效縮短收斂時間，提高聚類質量。

(2)最大速度vmax決定粒子在一次迭代計算中的最大移動距離，vmax過大則易使粒子錯過最優解，過小則會使粒子易陷入局部最優解。因此，通常將粒子最大速度設為一個常數。然而，在樣本各維取值存在較大量綱差異時，由于各維空間取值范圍不同，將粒子的vmax在樣本各維空間均設定為一個常數，顯然易出現錯過最優解或陷入局部最優解的情況，結果影響算法的全局收斂性。本文對粒子在樣本空間每一維都定義一個最大速度，最大速度vmax根據樣本每維變化的取值范圍設定。

vmax=λ(Xmax-Xmin)

(8)

其中，λ為常數。

(3)在實際應用中，PSO算法仍易出現早期迭代震蕩及早熟收斂的情況。因此，研究人員嘗試使用局部鄰居的概念，將鄰域也作為粒子進化的一個調節源，降低早熟收斂情況的發生概率。

在PSO算法中，粒子群的信息共享范圍即為粒子的鄰域拓撲結構。環形鄰域拓撲結構使用局部鄰居的概念，每個粒子只與最近的鄰居溝通，較好地協調粒子本身和群體之間的關系。本文通過引入環形拓撲結構鄰域改善PSO聚類算法性能。在初始階段，鄰域就是每個粒子自身，隨迭代次數增加，每個粒子只與最近鄰居溝通，鄰域逐步擴展到包含所有粒子[11]。新的速度更新策略調整為：

vi=ωvi+c1r1(pi-si)+c2r2(g-si)+c3r3(pl-si)

(9)

其中，pl為粒子鄰域極值。

3.2 改進的粒子群優化模糊C均值聚類

綜上分析，本文提出的IFCM-PSO算法將聚類中心作為種群中粒子的位置，將FCM算法目標函數作為適應函數，終止條件為最優粒子目標函數適應值變化量小于閾值或迭代次數達到設定值itertotle，算法歸納如下：

(1)設定聚類初始參數：聚類數，種群數，最大速度系數，迭代誤差。

(2)在取值范圍[Xmin，Xmax]內初始化聚類中心矩陣，并賦值給各粒子。

(3)根據式(1)計算初始種群中每個個體的適應值。

(4)根據公式(9)計算粒子移動速度，根據公式(6)更新粒子的位置。

(5)計算種群中個體粒子的適應值,若滿足終止條件, 則將粒子全局最優位置作為最優解輸出；否則返回步驟(3)繼續迭代計算。

4 實驗與結果分析

為了驗證算法的性能，選擇來自機器學習數據庫UCI中的3個真實數據集進行實驗，分別為IRIS、WINE和Breast Cancer Wisconsin(BCW)。以上3個數據集經常被用于測試聚類算法的有效性，數據集的詳細信息如表1所示。

表1 數據集信息

4.1 算法有效性測試

對選擇的3個數據集分別采用FCM算法、FCM-PSO算法以及本文的IFCM-PSO算法進行聚類仿真實驗。實驗參數為：FCM-PSO算法的粒子種群數為20，最大迭代次數為500，最優解改變量閾值為0.001；IFCM-PSO算法的粒子種群數為20，允許的最大速度系數λ=0.15,最大迭代次數為100，最優解改變量閾值為0.001。數據集分別對3種算法進行10次仿真運算，各指標為10次計算的平均值,聚類結果如表2所示。

表2 數據集聚類結果

由表2可知，對3個數據集，FCM算法迭代次數最少，表明收斂最快，但由于自身算法的缺陷使得聚類準確率較差；FCM-PSO算法對IRIS和BCW兩個數據集的聚類準確率較FCM算法高，但在3種算法中迭代次數最多，收斂速度最慢；本文的IFCM-PSO算法對3個數據集在迭代100次后均獲得了最高的準確率，表明該算法在聚類速度和準確率方面的綜合性能最好。

4.2 算法結果分析

對應3個數據集，FCM算法、FCM-PSO算法和IFCM-PSO算法各選取與聚類結果平均值最接近的一次聚類運算目標函數迭代曲線進行分析，目標函數值迭代曲線如圖1所示。

圖1 目標函數值迭代曲線圖

由圖1(a)可以發現，對IRIS數據集聚類時，FCM算法函數值下降迅速，很快收斂；FCM-PSO算法目標函數值在迭代100次后仍震蕩，未見明顯收斂；而IFCM-PSO算法由于初始化取值接近最優解，收斂較快，目標函數值最小。

圖1(b)顯示，對WINE數據集，FCM算法很快收斂，FCM-PSO算法迭代約30次后收斂，但目標函數未見明顯下降，表明出現早熟收斂；IFCM-PSO算法在迭代100次后基本收斂，目標函數值與FCM算法目標函數值接近。

圖1(c)顯示對Breast Cancer Wisconsin數據集雖然FCM-PSO算法和本文的IFCM-PSO算法均出現震蕩，但最終本文的IFCM-PSO算法震蕩幅度較小，收斂效果更好。

通過以上3種算法對應3個數據集的目標函數曲線比較可以發現：本文的IFCM-PSO聚類算法由于在聚類初始化取值、最大速度取值方面進行了改進，并引入了環形鄰域輔助進化，使該算法有效克服了FCM算法對初始值敏感、易陷入局部最優解及基本粒子群聚類算法迭代初期震蕩、早熟收斂的問題，因而獲得了最好的聚類效果。

5 結束語

本文針對模糊C均值聚類算法存在的主要問題，利用改進的粒子群聚類算法，提出了一種基于粒子群優化的模糊C均值聚類算法。通過對粒子初始化空間和粒子運動最大速度兩個參數的優化設置，并引入環形拓撲結構的鄰域，提高了粒子群聚類算法的聚類效果。仿真結果表明該算法在聚類準確性和收斂速度方面均優于模糊C均值聚類(FCM)算法和基本粒子群聚類(FCM-PSO)算法。