余文利,余建軍,方建文

1(衢州職業(yè)技術(shù)學(xué)院 信息工程學(xué)院,衢州 324000)2(衢州學(xué)院 電氣與信息工程學(xué)院,衢州 324000)

基于改進(jìn)高斯核度量和KPCA的數(shù)據(jù)聚類(lèi)新方法①

余文利1,余建軍1,方建文2

1(衢州職業(yè)技術(shù)學(xué)院 信息工程學(xué)院,衢州 324000)2(衢州學(xué)院 電氣與信息工程學(xué)院,衢州 324000)

大多數(shù)超橢球聚類(lèi)(hyper-ellipsoidal clustering,HEC)算法都使用馬氏距離作為距離度量,已經(jīng)證明在該條件下劃分聚類(lèi)的代價(jià)函數(shù)是常量,導(dǎo)致HEC無(wú)法實(shí)現(xiàn)橢球聚類(lèi).本文說(shuō)明了使用改進(jìn)高斯核的HEC算法可以解釋為尋找體積和密度都緊湊的橢球分簇,并提出了一種實(shí)用HEC算法-K-HEC,該算法能夠有效地處理橢球形、不同大小和不同密度的分簇.為實(shí)現(xiàn)更復(fù)雜形狀數(shù)據(jù)集的聚類(lèi),使用定義在核特征空間的橢球來(lái)改進(jìn)K-HEC算法的能力,提出了EK-HEC算法.仿真實(shí)驗(yàn)證明所提出算法在聚類(lèi)結(jié)果和性能上均優(yōu)于K-means算法、模糊C-means算法、GMM-EM算法和基于最小體積橢球(minimum-volume ellipsoids,MVE)的馬氏HEC算法,從而證明了本文算法的可行性和有效性.

數(shù)據(jù)聚類(lèi); 超橢球聚類(lèi); 最小體積橢球; 核主成分分析; 高斯核

聚類(lèi)作為一種重要的數(shù)據(jù)分析手段,是機(jī)器學(xué)習(xí)、模式識(shí)別、計(jì)算機(jī)視覺(jué)和數(shù)據(jù)挖掘等領(lǐng)域的研究熱點(diǎn)[1].聚類(lèi)分析就是把對(duì)象按照性質(zhì)上的親疏程度分多個(gè)類(lèi)或簇,使得簇內(nèi)的數(shù)據(jù)具有較高的相似度,簇間的數(shù)據(jù)具有較高的相異度[2].盡管許多研究者在不斷努力,但目前仍沒(méi)有一種能夠處理所有聚類(lèi)問(wèn)題的最優(yōu)算法,聚類(lèi)仍然是一個(gè)困難和具有挑戰(zhàn)性的問(wèn)題.

傳統(tǒng)的聚類(lèi)算法如K-means、GMM-EM、模糊C-means(FCM)等,都是基于最小化簇內(nèi)樣本點(diǎn)的歐氏距離和的通用聚類(lèi)準(zhǔn)則,基于歐氏度量的聚類(lèi)算法傾向于將樣本點(diǎn)劃分到相同大小、相同密度和球形的分簇中,這些算法無(wú)法完成大而細(xì)長(zhǎng)的分簇的劃分,而現(xiàn)實(shí)世界的數(shù)據(jù)常常以混合高斯分布的形式呈現(xiàn),如橢球形或其他復(fù)雜形狀.為解決上述問(wèn)題,人們提出了各種超橢球聚類(lèi)算法(hyper-ellipsoidal clustering,HEC)[3-10],這些算法通常使用馬氏距離作為距離度量來(lái)建立橢球分簇.現(xiàn)有的HEC算法主要存在以下問(wèn)題:1)過(guò)高的計(jì)算復(fù)雜度,導(dǎo)致在馬氏距離中直接計(jì)算協(xié)方差矩陣非常困難; 2)當(dāng)分簇包含少量樣本點(diǎn)時(shí),協(xié)方差矩陣可能是奇異的.為了克服以上的不足,文獻(xiàn)[3-5]提出基于改進(jìn)馬氏距離和偽協(xié)方差矩陣的HEC算法,但是這些算法的時(shí)間復(fù)雜度仍然很高.另一方面,文獻(xiàn)[8-10]通過(guò)近似分簇體積,即找到最小體積橢球(minimum-volume ellipsoids,MVE),取代了協(xié)方差矩陣的計(jì)算,部分克服了以上的不足.以上大多數(shù)方法都是使用馬氏距離作為距離度量,已經(jīng)證明直接將馬氏距離應(yīng)用于聚類(lèi)不能獲得橢球聚類(lèi)[7],而且劃分聚類(lèi)的代價(jià)函數(shù)也無(wú)法限定分簇的大小和分簇之間的關(guān)系.此外,因?yàn)檫@些算法在聚類(lèi)時(shí)無(wú)需考慮樣本集的密度,所以基于MVE的HEC算法只有等密度分簇的情況才能工作得很好.

