李斌 狄嵐 王少華 于曉瞳

摘要：傳統(tǒng)的核聚類僅考慮了類內元素的關系而忽略了類間的關系，對邊界模糊或邊界存在噪聲點的數(shù)據(jù)集進行聚類分析時，會造成邊界點的誤分問題。為解決上述問題，在核模糊C均值（KFCM）聚類算法的基礎上提出了一種基于改進核模糊C均值類間極大化聚類（MKFCM）算法。該算法考慮了類內元素和類間元素的聯(lián)系，引入了高維特征空間的類間極大懲罰項和調控因子，拉大類中心間的距離，使得邊界處的樣本得到了較好的劃分。在各模擬數(shù)據(jù)集的實驗中，該算法在類中心的偏移距離相對其他算法均有明顯降低。在人造高斯數(shù)據(jù)集的實驗中，該算法的精度（ACC）、歸一化互信息（NMI）、芮氏指標（RI）指標分別提升至0.9132，0.7575，0.9138。

對于邊界模糊或邊界存在噪聲點的數(shù)據(jù)集，該聚類算法具有理論研究意義。

關鍵詞：

核聚類；模糊C均值聚類；類間極大懲罰項；模糊邊界

中圖分類號： TP391.4； TP18 文獻標志碼：A

0引言

聚類分析是數(shù)據(jù)挖掘和無監(jiān)督模式識別學習的主要任務之一，已廣泛應用于數(shù)據(jù)挖掘、圖像處理、計算機視覺、生物信息和文本分析等領域中。針對數(shù)據(jù)的分析方法一般分為三大類，即有監(jiān)督的學習、半監(jiān)督的學習以及無監(jiān)督的學習。有監(jiān)督的學習方法中，典型代表就是K近鄰（KNearest Neighbor， KNN）算法；半監(jiān)督的學習方法中，具有代表性的是支持向量機（Support Vector Machine， SVM），以及一些相關的改進算法[1-2]；而無監(jiān)督方法主要是以聚類分析方法為主，聚類的方法可以分為基于劃分的方法、基于分層的方法、基于密度的方法和基于網(wǎng)格的方法，其中，基于劃分的聚類算法[3]在模式識別里是最常用的聚類分析方法，本文主要是針對此類算法進行討論的。

聚類是指將一組給定的未知類標號的數(shù)據(jù)分類到不同的類，且保證同一個類內的對象有較大的相似性，而類間的對象有較大的差異性[4]。聚類算法有很多，典型的算法有基于硬劃分的kmeans算法以及基于軟劃分的模糊C均值（Fuzzy CMeans， FCM）聚類算法[5]，此處的軟硬即表示隸屬度的模糊程度區(qū)別，隸屬度越模糊則“軟”的程度越大，隸屬度越精確則越偏向“硬”的程度。FCM算法存在對噪聲點與野值點敏感和只善于發(fā)現(xiàn)致密的球形結構等缺點。為了克服FCM的缺點，在模式識別的各個領域內出現(xiàn)了很多以FCM為基礎的一些算法，比較突出的有可能性C均值（Possibilistic CMeans， PCM）聚類算法[6]、模糊可能性C均值（Possibilistic Fuzzy CMeans， FPCM）聚類算法[7]、基于核的可能C均值（Kernel Possibilistic CMeans， KPCM）聚類算法[8]等。

Aizerman等[9]在1964年把核函數(shù)的思想引入到機器學習領域。1995年，基于VC理論，Cortes等[10]提出支持向量機（SVM）分類算法，SVM在一些問題上得到比傳統(tǒng)分類器更好的性能。SVM的成功使得核函數(shù)的應用得到重視并應用到機器學習的其他領域，如核主成分分析、核Fisher鑒別分析以及基于核的聚類分析等。基于核方法的聚類通過核函數(shù)把原始空間中的點映射到特征空間中，在特征空間直接或間接地進行算法設計、分析與計算，從而得到原始空間的聚類劃分。在一定程度上，基于核的聚類方法提高了聚類的效果，但是，不管是傳統(tǒng)聚類或者核聚類，大部分聚類算法都只是考慮類內關系，而忽略了類與類之間的關系。

