一種動(dòng)態(tài)加權(quán)模糊聚類算法的研究

劉 銳，張 寧

（北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044）

聚類是按照一定規(guī)則對(duì)某一事物進(jìn)行區(qū)分和歸類的動(dòng)態(tài)過程，在整個(gè)過程中，沒有專家知識(shí)的指導(dǎo)，沒有先驗(yàn)知識(shí)的支持，聚類僅僅依靠事物之間的“相似度”作為劃分的標(biāo)準(zhǔn)[1]。是一種典型的無(wú)監(jiān)督式學(xué)習(xí)，相較于監(jiān)督式學(xué)習(xí)，數(shù)據(jù)標(biāo)簽是區(qū)分兩者的最重要指標(biāo)。

FCM算法，即模糊C均值聚類算法，是一種典型的軟化分聚類算法，舍棄了硬劃分中非0即1的方法，采用一種劃分矩陣的輸出形式來表示某一樣本數(shù)據(jù)隸屬于某一類的概率。FCM算法以其“模糊”的輸出特點(diǎn)在數(shù)據(jù)挖掘、模式識(shí)別等領(lǐng)域應(yīng)用廣泛，而且，伴隨高鐵動(dòng)車組的發(fā)展，F(xiàn)CM聚類逐步應(yīng)用于動(dòng)車組故障關(guān)聯(lián)關(guān)系分析、健康狀態(tài)評(píng)估等方面[2]。

FCM算法的缺陷也是十分明顯[3]。在選取初始聚類中心時(shí)具有隨機(jī)性導(dǎo)致聚類易陷入局部極小，并且，F(xiàn)CM對(duì)于樣本數(shù)據(jù)中的噪聲與孤立點(diǎn)特別敏感，會(huì)導(dǎo)致影響聚類質(zhì)量。本文提出了一種基于FCM的動(dòng)態(tài)加權(quán)模糊聚類算法，利用遺傳算法全局搜索能力強(qiáng)的特點(diǎn)，自適應(yīng)選取最優(yōu)初始聚類中心，并且結(jié)合局部異常因子（LOF，Local Outlier Factorl）密度加權(quán)策略，降低噪聲點(diǎn)對(duì)聚類的影響。經(jīng)通用數(shù)據(jù)集驗(yàn)證，優(yōu)化后的算法有效提高了聚類質(zhì)量和準(zhǔn)確度。

1 模糊聚類

1.1 聚類劃分約束

對(duì)象特征輸入表示X={x1, x2,…, xN}歸為c個(gè)子集{x1, x2,…, xc}，其中，xk表示對(duì)象ok的特征輸入，xi是X中屬于第i輸入類的對(duì)象子集，其對(duì)應(yīng)的歸類輸入的類外延表示由劃分矩陣U=[uik]c×N表示，其中，uik表示對(duì)象ok屬于第i個(gè)輸入類的隸屬度，uik≥0，U通常被稱為隸屬矩陣。根據(jù)隸屬度的不同，產(chǎn)生了不同的劃分約束[4]。

（1）硬劃分 ：

（2）軟劃分 ：

（3）可能性劃分

1.2 FCM算法

FCM算法的表述為[5]：設(shè)樣本數(shù)據(jù)集為x={x1,x2, x3, …, xn}，共包含n個(gè)樣本，現(xiàn)在需將其分為k類，則在樣本數(shù)據(jù)集x中必存在一個(gè)k×n的分類矩陣 U(x)=[uij]，i=1, 2, …, k ；j=1, 2, …, n，uij表示樣本j屬于聚類i的隸屬度，滿足式（1）：

FCM算法是通過求出最佳分類矩陣U(x)以及聚類中心矩陣V(x)，使得總類內(nèi)方差達(dá)到極小。

其中，Xi表示第i類的聚類中心；Dis(xj, Xi)表示樣本點(diǎn)xj到類中心Xi的距離，F(xiàn)CM中最常用的距離公式是歐氏距離；中m表示影響聚類性能的加權(quán)系數(shù)，取值范圍為m≥1。

一個(gè)好的聚類應(yīng)該使得總類內(nèi)方差JFCM在的約束下到達(dá)全局最小。通過迭代運(yùn)算，解得：

1.3 聚類評(píng)價(jià)指標(biāo)

（1）DB指數(shù)，又稱為分類適確性指數(shù)[6]。計(jì)算公式為：

表示任意兩類別的類內(nèi)距離的平均距離除以兩聚類最小中心距離。DB指數(shù)越小意味著類內(nèi)距離越近，類間距離越遠(yuǎn)，聚類質(zhì)量越好。

