基于改進核可能性C均值類間極大化聚類算法

林嘉煒 祁云嵩 陳曉利 凡甲甲

關鍵詞： 核可能性C均值; 邊界模糊; 聚類算法; 類間極大懲罰項; 調控因子; 類內元素

中圖分類號： TN919.1?34; TP391.41 ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2018）24?0117?04

An improved kernel maximum center interval possibilitic C?means clustering algorithm

LIN Jiawei， QI Yunsong， CHEN Xiaoli， FAN Jiajia

（Jiangsu University of Science and Technology， Zhenjiang 212000， China）

Abstract： The kernel possibilitic C?means （KPCM） clustering algorithm only considers the relationships between intra?class elements but ignores the relationships between classes， as a result， the phenomena of too small clustering center interval and even clustering center overlap may occur during the clustering of data sets with fuzzy boundaries. Therefore， an improved kernel maximum center interval possibilitic C?means （KMPCM） clustering algorithm is proposed. In the algorithm， an inter?class maximum penalty term of high?dimensional feature space and regulating factor λ are introduced into the KPCM clustering algorithm， so as to construct a new objective function， which can appropriately expand intervals between class centers to effectively avoid the phenomena of too small clustering center interval and even overlap， make samples near the boundaries better classified， and consider the relationships between intra?class elements to maintain better robustness on noise points and outliers. The results of a large number of experiments show that the improved algorithm has a more obvious superiority in clustering effect on data sets with fuzzy boundaries than the traditional clustering algorithm.

Keywords： kernel possibilitic C?means; fuzzy boundary; clustering algorithm; inter?class maximum penalty term; regulating factor; intra?class element

0 ?引 ?言

模糊聚類是采用模糊數學語言對事物按照一定的要求進行描述和分類的數學方法[1]。經典的模糊聚類算法有模糊C均值（FCM）算法[2]，FCM的目標函數相對簡單，運行效率較高，但其有隸屬度和為1的約束條件，因此受噪聲點和野值點的影響較大。為解決此問題，提出可能性C均值（PCM）算法[3]，其打破隸屬度和為1的約束條件，使得噪聲點和野值點的隸屬度值較小，噪聲點和野值點對最終的聚類效果影響不大。而PCM相對FCM存在的缺陷在于最終結果會使得聚類中心距離較近甚至出現重合現象。FCM與PCM的共同缺陷在于處理高維度數據集時往往運行效率低下，數據集得不到好的劃分，而核的引入解決了上述問題，進而提出核模糊性C均值（KFCM）算法[4]和核可能性C均值聚類（KPCM）算法[5]。KPCM算法雖然在處理噪聲點和野值點時性能有所提升，但依舊存在兩點缺陷：缺乏考慮類與類之間的聯系，而在實際情況中，類與類之間是有聯系的;容易造成聚類中心距離過小甚至重合的現象。

針對上述問題，本文在KPCM的基礎上引入類間極大懲罰項以及調控因子λ構造新的目標函數，提出一種基于改進核可能性C均值類間極大化聚類（KMPCM）算法，極大懲罰項考慮類與類之間的聯系，通過拉大聚類中心距離，使得邊界模糊的數據集能得到較好的劃分。

1 ?改進的基于核可能性C均值聚類算法

設[X=x1，x2，…，xn?Rs]表示給定的樣本集合，[s]是樣本空間的維數，[n]是樣本個數。定義一個非線性映射[Φ：X→Φ（X）∈F]是從[X]到特征空間[F]的映射，[F]是映射[Φ]對應的核函數。KPCM的目標函數如下：[JKPCM（U，V）=2i=1Cj=1numij1+K（xj，vi）+ ? ? ? ? ? ? ? ? ? ? ? ? ?i=1Cηij=1n（1-uij）m] （1）

高維特征空間的類間極大懲罰項表達形式如下：

[q=λC-1i=1Ck=1，k≠iCvi-vk2] ?（2）

式中：[m>1]是模糊系數;[CC>1]是對聚類的個數;[V]表示聚類中心且[V=v1，v2，…，vC];[U=uij]是一個[C×n]的模糊劃分矩陣;[uij]是第[j]個樣本[xj]屬于第[i]類的隸屬度值;[ηi]是懲罰因子，建議取值為：

