一種動態加權模糊聚類算法的研究

劉 銳，張 寧

（北京交通大學 計算機與信息技術學院，北京 100044）

聚類是按照一定規則對某一事物進行區分和歸類的動態過程，在整個過程中，沒有專家知識的指導，沒有先驗知識的支持，聚類僅僅依靠事物之間的“相似度”作為劃分的標準[1]。是一種典型的無監督式學習，相較于監督式學習，數據標簽是區分兩者的最重要指標。

FCM算法，即模糊C均值聚類算法，是一種典型的軟化分聚類算法，舍棄了硬劃分中非0即1的方法，采用一種劃分矩陣的輸出形式來表示某一樣本數據隸屬于某一類的概率。FCM算法以其“模糊”的輸出特點在數據挖掘、模式識別等領域應用廣泛，而且，伴隨高鐵動車組的發展，FCM聚類逐步應用于動車組故障關聯關系分析、健康狀態評估等方面[2]。

FCM算法的缺陷也是十分明顯[3]。在選取初始聚類中心時具有隨機性導致聚類易陷入局部極小，并且，FCM對于樣本數據中的噪聲與孤立點特別敏感，會導致影響聚類質量。本文提出了一種基于FCM的動態加權模糊聚類算法，利用遺傳算法全局搜索能力強的特點，自適應選取最優初始聚類中心，并且結合局部異常因子（LOF，Local Outlier Factorl）密度加權策略，降低噪聲點對聚類的影響。經通用數據集驗證，優化后的算法有效提高了聚類質量和準確度。

1 模糊聚類

1.1 聚類劃分約束

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

（1）硬劃分 ：

（2）軟劃分 ：

（3）可能性劃分

1.2 FCM算法

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

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

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

一個好的聚類應該使得總類內方差JFCM在的約束下到達全局最小。通過迭代運算，解得：

1.3 聚類評價指標

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

表示任意兩類別的類內距離的平均距離除以兩聚類最小中心距離。DB指數越小意味著類內距離越近，類間距離越遠，聚類質量越好。

（2）聚類準確度[7]。是對最終聚類劃分正確度的評價。準確度指數的計算公式為：

k表示聚類個數，N表示樣本點總個數，ac表示每一個類中劃分正確的個數。為了保證結果的準確，通常會多做幾次實驗取均值來表示最終的準確度，H表示實驗次數。

2 GA-FCM算法

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

2.1 編碼

本文采用16 bit二進制編碼。假設原始數據集有d個維度，m行數據，則可以表示為：

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

解碼公式為：

2.2 確立適應度函數

GA-FCM算法最核心步驟之一就是利用FCM的類內總方差函數構造遺傳算法的適應度函數，其中的關系要表示為適應度函數越大，類內總方差越小，則聚類結果越優。所以將適應度函數定義為：

其中，c∈[1, 2]。

2.3 基于輪盤賭的選擇算子

計算當前第i代的個體染色體的選擇概率以及當前累計概率：

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

2.4 根據適應度值動態確定交叉算子

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

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

2.5 根據適應度值動態確定變異算子

變異率是指個體染色體編碼序列中每一位發生改變的概率。因為變異的不穩定性，所以說變異概率很低，通常的取值范圍為[0.000 1, 0.1]。本文中，根據適應度值確定變異概率，若當前染色體的適應度值很低，則有較高變異率；反之，若當前個體的適應度值很高，則有較低變異率。計算公式如下：

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

3 基于LOF的加權優化算法

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

圖1 噪聲點影響類中心示意圖

算法描述為：

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

（2）計算對于點p的第k 距離dk(p)，即dk(p)=d(p, o)；定義點p的第k鄰域為Nk(p)，表示p的第k距離以內的所有點，滿足|Nk(p)|≥k。

（3）計算點o到點p的第k可達距離，為：

（4）計算點p的可達密度，表示點p的第k鄰域內點到p的平均可達距離的倒數。具體公式為：

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

LOF算法對于樣本異常點的監測是根據上述求解出的各個數值的大小來進行判別，理論上講，數據異常點是不能剔除的，因為剔除異常點會嚴重破壞原始數據的完整性，而影響最終的聚類劃分，因此，本文將LOF與GA-FCM結合，可以實現聚類中心點最終停留在樣本密度大的區域，降低數據噪聲點對于聚類的影響。

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

該值越大，說明點p周圍的區域密度越大；該值越小，說明點p周圍區域密度越小，則其越可能是離群點。

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

GA-FCM算法中適應度函數也重新定義為：

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

4 實驗結果與分析

4.1 實驗描述

本文試驗平臺：Intel(R) Core(TM) i5-2450M CPU@2.50 GHZ，RAM 4 G，Windows 7操作系統和Matlab R2012(a)。實驗數據集：UCI數據庫上的Iris、Wine、Vowel共3組數據作為測試數據集進行驗證。UCI數據庫是國際通用的用于進行數據挖掘、機器學習等算法驗證的公開數據庫。測試數據集信息如表1所示。

4.2 聚類對比分析

本文選用改進的FCM算法與標準的FCM算法對上述3組數據集進行實驗，如表2所示的是3種算法聚類準確率對比。

表1 測試數據集信息表

由表1與表2可以看出，雖然當數據集中屬性維度越多時，聚類準確率會下降。但是縱向比較而言，WG-FCM還是可以有效提高聚類準確性。

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

表2 3種算法準確率對比

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

表3 3種算法DB指數對比

5 結束語

本文針對原始FCM算法中心點選取具有隨機性的缺陷，通過遺傳算法優化選取初始中心點，并且，根據適應度值計算交叉率與變異率，使之具有動態性；對于數據異常點過于敏感的問題，結合LOF算法，通過添加權重值重新構造FCM算法的準則函數，減少數據噪聲點對于聚類的影響，保證最終聚類中心停留在樣本點密度大的區域，通過UCI數據庫上的標準數據證明，WG-FCM算法可以有效提高聚類質量和準確度。

表4 3種算法平均收斂代數對比

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

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

[3]朱 然，李積英. 幾種優化FCM算法聚類中心的方法對比及仿真[J]. 計算機技術與發展，2015（5）：17-20.

[4]付 強，袁 磊. 基于聚類分析及SVM的DMI機車信號自動識別[J]. 鐵路計算機應用，2015（8）：46-49.

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

[6]胡嘉駿，侯麗麗，王志剛，等. 基于模糊C均值隸屬度約束的圖像分割算法[J]. 計算機應用，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].電工技術學報，2016，31（4）：64-70.

[10]肖林云，陳秀宏，林喜蘭. 特征加權和優化劃分的模糊C均值聚類算法[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.