類與類之間的關系被廣泛應用于聚類的有效性指標問題中，例如：Xie等[11]提出的XB（XieBeni）指標；Fukuyama[12]提出的有FS（FukuyamaSugeno）指標；Zahid等[13]提出的SC指標；Gath等[14]提出的FHV（Fuzzy Hyper Volume）和PD（Partition Density）指標等。zdemir等[15]提出的簇間分離（InterCluster Separation， ICS）算法將分離項應用到聚類目標函數(shù)中。由于類與類之間的協(xié)方陣是表示類中心與類中心之間的距離，而它們的距離取得最大值會有更好的聚類效果。本文提到的基于核化距離的模糊C均值（Kernel Fuzzy CMeans，KFCM）聚類算法[16]，在一定程度上，該算法增強了對噪聲點或野值點的魯棒性，提高改善了聚類效果；但是KFCM算法始終是以模糊聚類為基礎且忽略了類與類之間的距離信息。

綜上，本文提出了一種基于改進核模糊C均值類間極大化（Maximum betweencluster based on improved Kernel Fuzzy CMeans， MKFCM）聚類算法。該算法由類內最小和類間最松散的聚類準則推導而出，將Wu等[17]提出的算法作進一步改進，使得類中心與類中心之間距離極大化，構造出全新的目標函數(shù)。實驗結果表明，MKFCM算法比KFCM算法對噪聲點或野值點有較好的魯棒性，對樣本不平衡數(shù)據(jù)集和邊界模糊數(shù)據(jù)集具有更佳的聚類效果。

1基于核的模糊C均值聚類算法

2改進的基于核化距離的模糊C均值聚類算法

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

2.1參數(shù)優(yōu)化

2.2MKFCM的算法描述

根據(jù)定理1的推導，可得MKFCM算法的具體執(zhí)行步驟如下：

步驟1設定核函數(shù)參數(shù)σ、聚類個數(shù)c和模糊指數(shù)m及收斂精度ε；初始化調控因子λ=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，轉到步驟2。

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

3實驗

實驗是基于Matlab R2012a的編程環(huán)境中進行的。為了驗證本文提出的算法的有效性，本文擬通過與FCM[5]、PCM[6]、FPCM[7]、KPCM[8]、KFCM[16]在模擬數(shù)據(jù)集和UCI真實數(shù)據(jù)集上進行對比實驗，對本文所提出的算法進行評估和性能驗證。

3.1評價指標

本文將選用以下三個指標，對聚類的結果進行評價，通過3個指標可以直觀的評價本文算法的性能。

1）精度（ACCuracy， ACC）評價指標[19]。

ACC=[∑Ni=1δ（yi，map（ci））]/N（19）

其中：N表示數(shù)據(jù)點個數(shù)；yi表示真實的類標簽，ci表示聚類過后的類標簽；如果y=c，那么δ（y，c）=1，否則δ（y，c）=0a2+b2此處是否書寫有誤，是0乘以平方根嗎？不就等于0嗎？若有誤，請作相應調整。；map（·）表示每個聚類過后的類標簽到真實的類標簽的一個置換函數(shù)，并且可以通過匈牙利算法獲得最佳匹配。

2）歸一化互信息（Normalized Mutual Information， NMI）評價指標[20]。

NMI=∑ci=1∑cj=1Nij lgN×NijNi×Nj（∑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）評價指標[20]。

RI=f00+f11N（N-1）/2（21）

其中： f00表示數(shù)據(jù)點具有不同的類標簽，且屬于不同類的數(shù)據(jù)點數(shù)目； f11表示具有相同的類標簽，且屬于同一類別的數(shù)

據(jù)點數(shù)目；N表示樣本的容量大小。