（2）聚類準(zhǔn)確度[7]。是對(duì)最終聚類劃分正確度的評(píng)價(jià)。準(zhǔn)確度指數(shù)的計(jì)算公式為：

k表示聚類個(gè)數(shù)，N表示樣本點(diǎn)總個(gè)數(shù)，ac表示每一個(gè)類中劃分正確的個(gè)數(shù)。為了保證結(jié)果的準(zhǔn)確，通常會(huì)多做幾次實(shí)驗(yàn)取均值來表示最終的準(zhǔn)確度，H表示實(shí)驗(yàn)次數(shù)。

2 GA-FCM算法

FCM算法在選取初始聚類中心時(shí)具有隨機(jī)性，在迭代時(shí)是以一種類似于爬坡似的方法逐步迭代，是一種局部搜索最優(yōu)解的方法[8]，因而易導(dǎo)致聚類結(jié)果極易陷入局部極小值。遺傳算法是一種應(yīng)用廣泛的全局搜索方法，利用選擇、交叉和變異操作，通過不斷的迭代，逐步逼近最優(yōu)解，從而避免陷入局部最優(yōu)，因而可以和FCM算法進(jìn)行良好互補(bǔ)[9]。這樣，既能發(fā)揮遺傳算法全局搜索能力強(qiáng)的優(yōu)勢(shì)，又可以結(jié)合FCM善于局部搜索的特點(diǎn)，可以很好地解決聚類問題中對(duì)初始點(diǎn)過于敏感這一缺陷。本文將遺傳算法優(yōu)化FCM算法稱之GA-FCM算法。

2.1 編碼

本文采用16 bit二進(jìn)制編碼。假設(shè)原始數(shù)據(jù)集有d個(gè)維度，m行數(shù)據(jù)，則可以表示為：

若將DataSet劃分為k類，則k個(gè)初始聚類中心可以表示為：[(v11,…,v1d),(v21,…,v2d),(vk1,…,vkd]，采用16 bit二進(jìn)制編碼，對(duì)應(yīng)的編碼精度為：

解碼公式為：

2.2 確立適應(yīng)度函數(shù)

GA-FCM算法最核心步驟之一就是利用FCM的類內(nèi)總方差函數(shù)構(gòu)造遺傳算法的適應(yīng)度函數(shù)，其中的關(guān)系要表示為適應(yīng)度函數(shù)越大，類內(nèi)總方差越小，則聚類結(jié)果越優(yōu)。所以將適應(yīng)度函數(shù)定義為：

其中，c∈[1, 2]。

2.3 基于輪盤賭的選擇算子

計(jì)算當(dāng)前第i代的個(gè)體染色體的選擇概率以及當(dāng)前累計(jì)概率：

產(chǎn)生N個(gè)隨機(jī)數(shù)λi∈[0,1](i=1, 2,…, N)。若滿足 λi＜P1，則選擇第一個(gè)個(gè)體 ；若滿足 Pi–1＜λi＜Pi，則選擇第i個(gè)個(gè)體。直至選擇出N個(gè)個(gè)體。

2.4 根據(jù)適應(yīng)度值動(dòng)態(tài)確定交叉算子

本文舍棄隨機(jī)生成交叉算子法，采用一種自適應(yīng)法，根據(jù)種群的適應(yīng)度函數(shù)值來計(jì)算交叉概率，整體原則就是如果該染色體的適應(yīng)度值較小，則它發(fā)生交叉的概率越大；如果適應(yīng)度大，則交叉概率越小。這樣在保證種群豐富度的同時(shí)，還可以盡量避免優(yōu)良個(gè)體被破壞。交叉概率計(jì)算公式為：

其中，pmax表示最大交叉概率，為[0.8, 0.9]之間的隨機(jī)數(shù)；pmin表示最小交叉概率，為[0.2, 0.3]之間的隨機(jī)數(shù)；Fitmax表示的當(dāng)前種群中最大的適應(yīng)度值； Fitavg表示當(dāng)前種群中的平均適應(yīng)度值；Fit'max表示發(fā)生交叉的兩個(gè)染色體中較大的適應(yīng)度值。

2.5 根據(jù)適應(yīng)度值動(dòng)態(tài)確定變異算子

變異率是指?jìng)€(gè)體染色體編碼序列中每一位發(fā)生改變的概率。因?yàn)樽儺惖牟环€(wěn)定性，所以說變異概率很低，通常的取值范圍為[0.000 1, 0.1]。本文中，根據(jù)適應(yīng)度值確定變異概率，若當(dāng)前染色體的適應(yīng)度值很低，則有較高變異率；反之，若當(dāng)前個(gè)體的適應(yīng)度值很高，則有較低變異率。計(jì)算公式如下：

