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

1、 基于改進(jìn)核模糊C均值類間極大化聚類算法 李斌 狄嵐 王少華 于曉瞳Summary：傳統(tǒng)的核聚類僅考慮了類內(nèi)元素的關(guān)系而忽略了類間的關(guān)系，對邊界模糊或邊界存在噪聲點的數(shù)據(jù)集進(jìn)行聚類分析時，會造成邊界點的誤分問題。為解決上述問題，在核模糊C均值（KFCM）聚類算法的基礎(chǔ)上提出了一種基于改進(jìn)核模糊C均值類間極大化聚類（MKFCM）算法。該算法考慮了類內(nèi)元素和類間元素的聯(lián)系，引入了高維特征空間的類間極大懲罰項和調(diào)控因子，拉大類中心間的距離，使得邊界處的樣本得到了較好的劃分。在各模擬數(shù)據(jù)集的實驗中，該算法在類中心的偏移距離相對其他算法均有明顯降低。在人造高斯數(shù)據(jù)集的實驗中，該算法的精度（ACC）、歸一

2、化互信息（NMI）、芮氏指標(biāo)（RI）指標(biāo)分別提升至0.9132，0.7575，0.9138。對于邊界模糊或邊界存在噪聲點的數(shù)據(jù)集，該聚類算法具有理論研究意義。Key：核聚類；模糊C均值聚類；類間極大懲罰項；模糊邊界： TP391.4； TP18 文獻(xiàn)標(biāo)志碼：A0引言聚類分析是數(shù)據(jù)挖掘和無監(jiān)督模式識別學(xué)習(xí)的主要任務(wù)之一，已廣泛應(yīng)用于數(shù)據(jù)挖掘、圖像處理、計算機(jī)視覺、生物信息和文本分析等領(lǐng)域中。針對數(shù)據(jù)的分析方法一般分為三大類，即有監(jiān)督的學(xué)習(xí)、半監(jiān)督的學(xué)習(xí)以及無監(jiān)督的學(xué)習(xí)。有監(jiān)督的學(xué)習(xí)方法中，典型代表就是K近鄰（KNearest Neighbor， KNN）算法；半監(jiān)督的學(xué)習(xí)方法中，具有代表性的是支

3、持向量機(jī)（Support Vector Machine， SVM），以及一些相關(guān)的改進(jìn)算法1-2；而無監(jiān)督方法主要是以聚類分析方法為主，聚類的方法可以分為基于劃分的方法、基于分層的方法、基于密度的方法和基于網(wǎng)格的方法，其中，基于劃分的聚類算法3在模式識別里是最常用的聚類分析方法，本文主要是針對此類算法進(jìn)行討論的。聚類是指將一組給定的未知類標(biāo)號的數(shù)據(jù)分類到不同的類，且保證同一個類內(nèi)的對象有較大的相似性，而類間的對象有較大的差異性4。聚類算法有很多，典型的算法有基于硬劃分的kmeans算法以及基于軟劃分的模糊C均值（Fuzzy CMeans， FCM）聚類算法5，此處的軟硬即表示隸屬度的模糊程度區(qū)

4、別，隸屬度越模糊則“軟”的程度越大，隸屬度越精確則越偏向“硬”的程度。FCM算法存在對噪聲點與野值點敏感和只善于發(fā)現(xiàn)致密的球形結(jié)構(gòu)等缺點。為了克服FCM的缺點，在模式識別的各個領(lǐng)域內(nèi)出現(xiàn)了很多以FCM為基礎(chǔ)的一些算法，比較突出的有可能性C均值（Possibilistic CMeans， PCM）聚類算法6、模糊可能性C均值（Possibilistic Fuzzy CMeans， FPCM）聚類算法7、基于核的可能C均值（Kernel Possibilistic CMeans， KPCM）聚類算法8等。Aizerman等9在1964年把核函數(shù)的思想引入到機(jī)器學(xué)習(xí)領(lǐng)域。1995年，基于VC理論，C

