王義武，楊余旺，于天鵬，沈興鑫，李猛坤

(1.南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210000；2.304兵器廠，山西 長(zhǎng)治 046000；3.清華大學(xué) 經(jīng)管學(xué)院，北京 100000)

0 引 言

從算法復(fù)雜程度看，K-means算法簡(jiǎn)潔、高效，其他很多算法難以相比，因此其應(yīng)用愈加廣泛，但它也存在固有問題，如聚類中心需人為主觀設(shè)置，但只有了解數(shù)據(jù)分布才能掌握相關(guān)信息，這與現(xiàn)實(shí)相矛盾；聚類效果和中心點(diǎn)選擇有關(guān)，易陷入局部最優(yōu)解[1]，中心點(diǎn)的不同選擇，可能造成結(jié)果大不相同；傳統(tǒng)K-means需要依序逐個(gè)計(jì)算數(shù)據(jù)點(diǎn)之間的距離[2]，當(dāng)數(shù)據(jù)規(guī)模很大時(shí)在計(jì)算上耗費(fèi)了大量時(shí)間。針對(duì)這些固有問題，不斷有人提出優(yōu)化方法，使得K-means算法愈加成熟、多樣。

隨著分布式系統(tǒng)的出現(xiàn)與完善，傳統(tǒng)算法利用分布式計(jì)算的優(yōu)點(diǎn)在聚類效果上得到了不斷的優(yōu)化和提高。文獻(xiàn)[3]實(shí)現(xiàn)了Hadoop版本的并行處理，提高了算法的吞吐量；文獻(xiàn)[4]在Hive平臺(tái)下實(shí)現(xiàn)了K-means的分布式計(jì)算且運(yùn)用簡(jiǎn)單的類SQL語(yǔ)言即可以實(shí)現(xiàn)數(shù)據(jù)查詢；文獻(xiàn)[5]利用Canopy優(yōu)化K-means算法，并在MapRduce框架下實(shí)現(xiàn)。在上述研究的基礎(chǔ)上，文中提出一種新的OCC K-means算法。不同于傳統(tǒng)算法以隨機(jī)選擇的方式產(chǎn)生聚類中心，該算法進(jìn)行必要的預(yù)處理，利用UPGMA和最大最小距離算法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行篩選，得到可以反映數(shù)據(jù)分布特征的點(diǎn)，并作為初始的聚類中心，以提高聚類精度。

1 相關(guān)工作

1.1 Spark分布式框架

Spark作為一種正興起的計(jì)算框架，建立在彈性分布式數(shù)據(jù)集基礎(chǔ)之上，具有以下特點(diǎn)：

(1)數(shù)據(jù)分布式存儲(chǔ)在多個(gè)節(jié)點(diǎn)上；

(2)高度抽象化的RDD概念，這也是Spark與Hadoop、Hive最大的不同，RDD是一切計(jì)算的基礎(chǔ)，這也使得Spark迭代計(jì)算、并行計(jì)算的能力明顯好于其他現(xiàn)存的分布式框架；

(3)不同于Hadoop頻繁地在HDFS進(jìn)行I/O操作，Spark計(jì)算時(shí)將數(shù)據(jù)寫入內(nèi)存，有效降低了計(jì)算時(shí)間，同時(shí)當(dāng)內(nèi)存不夠時(shí)，它可以將數(shù)據(jù)寫到磁盤上；

(4)高度的容錯(cuò)性，Spark抽象出RDD并在計(jì)算時(shí)只記錄了各個(gè)RDD之間的關(guān)聯(lián)，沒有真正地產(chǎn)生相關(guān)數(shù)據(jù)，僅在Action動(dòng)作時(shí)才真正提交作業(yè)。

Spark運(yùn)行模式多樣，部署在單機(jī)上時(shí)可以選用本地模式(local)或者偽分布模式(local cluster)；當(dāng)部署在集群上時(shí)可以選用Standalone模式、Mesos模式或者Hadoop YANR模式。這里具體的介紹Standalone模式[6]。

1.2 基本概念

定義1：點(diǎn)Pi和Pj之間采用歐氏距離，定義為：

(1)

其中，Pi,Pj為n維數(shù)據(jù)。

定義2:簇C的中心定義為C=(C1,C2,…,CN),數(shù)據(jù)點(diǎn)第n維值為:

