鄒臣嵩,劉 松

(1.廣東松山職業(yè)技術(shù)學(xué)院電氣工程系，廣東 韶關(guān) 512126； 2.廣東松山職業(yè)技術(shù)學(xué)院機(jī)械工程系，廣東 韶關(guān) 512126)

0 引 言

聚類分析作為一種探索性分析方法被廣泛應(yīng)用于模式識(shí)別、計(jì)算機(jī)視覺(jué)、數(shù)據(jù)挖掘等領(lǐng)域中，其目的是根據(jù)相似性原則將物理或抽象的對(duì)象集合分成若干個(gè)子集，并分析各子集中的數(shù)據(jù)之間的內(nèi)在聯(lián)系、規(guī)律和特點(diǎn)[1]。K-means聚類算法是應(yīng)用最為廣泛的劃分方法之一，其實(shí)現(xiàn)簡(jiǎn)單、快速，并且能有效地處理大數(shù)據(jù)集，但該算法對(duì)初始聚類中心和異常數(shù)據(jù)較為敏感，且不能用于發(fā)現(xiàn)非凸形狀的簇，因此聚類結(jié)果不穩(wěn)定[2-3]。為了解決K-means算法的這些問(wèn)題，研究人員圍繞簇中心的選擇與優(yōu)化提出了新的計(jì)算方法[4-10]，提高了原算法的聚類質(zhì)量，減少了聚類時(shí)間，但這些改進(jìn)的聚類算法更多注重初始聚類中心的選擇，針對(duì)的對(duì)象往往是低維數(shù)據(jù)，因此，當(dāng)數(shù)據(jù)的維度升高、分布相對(duì)稀疏時(shí)，其聚類結(jié)果難以預(yù)料，這是因?yàn)樵诟呔S空間中，數(shù)據(jù)對(duì)象間的距離幾乎一致，所以基于距離和密度的聚類算法在面對(duì)高維數(shù)據(jù)集時(shí)，整體性能有所下滑[11]。此外，隨著數(shù)據(jù)特征維度的增加，不相關(guān)的特征值會(huì)產(chǎn)生大量的冗余信息，在一定程度上屏蔽了那些與真實(shí)聚類結(jié)果關(guān)系密切的特征信息，從而進(jìn)一步地影響了算法的聚類結(jié)果。因此，聚類算法的改進(jìn)不僅需要尋找合理的初始聚類中心，還要對(duì)原始數(shù)據(jù)進(jìn)行有效的預(yù)處理，尤其對(duì)于高維數(shù)據(jù)，在對(duì)其降維的同時(shí)，應(yīng)盡可能地挖掘并保留能夠?qū)垲惤Y(jié)果的劃分產(chǎn)生重要影響的“核心特征”。

1 相關(guān)算法的研究現(xiàn)狀

在聚類算法的改進(jìn)方面，段桂芹[4]選取數(shù)據(jù)對(duì)象到樣本均值和當(dāng)前聚類中心集合的距離乘積最大值法來(lái)確定新的初始聚類中心，克服了聚類結(jié)果對(duì)初始聚類中心的依賴性。熊忠陽(yáng)等[5]對(duì)最大最小距離法進(jìn)行了改進(jìn),提出了最大距離乘積法,解決了原方法因選取初始聚類中心過(guò)于稠密而導(dǎo)致的聚類沖突等問(wèn)題。翟東海等[6]提出了最大距離法選取初始簇中心的K-means文本聚類算法，解決了K-means算法的聚類結(jié)果不穩(wěn)定、總迭代次數(shù)較多等問(wèn)題。賀思云等[7]用改進(jìn)的人工蜂群算法優(yōu)化K-means算法的聚類中心，用最大距離乘積法對(duì)蜜源進(jìn)行初始化，增加蜜源搜索范圍的動(dòng)態(tài)調(diào)整因子，加快了算法的收斂速度。周鹿揚(yáng)等[8]提出了一種基于聚類中心的快速聚類算法，將數(shù)據(jù)集中較大或延伸狀的簇分割成若干球狀簇，而后合并這些小簇，較好地適應(yīng)任意形狀數(shù)據(jù)集。李曉瑜等[9]提出了一種基于Hadoop的分布式改進(jìn)K-means算法，通過(guò)引入Canopy算法初始化聚類中心，克服K-means算法因初始中心點(diǎn)的不確定性，易陷入局部最優(yōu)解的問(wèn)題。同時(shí),結(jié)合MapReduce分布式計(jì)算模型，給出改進(jìn)后算法的并行化設(shè)計(jì)方法和策略。張順龍等[10]提出了一種基于動(dòng)態(tài)類中心調(diào)整和Elkan三角判定思想的加速K-means聚類算法，采取動(dòng)態(tài)及時(shí)更新類中心策略，有效降低了算法的迭代次數(shù)和內(nèi)存開(kāi)銷。

