周功建

(廈門大學(xué) 嘉庚學(xué)院，福建 漳州 363105)

一、引言

大數(shù)據(jù)時(shí)代，隨著互聯(lián)網(wǎng)和信息技術(shù)的快速發(fā)展，數(shù)據(jù)量呈指數(shù)式增長(zhǎng)。如何快速準(zhǔn)確地從海量數(shù)據(jù)里挖掘出有價(jià)值的知識(shí)和信息是數(shù)據(jù)挖掘技術(shù)最重要的特征，而聚類分析是數(shù)據(jù)挖掘中一個(gè)非常重要的研究領(lǐng)域[1]。傳統(tǒng)的聚類分析算法在空間復(fù)雜度和時(shí)間復(fù)雜度上都有一定的局限性，利用云計(jì)算平臺(tái)對(duì)其進(jìn)行并行化改進(jìn)優(yōu)化，可以有效降低聚類算法的時(shí)間復(fù)雜度和空間復(fù)雜度，節(jié)約聚類時(shí)間，從而更好地滿足實(shí)際問(wèn)題中數(shù)據(jù)挖掘的需要[2]。

Hadoop是目前使用最廣的云計(jì)算平臺(tái)，利用其中的MapReduce模塊來(lái)提高聚類算法的效率，已經(jīng)成為大數(shù)據(jù)聚類分析研究的熱點(diǎn)[3]。針對(duì)經(jīng)典的基于劃分的Kmeans聚類算法，人們根據(jù)不同的要求和使用環(huán)境，在傳統(tǒng)Kmeans算法的基礎(chǔ)上提出了許多改進(jìn)思路，其中結(jié)合Canopy算法和Hadoop云平臺(tái)改進(jìn)生成的Canopy-Kmeans并行聚類算法及其優(yōu)化就是很有代表性的一類。張石磊、武裝等在Hadoop平臺(tái)上實(shí)現(xiàn)了Kmeans和Canopy-Kmeans算法的并行化，并且驗(yàn)證了Canopy-Kmeans并行算法比Kmeans并行算法在不同的數(shù)據(jù)集下有更高的聚類準(zhǔn)確率和更快的收斂速度[4]。李釗、王春梅等基于Hadoop平臺(tái)設(shè)計(jì)了Canopy-Kmeans并行化算法，應(yīng)用“最小最大原則”對(duì)Canopy中心點(diǎn)隨機(jī)性選取問(wèn)題進(jìn)行改進(jìn)，并用海量新聞數(shù)據(jù)做聚類測(cè)試驗(yàn)證改進(jìn)算法的性能和有效性[5]。李蘭英、董義明等采用“平均距離估值”方法對(duì)Canopy算法區(qū)域半徑T1和T2取值具有盲目性問(wèn)題進(jìn)行改進(jìn)，可以得到比較準(zhǔn)確的區(qū)域半徑取值，并在Hadoop云平臺(tái)上對(duì)改進(jìn)后的Canopy-Kmeans算法進(jìn)行了實(shí)現(xiàn)和驗(yàn)證[6]。

在學(xué)習(xí)借鑒他人研究基礎(chǔ)上，利用統(tǒng)計(jì)學(xué)思維對(duì)數(shù)據(jù)分組抽樣后聚類，并結(jié)合數(shù)據(jù)異度均值抽樣法和最小最大法原則對(duì)Canopy-Kmeans算法進(jìn)行優(yōu)化改進(jìn)；并在Hadoop平臺(tái)上對(duì)改進(jìn)的Canopy-Kmeans算法進(jìn)行并行化設(shè)計(jì)與實(shí)現(xiàn)；最后通過(guò)實(shí)驗(yàn)驗(yàn)證算法并行執(zhí)行時(shí)的加速比和可擴(kuò)展性。結(jié)果表明改進(jìn)的Canopy-Kmeans并行算法是有效的、收斂的。

二、Hadoop云計(jì)算平臺(tái)