Fiti表示當(dāng)前染色體的適應(yīng)度值。pmax'表示最大變異概率，通常為0.1；pmin'為最小變異概率，通常為0.000 1。

3 基于LOF的加權(quán)優(yōu)化算法

樣本數(shù)據(jù)中的離群點(diǎn)與噪聲點(diǎn)對(duì)聚類的影響如圖1所示，由于噪聲點(diǎn)的干擾，類中心的最終位置往往不在合理區(qū)域。針對(duì)FCM算法對(duì)數(shù)據(jù)樣本中的離群點(diǎn)與噪聲點(diǎn)過于敏感，本文采用LOF算法進(jìn)行優(yōu)化，從而保證類中心最后位于樣本區(qū)域密度大的位置。LOF是通過計(jì)算樣本區(qū)域密度來鑒別噪聲點(diǎn)的算法[10-11]。

圖1 噪聲點(diǎn)影響類中心示意圖

算法描述為：

（1）計(jì)算樣本中每個(gè)對(duì)象p與其他對(duì)象的歐氏距離 d(p, o)。

（2）計(jì)算對(duì)于點(diǎn)p的第k 距離dk(p)，即dk(p)=d(p, o)；定義點(diǎn)p的第k鄰域?yàn)镹k(p)，表示p的第k距離以內(nèi)的所有點(diǎn)，滿足|Nk(p)|≥k。

（3）計(jì)算點(diǎn)o到點(diǎn)p的第k可達(dá)距離，為：

（4）計(jì)算點(diǎn)p的可達(dá)密度，表示點(diǎn)p的第k鄰域內(nèi)點(diǎn)到p的平均可達(dá)距離的倒數(shù)。具體公式為：

（5）計(jì)算局部離群因子，定義為點(diǎn)p的鄰域點(diǎn)Nk(p)的局部可達(dá)密度與點(diǎn)p的局部可達(dá)密度之比的平均數(shù)，公式為：

LOF算法對(duì)于樣本異常點(diǎn)的監(jiān)測(cè)是根據(jù)上述求解出的各個(gè)數(shù)值的大小來進(jìn)行判別，理論上講，數(shù)據(jù)異常點(diǎn)是不能剔除的，因?yàn)樘蕹惓｜c(diǎn)會(huì)嚴(yán)重破壞原始數(shù)據(jù)的完整性，而影響最終的聚類劃分，因此，本文將LOF與GA-FCM結(jié)合，可以實(shí)現(xiàn)聚類中心點(diǎn)最終停留在樣本密度大的區(qū)域，降低數(shù)據(jù)噪聲點(diǎn)對(duì)于聚類的影響。

LOF算法中最終求解出的loc_ou_fak(p)，可以表示區(qū)域密度，即：

該值越大，說明點(diǎn)p周圍的區(qū)域密度越大；該值越小，說明點(diǎn)p周圍區(qū)域密度越小，則其越可能是離群點(diǎn)。

則FCM算法中的JFCM可以重新定義為：

GA-FCM算法中適應(yīng)度函數(shù)也重新定義為：

這樣可以保證在樣本密度大的區(qū)域附近，JFCM變小，F(xiàn)itFCM(x)'變大；反之，在樣本密度小的區(qū)域附近，F(xiàn)itFCM(x)'變小，JFCM會(huì)變大，則不會(huì)收斂。便可以保證聚類中心停留在樣本密度大的區(qū)域，有效提高聚類的合理性。因此，本文將這種通過遺傳算法與LOF加權(quán)共同優(yōu)化FCM的算法稱之為WG-FCM算法。

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

4.1 實(shí)驗(yàn)描述

本文試驗(yàn)平臺(tái)：Intel(R) Core(TM) i5-2450M CPU@2.50 GHZ，RAM 4 G，Windows 7操作系統(tǒng)和Matlab R2012(a)。實(shí)驗(yàn)數(shù)據(jù)集：UCI數(shù)據(jù)庫(kù)上的Iris、Wine、Vowel共3組數(shù)據(jù)作為測(cè)試數(shù)據(jù)集進(jìn)行驗(yàn)證。UCI數(shù)據(jù)庫(kù)是國(guó)際通用的用于進(jìn)行數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等算法驗(yàn)證的公開數(shù)據(jù)庫(kù)。測(cè)試數(shù)據(jù)集信息如表1所示。

