0  引言

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

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

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

1  模糊C均值聚類算法（FCM）

分為L個(gè)類簇的數(shù)據(jù)樣本集合 X = {x₁,x₂,…,x_n} ∈ R^p,，n為樣本個(gè)數(shù)，p為樣本空間維數(shù),，L介于2~n之間,。FCM算法采用誤差平方和函數(shù)作為目標(biāo)函數(shù)，其定義式為：

其中,，d_ij=||x_j－v_i為||樣本與聚類中心間距離,，通常為歐式距離；m為模糊加權(quán)指數(shù),；u_ij表示數(shù)據(jù)集X 中的第j個(gè)樣本對(duì)第i類的隸屬程度（0<u_ij<1）,；v_i表示各個(gè)聚類中心。

隸屬度uij應(yīng)滿足約束條件： 

FCM算法是以誤差平方和為準(zhǔn)則函數(shù)的一種逐點(diǎn)迭代聚類算法,。通過式(2)和式(3)迭代計(jì)算隸屬度矩陣U和聚類中心V,，使目標(biāo)函數(shù)J（U，V）的取值不斷減小,。當(dāng)準(zhǔn)則函數(shù)會(huì)聚時(shí),，獲得數(shù)據(jù)樣本的最終聚類結(jié)果，即模糊劃分后的隸屬度矩陣U和聚類中心V,。

2  基本粒子群聚類算法

2.1 粒子群優(yōu)化算法

在粒子群優(yōu)化算法中,，每個(gè)粒子s_i抽象為一個(gè)個(gè)體，種群就是由這些粒子構(gòu)成的,，所求問題的解就是粒子在空間中的最優(yōu)位置,。在每次迭代計(jì)算過程中，根據(jù)所有粒子的適應(yīng)值評(píng)價(jià)每個(gè)粒子的極值當(dāng)前最優(yōu)位置p_i和群體全局最優(yōu)位置g,。依靠?jī)蓚€(gè)位置極值,，粒子更新其移動(dòng)速度和位置，直至收斂到空間位置的最優(yōu)解,。

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

其中,，c₁、c₂為學(xué)習(xí)因子,，一般取c₁ = c₂,；r₁、r₂是［0,，1］之間的隨機(jī)數(shù),；w為慣性權(quán)重，取值限定在［w_min,，w_max］之間,。在迭代過程中，慣性權(quán)重通常采用線性遞減方式由最大值變?yōu)樽钚≈?，即?/span>

其中,，iter為當(dāng)前迭代次數(shù),，iter_totle為最大迭代次數(shù)。

2.2 FCM-PSO算法

為了實(shí)現(xiàn)傳統(tǒng)聚類方法缺陷的突破,，研究人員嘗試將粒子群優(yōu)化算法與傳統(tǒng)聚類算法相結(jié)合，通過PSO算法的全局尋優(yōu)能力和分布式隨機(jī)搜索特性解決傳統(tǒng)聚類算法易陷入局部最優(yōu)和對(duì)初值敏感的問題,。將聚類作為一種優(yōu)化問題實(shí)現(xiàn)對(duì)數(shù)據(jù)集的近似最優(yōu)劃分,。基本粒子群聚類算法的流程如下： 

（1）給定聚類的數(shù)目,，初始化聚類中心矩陣,，并賦值給各個(gè)粒子，隨機(jī)產(chǎn)生粒子的初始速度,。 

（2）對(duì)每個(gè)粒子計(jì)算隸屬度,，更新所有的聚類中心，計(jì)算各個(gè)粒子的適應(yīng)值,，更新個(gè)體極值,。 

（3）根據(jù)各個(gè)粒于的個(gè)體極值，找出全局極值和全局極值位置,。 

（4）根據(jù)粒子群優(yōu)化算法的速度公式更新粒子的速度,，并把它限制在最大速度內(nèi)。 

（5）根據(jù)粒子群優(yōu)化算法的位置公式更新粒子的位置,。

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

目前，將FCM算法與PSO算法相融合的聚類算法（Fuzzy C-Mean Clustering Algorithm Based on Particle Swarm Optimization,，F(xiàn)CM-PSO）已成為基本粒子群聚類算法的一種主要研究形式^［9］,。該方法將每個(gè)粒子表示為一種聚類中心的選取方式，應(yīng)用FCM算法的目標(biāo)函數(shù)計(jì)算各粒子的適應(yīng)值,，作為對(duì)應(yīng)聚類中心聚類效果的評(píng)判依據(jù),，算法收斂后輸出粒子的全局最優(yōu)位置，即最優(yōu)聚類中心,。

