胡建華　尹慧琳

摘 要： 模糊C-均值聚類算法（FCM）是一種經(jīng)典的聚類算法，主要通過迭代更新隸屬度和聚類中心來提高聚類的有效性。 FCM算法的性能主要通過類內(nèi)緊性和類間分離性來評價，但其既依賴于初始聚類中心，也對噪聲非常敏感?？紤]到每個數(shù)據(jù)點和每個聚類中心對目標函數(shù)的不同重要性，本文提出了一種具有自適應權(quán)重的改進FCM聚類算法（Hybrid FCM）。主要貢獻：將2個具有自適應指數(shù)p和q的自適應權(quán)向量ψ和φ引入FCM的目標函數(shù)，以體現(xiàn)不同數(shù)據(jù)點和聚類中心的重要性;為提高聚類性能，自適應指數(shù)p、q和模糊因子m采用粒子群優(yōu)化算法（PSO）優(yōu)化，新提出的聚類評價指標AWCVI作為PSO算法的適應度函數(shù);迭代過程中利用余弦相似性對隸屬度函數(shù)進行修正，提高算法的魯棒性。實驗表明，本文提出的算法能夠有效地提高聚類效果。

關(guān)鍵詞： 模糊C均值算法; 自適應權(quán)重; 余弦相似度; 粒子群算法

文章編號： 2095-2163（2021）07-0073-07中圖分類號：TP181文獻標志碼： A

Improved FCM algorithm with adaptive weights based on cosine similarity

HU Jianhua， YIN Huilin

（College of Science， University of Shanghai for Science and Technology， Shanghai 200093， China）

【Abstract】As a classical clustering algorithm， fuzzy C-means clustering algorithm （FCM） improves the effectiveness of clustering by updating membership and clustering centers. The performance of FCM algorithm is mainly evaluated by intra cluster compactness and inter cluster separation. But FCM algorithm relies on the clustering centers and is very sensitive to noise. Considering the different importance of each data point and each cluster center， two adaptive weight vectors ψand φwith adaptive exponents p and q are introduced into the objective function of FCM， and an improved FCM clustering algorithm with adaptive weights is proposed; At the same time， the new clustering evaluation index? AWCVI is used to optimize the parameters p， q and the fuzzy factor m， which is determined by the particle swarm optimization algorithm （PSO）; The cosine similarity is used to modify the membership function in the iterative process to improve the robustness of the algorithm. Experimental results show that the proposed algorithm can effectively improve the clustering effect.

【Key words】Fuzzy C-means algorithm（FCM）; adaptive weight; cosine similarity; Particle Swarm Optimization

0 引 言

模糊C均值聚類算法是一種經(jīng)典的聚類方法，由Dunn[1]在1973年提出，由于其簡單、易實現(xiàn)而廣泛應用于數(shù)據(jù)挖掘、模式識別、信號處理、圖像分割等領(lǐng)域中[2-4]。然而，F(xiàn)CM算法依賴初始聚類中心、對噪聲非常敏感、且容易陷入局部最優(yōu)。因此，許多改進的FCM算法也相繼提出以克服這些問題。一般FCM算法需要將樣本對每個類滿足歸一化條件，這樣會導致算法對非平衡數(shù)據(jù)集中噪聲點和離群值異常敏感，文獻[5]提出一種改進的模糊隸屬度函數(shù)的FCM 聚類算法，能在聚類過程中不斷對隸屬度進行修正，從而消除噪聲點，提高聚類的有效性;Zhou 等人 [6]結(jié)合了圖像的空間信息和FCM 算法，提出了一種自適應空間信息模糊聚類算法用來提高圖像分割的效果;文獻[7]建立了一種基于特征的2型模糊聚類算法，將2型模糊集引入到聚類算法中，可以更靈活地處理由噪聲環(huán)境引起的與隸屬度概念相關(guān)的不確定性;將FCM算法與其他算法結(jié)合起來，能夠解決FCM算法依賴初始值的問題，例如將FCM算法與粒子群算法結(jié)合在一起[8-9]，利用粒子群算法強大的全局尋優(yōu)能力，能夠使FCM算法取得相對更優(yōu)的初始點，提升聚類效果;文獻[10]將FCM算法與蟻群算法結(jié)合起來，克服FCM算法依賴初始值的缺點?？紤]到噪聲和樣本分布不均衡，文獻[11]中提出了一種具有自適應樣本權(quán)重的FCM算法（AFCM-SP），通過對每個樣本點賦予權(quán)重來區(qū)分不同的樣本點對聚類結(jié)果的影響，并且用改進的粒子群算法（PSO-SP）對新引入的自適應參數(shù)進行優(yōu)化，從而一定程度上降低了噪聲點的影響。