4.2 聚類對(duì)比分析

本文選用改進(jìn)的FCM算法與標(biāo)準(zhǔn)的FCM算法對(duì)上述3組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，如表2所示的是3種算法聚類準(zhǔn)確率對(duì)比。

表1 測(cè)試數(shù)據(jù)集信息表

由表1與表2可以看出，雖然當(dāng)數(shù)據(jù)集中屬性維度越多時(shí)，聚類準(zhǔn)確率會(huì)下降。但是縱向比較而言，WG-FCM還是可以有效提高聚類準(zhǔn)確性。

從表3中可以看出，GA-FCM與WG-FCM求解出的DB指數(shù)均比原始FCM的低，WG-FCM算法的DB指數(shù)最小，表示可以有效提高聚類質(zhì)量，讓聚類變得更加合理。

表2 3種算法準(zhǔn)確率對(duì)比

從表4中可以看出，WG-FCM算法的收斂速度明顯高于原始FCM算法，相較于GA-FCM算法也是有所提升的，證明了FCM算法通過結(jié)合遺傳算法與LOF加權(quán)后能夠明顯提高全局搜索最優(yōu)值的速度。

表3 3種算法DB指數(shù)對(duì)比

5 結(jié)束語(yǔ)

本文針對(duì)原始FCM算法中心點(diǎn)選取具有隨機(jī)性的缺陷，通過遺傳算法優(yōu)化選取初始中心點(diǎn)，并且，根據(jù)適應(yīng)度值計(jì)算交叉率與變異率，使之具有動(dòng)態(tài)性；對(duì)于數(shù)據(jù)異常點(diǎn)過于敏感的問題，結(jié)合LOF算法，通過添加權(quán)重值重新構(gòu)造FCM算法的準(zhǔn)則函數(shù)，減少數(shù)據(jù)噪聲點(diǎn)對(duì)于聚類的影響，保證最終聚類中心停留在樣本點(diǎn)密度大的區(qū)域，通過UCI數(shù)據(jù)庫(kù)上的標(biāo)準(zhǔn)數(shù)據(jù)證明，WG-FCM算法可以有效提高聚類質(zhì)量和準(zhǔn)確度。

表4 3種算法平均收斂代數(shù)對(duì)比

[1]伍育紅.聚類算法綜述[J].計(jì)算機(jī)科學(xué)，2015，42（Z6）：491-499.

[2]歐陽(yáng)喜德，黃地龍. 基于模糊聚類的數(shù)據(jù)挖掘方法與應(yīng)用[J].鐵路計(jì)算機(jī)應(yīng)用，2008，17（4）：13-16.

[3]朱 然，李積英. 幾種優(yōu)化FCM算法聚類中心的方法對(duì)比及仿真[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2015（5）：17-20.

[4]付 強(qiáng)，袁 磊. 基于聚類分析及SVM的DMI機(jī)車信號(hào)自動(dòng)識(shí)別[J]. 鐵路計(jì)算機(jī)應(yīng)用，2015（8）：46-49.

[5]樸尚哲，超木日力格，于 劍. 模糊C均值算法的聚類有效性評(píng)價(jià)[J]. 模式識(shí)別與人工智能，2015，28（5）.

[6]胡嘉駿，侯麗麗，王志剛，等. 基于模糊C均值隸屬度約束的圖像分割算法[J]. 計(jì)算機(jī)應(yīng)用，2016，36（1）：126-129.

[7]Yang S, Kim J, Chung M. A prediction model based on Big Data analysis using hybrid FCM clustering[C]// Internet Technology and Secured Transactions. IEEE, 2015:337-339.

[8]Vimali J S, Taj Z S. FCM based CF: An efficient approach for consolidating big data applications[C]// International Conference on Innovation Information in Computing Technologies. IEEE,2016:1-7.

[9]李 贏, 舒乃秋. 基于模糊聚類和完全二叉樹支持向量機(jī)的變壓器故障診斷[J].電工技術(shù)學(xué)報(bào)，2016，31（4）：64-70.

[10]肖林云，陳秀宏，林喜蘭. 特征加權(quán)和優(yōu)化劃分的模糊C均值聚類算法[J]. 微電子學(xué)與計(jì)算機(jī)，2016，33（10）：143-146.

[11]Varghese J, Subash S, Khan M S, et al. An efficient LOF-based long-range correlation filter for the restoration of salt and pepper impulse corrupted digital images[J]. Turkish Journal of Electrical Engineering & Computer Sciences, 2016, 24(4):2429-2441.