3  改進(jìn)的粒子群優(yōu)化模糊C均值聚類算法

3.1 粒子群聚類算法的改進(jìn)

（1）PSO算法通常將粒子初始值均勻分布于［0,，1］之間，而非在粒子的最優(yōu)解的附近空間,，這將使粒子搜尋最優(yōu)解的迭代時(shí)間增加,，聚類的效果變差^［10］。本文將樣本聚類中心作為種群個(gè)體,，因此粒子的最優(yōu)解空間即為樣本的分布空間,。將粒子的初始位置隨機(jī)分布于取值范圍［X_min,，X_max］，X_min,、X_max分別為樣本每維最小值和最大值組成的向量,。這樣初始化的粒子在接近最優(yōu)解的搜索空間開始進(jìn)化運(yùn)算，可有效縮短收斂時(shí)間,，提高聚類質(zhì)量,。

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

其中,，λ為常數(shù),。

（3）在實(shí)際應(yīng)用中，PSO算法仍易出現(xiàn)早期迭代震蕩及早熟收斂的情況,。因此,，研究人員嘗試使用局部鄰居的概念，將鄰域也作為粒子進(jìn)化的一個(gè)調(diào)節(jié)源,，降低早熟收斂情況的發(fā)生概率,。 

在PSO算法中，粒子群的信息共享范圍即為粒子的鄰域拓?fù)浣Y(jié)構(gòu),。環(huán)形鄰域拓?fù)浣Y(jié)構(gòu)使用局部鄰居的概念,，每個(gè)粒子只與最近的鄰居溝通，較好地協(xié)調(diào)粒子本身和群體之間的關(guān)系,。本文通過引入環(huán)形拓?fù)浣Y(jié)構(gòu)鄰域改善PSO聚類算法性能,。在初始階段，鄰域就是每個(gè)粒子自身,，隨迭代次數(shù)增加,，每個(gè)粒子只與最近鄰居溝通，鄰域逐步擴(kuò)展到包含所有粒子^［11］。新的速度更新策略調(diào)整為：

其中,，p_l為粒子鄰域極值,。

3.2 改進(jìn)的粒子群優(yōu)化模糊C均值聚類

綜上分析，本文提出的IFCM-PSO算法將聚類中心作為種群中粒子的位置,，將FCM算法目標(biāo)函數(shù)作為適應(yīng)函數(shù),，終止條件為最優(yōu)粒子目標(biāo)函數(shù)適應(yīng)值變化量小于閾值或迭代次數(shù)達(dá)到設(shè)定值itertotle，算法歸納如下： 

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

（2）在取值范圍［Xmin，Xmax］內(nèi)初始化聚類中心矩陣,，并賦值給各粒子,。 

（3）根據(jù)式(1)計(jì)算初始種群中每個(gè)個(gè)體的適應(yīng)值。 

（4）根據(jù)公式(9)計(jì)算粒子移動(dòng)速度,，根據(jù)公式(6)更新粒子的位置,。

（5）計(jì)算種群中個(gè)體粒子的適應(yīng)值,若滿足終止條件, 則將粒子全局最優(yōu)位置作為最優(yōu)解輸出；否則返回步驟（3）繼續(xù)迭代計(jì)算,。

4  實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證算法的性能,，選擇來自機(jī)器學(xué)習(xí)數(shù)據(jù)庫UCI中的3個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，分別為IRIS,、WINE和Breast Cancer Wisconsin(BCW),。以上3個(gè)數(shù)據(jù)集經(jīng)常被用于測(cè)試聚類算法的有效性，數(shù)據(jù)集的詳細(xì)信息如表1所示,。

表 1  數(shù)據(jù)集信息

4.1 算法有效性測(cè)試

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

表 2  數(shù)據(jù)集聚類結(jié)果

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

4.2 算法結(jié)果分析

對(duì)應(yīng)3個(gè)數(shù)據(jù)集，F(xiàn)CM算法,、FCM-PSO算法和IFCM-PSO算法各選取與聚類結(jié)果平均值最接近的一次聚類運(yùn)算目標(biāo)函數(shù)迭代曲線進(jìn)行分析,，目標(biāo)函數(shù)值迭代曲線如圖1所示。

圖 1  目標(biāo)函數(shù)值迭代曲線圖