隨著降維技術(shù)理論研究和實(shí)踐應(yīng)用的不斷深入，許多降維算法在特定的領(lǐng)域也發(fā)揮著重要的作用。如Luebke和Weihs[12]提出了一種兩步驟適應(yīng)過(guò)程的線性數(shù)據(jù)降維算法，自適應(yīng)地完成各種類型數(shù)據(jù)的降維分類處理，但處理較多異常數(shù)據(jù)集時(shí)性能不穩(wěn)定。Magdalinos等[13]針對(duì)高維數(shù)據(jù)集提出了一種快速降維算法，主要思路是將數(shù)據(jù)對(duì)象間的距離嵌入到低維的投影空間，顯著加快K-means的收斂速率。Ge等[14]提出了一種幾何局部嵌入的降維方法，該方法用幾何距離來(lái)測(cè)量數(shù)據(jù)內(nèi)部相鄰節(jié)點(diǎn)的距離以達(dá)到高維數(shù)據(jù)的清晰可視化，這種幾何距離強(qiáng)調(diào)了由中心向量所生成的局部幾何結(jié)構(gòu)，而不用再計(jì)算數(shù)據(jù)的成對(duì)距離。Li等[15]提出了一種基于歸一化網(wǎng)格子空間的高維數(shù)據(jù)相似性度量方法，將每個(gè)維度的數(shù)據(jù)區(qū)間劃分為若干個(gè)區(qū)間，并將不同維度的組件映射到相應(yīng)的區(qū)間上，僅使用相同或相鄰區(qū)間中的組件來(lái)計(jì)算相似度。

受上述文獻(xiàn)啟發(fā)，本文以數(shù)據(jù)預(yù)處理技術(shù)中的降維為突破口，針對(duì)數(shù)據(jù)降維、初始聚類中心選擇、簇中心更新等關(guān)鍵問(wèn)題，提出了基于譜聚類的全局中心快速更新聚類算法。首先完成數(shù)據(jù)從高維到低維的轉(zhuǎn)換，然后對(duì)文獻(xiàn)[6]的最大距離法進(jìn)行了改進(jìn)，得到了更加分散、更具有代表性的初始聚類中心；在簇中心更新過(guò)程中，用均值最近點(diǎn)作為新的簇中心，取代了K-means算法的均值中心法。實(shí)驗(yàn)測(cè)試表明，本文算法的聚類準(zhǔn)確率、整體耗時(shí)、rand指數(shù)等有效性評(píng)價(jià)指標(biāo)優(yōu)于傳統(tǒng)K-means算法和其他3種改進(jìn)算法。

2 基于譜聚類的全局中心快速更新聚類算法

本文算法分為3個(gè)階段：數(shù)據(jù)預(yù)處理、選擇初始聚類中心和更新簇中心，基本思路如下：

1)在數(shù)據(jù)預(yù)處理階段，采用譜聚類算法[16]對(duì)樣本進(jìn)行降維，并對(duì)降維后的數(shù)據(jù)進(jìn)行歸一化處理。

2)在選擇初始聚類中心階段，首先計(jì)算樣本集X中各數(shù)據(jù)對(duì)象之間的距離，構(gòu)建整個(gè)樣本集的距離矩陣；再在距離矩陣中選取k個(gè)首尾相連且距離乘積最大的數(shù)據(jù)對(duì)象作為初始聚類中心，得到初始聚類中心集合Z={Z1，Z2，…，Zk}。