[ηi=K2j=1nuij（1-K（xj，vi））j=1nuijm， K>0，一般取1] （3）

式中，[m]是加權指數，[m]的取值如下：

[m=min（n，p）min（n，p-1）-2 或 m=2] ? ? ? ? ? （4）

則KMPCM的目標函數為：

[JKMPCM（U，V）=2i=1Cj=1numij1-Kxj，vi+ ? ? ? ? ?i=1Cηij=1n（1-uij）m-2λC-1i=1Ck=1，k≠iC1-Kvi，vk] ? ? ?（5）

根據拉格朗日求極值法，當目標函數式（5）取得極小值時，其對應的必要條件為：

[uij=11+21-K（xj，vi）-2λk=1，k≠iC1-K（vi，vk）ηi1m-1] （6）

[vi=j=1nuijKxj，vixj-λC-1k=1，k≠iCKvi，vkvkj=1numijKxj，vi-λC-1k=1，k≠iCKvi，vkvi] ?（7）

可得KMPCM算法的具體執行步驟如下：

1） 設定核函數參數[σ]，聚類個數c，模糊指數m，收斂精度ε，初始化調控因子[λ=1n]，最大迭代次數tmax，令迭代次數k=0。

2） 用FCM算法初始化中心矩陣[V（0）]。

3） 用式（6）計算[U（k+1）]。

4） 用式（7）計算[V（k+1）]。

5） 如果[U（k）-U（k+1）≤ε]，停止迭代;否則，[k=k+1]，轉到步驟2）。

當滿足終止條件時，隸屬度矩陣[U]和聚類中心矩陣[V]為算法的最優解。

2 ?實 ?驗

本文實驗是使用Matlab R2012a的編程環境。為說明本文提出的算法具有較好的有效性，本文擬通過與經典的算法，例如FCM，PCM以及一些改進的經典算法KPCM，KFCM進行比較，主要是在模擬數據集和UCI真實數據集上進行對比試驗。

2.1 ?評價指標

本文將選用國際常用的歸一化互信息（Normalized Mutual Information，NMI）[6]和芮氏（Rand Index，RI）[7]兩個指標來評價本文算法的性能。這兩個評價指標的取值范圍均為[0，1]，且隨著數值的增大，顯示出算法的性能更加優越。

2.2 ?帶噪聲和野值點的模擬數據實驗

為驗證KMPCM算法是否依舊保留對噪聲點和野值點具有良好的魯棒性，進行噪聲點和野值點的模擬數據實驗。在這部分實驗中，采用原始數據集中具有噪聲點和野值點的Square數據集[8]和邊界模糊的高斯數據集[9]。

2.2.1 ?Square數據集實驗

Square數據集由三部分組成：一大一小兩個正方形數據集以及噪聲點。圖1和表1分別給出實驗結果圖和實驗數據表。

通過圖1、表1得知，KMPCM算法最終聚類效果最佳，使得聚類中心偏離距離最小，對噪聲點和野值點具有更好的魯棒性。

2.2.2 ?邊界模糊的模擬數據實驗

人造高斯數據集可以根據實驗需求進行構造，因此本文在選取數據集來進行算法對邊界模糊處的處理時采用人造高斯數據集。構造高斯數據集時，將高斯核函數的類中心、類方差，以及數據樣本數設定好，再隨機生成。本文采用兩組數據集的相關參數如圖2，圖3，表2，表3所示。

從圖2、圖3以及表2、表3可以看出，在處理邊界模糊數據集時，FCM，PCM，KFCM和KPCM容易造成誤分的問題，而KMPCM因為考慮到類與類間的聯系，并且沒有放棄原來類內元素的關系，所以使得邊界處的模糊數據得到了較好的劃分，分類性能也較其他4種算法有了一定的提高。

2.3 ?UCI真實數據集實驗

