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

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

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

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

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

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

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

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

式中：[m>1]是模糊系數(shù);[CC>1]是對(duì)聚類的個(gè)數(shù);[V]表示聚類中心且[V=v1，v2，…，vC];[U=uij]是一個(gè)[C×n]的模糊劃分矩陣;[uij]是第[j]個(gè)樣本[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）取得極小值時(shí)，其對(duì)應(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ù)[σ]，聚類個(gè)數(shù)c，模糊指數(shù)m，收斂精度ε，初始化調(diào)控因子[λ=1n]，最大迭代次數(shù)tmax，令迭代次數(shù)k=0。

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

3） 用式（6）計(jì)算[U（k+1）]。

4） 用式（7）計(jì)算[V（k+1）]。

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

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

2 ?實(shí) ?驗(yàn)

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

2.1 ?評(píng)價(jià)指標(biāo)

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

2.2 ?帶噪聲和野值點(diǎn)的模擬數(shù)據(jù)實(shí)驗(yàn)

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

2.2.1 ?Square數(shù)據(jù)集實(shí)驗(yàn)

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

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

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

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

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

2.3 ?UCI真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

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

3 ?結(jié) ?論

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