本文的目標(biāo)是實(shí)現(xiàn)橢球聚類(lèi)并給出改進(jìn)的實(shí)用HEC算法的實(shí)現(xiàn),首先,提出了使用改進(jìn)高斯核度量的基于MVE的K-HEC算法,該算法能夠處理橢球形狀、不同大小和密度的分簇.為了增強(qiáng)K-HEC算法的能力,通過(guò)在特征空間中映射橢球,提出了EK-HEC算法,該算法能夠處理非線(xiàn)性和細(xì)長(zhǎng)結(jié)構(gòu)的分簇.在模擬數(shù)據(jù)集和標(biāo)準(zhǔn)評(píng)測(cè)數(shù)據(jù)集上的仿真實(shí)驗(yàn)表明,本文算法在聚類(lèi)結(jié)果和性能上與K-means算法、模糊C-means算法、GMM-EM算法和馬氏MVE-HEC算法相比有了很大的提高,從而驗(yàn)證了本文算法在處理橢球形或復(fù)雜形狀數(shù)據(jù)集聚類(lèi)時(shí)的可行性和有效性.

1 問(wèn)題定義

其中D(xi,mk)為輸入模式與第k個(gè)分簇mk的均值向量之間的距離度量.

為了構(gòu)造橢球分簇,HEC算法通常采用馬氏距離.然而在該條件下,劃分聚類(lèi)的代價(jià)函數(shù)是常量[7].為了實(shí)現(xiàn)橢球聚類(lèi),本文使用式(3)的改進(jìn)高斯核作為距離度量

其中mk和Qk分別是第k個(gè)分簇的均值向量和協(xié)方差矩陣.變量α∈[0,1]控制著式(3)的第1項(xiàng)和第2項(xiàng)的權(quán)重.式(3)的第1項(xiàng)表示馬氏距離,第2項(xiàng)與由協(xié)方差矩陣Qk表示的第k個(gè)橢圓分簇的容積成正比.則聚類(lèi)代價(jià)函數(shù)改寫(xiě)為

代價(jià)函數(shù)EC(P)達(dá)到最優(yōu)的必要條件為通過(guò)最小化式(4)得到劃分的分簇中心表示為

證畢.

定理1.如果改進(jìn)高斯核式(3)作為式(2)的聚類(lèi)代價(jià)函數(shù)的距離度量,則

證畢.

2 橢球和復(fù)雜形狀聚類(lèi)

本文提出了兩種最小化分簇體積權(quán)重和的HEC算法—K-HEC算法和EK-HEC算法.其中K-HEC算法是使用改進(jìn)高斯核和MVE近似的迭代HEC算法,它將樣本劃分到指定數(shù)量的橢球分簇中; EK-HEC算法是K-HEC算法的擴(kuò)展,它通過(guò)使用定義在核特征空間的橢球來(lái)改善K-HEC算法的聚類(lèi)能力,以便能處理更復(fù)雜形狀樣本集的聚類(lèi).

2.1 K-HEC算法