(2)

其中，m為數(shù)據(jù)個(gè)數(shù)；Xi為第i個(gè)數(shù)據(jù)；n為維度。

定義3：d為數(shù)據(jù)j距集合i中所有的數(shù)據(jù)的最小距離。

d=Min(Dist(Uik-Uj))

(3)

其中，Uik為數(shù)據(jù)集i中第k個(gè)數(shù)據(jù)；Uj標(biāo)記數(shù)據(jù)集j。

定義4：由定義3進(jìn)一步得出最大最小距離為：

(4)

定義5：最大最小距離算法[7-8]中用于選出分布較遠(yuǎn)的數(shù)據(jù)點(diǎn)。

Dimax>θ‖v1-v2‖

(5)

其中，v1，v2為數(shù)據(jù)集i，j間距離最小的兩個(gè)數(shù)據(jù)點(diǎn)；θ為算法參數(shù)，值取(0,1)之間。

定義6：算法的收斂判定標(biāo)準(zhǔn)-誤差平方和準(zhǔn)則函數(shù)。

(6)

其中，Mi是簇Ci的中心點(diǎn)；p是簇Ci的數(shù)據(jù)點(diǎn)元素；k為簇的個(gè)數(shù)。在給定數(shù)據(jù)集時(shí)，Jc表示將數(shù)據(jù)集劃分為k個(gè)簇的總體誤差。從式6可以看出,Mi決定了Jc取值大小，Jc值越大表示數(shù)據(jù)劃歸的誤差越大。因此在聚類過程中應(yīng)致力于Jc最小化，從而使聚類最優(yōu)化[9]。

定義7：準(zhǔn)確率和召回率。

P(i,j)=precision(i,j)=Nij/Ni

(7)

R(i,j)=recall(i,j)=Nij/Nj

(8)

其中，Nij表示屬于類i，但被劃歸到類j中的數(shù)據(jù)數(shù)；Ni表示類i中全部數(shù)據(jù)點(diǎn)個(gè)數(shù)；Nj表示類j中全部數(shù)據(jù)點(diǎn)的個(gè)數(shù)。由式7和式8可得F-measure：

F(i)=2P*R/(P+R)

(9)

其中，F(xiàn)(i)結(jié)合準(zhǔn)確率和召回率，表示相對(duì)準(zhǔn)確率。

定義8：加速比(sizeup)。

(10)

其中，Ts為一個(gè)Worker算法完成時(shí)間；Tn為n個(gè)Worker算法完成時(shí)間。

定義9：擴(kuò)展比(scaleup)。

(11)

其中，S為加速比；n為Worker節(jié)點(diǎn)的個(gè)數(shù)。

2 OCC K-means并行算法

2.1 算法思想

傳統(tǒng)K-means算法對(duì)聚類中心過于敏感，這也導(dǎo)致聚類效果上的顯著不同，因此文中提出使用UPGMA算法[10]篩選出可以反映數(shù)據(jù)集整體分布的候選中心，同時(shí)被選擇的數(shù)據(jù)點(diǎn)應(yīng)該是相距比較遠(yuǎn)的，防止過于集中[11-12]，以避免同一個(gè)聚類因?yàn)閰?shù)設(shè)置的原因選出了兩個(gè)聚類中心，這樣K-means算法就獲得了一個(gè)較好的輸入，并且在整個(gè)執(zhí)行過程中UPGMA算法和K-means算法兩個(gè)階段都是并行的。

UPGMA階段的執(zhí)行過程如下：

(1)讀入HDFS上將要聚類的數(shù)據(jù)，初始情況下每一個(gè)數(shù)據(jù)點(diǎn)都看作一個(gè)類，并通過Map將其轉(zhuǎn)化為Vector；

(2)Worker節(jié)點(diǎn)的各個(gè)數(shù)據(jù)計(jì)算距其他數(shù)據(jù)點(diǎn)的最小歐氏距離，通過Reduce操作將距離最近的兩個(gè)數(shù)據(jù)點(diǎn)合并，計(jì)算它們的中心作為新的數(shù)據(jù)點(diǎn)(同時(shí)記錄這個(gè)數(shù)據(jù)點(diǎn)代表的類所擁有的數(shù)據(jù)的數(shù)目)參與聚類；