但是由于樣本的最終聚類結(jié)果也受到了聚類中心的影響，本文通過對樣本與中心同時賦予權(quán)重的方法來提高算法聚類效果，基于自適應權(quán)重，還提出了新的聚類評價指標對聚類結(jié)果進行評價，同時，聚類過程中的隸屬度函數(shù)可能會因為隨機的初始值而降低聚類效果，所以對迭代過程中的隸屬度進行余弦修正增強算法的魯棒性，實驗表明這一想法的確能夠有效提高算法的性能。考慮到每個數(shù)據(jù)點和每個聚類中心對目標函數(shù)的不同重要性，本文提出了一種具有自適應權(quán)重的改進FCM聚類算法（Hybrid FCM）。在新算法中，2個具有自適應指數(shù)p和q的自適應權(quán)向量ψ和φ引入FCM的目標函數(shù)，以區(qū)分不同數(shù)據(jù)點和聚類中心在迭代過程中的不同重要性;為提高聚類性能，自適應指數(shù)p、q和模糊因子m采用粒子群優(yōu)化算法（PSO）優(yōu)化;相應地，新提出一種帶權(quán)重的聚類評價指標AWCVI用來刻畫類內(nèi)緊致度和類間分離性，并作為PSO算法的適應度函數(shù);為了提高算法的魯棒性，迭代過程中利用余弦相似性對隸屬度函數(shù)進行修正。通過在5個數(shù)據(jù)集上與另外3種算法對比的實驗表明，本文提出的算法能夠有效地提高聚類效果。

1 相關(guān)工作

1.1 經(jīng)典FCM算法

模糊C-均值聚類算法（FCM）是一種經(jīng)典的聚類算法，主要通過迭代更新隸屬度和聚類中心來提高聚類的有效性。從模型上看，F(xiàn)CM算法是用于求解最小化問題，以C均值函數(shù)作為目標函數(shù)：

其中，xi表示第i個樣本;令U=（μji）c×n表示模糊隸屬度矩陣，μji表示第i個樣本屬于第j類的隸屬度，滿足約束條件：

研究中，V={v1，v2，…，vc}是所有聚類中心的集合，ci為第i個聚類中心;m為模糊因子，一般取值為2。FCM的隸屬度函數(shù)和聚類中心的更新迭代公式為：

1.2 余弦相似性

余弦相似性，也叫余弦距離，是用向量空間中2個向量夾角的余弦值作為衡量2個個體之間的差異的大小度量。設(shè)M和N為2個樣本向量，其計算公式為：

其中，分子為M，N的向量內(nèi)積，分母為向量M，N的模的乘積。余弦值取值范圍為[-1，1]，越接近1，就說明2個向量越相似。余弦值注重從方向上區(qū)分樣本的差異，而對絕對的數(shù)值不敏感，可修正數(shù)據(jù)度量標準不統(tǒng)一等問題

。在數(shù)據(jù)挖掘領(lǐng)域，余弦相似性常用來衡量聚類的類內(nèi)凝聚程度。

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

粒子群優(yōu)化（PSO）算法因為其具有搜索速度快、效率高、算法簡單等優(yōu)點，成為近年來廣泛使用的優(yōu)化算法之一[12-15]，其傳統(tǒng)模型為：

其中，Vi（t）表示在搜索空間內(nèi)第i個粒子在t時刻的速度;Xi（t）表示在t時刻的位移;ω是慣性權(quán)重;c1，c2是加速系數(shù)，分別稱為認知加速系數(shù)和社會加速系數(shù)，本文設(shè)置ω=0.729，c1=c2=1.49。在尋優(yōu)過程中，Pi和Pg分別代表第i個粒子的個體最佳位置與全局最佳位置。

2混合自適應加權(quán)FCM算法

2.1 混合自適應加權(quán)FCM模型

FCM是一種快速有效的聚類算法，但在噪聲和樣本分布不均衡的情況下，算法聚類結(jié)果不理想。文獻[11]考慮到每個樣本的重要性，提出了具有樣本自適應權(quán)重的FCM算法（AFCM-SP） ，一定程度上減少了噪聲干擾，提高算法性能。但在聚類過程中，聚類中心也起著非常重要的作用。觀察式（1），可以發(fā)現(xiàn)經(jīng)典FCM算法的目標函數(shù)可以寫成：