K-HEC算法開(kāi)始于一個(gè)初始的聚類(lèi),最終將初始的聚類(lèi)劃分為C個(gè)分簇,在此過(guò)程中算法迭代查找改進(jìn)的劃分矩陣的分配,分簇體積的權(quán)重和不斷縮小,直到分簇結(jié)果沒(méi)有進(jìn)一步可能的改進(jìn)為止.

因此,本文使用三個(gè)近似方法來(lái)尋找MVE.首先,推導(dǎo)式(9)所示的L?wner-John橢球體[11]凸優(yōu)化問(wèn)題,該問(wèn)題可以幾何解釋為最小化橢球體的體積.

其次,通過(guò)近似計(jì)算包含矩陣Q特征向量和的目標(biāo)函數(shù)來(lái)求解式(10)所示凸優(yōu)化問(wèn)題[8,11].

最后,使用Khachiyan的快速近似算法[12]來(lái)尋找MVE.

算法1.K-HEC算法輸入:d維空間的n個(gè)樣本輸出:劃分矩陣P步驟1.確定分簇?cái)?shù)C,從樣本集中隨機(jī)選擇C個(gè)樣本,設(shè)定為分簇的中心,記作mk;步驟2.首先使用樣本與分簇中心mk歐氏距離來(lái)確定劃分矩陣的初始分配x={xi∈Rd}n i=1■■■■■Pik=1,ifDEuc(xi,mk)＜DEuc(xi,mj),j=1,2,...,Candj≠k Pik=0,otherwise步驟3.計(jì)算新的分簇中心和屬于該分簇的樣本的數(shù)量mk=∑n∑ni i=1Pikxi=1Pik,nk=∑n i=1Pik步驟4.使用MVE近似算法計(jì)算偽協(xié)方差矩陣Qk;步驟5.使用式(3)的改進(jìn)高斯核度量、mk和Qk確定劃分矩陣P的一個(gè)新的分配{Pik=1,ifDMGK(xi,mk;Qk)＜DMGK(xi,mj;Qj)Pik=0,otherwise步驟6.如果劃分矩陣P沒(méi)有變化,則算法停止.否則重復(fù)步驟3到步驟5.

2.2 EK-HEC算法

大部分劃分聚類(lèi)算法在對(duì)非線(xiàn)性和細(xì)長(zhǎng)結(jié)構(gòu)數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí),不能取得理想的效果,為此人們提出了譜聚類(lèi)算法[13]和核方法[14].為了在非線(xiàn)性和細(xì)長(zhǎng)結(jié)構(gòu)數(shù)據(jù)集上執(zhí)行聚類(lèi),本文使用了核主成分分析(Kernel principal component analysis,KPCA).通過(guò)RBF核函數(shù),能夠有效地在與基于非線(xiàn)性映射的輸入空間相關(guān)聯(lián)的高維特征空間中計(jì)算主成分.KPCA的原理如下所示.

EK-HEC算法通過(guò)在核空間中執(zhí)行K-HEC算法實(shí)現(xiàn)復(fù)雜形狀聚類(lèi),算法的具體描述如算法2.

算法2.EK-HEC算法輸入:d維空間的n個(gè)樣本輸出:劃分矩陣P Kij=Φ(xi)·Φ(xj)=K(xi,xj);x={xi∈Rd}n i=1步驟1.計(jì)算核矩陣K,i,j = 1,2,...,n;步驟2.解式(12),找到非零的特征值;步驟3.使用非零特征值αk(k=1,2,…,p),計(jì)算樣本Ф(x)在特征向量Vk上的投影;?x=(Vk·Φ(x))=∑n i =1αkiK(xi,x)步驟4.確定分簇?cái)?shù)C,在特征空間中隨機(jī)選擇C個(gè)樣本,將它們?cè)O(shè)置為分簇的中心,記作 ;?mk ?mk步驟5.使用歐氏距離計(jì)算樣本與分簇中心 的距離,確定劃分矩陣P的初始分配■■■■■Pik=1,ifDEuc(?xi,?mk)＜DEuc(?xi,?mj),j=1,2,...Candj≠k Pik=0,otherwise步驟6.計(jì)算新的分簇中心和屬于新分簇的樣本數(shù)?mk=∑ni=1Pik?xi/∑n i=1Pik,nk=∑n i=1Pik ?Qk步驟8.使用式(3)的改進(jìn)高斯核度量、 和 確定劃分矩陣P的新的分配步驟7.使用MVE近似算法計(jì)算偽協(xié)方差矩陣 ;?mk ?Qk■■■■■Pik=1,ifDEuc(?xi,?mk;?Qk)＜DEuc(?xi,?mj;?Qj),j=1,2,...Candj≠k Pik=0,otherwise步驟9.如果劃分矩陣P沒(méi)有變化,則算法終止; 否則重復(fù)步驟6至步驟8.

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)描述