5、ortes等10提出支持向量機(jī)（SVM）分類算法，SVM在一些問題上得到比傳統(tǒng)分類器更好的性能。SVM的成功使得核函數(shù)的應(yīng)用得到重視并應(yīng)用到機(jī)器學(xué)習(xí)的其他領(lǐng)域，如核主成分分析、核Fisher鑒別分析以及基于核的聚類分析等?；诤朔椒ǖ木垲愅ㄟ^核函數(shù)把原始空間中的點映射到特征空間中，在特征空間直接或間接地進(jìn)行算法設(shè)計、分析與計算，從而得到原始空間的聚類劃分。在一定程度上，基于核的聚類方法提高了聚類的效果，但是，不管是傳統(tǒng)聚類或者核聚類，大部分聚類算法都只是考慮類內(nèi)關(guān)系，而忽略了類與類之間的關(guān)系。類與類之間的關(guān)系被廣泛應(yīng)用于聚類的有效性指標(biāo)問題中，例如：Xie等11提出的XB（XieBeni）指標(biāo)

6、；Fukuyama12提出的有FS（FukuyamaSugeno）指標(biāo)；Zahid等13提出的SC指標(biāo)；Gath等14提出的FHV（Fuzzy Hyper Volume）和PD（Partition Density）指標(biāo)等。zdemir等15提出的簇間分離（InterCluster Separation， ICS）算法將分離項應(yīng)用到聚類目標(biāo)函數(shù)中。由于類與類之間的協(xié)方陣是表示類中心與類中心之間的距離，而它們的距離取得最大值會有更好的聚類效果。本文提到的基于核化距離的模糊C均值（Kernel Fuzzy CMeans，KFCM）聚類算法16，在一定程度上，該算法增強(qiáng)了對噪聲點或野值點的魯棒性，提高

7、改善了聚類效果；但是KFCM算法始終是以模糊聚類為基礎(chǔ)且忽略了類與類之間的距離信息。綜上，本文提出了一種基于改進(jìn)核模糊C均值類間極大化（Maximum betweencluster based on improved Kernel Fuzzy CMeans， MKFCM）聚類算法。該算法由類內(nèi)最小和類間最松散的聚類準(zhǔn)則推導(dǎo)而出，將Wu等17提出的算法作進(jìn)一步改進(jìn)，使得類中心與類中心之間距離極大化，構(gòu)造出全新的目標(biāo)函數(shù)。實驗結(jié)果表明，MKFCM算法比KFCM算法對噪聲點或野值點有較好的魯棒性，對樣本不平衡數(shù)據(jù)集和邊界模糊數(shù)據(jù)集具有更佳的聚類效果。1基于核的模糊C均值聚類算法2改進(jìn)的基于核化距離的

8、模糊C均值聚類算法盡管KFCM算法在一定程度上，相對FCM算法在噪聲點或野值點的魯棒性上有所提高；但是KFCM仍存在以下兩個主要缺點：1）由于仍然采用基于核空間的歐氏距離，沒有考慮類與類之間的信息，而實際情況中，類與類之間的信息在聚類過程中發(fā)揮巨大的作用。2）由于采用梯度下降法迭代求解，易收斂于局部最優(yōu)值，造成了KFCM對野值點或噪聲點的魯棒性不高。本文針對上述問題，提出了改進(jìn)的基于核化距離的模糊C均值聚類（MKFCM）算法。該算法在KFCM算法的目標(biāo)函數(shù)上引入了特征空間內(nèi)的類間極大懲罰項，并通過引入調(diào)控因子實現(xiàn)對特征空間內(nèi)類間劃分的控制，使得聚類中心之間的距離最大化，使特征空間內(nèi)類與類之間的

9、間隔盡可能大。特征空間內(nèi)的類間極大懲罰項的表達(dá)式如下：2.1參數(shù)優(yōu)化2.2MKFCM的算法描述根據(jù)定理1的推導(dǎo)，可得MKFCM算法的具體執(zhí)行步驟如下：步驟1設(shè)定核函數(shù)參數(shù)、聚類個數(shù)c和模糊指數(shù)m及收斂精度；初始化調(diào)控因子=1/n；最大迭代次數(shù)tmax；令迭代次數(shù)k=0。步驟2用FCM算法初始化中心矩陣V（0）。步驟3用式（12）計算U（k+1）。步驟4用式（13）計算V（k+1）。步驟5如果U（k）-U（k-1），停止迭代；否則，k=k+1，轉(zhuǎn)到步驟2。當(dāng)滿足終止條件時，隸屬度矩陣U和聚類中心矩陣V為算法的最優(yōu)解。3實驗實驗是基于Matlab R2012a的編程環(huán)境中進(jìn)行的。為了驗證本文提出的