上述實驗均為模擬數據集，為更加全面地驗證本文算法的有效性，采用6個經典的UCI[10]真實數據集進行實驗，并與其他4種算法進行對比實驗。實驗結果如表4所示。通過表4可以看出，KMPCM在對高維數據集進行聚類實驗時，其效果相對其他4種聚類算法有所提升。上述實驗數據從模擬數據集到真實數據集再到UCI數據集，全面地驗證了算法的有效性。在模擬數據集中，先是對有噪聲點和野值點的數據集進行試驗。試驗結果表明，KMPCM依舊保存著PCM和KPCM抗噪聲性能良好的特性，并且由于考慮到類間關系，從而使得聚類效果更佳。在邊界模糊的數據集中采用人造高斯核函數隨機生成的數據集。由于其他4個聚類算法只是考慮類內關系，因此在處理具有這類特性的數據集時，效果不是很理想。反觀本文提出的KMPCM算法，考慮類間關系，適當拉大類中心距離，從而使得聚類效果有所提升。但是本文的算法還是存在一些缺點，在對初始化的參數如何選取時并沒有一個很好的方法來選取。

3 ?結 ?論

PCM對于高維數據集的處理顯得效率低下且得不到好的劃分。在引入核函數后，提出KPCM較好地解決了高維數據集的聚類問題，但是保留了PCM的缺陷：聚類結果往往使得聚類中心距離較小甚至出現重合現象，使得邊界模糊的數據集得不到好的聚類效果。針對上述問題，本文引入類間極大懲罰項和調控因子λ，考慮類與類之間的關系，提出一種基于改進型核可能性C均值類間極大化聚類（KMPCM）算法。在實驗部分，采用帶噪聲和野值點的模擬數據實驗、邊界模糊的高斯數據集和UCI真實數據集進行對比實驗。最終的實驗結果表明，KMPCM相對其他4種聚類算法具有更好的抗噪聲能力，對于邊界模糊的數據集具有更好的聚類效果，以及處理高維數據集的優越性。但是該算法依舊存在現有聚類算法普遍存在的問題：沒有一個好的選取機制選取算法的初始化參數。以后的研究方向是如何選取參數使得聚類算法達到最優的、穩定的聚類效果。

參考文獻

[1] LZAKIAN H， PEDRYCZ W， JAMAL I. Fuzzy clustering of time series data using dynamic time warping distance [J]. Engineering applications of artificial intelligence， 2015， 39： 235?244.

[2] 孫如英，韓榮蒼.基于FCM的模糊粗糙屬性約簡[J].現代電子技術，2009，32（17）：194?196.

SUN Ruying， HAN Rongcang. Attribute reduction approach based on fuzzy rough set and FCM [J]. Modern electronics technique， 2009， 32（17）： 194?196.

[3] LIU Z M， LI S Z， LIN D Z， et al. Blog community discovery based on PCM clustering algorithm [J]. Journal of Xiamen University， 2009， 48（4）： 508?513.

[4] WANG X. KFCM algorithm based on the source code mining method study [C]// Proceedings of 5th International Conference on Intelligent Systems Design and Engineering Applications. Changsha： IEEE， 2014： 586?588.

[5] MA Z T， GAO J W， QIN Y， et al. Fault diagnosis of metro vehicle auxiliary inverter based on PSO?KPCM algorithm [J]. Applied mechanics & materials， 2013， 385： 593?596.

[6] LIU J， MOHAMMED J， CARTER J， et al. Distance?based clustering of CGH data [J]. Bioinformatics， 2006， 22（16）： 1971?1978.

[7] PAL N R， PAL K， KELLER J M， et al. A possibilistic fuzzy C?means clustering algorithm [J]. IEEE transactions on fuzzy systems， 2005， 13（4）： 517?530.

[8] ZADEH L A. Fuzzy sets [J]. Information and control， 1965， 8（3）： 338?353.

[9] YOSHIKAWA Y， IWATA T， SAWADA H. Non?linear regression for bag?of?words data via Gaussian process latent variable set model [C/OL]. [2015?02?21]. https：//www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9796.

[10] LIANG G E， LANG J T， TANG H， et al. Clustering high?dimensional data using PCA?Hubness [J]. Modern computer， 2017（11）： 52?55.