基于余弦相似性的自適應(yīng)權(quán)重的改進(jìn)FCM算法

胡建華　尹慧琳

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

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

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

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

1 相關(guān)工作

1.1 經(jīng)典FCM算法

模糊C-均值聚類算法（FCM）是一種經(jīng)典的聚類算法，主要通過迭代更新隸屬度和聚類中心來提高聚類的有效性。從模型上看，F(xiàn)CM算法是用于求解最小化問題，以C均值函數(shù)作為目標(biāo)函數(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ù)度量標(biāo)準(zhǔn)不統(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ù)，分別稱為認(rèn)知加速系數(shù)和社會加速系數(shù)，本文設(shè)置ω=0.729，c1=c2=1.49。在尋優(yōu)過程中，Pi和Pg分別代表第i個粒子的個體最佳位置與全局最佳位置。

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

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

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

將Di=∑cj=1μmji‖xi-vj‖2看成數(shù)據(jù)點xi對目標(biāo)函數(shù)Jc的貢獻(xiàn)，則式（8）表明每個數(shù)據(jù)點對于目標(biāo)函數(shù)具有相同的重要性，顯然這是不合實際情況的。本文同時考慮到不同樣本和聚類中心對目標(biāo)函數(shù)的不同影響程度，提出混合自適應(yīng)加權(quán)FCM算法（Hybrid FCM），其目標(biāo)函數(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)的偏導(dǎo)數(shù)，并使其分別等于0，結(jié)合約束條件（10）∏nl=1，l≠iψl=1ψi，∏cl=1，l≠jφl=1φj，得到使目標(biāo)函數(shù)（9）達(dá)到最小的充要條件：

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

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

2.2 基于自適應(yīng)權(quán)重的聚類有效性指標(biāo)

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

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

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

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

Hybrid FCM算法分為2部分。首先，為了更好的聚類效果，新引入的自適應(yīng)參數(shù)p，q和模糊因子m通過經(jīng)典的PSO算法優(yōu)化，基于自適應(yīng)權(quán)重的聚類有效性指標(biāo)AWCVI作為PSO算法的適應(yīng)度函數(shù)。其次，以式（9）為最小化的目標(biāo)函數(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）計算每個粒子的適應(yīng)度AWCVI（Xi（t）），得到t時刻的Pi， Pg。

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

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

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

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

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

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

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

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

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

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

算法1 基于自適應(yīng)權(quán)重的聚類有效性指標(biāo)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 混合自適應(yīng)加權(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‖

＼＼＼＼ 對隸屬度進(jìn)行余弦修正

end for

end for

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

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

else

k：=k+1

end if

end for

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

end function

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

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

4 結(jié)束語

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

參考文獻(xiàn)

[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ìn)[J]. 西安工程大學(xué)學(xué)報， 2019， 33（1）：100-105.

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

[4]高立揚， 牛衍亮， 張小平. 基于模糊C均值聚類推理模型的高鐵土建工程造價智能估算[J]. 石家莊鐵道大學(xué)學(xué)報（社會科學(xué)版）， 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]文傳軍， 詹永照. 粒子群高斯誘導(dǎo)核模糊C均值聚類算法[J]. 科學(xué)技術(shù)與工程， 2018， 18（8）：78-84.

[10]魯明， 王彬， 劉東儒，等. 基于蟻群優(yōu)化模糊C均值聚類算法的疲勞駕駛研究[J]. 湖北汽車工業(yè)學(xué)院學(xué)報， 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].軟件導(dǎo)刊，2017，16（2）：59-62.

[14]徐超， 單志勇， 徐好好. 具有動態(tài)學(xué)習(xí)能力的分層進(jìn)化粒子群優(yōu)化算法[J]. 軟件導(dǎo)刊， 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.

基金項目： 國家自然科學(xué)基金（61873169）。

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

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

收稿日期： 2021-04-23