由圖1（a）可以發(fā)現(xiàn),，對(duì)IRIS數(shù)據(jù)集聚類時(shí),，F(xiàn)CM算法函數(shù)值下降迅速，很快收斂,；FCM-PSO算法目標(biāo)函數(shù)值在迭代100次后仍震蕩,，未見明顯收斂；而IFCM-PSO算法由于初始化取值接近最優(yōu)解,，收斂較快,，目標(biāo)函數(shù)值最小。

圖1（b）顯示,，對(duì)WINE數(shù)據(jù)集,，F(xiàn)CM算法很快收斂，F(xiàn)CM-PSO算法迭代約30次后收斂,，但目標(biāo)函數(shù)未見明顯下降,，表明出現(xiàn)早熟收斂；IFCM-PSO算法在迭代100次后基本收斂,，目標(biāo)函數(shù)值與FCM算法目標(biāo)函數(shù)值接近,。 

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

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

5  結(jié)束語

本文針對(duì)模糊C均值聚類算法存在的主要問題,，利用改進(jìn)的粒子群聚類算法,，提出了一種基于粒子群優(yōu)化的模糊C均值聚類算法,。通過對(duì)粒子初始化空間和粒子運(yùn)動(dòng)最大速度兩個(gè)參數(shù)的優(yōu)化設(shè)置，并引入環(huán)形拓?fù)浣Y(jié)構(gòu)的鄰域,，提高了粒子群聚類算法的聚類效果,。仿真結(jié)果表明該算法在聚類準(zhǔn)確性和收斂速度方面均優(yōu)于模糊C均值聚類（FCM）算法和基本粒子群聚類（FCM-PSO）算法。

參考文獻(xiàn)

［1］ 賀正洪, 雷英杰. 直覺模糊C 均值聚類算法研究［J］. 控制與決策,2011, 26(6): 847-850,856.

［2］ PIMENTEL B A, SOUZA R M. A weighted multivariate fuzzy C-means method in interval-valued scientific production data ［J］. Expert Systems with Applications, 2014, 41(7), 3223-3236. 

［3］ 楊慧,，吳沛澤,，倪繼良. 基于改進(jìn)粒子群置信規(guī)則庫參數(shù)訓(xùn)練算法［J］. 計(jì)算機(jī)工程與設(shè)計(jì), 2017,38(2)：400-404.

［4］ FARHAD S， AMIN A N,， SHAHIN R N,，et al. Evaluating the potential of particle swarm optimization in clustering of hyperspectral imagery using fuzzy C-means［C］// International Conference on Asia Agriculture and Animal, Singapore: IACSIT, 2011: 201-207. 

［5］ Niu Qiang， Huang Xinjian. An improved fuzzy C-means clustering algorithm based on PSO［J］. Journal of Software, 2011,6(5): 873-879. 

［6］ 王縱虎, 劉志鏡, 陳東輝. 基于粒子群優(yōu)化的模糊Ｃ－均值聚類算法研究［J］. 計(jì)算機(jī)科學(xué), 2012,39(9): 166-169. 

［7］ KUMUTHA V, PALANIAMMAL S. Improved fuzzy clustering method based on intuitionistic fuzzy particle swarm optimization ［J］. Journal of Theoretical and Applied Information Technology,2014, 62 (1):8-15. 

［8］ Chen Shouwen, Xu Zhuoming, Tang Yan. A hybrid clustering algorithm based on fuzzy C-means and improved particle swarm optimization ［J］. Arabian Journal for Science & Engineering, 2014, 39(12):8875-8887. 

［9］ 李峻金,，向陽,，蘆英明，等. 粒子群聚類算法綜述［J］. 計(jì)算機(jī)應(yīng)用研究, 2009,，26(12): 4423-4427. 

［10］FILHO T M S, PIMENTEL B A, SOUZA R M C R, et al. Hybrid methods for fuzzy clustering based on fuzzy C-means and improved particle swarm optimization ［J］. Expert Systems with Applications, 2015, 42(17): 6315-6328. 

［11］石松,，陳云. 層次環(huán)形拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)粒子群算法［J］. 計(jì)算機(jī)工程與應(yīng)用, 2013, 49(8):1-5.

（收稿日期：2018-04-29）

作者簡(jiǎn)介：

王宇鋼(1977-)，男,，博士研究生，講師,，主要研究方向：機(jī)械制造自動(dòng)化,。

*基金項(xiàng)目：遼寧省自然科學(xué)基金資助項(xiàng)目（20170540445）