將Di=∑cj=1μmji‖xi-vj‖2看成數(shù)據(jù)點xi對目標函數(shù)Jc的貢獻，則式（8）表明每個數(shù)據(jù)點對于目標函數(shù)具有相同的重要性，顯然這是不合實際情況的。本文同時考慮到不同樣本和聚類中心對目標函數(shù)的不同影響程度，提出混合自適應加權(quán)FCM算法（Hybrid FCM），其目標函數(shù)如下：

其約束條件為：

其中， μij∈[0，1]; ψ=（ψ1，ψ2，…，ψn）為樣本權(quán)重向量;? φ=（φ1，φ2，…，φc）為中心權(quán)重向量; ψi>0，φj>0。為了最小化Gh，引入了拉格朗日函數(shù)：

對任意的i，j，對L計算與μji，ψi，φj，vj相關(guān)的偏導數(shù)，并使其分別等于0，結(jié)合約束條件（10）∏nl=1，l≠iψl=1ψi，∏cl=1，l≠jφl=1φj，得到使目標函數(shù)（9）達到最小的充要條件：

將式（11）、式（14）與式（3）、式（4）對比，Hybrid FCM的隸屬度和中心都因為自適應隨權(quán)向量ψ、φ的引進做了相應的調(diào)整， 這有利于克服FCM算法對初始聚類中心的依賴和減低噪聲的干擾。為了降低算法陷入局部最優(yōu)的可能性，隸屬度函數(shù)進一步用余弦相似度作為矯正因子來修正，計算公式為[16]：

同時，Hybrid FCM中，自適應參數(shù)p，q和m一樣是個超參數(shù)，用來控制函數(shù)的凸性和模糊度，恰當?shù)娜≈祵垲惤Y(jié)果起著至關(guān)重要的作用。

2.2 基于自適應權(quán)重的聚類有效性指標

聚類有效性指標（AWCVI）是用來衡量聚類效果的評價函數(shù)，XB指標[13]是最廣泛使用的聚類有效性指標之一，具體公式為：

CVIXB值越小，則表示具有良好的類內(nèi)緊湊性和類間的分離性，說明聚類結(jié)果越好。此外，類間的最小距離反映了類間分離的尺度，而類內(nèi)的平均距離體現(xiàn)了集群內(nèi)的緊湊性尺度。本文結(jié)合新引入的自適應權(quán)重，提出新的聚類有效性指標AWCVI如下：

作為比值函數(shù)，AWCVI的值越小，表示聚類效果越好。

2.3 混合自適應加權(quán)FCM算法的流程

Hybrid FCM算法分為2部分。首先，為了更好的聚類效果，新引入的自適應參數(shù)p，q和模糊因子m通過經(jīng)典的PSO算法優(yōu)化，基于自適應權(quán)重的聚類有效性指標AWCVI作為PSO算法的適應度函數(shù)。其次，以式（9）為最小化的目標函數(shù)，通過有限次的迭代，得到最終的聚類結(jié)果。算法流程如下：

（1）在三維搜索空間內(nèi)初始化粒子種群Xi=（pi，qi，mi）， i=1，2，…，N，初始化隸屬度矩陣U，樣本權(quán)重向量ψ，中心權(quán)重向量φ，通過式（10）計算初始聚類中心V，設(shè)置收斂閾值eps。

（2）初始化粒子的速度和位移。

（3）根據(jù)式（11）～式 （15）迭代更新U，ψ，φ，V。

（4）根據(jù)式（19）計算每個粒子的適應度AWCVI（Xi（t）），得到t時刻的Pi， Pg。

（5）根據(jù)式（6）、式（7）更新粒子的速度和位移。

（6）當達到最大迭代次數(shù)時或者當∣AWCVI（Pg（k））-AWCVI（Pg（k-1））∣

同時，研究又給出基于余弦相似性的自適應權(quán)重的改進FCM算法流程如下：

（7）初始化U，ψ， φ， 通過式（14）計算聚類中心V。

（8）根據(jù)式（11）～（14）迭代更新U， ψ，φ，V。

（9）通過式（15）對更新后的U進行余弦修正。

（10）利用式（9）計算目標函數(shù)Gh。

（11）當算法收斂時或達到最大迭代次數(shù)時，進行（5）;否則，回到（2）。

（12）得到最終聚類結(jié)果。

在此基礎(chǔ)上，研發(fā)得到的算法偽代碼如下。

算法1 基于自適應權(quán)重的聚類有效性指標AWCVI的PSO算法

輸入：Xi=（mi， pi， qi）

輸出：最優(yōu)的m， p， q

初始化粒子群X=X（m， p， q）， 隸屬度函數(shù)U， 權(quán)重向量ψ，φ， 并且計算初始聚類中心V