Hadoop云平臺(tái)是一個(gè)開(kāi)源分布式系統(tǒng)框架，遵循了Google的Bigtable、GFS、MapReduce三大關(guān)鍵技術(shù)及其設(shè)計(jì)思想[2,7]；在Hadoop框架中，MapReduce和HDFS(Hadoop Distributed File System)是兩個(gè)最核心模塊，分別負(fù)責(zé)海量數(shù)據(jù)的存儲(chǔ)與計(jì)算。HDFS是一種運(yùn)行在大量普通配置的機(jī)器節(jié)點(diǎn)上的分布式文件系統(tǒng)[7]。MapReduce是Google提出的一種并行編程框架，用于對(duì)海量數(shù)據(jù)集的并行分析與運(yùn)算，能夠?qū)崿F(xiàn)程序的自動(dòng)并行處理，并提供數(shù)據(jù)分割、任務(wù)調(diào)度等細(xì)節(jié)，實(shí)現(xiàn)程序高度并行性和可擴(kuò)展性[3,8]。

三、Canopy-Kmeans算法研究

(一) Kmeans算法原理

Kmeans算法是一種基于劃分的聚類算法，利用數(shù)據(jù)對(duì)象間的距離作為相似性的評(píng)價(jià)指標(biāo)[4，7]。聚類過(guò)程是一個(gè)不斷循環(huán)迭代的過(guò)程，對(duì)數(shù)據(jù)點(diǎn)進(jìn)行簇劃分和對(duì)簇中心點(diǎn)進(jìn)行調(diào)整交替執(zhí)行，直到簇中心點(diǎn)不再發(fā)生變化為止，最后生成的同一簇內(nèi)數(shù)據(jù)相似度高，不同簇間數(shù)據(jù)相似度低，其算法執(zhí)行流程如圖1所示。

圖1 Kmeans算法聚類流程

Kmeans算法思想簡(jiǎn)單、理論可靠、處理大數(shù)據(jù)集時(shí)有較強(qiáng)的魯棒性和可伸縮性，實(shí)際應(yīng)用中得到廣泛關(guān)注，但算法也存在如下不足之處：

(1)Kmeans算法的聚類簇?cái)?shù)量k值需人為指定，不同的k值對(duì)聚類結(jié)果會(huì)產(chǎn)生很大影響；并且每個(gè)簇的初始中心點(diǎn)是隨機(jī)選取的，易導(dǎo)致聚類結(jié)果不穩(wěn)定和聚類質(zhì)量不高[9]。如何準(zhǔn)確確定k值和選擇初始中心點(diǎn)是使用Kmeans算法聚類時(shí)需思考的優(yōu)化改進(jìn)方向。

(2)串行執(zhí)行時(shí)，當(dāng)聚類數(shù)據(jù)量為n，聚類簇個(gè)數(shù)為k，迭代次數(shù)為t時(shí)，算法的時(shí)間復(fù)雜度為O(nkt)；可以看出當(dāng)聚類的數(shù)據(jù)集較大時(shí)，算法的運(yùn)行時(shí)間將大大增加，如果能將聚類過(guò)程改為并行化執(zhí)行，則可有效降低時(shí)間復(fù)雜度，提升聚類效率[4,8]。

(二)Canopy-Kmeans算法原理

Canopy-Kmeans算法是一種借助Canopy算法進(jìn)行改進(jìn)優(yōu)化后的Kmeans算法，在Canopy-Kmeans算法中，先用Canopy算法對(duì)數(shù)據(jù)集進(jìn)行“粗”聚類預(yù)處理，快速算出k個(gè)Canopy中心點(diǎn)，再用Kmeans算法對(duì)數(shù)據(jù)集進(jìn)行 “細(xì)”聚類，生成聚類結(jié)果[5,9]。Canopy-Kmeans算法執(zhí)行步驟如下：