為驗(yàn)證K-HEC算法和EK-HEC算法的有效性,在模擬數(shù)據(jù)集和基準(zhǔn)評(píng)測(cè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn).K-HEC算法和 EK-HEC 算法是在 Matlab 上使用CVX[15]和LMI工具箱編程實(shí)現(xiàn),在Intel(R)Xeon? CPU W5590@line-height:15.5pt3.33GHZ的微機(jī)Windows XP環(huán)境下運(yùn)行.在性能評(píng)估時(shí),使用誤分類(lèi)率(Misclassification rate,MCR)和歸一化互信息(Normalized mutual information,NMI)作為評(píng)價(jià)指標(biāo),分別定義如下

其中X、Y是兩個(gè)隨機(jī)變量,I(X,Y)是互信息,H(X)和H(Y)是X和Y的熵.

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 模擬數(shù)據(jù)集

為了說(shuō)明本文所提出算法的有效性,在實(shí)驗(yàn)中使用了2個(gè)模擬數(shù)據(jù)集(具體描述如表1所示).模擬數(shù)據(jù)集1用以驗(yàn)證K-HEC算法對(duì)于不同大小、不同密度和橢圓形分簇的聚類(lèi)能力,該數(shù)據(jù)集包含一個(gè)圓形的分簇和一人細(xì)長(zhǎng)橢圓形的分簇.K-HEC算法在模擬數(shù)據(jù)集1上使用式(9)-式(11)三種不同的MVE近似方法所提到的聚類(lèi)結(jié)果是一樣的,因此忽略式(9)和式(10)的方法,使用式(11)方法的K-HEC算法在數(shù)據(jù)集1上的聚類(lèi)結(jié)果如圖1所示.

表1 模擬數(shù)據(jù)集

圖1 不同算法在模擬數(shù)據(jù)集1上的聚類(lèi)結(jié)果

從圖1(b)可以看出,K-means算法在模擬數(shù)據(jù)集1上不能得到正確的聚類(lèi); 從(c)可以看出,馬氏HEC算法雖然將樣本劃分為不同大小的兩個(gè)橢圓分簇,但當(dāng)兩個(gè)分簇距離較近時(shí)聚類(lèi)結(jié)果也不準(zhǔn)確; (d)表明本文提出的K-HEC算法通過(guò)調(diào)整α的值來(lái)控制改進(jìn)高斯核的第1項(xiàng)和第2項(xiàng)的權(quán)重,從而最小化分簇體積權(quán)重和,使得聚類(lèi)后分簇的緊湊性和密度達(dá)到最大.

模擬數(shù)據(jù)集2包含一個(gè)高斯分布分簇和一個(gè)香蕉形分簇,用于驗(yàn)證EK-HEC算法的有效性,該算法專(zhuān)門(mén)設(shè)計(jì)用于復(fù)雜幾何形狀樣本集的聚類(lèi).K-means算法、HEC算法、K-HEC算法和EK-HEC算法在模擬數(shù)據(jù)集2上的聚類(lèi)結(jié)果如圖2(b)～(f)所示.

圖2 不同算法在模擬數(shù)據(jù)集2上的聚類(lèi)結(jié)果