10、算法的有效性，本文擬通過與FCM5、PCM6、FPCM7、KPCM8、KFCM16在模擬數(shù)據(jù)集和UCI真實數(shù)據(jù)集上進(jìn)行對比實驗，對本文所提出的算法進(jìn)行評估和性能驗證。3.1評價指標(biāo)本文將選用以下三個指標(biāo)，對聚類的結(jié)果進(jìn)行評價，通過3個指標(biāo)可以直觀的評價本文算法的性能。1）精度（ACCuracy， ACC）評價指標(biāo)19。ACC=Ni=1（yi，map（ci）/N（19）其中：N表示數(shù)據(jù)點個數(shù)；yi表示真實的類標(biāo)簽，ci表示聚類過后的類標(biāo)簽；如果y=c，那么（y，c）=1，否則（y，c）=0a2+b2此處是否書寫有誤，是0乘以平方根嗎？不就等于0嗎？若有誤，請作相應(yīng)調(diào)整。；map（）表示每個聚類過

11、后的類標(biāo)簽到真實的類標(biāo)簽的一個置換函數(shù)，并且可以通過匈牙利算法獲得最佳匹配。2）歸一化互信息（Normalized Mutual Information， NMI）評價指標(biāo)20。NMI=ci=1cj=1Nij lgNNijNiNj（ci=1Ni lg Ni/N）（cj=1Nj lg Nj/N）（20）其中：Nij表示第i個聚類與類j之間的契合度；N表示樣容量的大?。籒ij表示第i個聚類的樣本數(shù)目；Nj表示第j個聚類的樣本數(shù)目。3）芮氏（Rand Index， RI）評價指標(biāo)20。RI=f00+f11N（N-1）/2（21）其中： f00表示數(shù)據(jù)點具有不同的類標(biāo)簽，且屬于不同類的數(shù)據(jù)點數(shù)目； f

12、11表示具有相同的類標(biāo)簽，且屬于同一類別的數(shù)據(jù)點數(shù)目；N表示樣本的容量大小。以上的3種評價指標(biāo)的取值范圍均為0，1，且數(shù)值越大，顯示出算法的性能越優(yōu)越。3.2模擬數(shù)據(jù)實驗在模擬實驗部分采用Diamond數(shù)據(jù)集21、Square數(shù)據(jù)集22、Bensaid數(shù)據(jù)集23，這3個數(shù)據(jù)集都是基于原始數(shù)據(jù)中存在噪聲點或野值點的數(shù)據(jù)集，可以很好地驗證MKFCM對噪聲點和野值點的魯棒性；采用人造高斯數(shù)據(jù)集，這個數(shù)據(jù)集中3個類邊界非常模糊，對聚類過程的影響非常大，可以用來檢測MKFCM對邊界模糊數(shù)據(jù)集的聚類效果。3.2.1Diamond數(shù)據(jù)集實驗Diamond數(shù)據(jù)集包含了12個樣本點，其中10個點是關(guān)于Y軸對稱的

13、兩個類，兩類的準(zhǔn)確中心分別為C1（-3.34，0）與C2（3.34，0），中間位置的兩個樣本點分別是噪聲點和野值點，且它們到中心的距離相等。相關(guān)的實驗結(jié)果如圖1所示，較小的“+”表示第一類數(shù)據(jù)集，“”表示第一類數(shù)據(jù)集的聚類中心；“o”表示第二類數(shù)據(jù)集，“”表示第二類數(shù)據(jù)集的聚類中心。相關(guān)的中心偏移距離如表1所示。3.2.2Square數(shù)據(jù)集實驗Square數(shù)據(jù)集則包括一個小正方形數(shù)據(jù)集、一個大正方形數(shù)據(jù)行和部分噪聲點，兩個類的中心分別為C1（5.25，0.25）和C2（17，0），實驗結(jié)果圖2所示，“o”表示第一類數(shù)據(jù)集，“”表示第一類數(shù)據(jù)集的聚類中心；“+”表示第二類數(shù)據(jù)集，“*”表示第二類