3)在更新簇中心階段，為緩解K-means算法對(duì)孤立點(diǎn)的敏感性，本文借鑒K-medoids算法的思想，選取與簇均值距離最近的數(shù)據(jù)對(duì)象作為簇中心，構(gòu)建新的簇中心集合Z′={Z1′，Z2′，…，Zk′}，再將樣本集X中其他數(shù)據(jù)對(duì)象按最小距離劃分到相應(yīng)簇中，重復(fù)迭代過(guò)程，直至準(zhǔn)則函數(shù)收斂，最終完成聚類。

下面是本文算法的相關(guān)概念、算法描述以及算法復(fù)雜度分析。

2.1 基本概念與定義

設(shè)X={X1,X2,…,Xi,…,Xn}為含有n個(gè)數(shù)據(jù)對(duì)象的樣本集合，每個(gè)樣本含有p個(gè)屬性,Xi={Xi1,Xi2,…,Xip}?，F(xiàn)將該集合劃分為k個(gè)簇,Cluster={Cluster1,Cluster2,…,Clusterk},Cluster∈X，每簇樣本個(gè)數(shù)為m，簇中心集合為Z={Z1,Z2,…,Zk}(k

定義1空間兩點(diǎn)間的歐氏距離定義為：

(1)

其中，i=1,2,…,n;j=1,2,…,n;w=1,2,…,p。

數(shù)據(jù)降維方法可以分為2大類，線性和非線性。線性降維法包括多維尺度分析、主成分分析、線性判別分析、獨(dú)立成分分析和隨機(jī)投影；非線性降維法包括基于核的主成分分析方法、等距離映射算法、局部線性嵌入算法、拉普拉斯特征映射法等[17]。譜聚類算法是在譜圖理論的基礎(chǔ)上提出來(lái)的一種聚類算法，該算法首先根據(jù)距離公式得到樣本的空間距離矩陣W，再計(jì)算出構(gòu)造矩陣L，然后對(duì)L中的前k個(gè)最大特征值所對(duì)應(yīng)的特征向量進(jìn)行歸一化處理，從而在k維空間中形成與原樣本的映射關(guān)系，達(dá)到降維的目的。

定義2樣本集X的相似度矩陣為W={Wij|1≤i≤n,1≤j≤n}，其中相似性是按照高斯相似度來(lái)計(jì)算的，即：

(2)

定義3對(duì)角矩陣D是由空間距離矩陣W的每一列的和構(gòu)成，即:

(3)

定義4構(gòu)造矩陣L定義為：

(4)

定義5簇均值定義為：

(5)

其中，i=1,2,…,k。

定義6簇內(nèi)樣本Xj到該簇均值的距離定義為：

distMean_X(j)=dXj,mean(i)

(6)

其中，i=1,2,…,k;j=1,2,…,m;Xj∈Ci。

定義7簇內(nèi)各樣本到簇均值的距離矩陣定義為：

(7)

其中，i=1,2,…,k。

定義8在簇中心更新過(guò)程中將與簇內(nèi)均值距離最小的數(shù)據(jù)對(duì)象Xj作為該簇的中心，Xj滿足以下條件：

distMean_X(j)=min(distArrayC(i))

(8)

其中，i=1,2,…,k;j=1,2,…,m;Xj∈Ci。

定義9聚類誤差平方和E的定義為：

(9)

其中，Xij是第i簇的第j個(gè)數(shù)據(jù)對(duì)象，Zi是第i簇的中心。

2.2 算法描述

Step1降維。

a)根據(jù)式(1)計(jì)算樣本集X中各數(shù)據(jù)對(duì)象之間的距離；

b)根據(jù)式(2)構(gòu)建樣本集X的空間距離矩陣W；

c)根據(jù)式(3)、式(4)構(gòu)造矩陣L；

d)選取L的前k個(gè)最大特征值所對(duì)應(yīng)的特征向量x1，x2，…，xn，構(gòu)造矩陣Xnew=[x1，x2，…，xn]∈Rn×k；