(1) 將待聚類的數(shù)據(jù)集向量化為一個(gè)List集合，并指定兩個(gè)距離閾值T2和T1(T2

(2)從集合List中隨機(jī)刪除一個(gè)數(shù)據(jù)對(duì)象P，構(gòu)成一個(gè)新的Canopy;

(3)對(duì)于List中剩余數(shù)據(jù)對(duì)象，如果與P的間距小于T1，就把它指派到P所在的Canopy中; 如果與點(diǎn)P的間距小于T2，則將它從List中刪除;

(4)重復(fù)步驟(2)和步驟(3)，直到List為空，至此將形成多個(gè)Canopy;

(5)將得到的Canopy數(shù)目作為k值，每個(gè)Canopy的中心點(diǎn)作為初始聚類中心點(diǎn)代入Kmeans算法中進(jìn)行再次聚類，生成最終聚類結(jié)果。

圖2 Canopy聚類結(jié)果示意圖

在Canopy-Kmeans算法中，無(wú)須事先指定k值和隨機(jī)選取初始中心點(diǎn)，而是利用Canopy算法聚類求得，可有效解決k值人為指定和隨機(jī)選取初始中心點(diǎn)的盲目性；但Canopy-Kmeans算法仍有以下不足之處：

(1)Canopy算法在求解過(guò)程中各個(gè)Canopy的初始中心點(diǎn)仍然是隨機(jī)選取的，這種做法可能會(huì)造成聚類結(jié)果的不穩(wěn)定[1,5]；

(2)串行執(zhí)行時(shí)，Canopy-Kmeans算法的時(shí)間復(fù)雜度為O(nktf2/c)，其中c為Canopy的總個(gè)數(shù)，n為數(shù)據(jù)的規(guī)模，t為算法迭代的次數(shù)，k為最終生成的聚類數(shù)目，f為平均每個(gè)數(shù)據(jù)對(duì)應(yīng)的Canopy數(shù)量[8]；可以看出，在處理海量數(shù)據(jù)時(shí)，仍然有較高的時(shí)間復(fù)雜度[2,6]。

四、改進(jìn)的Canopy-kmeans算法

通過(guò)對(duì)Canopy算法聚類過(guò)程、Kmeans算法迭代過(guò)程及時(shí)間復(fù)雜度等方面分別進(jìn)行優(yōu)化，改進(jìn)的Canopy-Kmeans算法執(zhí)行流程如圖3所示。

圖3 改進(jìn)的Canopy-Kmeans算法執(zhí)行流程

(一) Canopy聚類過(guò)程優(yōu)化

為避免聚類陷入局部最優(yōu)解，針對(duì)Canopy聚類時(shí)初始中心點(diǎn)選取隨機(jī)性問(wèn)題，利用“最小最大原則”對(duì)Canopy算法進(jìn)行優(yōu)化，基本思想為:在將數(shù)據(jù)聚類劃分為若干個(gè)Canopy過(guò)程中，任意兩個(gè)Canopy中心點(diǎn)之間的距離應(yīng)盡可能遠(yuǎn)；即如果已知m個(gè)Canopy中心點(diǎn)，則第m+1個(gè)Canopy初始中心點(diǎn)應(yīng)為所有候選數(shù)據(jù)對(duì)象與前m個(gè)Canopy中心點(diǎn)之間最小距離中的最大者[6]。具體優(yōu)化流程如下：

(1)從數(shù)據(jù)集List中隨機(jī)刪去第一個(gè)點(diǎn)P1，計(jì)算與其對(duì)應(yīng)的Canopy；

(2) 計(jì)算List中剩余的點(diǎn)到點(diǎn)P1的距離，選取其中距離最大的點(diǎn)P2作為第二個(gè)Canopy的初始中心點(diǎn)，并從List中刪除點(diǎn)P2，計(jì)算與其對(duì)應(yīng)的Canopy；

(3)計(jì)算List中剩余的點(diǎn)到所有已生成Canopy中心點(diǎn)最小距離d，選取d的數(shù)值最大的點(diǎn)作為下一個(gè)Canopy的初始中心點(diǎn)，計(jì)算與其對(duì)應(yīng)的Canopy；

(4)重復(fù)執(zhí)行步驟(3)，直到數(shù)據(jù)集List為空。

另外，為了提高下一步Kmeans聚類的穩(wěn)定性和準(zhǔn)確率，還需檢測(cè)每個(gè)Canopy簇中數(shù)據(jù)對(duì)象的個(gè)數(shù)，若一個(gè)Canopy簇只有一個(gè)或很少的數(shù)據(jù)對(duì)象，則認(rèn)為該Canopy簇是孤立的，應(yīng)將他們從總的Canopy簇中減掉，從而得到Kmeans聚類過(guò)程的K值和初始聚類中心。

(二) kmeans迭代過(guò)程優(yōu)化

Canopy算法作為Kmeans聚類的初始化操作，在快速得到k個(gè)Canopy中心時(shí)，會(huì)對(duì)每個(gè)Canopy中的數(shù)據(jù)對(duì)象進(jìn)行標(biāo)注，每個(gè)數(shù)據(jù)對(duì)象至少屬于一個(gè)Canopy，也可能出現(xiàn)在多個(gè)Canopy中?？梢詳喽〝?shù)據(jù)在同一Canopy中相似度高，不同Canopy中相似度低，因此在Kmeans迭代時(shí)，不屬于同一個(gè)Canopy中的數(shù)據(jù)之間可不再計(jì)算它們的相似性。當(dāng)計(jì)算數(shù)據(jù)所屬聚類簇時(shí)，只需計(jì)算它到所屬Canopy中心點(diǎn)的距離，并將其歸入到距離最近的Canopy中心點(diǎn)所屬類簇中，形成相不重疊的簇，從而減少了迭代過(guò)程中的計(jì)算量。在Canopy較小，且相互間數(shù)據(jù)重疊不多的情況下可有效降低Canopy-Kmeans算法的時(shí)間復(fù)雜度。