初始化Pi， Pg，設(shè)置最大迭代次數(shù)Itermax， 收斂域eps

function FISTNESS FUNCTION=AWCVI（X）

for k=1：itermax do

for i=1：N＼＼＼＼ N為種群數(shù)量

if AWCVI（Xi（k））

Pi（k）=Xi（k）

end if

[JP4]Vi（t+1）=ωVi（t）+c1r1（Pi（t）-Xi（t））+c2r2（Pg（t）-Xi（t））

Xi（t+1）=Xi（t）+Vi（t+1）

i=i+1

end for ＼＼＼＼ 更新粒子的速度與位置

Pg=arg min AWCVI（Pi（k））

if ∣AWCVI（Pg（k））-AWCVI（Pg（k-1））∣

return Pg=（m， p， q） ＼＼＼＼ 全局最優(yōu)粒子

else

k：=k+1

end if

end for

Return Pg =（m， p， q）

end function

算法2 混合自適應加權(quán)FCM算法

輸入： Pg=（m， p， q）＼＼＼＼ 由算法1可以得到全局最優(yōu)的m， p ，q值

輸出： 聚類結(jié)果

初始化 隸屬度函數(shù)U， 權(quán)重向量ψ，φ， 并且計算初始聚類中心V， 聚類數(shù)目c， 設(shè)置最大運算次數(shù)Itermax， 收斂閾值eps

function OBJECT FUNCTION=Gh （U，ψ，φ， V）

for k=1：Itermax do

for? i=1：n＼＼＼＼ n為數(shù)據(jù)的數(shù)量

for? j=1：c

計算μji，ψi，φj，vj

＼＼＼＼更新隸屬度， 權(quán)重向量和聚類中心

uk+1ji=12ukji+12xi·vj‖xi‖‖vj‖

＼＼＼＼ 對隸屬度進行余弦修正

end for

end for

if |Gh （k）-Gh （k-1）|

return Gh （k） ＼＼＼＼ 算法收斂時的目標函數(shù)值

else

k：=k+1

end if

end for

Return 隸屬度函數(shù)U，權(quán)重向量ψ， φ， 聚類中心V， 與目標函數(shù)值Gh

end function

3 仿真實驗與結(jié)果分析

為了驗證提出算法的聚類性能，本文對5個數(shù)據(jù)集進行仿真實驗，人工數(shù)據(jù)集Twomoons用來驗證算法的魯棒性，數(shù)據(jù)集信息包括數(shù)據(jù)的數(shù)量、特征、類別，見表1;同時采用FCM算法[1]，AFCM-SP[11]算法與SFCM算法[16]作為對比算法。實驗之初，隨機分配[0，1]之間的值給uji，ψi和φj設(shè)置為1;在聚類過程的最大迭代次數(shù)為200，收斂閾值eps為10-5;在優(yōu)化參數(shù)p，q，m的PSO中，搜索空間為3維，種群粒子數(shù)為20，最大迭代次數(shù)設(shè)置為20。在5個數(shù)據(jù)集中由PSO算法得到的最優(yōu)p，q，m值列在表中，詳見表2。

對于前四個數(shù)據(jù)集，本文從Xie Beni指標（CVIXB）、聚類準確率（Accuracy）、標準互信息（NMI）三個方面對4種算法進行對比實驗。CVIXB值越小、Accuracy和NMI值越大說明聚類效果越好。實驗結(jié)果見表3～表6。從表3～表6中可以看出，本文提出的改進算法Hybrid FCM在IRIS上的各個指標都優(yōu)于其它3種算法，在SONAR中，Hybrid FCM和AFCM-SP算法有相同的準確率，但是CVIXB和NMI值都優(yōu)于AFCM-SP;在SPIRAL中，經(jīng)典的FCM有著較好的CVIXB值，但是準確率和NMI值還是Hybrid FCM更為優(yōu)異;在SYM上，Hybrid FCM準確率略低于SFCM算法，但CVIXB和NMI值都排在第一位。對于人工數(shù)據(jù)集Twomoons，本文添加3個評價指標，即：召回率（Recall）、 精確率（Precision）和F1值，結(jié)果見表7。Hybrid FCM在Accuracy、NMI、Recall、F1值在4個方面都有優(yōu)勢;Twomoons數(shù)據(jù)集經(jīng)過4種算法聚類后的數(shù)據(jù)分布如圖1所示，可以發(fā)現(xiàn)在類邊界部分，改進的算法有著更好的效果。圖2給出4種算法在不同數(shù)據(jù)集上的收斂曲線以證明算法良好的收斂性。綜上所述，本文提出的Hybrid FCM算法在5個數(shù)據(jù)集上都體現(xiàn)出較為優(yōu)異的性能，能有效提高聚類效果。