14、數(shù)據(jù)集的聚類中心。實驗結(jié)果數(shù)據(jù)如表2所示。3.2.3Bensaid數(shù)據(jù)集實驗Bensaid數(shù)據(jù)集包括兩個小的類和一個大的類以及各類之間的噪聲點構(gòu)成的，其3個準(zhǔn)確的類中心為C1（3.2904，48.7730）、C2（55.3239，52.0772）和C3（112.1437，49.1043），實驗結(jié)果如圖3所示和，“o”表示第一類數(shù)據(jù)集，“”表示第一類數(shù)據(jù)集的聚類中心；“+”表示第二類數(shù)據(jù)集，“”表示第二類數(shù)據(jù)集的聚類中心；“*”表示第三類數(shù)據(jù)集，“”表示第三類數(shù)據(jù)集的聚類中心。實驗結(jié)果如表3所示。通過圖13以及圖表13的實驗結(jié)果可以看出MKFCM相比其他算法聚類中心偏離的最小，聚類效果更佳，對噪

15、聲點和野值點具有較好的魯棒性。通過上述3組數(shù)據(jù)集的實驗可以看出：傳統(tǒng)的FCM、KFCM對存在噪聲點或野值點的數(shù)據(jù)集進(jìn)行聚類分析時，易受噪聲點或野值點的影響，因此聚類中心會發(fā)生較大的偏移。PCM、KPCM雖通過解除了隸屬度和為1的約束，對噪聲點或野值點具有較好的魯棒性；但是它們在對邊界模糊的數(shù)據(jù)集進(jìn)行聚類時，會出現(xiàn)聚類中心重合的現(xiàn)象；本文算法通過類間極大懲罰項本文算法通過添加類間極大懲罰項此句完整嗎？感覺未完或者描述有些問題？請作相應(yīng)調(diào)整。，同時考慮了類內(nèi)元素的緊密性和類間元素的相異性，對噪聲點和野值點有很好的魯棒性；同時對邊界模糊的數(shù)據(jù)集可以通過拉大類中心間距離，使得邊界處的數(shù)據(jù)集得到最佳分類

16、。3.2.4人造高斯數(shù)據(jù)集實驗人造高斯數(shù)據(jù)集由三類組成的，類之間邊界模糊，實驗結(jié)果如圖4所示。“o”表示第一類數(shù)據(jù)集，“”表示第一類數(shù)據(jù)集的聚類中心；“+”表示第二類數(shù)據(jù)集，“”表示第二類數(shù)據(jù)集的聚類中心；“*”表示第三類數(shù)據(jù)集，“”表示第三類數(shù)據(jù)集的聚類中心。從圖4以及表4可以看出：FCM、PCM、FPCM、KPCM和KFCM由于邊界處的數(shù)據(jù)較模糊，因此容易造成誤分的問題；而MKFCM則通過拉大類中心間的距離，同時考慮了類內(nèi)與類間的關(guān)系，使得邊界處的模糊數(shù)據(jù)得到了較好的劃分，因此分類性能較其他4種算法有了一定的提高。3.3UCI真實數(shù)據(jù)集實驗為了更好地證明本文算法的聚類優(yōu)越性以及魯棒性，與相

17、關(guān)的傳統(tǒng)算法進(jìn)行比較，本文采用4個經(jīng)典的UCI真實數(shù)據(jù)集進(jìn)行實驗。表5為本文采用的UCI數(shù)據(jù)集詳細(xì)描述。通過表6可以看出，MKFCM在公認(rèn)的高維數(shù)據(jù)集中的聚類性能較之其余4種算法也有了明顯的提升。通過表24以及表6中MKFCM與傳統(tǒng)的聚類算法在ACC、NMI、RI三種性能指標(biāo)上的比較，可以得到一個結(jié)論：即本文算法能夠很好地通過調(diào)節(jié)中心之間的距離來提高聚類效果，并且特別是對帶有噪聲和邊界模糊的數(shù)據(jù)集有很好的魯棒性。MKFCM算法，既繼承了傳統(tǒng)算法的可以很好地劃分非線性可分?jǐn)?shù)據(jù)的優(yōu)點，又降低了對噪聲點的敏感程度，還能較好地對邊界模糊數(shù)據(jù)集進(jìn)行聚類。通過幾組實驗，很好地證明了類間極大化的KFCM算法