(三)時(shí)間復(fù)雜度優(yōu)化

為進(jìn)一步降低算法的整體時(shí)間復(fù)雜度，利用統(tǒng)計(jì)學(xué)思維對(duì)數(shù)據(jù)集進(jìn)行分組抽樣后聚類，以增強(qiáng)其時(shí)效性。具體思路為：先將待聚類數(shù)據(jù)集進(jìn)行分組，從每組抽樣出一定量的數(shù)據(jù)，并對(duì)各組抽樣數(shù)據(jù)分別進(jìn)行Canopy聚類，然后對(duì)求得的全部Canopy中心點(diǎn)再次進(jìn)行Canopy聚類，生成k個(gè)Canopy中心點(diǎn)，代入Kmeans算法中對(duì)全部抽樣數(shù)據(jù)進(jìn)行聚類劃分，產(chǎn)生新的Kmeans聚類簇，最后將所有未被抽樣到的數(shù)據(jù)對(duì)象歸類到距離最近的Kmeans聚類簇中。

分組的目的是為了更方便在Hadoop平臺(tái)上進(jìn)行并行化實(shí)現(xiàn)。在對(duì)數(shù)據(jù)抽樣時(shí)，利用數(shù)據(jù)異度均值抽樣方法來(lái)確保數(shù)據(jù)樣本盡量均勻分布在原始數(shù)據(jù)中，使其能夠代表全體數(shù)據(jù)，從而保證算法的穩(wěn)定性和正確性。數(shù)據(jù)異度均值抽樣操作步驟如下：

(1)對(duì)于非空數(shù)據(jù)集S={ci|ci=

(ci1,ci2,…,cip),i=1,2,…n},用公式(1)找出集合S中最小數(shù)據(jù)對(duì)象cm=(cm1,cm2,…,cmp),1≤m≤n;

(1)

(2)用公式(2)計(jì)算所有其余數(shù)據(jù)對(duì)象到cm的距離，形成一個(gè)距離值集合DIS；

(2)

(3)根據(jù)DIS中的距離值，按從小到大的順序?qū)蟂中的全部數(shù)據(jù)對(duì)象進(jìn)行升序排序；

(4)利用公式(3)從排好序的集合S中均勻地選取t個(gè)數(shù)據(jù)對(duì)象作為抽樣數(shù)據(jù)集RIS={c1,c2,…,ct}。

,(i=1,2,…,t)。

(3)

五、基于Hadoop平臺(tái)Canopy-kmeans改進(jìn)算法的并行化設(shè)計(jì)實(shí)現(xiàn)

在改進(jìn)的Canopy-Kmeans算法中，因?qū)?shù)據(jù)集采取了分組抽樣策略，所有數(shù)據(jù)對(duì)象到各Canopy質(zhì)心點(diǎn)距離的計(jì)算操作都可以獨(dú)立執(zhí)行，相互之間不存在任何依賴關(guān)系，因此改進(jìn)算法完全可以應(yīng)用Hadoop平臺(tái)上的Map-Reduce編程框架進(jìn)行并行化設(shè)計(jì)實(shí)現(xiàn)，將執(zhí)行過(guò)程分成三個(gè)階段，具體流程如圖4所示：