從圖2可以看出,K-means算法、馬氏HEC算法以及K-HEC算法有相似的聚類(lèi)結(jié)果.可以注意到,雖然聚類(lèi)結(jié)果相似,但是由每個(gè)算法所確定的聚類(lèi)的決策邊界仍有很大的不同.與其他算法相比,基于Moshtagh方法的MVE近似的Moshtagh-K-HEC算法建立了清晰的決策邊界,而馬氏HEC算法和LMI-K-HEC算法有重疊的決策邊界.EK-HEC算法按照預(yù)期找到了正確的分簇,僅有一個(gè)樣本錯(cuò)分.圖3描述了EK-HEC算法在模擬數(shù)據(jù)集2上的聚類(lèi)結(jié)果,其中(a)和(b)分別描述了在算法在輸入空間和特征空間的聚類(lèi)結(jié)果,映射到特征空間的樣本得到很好的分離,并且能夠通過(guò)橢圓的決策邊界實(shí)現(xiàn)聚類(lèi).

圖3 EK-HEC算法在模擬數(shù)據(jù)集2上的聚類(lèi)結(jié)果

3.2.2 基準(zhǔn)評(píng)測(cè)數(shù)據(jù)集

為了評(píng)估本文提出算法的性能,在來(lái)自UCI的3個(gè)基準(zhǔn)評(píng)測(cè)數(shù)據(jù)集(具體描述見(jiàn)表2)上與K-means算法、模糊C-means算法、GMM-EM算法和馬氏距離MVE-HEC算法進(jìn)行了比較實(shí)驗(yàn).6種算法在MCR和NMI兩個(gè)評(píng)判準(zhǔn)則上的比較結(jié)果如圖4所示,由圖4可知,K-HEC算法在MCR和NMI兩個(gè)指標(biāo)上均優(yōu)于K-means、模糊C-means、GMM-EM和HEC算法,EK-HEC算法與其他算法相比有更好或類(lèi)似的聚類(lèi)性能.

表2 來(lái)自UCI的基準(zhǔn)評(píng)測(cè)數(shù)據(jù)集

4 結(jié)語(yǔ)

本文將基于MVE的HEC算法與改進(jìn)的高斯核相結(jié)合,提出了K-HEC算法,通過(guò)應(yīng)用定義在核空間的橢圓聚類(lèi),增強(qiáng)了K-HEC算法聚類(lèi)能力,提出了EK-HEC算法.K-HEC算法能夠處理不同大小、不同密度和橢球形壯的分簇,EK-HEC算法能夠處理非線(xiàn)性和細(xì)長(zhǎng)結(jié)構(gòu)的復(fù)雜幾何形狀的分簇.在模擬數(shù)據(jù)集和UCI基準(zhǔn)評(píng)測(cè)數(shù)據(jù)集上的仿真實(shí)驗(yàn)表明,K-HEC算法能夠通過(guò)建立緊湊的分類(lèi)邊界有效地分離各分簇,EK-HEC算法在非線(xiàn)性和細(xì)長(zhǎng)結(jié)構(gòu)的數(shù)據(jù)集上完成了正確的聚類(lèi).本文算法無(wú)論在聚類(lèi)能力和性能方面均優(yōu)于K-means、模糊C-means、GMM-EM和HEC算法,從而驗(yàn)證了本文算法的可行性和有效性.

圖4 基準(zhǔn)評(píng)測(cè)數(shù)據(jù)集上的聚類(lèi)性能比較

1Duda RO,Hart PE,Stork DG.Pattern Classification.New York:John Wiley & Sons,2012.

2Nagpal A,Jatain A,Gaur D.Review based on data clustering algorithms.Proc.of the 2013 IEEE Conference on Information & Communication Technologies (ICT).JeJu Island,Korea.2013.298–303.

3Mao JC,Jain AK.A self-organizing network for hyperellipsoidal clustering (HEC).IEEE Trans.on Neural Networks,1996,7(1):16–29.[doi:10.1109/72.478389]