(3)若類內(nèi)的數(shù)據(jù)大于數(shù)據(jù)點(diǎn)總數(shù)的m%，則將此數(shù)據(jù)點(diǎn)加入到候選列表，通過Filter操作過濾掉已存在于候選列表中的類中數(shù)據(jù)；否則重復(fù)步驟2；

(4)當(dāng)無(wú)歸屬的數(shù)據(jù)點(diǎn)的數(shù)目小于總數(shù)的m%時(shí)，算法停止，輸出候選列表作為最大最小距離算法的輸入數(shù)據(jù)；否則一直重復(fù)上述過程。

K-means階段的執(zhí)行過程如下：

(1)將最大最小距離算法的輸出作為K-means算法的輸入；

(2)Worker查找距離自己最近的中心點(diǎn)；

(3)將距離同一個(gè)初始中心最近的所有數(shù)據(jù)點(diǎn)通過Iterator對(duì)距離全局求和、記錄數(shù)據(jù)個(gè)數(shù)，然后加入到同一個(gè)類中，更新此類的中心；

(4)若算法收斂則停止，否則返回步驟2。

2.2 基于Spark的OCC K-means算法的并行化

2.2.1 UPGMA算法的并行化

使用UPGMA算法主要目的是為了了解數(shù)據(jù)的分布，找到數(shù)據(jù)的密集區(qū)域，從中選出代表這一區(qū)域的數(shù)據(jù)點(diǎn)。

改進(jìn)的UPGMA算法的并行化過程如下：

(1)算法輸入:待聚類的數(shù)據(jù)集，m,p,θ；算法輸出：初始候選中心集合。

(2)將單個(gè)數(shù)據(jù)作為獨(dú)立的類。

(3)計(jì)算類間彼此距離，合并相距最近的兩個(gè)類，同時(shí)判斷剩下數(shù)據(jù)的總數(shù)是否大于等于總數(shù)的m%,若不大于等于則轉(zhuǎn)步驟4。

(4)i=0,t=0，t=t+1，forj=i+1...maxcluster do

(5)當(dāng)子類i和子類j內(nèi)部的數(shù)據(jù)個(gè)數(shù)少于等于總數(shù)的m%,且兩個(gè)類數(shù)據(jù)元素之和大于總數(shù)的m%時(shí),計(jì)算兩個(gè)類之間距離,并加入到距離矩陣中。

(6)合并距離矩陣中最近的類,并且加入到序列Q,轉(zhuǎn)至步驟3。

(7)選取序列Q的前p%，計(jì)算中心位置，即為初始候選中心。

m%為類中的數(shù)據(jù)點(diǎn)占數(shù)據(jù)總數(shù)的百分比，當(dāng)合并后的類中數(shù)據(jù)點(diǎn)的個(gè)數(shù)滿足這一比例時(shí)才會(huì)將其加入到序列Q；最后選取序列Q的前q%。

2.2.2 K-means算法的并行化

經(jīng)過上面兩個(gè)過程，K-means算法獲得了一個(gè)較好的輸入，這里主要說明K-means并行化的實(shí)現(xiàn)。

Map操作：

輸入：待聚類數(shù)據(jù)集S，初始聚類中心數(shù)組Centerlist

輸出：已被標(biāo)記所屬聚類的數(shù)據(jù)集合

(1)while(S!=null)，計(jì)算P(S中的數(shù)據(jù))與Centerlist中第i個(gè)數(shù)據(jù)的距離，記為Dpi，加入集合{Dpi}(i=1,2,…,Centerlist.length),在S中刪除P。

(2)找出{Dpi}(i=1,2,…,Centerlist.length)中最小的所對(duì)應(yīng)的中心Dpi，將PMap為(p,i)

Combine操作：

相同i構(gòu)成的集合(類)對(duì)Map產(chǎn)生的數(shù)據(jù)進(jìn)行分類、匯總

Reduce操作：

(1)while(C.hasNext())，num=0，double du [demesions]，P=C.next(),將數(shù)據(jù)點(diǎn)P的第i分量值加入du[i]中,num++

(2)輸出類中心du[i]/num

每一次reduce操作都會(huì)更新一次聚類中心，當(dāng)前后兩次中心的值不發(fā)生變化或者變化滿足停止條件時(shí)說明已經(jīng)收斂，此時(shí)算法停止。

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