圖4 基于Hadoop平臺(tái)改進(jìn)Canopy-Kmeans算法并行化執(zhí)行流程

(一) Canopy聚類階段

1.Map過(guò)程

從分組數(shù)據(jù)集split中采用數(shù)據(jù)異度均值抽樣方法抽取t個(gè)數(shù)據(jù)對(duì)象，然后對(duì)抽取的數(shù)據(jù)對(duì)象利用Canopy算法聚類，得到多個(gè)重疊的Canopy，輸出Canopy中心點(diǎn)集合。

圖5 Map函數(shù)執(zhí)行偽代碼

2.Reduce過(guò)程

使用改進(jìn)的Canopy算法將Map過(guò)程中得到的多組Canopy中心點(diǎn)合并為一組，再將所有抽樣的數(shù)據(jù)對(duì)象劃分到距離最近的Canopy中，并重新計(jì)算各個(gè)Canopy的中心點(diǎn)，將結(jié)果保存至HDFS中。

圖6 Reduce函數(shù)執(zhí)行偽代碼

(二)Kmeans聚類階段

Kmeans算法每一輪迭代都啟動(dòng)一次Map-Reduce任務(wù)，算法所需的k值及初始聚類中心由Canopy算法得到，因Canopy算法對(duì)每個(gè)數(shù)據(jù)做了所屬Canopy標(biāo)注，所以Kmeans聚類過(guò)程只需計(jì)算各數(shù)據(jù)對(duì)象與所屬Canopy中心的距離，選擇距離最短的Canopy中心對(duì)其進(jìn)行簇歸類。

圖7 Kmeans迭代執(zhí)行偽代碼

在Kmeans算法每一輪Map-Reduce過(guò)程結(jié)束后，將本次輸出結(jié)果與上次進(jìn)行比較，當(dāng)兩者差值小于給定的閾值T2，就進(jìn)入后續(xù)過(guò)程；否則，就將本次的輸出結(jié)果作為新一輪的Map-Reduce輸入傳輸?shù)紿DFS上，再次進(jìn)入下一輪Kmeans迭代，直到滿足前后兩次輸出結(jié)果差值小于閾值T2后進(jìn)入后續(xù)過(guò)程。

(三)未抽樣數(shù)據(jù)簇歸類階段

根據(jù)Kmeans聚類結(jié)果，使用Map函數(shù)對(duì)未被抽樣到的數(shù)據(jù)集進(jìn)行歸類操作，把數(shù)據(jù)對(duì)象歸入到離其距離最近的簇中心點(diǎn)所在的聚類簇中，生成最終聚類結(jié)果。

圖8 Map函數(shù)執(zhí)行偽代碼

六、實(shí)驗(yàn)驗(yàn)證與分析

(一)實(shí)驗(yàn)平臺(tái)和實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)平臺(tái)采用開(kāi)源Hadoop分布式框架，由4臺(tái)計(jì)算機(jī)組成集群，其中1臺(tái)作為主節(jié)點(diǎn)(Namenode)，另外3臺(tái)作為從節(jié)點(diǎn)(Datanode)。每一臺(tái)配置為Intel Xeon CPU ES-2620 2GHz, 128GB內(nèi)存與2TB的硬盤。操作系統(tǒng)為Ubuntu14.04, JDK版本是jdk1.7, Hadoop版本是Hadoop2.5.2。

實(shí)驗(yàn)數(shù)據(jù)采用UCI數(shù)據(jù)集下60維的Synthetic_ Control數(shù)據(jù)集，分別采集了100 k、200 k、400 k、800 k、1 000 k五種不同大小的數(shù)據(jù)集。分組抽樣的樣本數(shù)據(jù)占原始數(shù)據(jù)量的60%，Canopy聚類所需的距離閾值T1和T2的設(shè)定可以根據(jù)實(shí)際情況通過(guò)交叉驗(yàn)證給出。另外，為避免算法隨機(jī)性的影響，每類數(shù)據(jù)集均取20次運(yùn)行結(jié)果的平均值進(jìn)行分析。

(二)加速比分析