18、，相比其他幾種聚類算法，在ACC、NMI、RI三種性能指標(biāo)上有著明顯的精度提升；但是本文提出的算法也有一些不足，即對聚類中心初始化以及參數(shù)選擇問題仍有待改進(jìn)。4結(jié)語KFCM是FCM在高維特征空間中的推廣，本文從特征空間中類與類之間的距離關(guān)系進(jìn)行改進(jìn)，引入了類間極大懲罰項，并引入懲罰因子實現(xiàn)對類間劃分的控制，提出了一種基于改進(jìn)型核模糊C均值類間極大化（MKFCM）聚類算法。該算法優(yōu)于現(xiàn)有的FCM、PCM、FPCM、KFCM等算法，聚類的準(zhǔn)確性和穩(wěn)定性有明顯提高，對噪聲點的魯棒性較佳，對樣本不平衡數(shù)據(jù)集和邊界模糊數(shù)據(jù)集的聚類效果較好；但是該算法引入了新的參數(shù)且對參數(shù)的確定沒有較好的辦法，所以接下來

19、的方向主要是研究如何確定參數(shù)使得聚類的效果最好。Reference：1CAI F， CHERKASSKY V. Generalized SMO algorithm for SVMbased multitask learning J. IEEE Transactions on Neural Networks and Learning Systems， 2012， 23（6）： 997-1003.2LIN K P， MING S C. On the design and analysis of the privacypreserving SVM classifier J. IEEE Transac

20、tions on Knowledge and Data Engineering， 2011， 23（11）： 1704-1717.3HALL L O， GOLDGOF D B. Convergence of the singlepass and online fuzzy Cmeans algorithms J. IEEE Transactions on Fuzzy Systems， 2011， 19（4）： 792-794.4CAMERON A C， MILLER D L. A practitioners guide to clusterrobust inference J. Journal

21、of Human Resources， 2015， 50（2）： 317-372.5GONG M， LIANG Y， SHI J， et al. Fuzzy Cmeans clustering with local information and kernel metric for image segmentation J. IEEE Transactions on Image Processing， 2013， 22（2）： 573-584.6ZANG J， LI C. Possibilistic Cmeans algorithm based on collaborative optimiz

22、ation C/ Proceedings of the 2014 International Conference on Computer Science and Information Technology. Berlin： Springer， 2014： 587-593.7RUBIO E， CASTILLO O. A new proposal for a granular fuzzy Cmeans algorithm M/ Design of Intelligent Systems based on Fuzzy Logic， Neural Networks and NatureInspir

23、ed Optimization. Berlin： Springer， 2015： 47-57.8RAZA M A， RHEE F C H. Interval type2 approach to kernel possibilistic Cmeans clustering C/ Proceedings of the 2012 IEEE International Conference on Fuzzy Systems. Piscataway， NJ： IEEE， 2012： 1-7.9AIZERMAN A， BRAVERMAN E M， ROZONER L I. Theoretical foun

24、dations of the potential function method in pattern recognition learning J. Automation and Remote Control， 1964， 25（5）： 821-837.10CORTES C， VAPNIK V. Supportvector networks J. Machine Learning， 1995， 20（3）： 273-297.11XIE X L， BENI G. A validity measure for fuzzy clustering J. IEEE Transactions on Pa

25、ttern Analysis and Machine Intelligence， 1991， 13（8）： 841-847.12FUKUYAMA F. What is governance？ J. Governance， 2013， 26（3）： 347-368.13ZAHID N， LIMOURI M， ESSAID A. A new clustervalidity for fuzzy clustering J. Pattern Recognition， 1999， 32（7）： 1089-1097.14GATH I， GEVA A B. Unsupervised optimal fuzzy

26、 clustering J. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1989， 11（7）： 773-780.15ZDEMIR D， AKARUN L. Fuzzy algorithms for combined quantization and dithering J. IEEE Transactions on Image Processing， 2001， 10（6）： 923-931.16FERREIRA M R P， CARVALHO F D A T D. Kernel fuzzy Cmeans with automatic variable weighting J. Fuzzy Sets and Systems， 2014， 237（4）： 1-46.17WU K L， YU J， YANG M S. A novel fuzzy clusteri