4 結(jié)束語

針對傳統(tǒng)FCM算法依賴于初始聚類中心、對噪聲敏感、容易陷入局部最優(yōu)等缺點，本文提出一種基于余弦相似性的自適應權(quán)重的改進FCM算法。首先，新算法考慮了樣本與聚類中心聯(lián)合起來對目標函數(shù)的影響程度，引入了樣本與聚類中心權(quán)重和相應的自適應因子，使得原問題解空間的維數(shù)更大，最優(yōu)解的精度提高;其次，提出了一種基于權(quán)重的聚類有效性指標作為PSO算法的適應度函數(shù)去優(yōu)化模糊因子m與自適應因子p， q;最后，對隸屬度函數(shù)進行余弦相似性修正，大大增強了算法的魯棒性。實驗結(jié)果表明本文改進的算法能有效提高算法的聚類性能。

參考文獻

[1]DUNN J C. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J]. Journal of Cybernetics， 1973，3（3）： 32-57.

[2]夏邢， 薛濤， 李婷. 基于Spark的模糊C均值算法改進[J]. 西安工程大學學報， 2019， 33（1）：100-105.

[3]徐曉東，呂干云，魯濤， 等. 基于智能電表數(shù)據(jù)與模糊C均值算法的臺區(qū)識別[J]. 南京工程學院學報（自然科學版），2020，18（4）：1-7.

[4]高立揚， 牛衍亮， 張小平. 基于模糊C均值聚類推理模型的高鐵土建工程造價智能估算[J]. 石家莊鐵道大學學報（社會科學版）， 2020， 14（2）：36-43.

[5]XIAO Mansheng， WEN Zhicheng， ZHANG Juwu， et al. An FCM clustering algorithm with improved membership function[J]. Control and Decision， 2015，30（12）：2270-2274.

[6]ZHOU Wengang， SUN Ting， ZHU Hai. Image segmentation algorithm based on FCM optimized by adaptive spatial information[J]. Application Research of Computers， 2015，32（7）：2205-2208.

[7]YANG Xiyang， YU Fusheng， PEDRYCZ W. Typical characteristics-based type-2 fuzzy C-Means algorithm[EB/OL]. [2020]. https：//10.1109 /TFUZZ.2020.2969907.

[8]HESAM I， AJITH A. Fuzzy C-means and fuzzy swarm for fuzzy clustering problem[J]. Expert Systems with Applications，2011，38（3）：1835-1838.

[9]文傳軍， 詹永照. 粒子群高斯誘導核模糊C均值聚類算法[J]. 科學技術(shù)與工程， 2018， 18（8）：78-84.

[10]魯明， 王彬， 劉東儒，等. 基于蟻群優(yōu)化模糊C均值聚類算法的疲勞駕駛研究[J]. 湖北汽車工業(yè)學院學報， 2019， 33（2）：23-28.

[11]WU Ziheng， WU Zhongcheng， ZHANG Jun. An improved FCM algorithm with adaptive weights based on SA-PSO[J]. Neural Computing and Applications， 2017，28： 3113-3118.

[12]XIE X L， BENI G. A validity measure for fuzzy clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1991， 13（8）：841-847.

[13]劉軍梅. 新型混沌粒子群混合優(yōu)化算法[J].軟件導刊，2017，16（2）：59-62.

[14]徐超， 單志勇， 徐好好. 具有動態(tài)學習能力的分層進化粒子群優(yōu)化算法[J]. 軟件導刊， 2021， 20（1）：128-131.

[15]LIU Weibo， WANG Zidong， LIU Xiaohui， et al. A novel particle swarm optimization approach for patient clustering from emergency departments[J]. IEEE Transactions on Evolutionary Computation，2019，23（4）： 632-644.

[16]LI Minxuan. An improved FCM clustering algorithm based on cosine similarity[C]// ACM International Conference Proceeding Series. Hong Kong，China：ACM，2019： 103-109.

[17]LANCICHINETTI A ， FORTUNATO S ， KERTéSZ J. Detecting the overlapping and hierarchical community structure of complex networks[J]. New Journal of Physics， 2009， 11（3）：033015.

基金項目： 國家自然科學基金（61873169）。

作者簡介： 胡建華（1978-），女，博士，講師，主要研究方向：人工智能、李代數(shù); 尹慧琳（1996-），女，碩士研究生，主要研究方向：人工智能、李代數(shù)。

通訊作者： 胡建華Email： hjh_2021@usst.edu.cn

收稿日期： 2021-04-23