e)對(duì)矩陣Xnew的行向量進(jìn)行歸一化處理，得到矩陣X′；

Step2選擇初始聚類中心。

a)根據(jù)式(2)構(gòu)建樣本集X′的空間距離矩陣Wnew；

Step3更新簇中心。

a)根據(jù)式(1)計(jì)算樣本集X′中各數(shù)據(jù)對(duì)象與Z中各中心點(diǎn)的距離，并按最小距離將各對(duì)象劃分至最近的簇中；

b)根據(jù)式(5)～式(7)得到簇內(nèi)各樣本到簇均值的距離矩陣distArrayC；

c)根據(jù)式(8)從distArrayC中查詢當(dāng)前簇內(nèi)到簇均值距離最小的數(shù)據(jù)對(duì)象，并將其作為簇中心存入新的簇中心集合Z′中；

d)重復(fù)Step3中的步驟b、c，更新各簇的中心，直到|Z′|=k，再用Z′取代Z；

Step4分配數(shù)據(jù)。

a)將樣本集X′中的數(shù)據(jù)對(duì)象劃分到與其距離最近的簇中；

b)根據(jù)式(9)計(jì)算聚類結(jié)果評(píng)價(jià)指標(biāo)，判斷是否收斂，如果收斂，則聚類算法結(jié)束，否則轉(zhuǎn)到Step3繼續(xù)執(zhí)行。

2.3 算法復(fù)雜度分析

K-means算法的時(shí)間復(fù)雜度為On×k×T，n是數(shù)據(jù)集樣本個(gè)數(shù)，k是聚類個(gè)數(shù)，T是算法每次運(yùn)行時(shí)簇中心更新的迭代次數(shù)。本文算法的時(shí)間復(fù)雜度具體為On2+n×k×t，與K-means相比，在初始聚類中心選擇階段，本文算法用改進(jìn)的全局中心算法取代傳統(tǒng)的隨機(jī)選取算法，故n2>n，但由于使用了譜聚類的降維方法，這使得算法的運(yùn)算量在一定程度上有所減少，此外，改進(jìn)后的全局中心算法使得各初始聚類中心相對(duì)分散，同時(shí)具有更強(qiáng)的代表性，這使得簇中心在更新過(guò)程中可以更加快速地接近真實(shí)解，使得迭代次數(shù)減少，故t<

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

本文實(shí)驗(yàn)環(huán)境為：Intel Core i3-3240 3.40 GHz，8 GB內(nèi)存，1 TB硬盤(pán)，Win7操作系統(tǒng)，實(shí)驗(yàn)平臺(tái)Matlab 2011b。選用iris、heart、wine等5個(gè)常用的UCI數(shù)據(jù)集對(duì)本文算法進(jìn)行測(cè)試，各數(shù)據(jù)集描述如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)

3.1 算法的實(shí)現(xiàn)

本文算法中的相似矩陣是基于高斯核距離的全連接方式，切圖采用Ncut，算法實(shí)現(xiàn)的偽代碼如下：

input:(data,K,σ)

S=Euclidean(data)

W=Gaussian(S,σ)

L=D-W

L′=normalized(L)

EV=EigenVector(L′,K)

SelectInitialClusterCenter();//選擇初始聚類中心

while(newCenter !=oldCenter)

{

UpdateClusterCenter()//更新簇中心

}

output：K clusters

其中，data為表1中的樣本集，K為標(biāo)準(zhǔn)聚類個(gè)數(shù)，σ為構(gòu)造W矩陣時(shí)的高斯函數(shù)參數(shù),控制了函數(shù)的徑向作用范圍。需要特別指出的是，本文將聚類中心點(diǎn)和上次是否完全相同或聚類準(zhǔn)則函數(shù)是否無(wú)變化作為聚類收斂的判斷依據(jù)。

3.2 聚類準(zhǔn)確率和時(shí)間性能分析