4Wang S,Ma F,Shi W,et al.The hyperellipsoidal clustering using genetic algorithm.Proc.of the 1997 IEEE International Conference on Intelligent Processing Systems.Beijing,China.1997,1.592–596.

5Ichihashi H,Ohue M,Miyoshi T.Fuzzy C-means clustering algorithm with pseudo Mahalanobis distances.Proc.of the 3rd Asian Fuzzy Systems Symposium.Changwon,Korea.1998.148–152.

6Moshtaghi M,Rajasegarar S,Leckie C,et al.An efficient hyperellipsoidal clustering algorithm for resource-constrained environments.Pattern Recognition,2011,44(9):2197–2209.[doi:10.1016/j.patcog.2011.03.007]

7Wang S,Xia SW,Mao JC,et al.Comments on “a self-organizing network for hyperellipsoidal clustering (HEC)”.IEEE Trans.on Neural Networks,1997,8(6):1561–1563.[doi:10.1109/72.641479]

8Lee HS,Park JY,Park DH.Hyper-ellipsoidal clustering algorithm using linear matrix inequality.Journal of Korean Institute of Intelligent Systems,2002,12(4):300–305.[doi:10.5391/JKIIS.2002.12.4.300]

9Kumar M,Orlin JB.Scale-invariant clustering with minimum volume ellipsoids.Computer & Operations Research,2008,35(4):1017–1029.

10Shioda R,Tun?el L.Clustering via minimum volume ellipsoids.Computational Optimization and Applications,2007,37(3):247–295.[doi:10.1007/s10589-007-9024-1]

11Boyd S,Vandenberghe L.Convex optimization.Cambridge,UK:Cambridge University Press,2004.

12Todd MJ,Yildirim EA.On Khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids.Discrete Applied Mathematics,2007,155(13):1731–1744.[doi:10.1016/j.dam.2007.02.013]

13Cao JZ,Chen P,Zheng Y,et al.A max-flow-based similarity measure for spectral clustering.ETRI Journal,2013,35(2):311–320.[doi:10.4218/etrij.13.0112.0520]

14Shawe-Taylor J,Cristianini N.Kernel methods for pattern analysis.Cambridge,UK:Cambridge University Press,2004.

15CVX Research,Inc.CVX:Matlab software for disciplined convex programming,version 2.0.http://cvxr.com/cvx.[2013-04].

Novel Data Clustering Method Based on A Modified Gaussian Kernel Metric and Kernel PCA

YU Wen-Li1,YU Jian-Jun1,FANG Jian-Wen21(College of Information Engineering,Quzhou College of Technology,Quzhou 324000,China)2(College of Electrical and Information Engineering,Quzhou University,Quzhou 324000,China)

Most hyper-ellipsoidal clustering(HEC)algorithms use the Mahalanobis distance as a distance metric.It has been proven that HEC,under this condition,cannot be realized since the cost function of partitional clustering is a constant.We demonstrate that HEC with a modified Gaussian kernel metric can be interpreted as a problem of finding condensed ellipsoidal clusters(with respect to the volumes and densities of the clusters)and propose a practical HEC algorithm named K-HEC that is able to efficiently handle clusters that are ellipsoidal in shape and that are of different size and density.We then try to refine the K-HEC algorithm by utilizing ellipsoids defined on the kernel feature space to deal with more complex-shaped clusters.Simulation experiments demonstrate the proposed methods have a significant improvement in the clustering results and performance over K-means algorithm,fuzzy C-means algorithm,GMM-EM algorithm and HEC algorithm based on minimum-volume ellipsoids using Mahalanobis distance.

data clustering; hyper-ellipsoidal clustering; minimum-volume ellipsoids; kernel PCA; Gaussian kernel

余文利,余建軍,方建文.基于改進(jìn)高斯核度量和KPCA的數(shù)據(jù)聚類(lèi)新方法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(10):150–155.http://www.c-sa.org.cn/1003-3254/5988.html

2017-01-11; 采用時(shí)間:2017-02-15