3.1 實(shí)驗(yàn)環(huán)境、測(cè)試數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)是在Spark的Standalone模式下進(jìn)行的，Spark采用1.4.0版本，Hadoop采用2.6.0版本，Java jdk為1.8，Master和Worker節(jié)點(diǎn)的操作系統(tǒng)為ubuntu 14.04 LTSk，其中Worker節(jié)點(diǎn)的個(gè)數(shù)為5。

3.2 實(shí)驗(yàn)過程

這里進(jìn)行了兩組實(shí)驗(yàn)，使用傳統(tǒng)K-means和OCC K-means對(duì)三個(gè)數(shù)據(jù)集進(jìn)行處理。實(shí)驗(yàn)中采用的數(shù)據(jù)集為Iris,Seeds,Dum，OCC K-means算法中的參數(shù)依次設(shè)置為：(0.8,0.8,0.5)、(0.5,0.8,0.5)、(0.5,0.8,0.5)，兩組實(shí)驗(yàn)結(jié)果如表1所示。

表1 實(shí)驗(yàn)結(jié)果

效果對(duì)比如圖1～3所示；OCC K-means算法加速比和擴(kuò)展比分別如圖4和圖5所示。

圖1 Iris數(shù)據(jù)集上的效果對(duì)比

圖2 Seeds數(shù)據(jù)集上的效果對(duì)比

圖3 Dum數(shù)據(jù)集上的效果對(duì)比

圖4 OCC K-means算法加速比

圖5 OCC K-means算法擴(kuò)展比

可以發(fā)現(xiàn)在Iris數(shù)據(jù)集上，OCC K-means算法相比傳統(tǒng)K-means算法在準(zhǔn)確率上提高了3.33%，召回率提高了8.78%,F-measure提高了6.11%；在Seeds的數(shù)據(jù)集上，準(zhǔn)確率提高了2.59%，召回率提高了3.58%，F(xiàn)-measure提高了3.09%；在Dum數(shù)據(jù)集上，準(zhǔn)確率提高了14.22%，召回率提高了8.72%，F(xiàn)-measure提高了12.00%，可見改進(jìn)后的算法在聚類效果上得到了優(yōu)化[13]。原因在于OCC K-means算法使用UPGMA算法和最大最小距離算法對(duì)聚類中心進(jìn)行了選擇優(yōu)化，這些中心點(diǎn)來(lái)自數(shù)據(jù)密集區(qū)域可以很好地代表數(shù)據(jù)的分布，同時(shí)在一定程度上將噪聲數(shù)據(jù)和邊緣數(shù)據(jù)的影響盡可能降低，使得算法體現(xiàn)出更好的準(zhǔn)確性和魯棒性[14-15]。

同時(shí)對(duì)加速比和擴(kuò)展比的分析可知，當(dāng)Worker的節(jié)點(diǎn)小于3時(shí)，算法的加速比近似于線性上升，但隨著節(jié)點(diǎn)數(shù)增大而增幅出現(xiàn)下降，這是因?yàn)殡m然硬件資源成倍增加，但它們并沒有全部得到使用，反而集群初始化時(shí)間，資源調(diào)度的代價(jià)，節(jié)點(diǎn)間通信代價(jià)等會(huì)增加，這些都會(huì)影響算法的并行效果。

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

從兩組實(shí)驗(yàn)結(jié)果可以得出，基于Spark實(shí)現(xiàn)的OCC K-means算法，在準(zhǔn)確率、召回率、F-measure上的表現(xiàn)都優(yōu)于傳統(tǒng)K-means，并且在Iris、Seeds、Dum不同數(shù)據(jù)集上均取得了較好的結(jié)果，說明K-means算法在聚類中心選擇上得到了一定程度的優(yōu)化，擁有更好的刻畫數(shù)據(jù)分布特征的能力。同時(shí)當(dāng)工作節(jié)點(diǎn)數(shù)量小于一定值時(shí)，加速比、擴(kuò)展比可出現(xiàn)理想的變化，說明算法具有較好的并行化能力，但是當(dāng)工作節(jié)點(diǎn)過多或者實(shí)驗(yàn)數(shù)據(jù)集過小時(shí)，算法的并行化效果就會(huì)受到影響，有待進(jìn)一步完善。