加速比(speedup) 可用來(lái)衡量一個(gè)算法并行化執(zhí)行的有效性，是算法在并行系統(tǒng)和串行系統(tǒng)中運(yùn)行所消耗時(shí)間的比率。其定義為：Sp=Tl/Tp，其中，Tl代表串行時(shí)的處理時(shí)間，Tp代表并行時(shí)的處理時(shí)間。當(dāng)加速比指標(biāo)Sp越大，算法效率越高。

圖9 改進(jìn)的Canopy_Kmeans算法加速比

可以看出，數(shù)據(jù)集在100 k、200 k、400 k規(guī)模時(shí)，隨著節(jié)點(diǎn)數(shù)目的增加，加速比曲線趨向平緩。這是因?yàn)?00 k、200 k、400 k數(shù)據(jù)集的數(shù)據(jù)量相對(duì)較小，處理時(shí)間相對(duì)較短，節(jié)點(diǎn)數(shù)的增加，使數(shù)據(jù)傳輸、任務(wù)調(diào)度、資源管理等方面的時(shí)間開(kāi)銷加大，從而降低了算法的執(zhí)行效率。而在處理800 k、1 000 k規(guī)模的較大數(shù)據(jù)集合時(shí)，加速比曲線呈現(xiàn)線性增長(zhǎng)，說(shuō)明改進(jìn)的Canopy-Kmeans算法在并行化執(zhí)行時(shí)能夠有效提升聚類效率，并且數(shù)據(jù)量越大時(shí)算法的效率越高。

(三)可擴(kuò)展性分析

可擴(kuò)展性(scalability) 反映了集群計(jì)算節(jié)點(diǎn)數(shù)目對(duì)并行化效率的影響，主要用于檢驗(yàn)并行化算法的實(shí)用性。其定義為：E=SP/P，其中P表示集群計(jì)算節(jié)點(diǎn)數(shù)目，SP表示加速比；若E越大，則算法可擴(kuò)展性越好。

可以看出，隨著集群節(jié)點(diǎn)數(shù)的增加，算法的可擴(kuò)展性會(huì)下降，這是因?yàn)楣?jié)點(diǎn)數(shù)的增多會(huì)增加網(wǎng)絡(luò)通信、任務(wù)調(diào)度、資源管理等方面的開(kāi)銷。但當(dāng)數(shù)據(jù)的規(guī)模越來(lái)越大，節(jié)點(diǎn)越來(lái)越多時(shí)，算法的并行擴(kuò)展比曲線下降的幅度越來(lái)越小，最后趨向維持平滑，說(shuō)明隨著節(jié)點(diǎn)數(shù)的增加，算法在處理大數(shù)據(jù)時(shí)的效率基本保持穩(wěn)定。

圖10 改進(jìn)的Canopy_Kmeans算法可擴(kuò)展性

七、結(jié)語(yǔ)

綜上所述，改進(jìn)的Canopy-Kmeans聚類算法通過(guò)將數(shù)據(jù)集進(jìn)行分組抽樣后聚類減少了整體計(jì)算量；最小最大原則解決了Canopy聚類初始中心點(diǎn)選取隨機(jī)性問(wèn)題；數(shù)據(jù)異度均值抽樣法確保能均勻提取數(shù)據(jù)樣本，使其能代表全局?jǐn)?shù)據(jù)，避免聚類陷入局部最優(yōu)解，保證了算法的正確性；對(duì)Kmeans迭代計(jì)算過(guò)程進(jìn)行優(yōu)化可進(jìn)一步降低算法的時(shí)間復(fù)雜度；最后在分布式Hadoop集群系統(tǒng)中測(cè)試實(shí)驗(yàn)表明，對(duì)海量多維數(shù)值數(shù)據(jù)進(jìn)行聚類處理時(shí)，改進(jìn)的Canopy-Kmeans算法是有效的、收斂的，在聚類準(zhǔn)確率和時(shí)效性上都有一定程度的提升。但另一方面，抽樣數(shù)據(jù)規(guī)模如何確定以及Canopy過(guò)程中的兩個(gè)距離閾值(T1和T2)的取值如何準(zhǔn)確給出都對(duì)聚類結(jié)果的精度和穩(wěn)定性有較大影響，這些問(wèn)題還有待后續(xù)更進(jìn)一步深入研究。