圖1～圖5是K-means算法、文獻(xiàn)[4-6]算法和本文算法在UCI數(shù)據(jù)集的聚類準(zhǔn)確率、初始中心選擇耗時(shí)、簇中心更新耗時(shí)、迭代次數(shù)、聚類總耗時(shí)的實(shí)驗(yàn)對(duì)比結(jié)果，其中K-means算法的實(shí)驗(yàn)結(jié)果為算法運(yùn)行50次所得的平均值。

本文首先采用purity方法對(duì)聚類結(jié)果的準(zhǔn)確性進(jìn)行評(píng)價(jià)，即將正確聚類的樣本數(shù)與總樣本數(shù)的比值作為聚類準(zhǔn)確率。如圖1所示，在聚類準(zhǔn)確率方面，本文算法全部?jī)?yōu)于其他4種算法。

圖1 聚類準(zhǔn)確率比較

由圖2可知，在初始聚類中心選擇階段，本文算法的耗時(shí)明顯低于文獻(xiàn)[4-6]，略高于K-means算法，其原因是本文算法降低了整個(gè)樣本集的維數(shù)，使得數(shù)據(jù)在子空間的結(jié)構(gòu)更加清晰，聚類時(shí)的運(yùn)算量明顯減少，故耗時(shí)較少。耗時(shí)大于K-means算法的原因在于后者隨機(jī)選擇初始聚類中心，計(jì)算量較少，因此初始化速度較快，而本文和文獻(xiàn)[4-6]對(duì)聚類中心的初始選擇從距離、密度等不同角度進(jìn)行了改進(jìn)，計(jì)算量在一定程度上有所增加，耗時(shí)也相對(duì)增加。

圖2 初始中心選擇耗時(shí)比較

由圖3可知，在簇中心更新階段，本文算法的耗時(shí)不僅小于文獻(xiàn)[4-6]，更小于傳統(tǒng)K-means算法,這說(shuō)明選取與簇均值距離最近的數(shù)據(jù)對(duì)象作為簇中心，可以更直接地反映出數(shù)據(jù)對(duì)象的具體位置，更準(zhǔn)確地反映數(shù)據(jù)集的整體分布情況。此外，除樣本集wdbc外，文獻(xiàn)[4-6]的耗時(shí)明顯小于傳統(tǒng)K-means算法，這是因?yàn)榍罢咴谏弦浑A段篩選出的聚類中心基本體現(xiàn)了數(shù)據(jù)對(duì)象的大致分布，從而減少了本階段的迭代次數(shù)(結(jié)果詳見(jiàn)圖4)，故耗時(shí)減少。

圖3 簇中心更新耗時(shí)比較

如圖4、圖5所示，與其他4種算法相比，本文算法迭代次數(shù)少、收斂速度快、總耗時(shí)短，這是由于K-means算法的隨機(jī)性導(dǎo)致準(zhǔn)則函數(shù)易陷入局部極小、使得總迭代次數(shù)與總耗時(shí)同時(shí)增加，而文獻(xiàn)[4-6]雖然對(duì)初始聚類中心的選擇進(jìn)行了改進(jìn)，但簇中心的更新依然沿用均值中心算法，這使得中心點(diǎn)的選擇代表性較差，因此迭代次數(shù)及總耗時(shí)都大于本文算法。

圖4 迭代次數(shù)比較

圖5 聚類總耗時(shí)比較

3.3 其他外部評(píng)價(jià)指標(biāo)結(jié)果

關(guān)于算法聚類結(jié)果的評(píng)價(jià)，除采用常用的聚類準(zhǔn)確率、迭代次數(shù)和各階段聚類耗時(shí)之外，還采用3個(gè)外部評(píng)價(jià)指標(biāo)：Rand指數(shù)、Jaccard系數(shù)和Adjusted Rand Index參數(shù)[18]對(duì)聚類結(jié)果進(jìn)行比較分析。