以上的3種評價指標的取值范圍均為[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個點是關于Y軸對稱的兩個類，兩類的準確中心分別為C1（-3.34，0）與C2（3.34，0），中間位置的兩個樣本點分別是噪聲點和野值點，且它們到中心的距離相等。相關的實驗結果如圖1所示，較小的“+”表示第一類數(shù)據(jù)集，“△”表示第一類數(shù)據(jù)集的聚類中心；“o”表示第二類數(shù)據(jù)集，“·”表示第二類數(shù)據(jù)集的聚類中心。相關的中心偏移距離如表1所示。

3.2.2Square數(shù)據(jù)集實驗

Square數(shù)據(jù)集則包括一個小正方形數(shù)據(jù)集、一個大正方形數(shù)據(jù)行和部分噪聲點，兩個類的中心分別為C1（5.25，0.25）和C2（17，0），實驗結果圖2所示，“o”表示第一類數(shù)據(jù)集，“·”表示第一類數(shù)據(jù)集的聚類中心；“+”表示第二類數(shù)據(jù)集，“*”表示第二類數(shù)據(jù)集的聚類中心。實驗結果數(shù)據(jù)如表2所示。

3.2.3Bensaid數(shù)據(jù)集實驗

Bensaid數(shù)據(jù)集包括兩個小的類和一個大的類以及各類之間的噪聲點構成的，其3個準確的類中心為C1（3.2904，48.7730）、C2（55.3239，52.0772）和C3（112.1437，49.1043），實驗結果如圖3所示和，“o”表示第一類數(shù)據(jù)集，“·”表示第一類數(shù)據(jù)集的聚類中心；“+”表示第二類數(shù)據(jù)集，“☆”表示第二類數(shù)據(jù)集的聚類中心；“*”表示第三類數(shù)據(jù)集，“△”表示第三類數(shù)據(jù)集的聚類中心。實驗結果如表3所示。

通過圖1～3以及圖表1～3的實驗結果可以看出MKFCM相比其他算法聚類中心偏離的最小，聚類效果更佳，對噪聲點和野值點具有較好的魯棒性。

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

3.2.4人造高斯數(shù)據(jù)集實驗

人造高斯數(shù)據(jù)集由三類組成的，類之間邊界模糊，實驗結果如圖4所示?！皁”表示第一類數(shù)據(jù)集，“·”表示第一類數(shù)據(jù)集的聚類中心；“+”表示第二類數(shù)據(jù)集，“☆”表示第二類數(shù)據(jù)集的聚類中心；“*”表示第三類數(shù)據(jù)集，“△”表示第三類數(shù)據(jù)集的聚類中心。

從圖4以及表4可以看出：FCM、PCM、FPCM、KPCM和KFCM由于邊界處的數(shù)據(jù)較模糊，因此容易造成誤分的問題；而MKFCM則通過拉大類中心間的距離，同時考慮了類內與類間的關系，使得邊界處的模糊數(shù)據(jù)得到了較好的劃分，因此分類性能較其他4種算法有了一定的提高。

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

為了更好地證明本文算法的聚類優(yōu)越性以及魯棒性，與相關的傳統(tǒng)算法進行比較，本文采用4個經典的UCI真實數(shù)據(jù)集進行實驗。表5為本文采用的UCI數(shù)據(jù)集詳細描述。

通過表6可以看出，MKFCM在公認的高維數(shù)據(jù)集中的聚類性能較之其余4種算法也有了明顯的提升。

通過表2～4以及表6中MKFCM與傳統(tǒng)的聚類算法在ACC、NMI、RI三種性能指標上的比較，可以得到一個結論：即本文算法能夠很好地通過調節(jié)中心之間的距離來提高聚類效果，并且特別是對帶有噪聲和邊界模糊的數(shù)據(jù)集有很好的魯棒性。MKFCM算法，既繼承了傳統(tǒng)算法的可以很好地劃分非線性可分數(shù)據(jù)的優(yōu)點，又降低了對噪聲點的敏感程度，還能較好地對邊界模糊數(shù)據(jù)集進行聚類。通過幾組實驗，很好地證明了類間極大化的KFCM算法，相比其他幾種聚類算法，在ACC、NMI、RI三種性能指標上有著明顯的精度提升；但是本文提出的算法也有一些不足，即對聚類中心初始化以及參數(shù)選擇問題仍有待改進。

4結語

KFCM是FCM在高維特征空間中的推廣，本文從特征空間中類與類之間的距離關系進行改進，引入了類間極大懲罰項，并引入懲罰因子實現(xiàn)對類間劃分的控制，提出了一種基于改進型核模糊C均值類間極大化（MKFCM）聚類算法。該算法優(yōu)于現(xiàn)有的FCM、PCM、FPCM、KFCM等算法，聚類的準確性和穩(wěn)定性有明顯提高，對噪聲點的魯棒性較佳，對樣本不平衡數(shù)據(jù)集和邊界模糊數(shù)據(jù)集的聚類效果較好；但是該算法引入了新的參數(shù)且對參數(shù)的確定沒有較好的辦法，所以接下來的方向主要是研究如何確定參數(shù)使得聚類的效果最好。

參考文獻：

[1]

CAI F， CHERKASSKY V. Generalized SMO algorithm for SVMbased multitask learning [J]. IEEE Transactions on Neural Networks and Learning Systems， 2012， 23（6）： 997-1003.

[2]

LIN K P， MING S C. On the design and analysis of the privacypreserving SVM classifier [J]. IEEE Transactions on Knowledge and Data Engineering， 2011， 23（11）： 1704-1717.

[3]

HALL 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.

[4]

CAMERON A C， MILLER D L. A practitioners guide to clusterrobust inference [J]. Journal of Human Resources， 2015， 50（2）： 317-372.

[5]

GONG 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.

[6]

ZANG J， LI C. Possibilistic Cmeans algorithm based on collaborative optimization [C]// Proceedings of the 2014 International Conference on Computer Science and Information Technology. Berlin： Springer， 2014： 587-593.

[7]

RUBIO E， CASTILLO O. A new proposal for a granular fuzzy Cmeans algorithm [M]// Design of Intelligent Systems based on Fuzzy Logic， Neural Networks and NatureInspired Optimization. Berlin： Springer， 2015： 47-57.

[8]

RAZA 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.

[9]

AIZERMAN A， BRAVERMAN E M， ROZONER L I. Theoretical foundations of the potential function method in pattern recognition learning [J]. Automation and Remote Control， 1964， 25（5）： 821-837.

[10]

CORTES C， VAPNIK V. Supportvector networks [J]. Machine Learning， 1995， 20（3）： 273-297.

[11]

XIE X L， BENI G. A validity measure for fuzzy clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1991， 13（8）： 841-847.

[12]

FUKUYAMA F. What is governance？ [J]. Governance， 2013， 26（3）： 347-368.

[13]

ZAHID N， LIMOURI M， ESSAID A. A new clustervalidity for fuzzy clustering [J]. Pattern Recognition， 1999， 32（7）： 1089-1097.

[14]

GATH I， GEVA A B. Unsupervised optimal fuzzy clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1989， 11（7）： 773-780.

[15]

ZDEMIR D， AKARUN L. Fuzzy algorithms for combined quantization and dithering [J]. IEEE Transactions on Image Processing， 2001， 10（6）： 923-931.

[16]

FERREIRA 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.

[17]

WU K L， YU J， YANG M S. A novel fuzzy clustering algorithm based on a fuzzy scatter matrix with optimality tests [J]. Pattern Recognition Letters， 2005， 26（5）： 639-652.

[18]

WU K L， YANG M S. Alternative Cmeans clustering algorithms [J]. Pattern Recognition， 2002， 35（10）： 2267-2278.

[19]

HUANG Z， NG M K. A fuzzy kmodes algorithm for clustering categorical data [J]. IEEE Transactions on Fuzzy Systems， 1999， 7（4）： 446-452.

[20]

LIU J， MOHAMMED J， CARTER J， et al. Distancebased clustering of CGH data [J]. Bioinformatics， 2006， 22（16）： 1971-1978.

[21]

PAL N R， PAL K， KELLER J M， et al. A possibilistic fuzzy Cmeans clustering algorithm [J]. IEEE Transactions on Fuzzy Systems， 2005， 13（4）： 517-530.

[22]

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

[23]

BENSAID A M， HALL L O， BEZDEK J C， et al. Validityguided （re）clustering with applications to image segmentation [J]. IEEE Transactions on Fuzzy Systems， 1996， 4（2）： 112-123.