基于改進(jìn)核可能性C均值類間極大化聚類算法

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

關(guān)鍵詞： 核可能性C均值; 邊界模糊; 聚類算法; 類間極大懲罰項; 調(diào)控因子; 類內(nèi)元素

中圖分類號： TN919.1?34; TP391.41 ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： 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 ?引 ?言

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

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

1 ?改進(jìn)的基于核可能性C均值聚類算法

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

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

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

式中：[m>1]是模糊系數(shù);[CC>1]是對聚類的個數(shù);[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]是加權(quán)指數(shù)，[m]的取值如下：

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

則KMPCM的目標(biāo)函數(shù)為：

[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）

根據(jù)拉格朗日求極值法，當(dāng)目標(biāo)函數(shù)式（5）取得極小值時，其對應(yīng)的必要條件為：

[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算法的具體執(zhí)行步驟如下：

1） 設(shè)定核函數(shù)參數(shù)[σ]，聚類個數(shù)c，模糊指數(shù)m，收斂精度ε，初始化調(diào)控因子[λ=1n]，最大迭代次數(shù)tmax，令迭代次數(shù)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]，轉(zhuǎn)到步驟2）。

當(dāng)滿足終止條件時，隸屬度矩陣[U]和聚類中心矩陣[V]為算法的最優(yōu)解。

2 ?實 ?驗

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

2.1 ?評價指標(biāo)

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

2.2 ?帶噪聲和野值點的模擬數(shù)據(jù)實驗

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

2.2.1 ?Square數(shù)據(jù)集實驗

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

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

2.2.2 ?邊界模糊的模擬數(shù)據(jù)實驗

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

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

2.3 ?UCI真實數(shù)據(jù)集實驗

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

3 ?結(jié) ?論

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

參考文獻(xiàn)

[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].現(xiàn)代電子技術(shù)，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.