3個(gè)評(píng)價(jià)指標(biāo)的定義如下:設(shè)U和V分別是關(guān)于數(shù)據(jù)集的2種劃分，其中U是已知的正確劃分，而V是通過(guò)某種聚類算法得到的劃分結(jié)果，定義a、b、c、d這4個(gè)參數(shù)。設(shè)a為在U和V都在同一類的樣本對(duì)數(shù)目;b表示在U中為同一類，而在V中卻不在同一類的樣本對(duì)數(shù)目;c表示在V中為同一類，而在U中卻不在同一類的樣本對(duì)數(shù)目;d為U和V都不在同一類簇的樣本對(duì)數(shù)目。a+b+c+d=n(n-1)/2，其中，n為數(shù)據(jù)集中所有樣本數(shù)，即數(shù)據(jù)集的規(guī)模。

設(shè)M=a+b+c+d，則M表示所有可能的樣本對(duì)。Rand指數(shù)、Jaccard系數(shù)和Adjusted Rand Index參數(shù)的定義如下:

Rand指數(shù):R=(a+d)/M

Jaccard系數(shù):J=a/(a+b+c)

Adjusted Rand Index參數(shù):

RI=2(ad-bc)/[(a+b)(b+d)+(a+c)(c+d)]

其中:R表示Rand指數(shù);J表示Jaccard系數(shù);RI表示Adjusted Rand Index參數(shù)。

從定義可知，Rand指數(shù)表示聚類結(jié)果與原始數(shù)據(jù)集樣本分布的一致性;Jaccard系數(shù)表示實(shí)現(xiàn)正確聚類樣本對(duì)占聚類前或后在同一類簇樣本對(duì)的比率;RI值越大表示實(shí)現(xiàn)正確聚類的樣本對(duì)越多，聚類效果越好(其上界為1，表示聚類結(jié)果與原始數(shù)據(jù)集的樣本分布完全一致;下界為-1，表示聚類結(jié)果與原始數(shù)據(jù)集的樣本分布完全不一致)。

觀察表2～表5的Rand指數(shù)、Jaccard系數(shù)、Adjusted Rand Index參數(shù)和F值的對(duì)比結(jié)果可知，本文算法在UCI的5個(gè)數(shù)據(jù)集上的聚類外部評(píng)價(jià)指標(biāo)全部?jī)?yōu)于其他4種算法，尤其在特征維度相對(duì)較多的ionosphere和wdbc數(shù)據(jù)集上，本文算法的優(yōu)勢(shì)更為突出。

表2 Rand指數(shù)比較

表3 Jaccard系數(shù)比較

表4 Adjusted Rand Index參數(shù)比較

表5 F值比較

從上述UCI數(shù)據(jù)集的對(duì)比實(shí)驗(yàn)結(jié)果可以得出：本文算法在多種聚類結(jié)果的評(píng)價(jià)指標(biāo)中展現(xiàn)出更佳的聚類質(zhì)量、更快的收斂速度和更高的穩(wěn)定性，尤其在對(duì)較高維度數(shù)據(jù)聚類時(shí)，相比其他3種改進(jìn)算法，新算法的聚類質(zhì)量更為理想。

4 結(jié)束語(yǔ)

本文將聚類算法的整體性能提升作為研究目標(biāo)，采用譜聚類算法降低了數(shù)據(jù)集的特征維度，用全局中心法完成對(duì)最大距離法的改進(jìn)，得到了具有良好分散性的初始聚類中心，在簇中心更新階段，將均值最近點(diǎn)作為簇中心，降低了迭代次數(shù)，減少了算法的運(yùn)算時(shí)間。對(duì)比測(cè)試表明，本文算法對(duì)聚類中心的選取合理、有效，尤其在對(duì)高維數(shù)據(jù)進(jìn)行聚類時(shí)，本文算法的聚類質(zhì)量更加理想。在實(shí)驗(yàn)中發(fā)現(xiàn)，在中小規(guī)模數(shù)據(jù)集上本文算法的收斂速度明顯優(yōu)于K-means算法，但隨著數(shù)據(jù)集規(guī)模的增大，選擇初始聚類中心階段所消耗的時(shí)間呈指數(shù)上升，下一步工作將以提高算法的聚類質(zhì)量為研究目標(biāo)，同時(shí)兼顧算法的時(shí)間性能，尋求更為合理高效的聚類方法。