面向海量數(shù)據(jù)的改進最近鄰優(yōu)先吸收聚類算法

,,

(1.杭州電子科技大學(xué) 自動化學(xué)院,杭州 310018; 2.浙江省電子信息產(chǎn)品檢驗所,杭州 310007)

0 概述

聚類[1]是將對象集分成由類似對象組成的多個聚簇的過程,常用于統(tǒng)計分析方法,目前已經(jīng)在圖像識別、模式識別、數(shù)據(jù)挖掘等諸多方面大規(guī)模應(yīng)用。

隨著互聯(lián)網(wǎng)的興起和數(shù)據(jù)庫技術(shù)的發(fā)展,數(shù)據(jù)集的規(guī)模不斷擴大,傳統(tǒng)的聚類方法因限于運行速度和準確率無法適用于大規(guī)模的數(shù)據(jù)集。以MapReduce[2-3]為代表的并行化編程框架的出現(xiàn),為聚類算法應(yīng)用于大規(guī)模數(shù)據(jù)集提供了一種新的途徑。其中,文獻[4]提出利用MapReduce對生物醫(yī)學(xué)概念之間的關(guān)聯(lián)進行提取的方法,文獻[5]將MapReduce應(yīng)用于數(shù)據(jù)分類方向,并對MapReduce進行穩(wěn)定性測試。

目前已經(jīng)有很多算法實現(xiàn)在MapReduce框架上,如使用范圍最廣的K-means算法[6-7],其中具有代表性的改進有基于MapReduce模型的單通和線性時間K-均值聚類算法[8]和基于海量數(shù)據(jù)分析的改進K-Medoids算法[9]。

MapReduce框架上較為常見的算法還有Canopy聚類算法,其中最具代表性的是文獻[10]提出的改進Canopy高效算法。該文將改進的Canopy算法實現(xiàn)在Hadoop平臺上,極大地節(jié)省了聚類運行的時間。

上述2種算法各有優(yōu)劣：K-Means算法原理簡單、便于操作,但類別數(shù)需要人為設(shè)置,而且初始聚類中心也很難選擇,容易出現(xiàn)局部最優(yōu)的情況；Canopy算法無需指定類別數(shù),運行速度極快,適合處理大規(guī)模的數(shù)據(jù)集,但聚類效果一般,尤其是在不同類別的邊界,極容易出現(xiàn)聚類重疊的現(xiàn)象。

文獻[11]提出最近鄰優(yōu)先吸收(Nearest Neighbor Absorption First,NNAF)聚類算法,該算法適用于任意形狀的聚類,可快速處理高維數(shù)據(jù),但在數(shù)據(jù)密度和聚類間距離不均勻時聚類質(zhì)量較差,文獻[12]針對此問題提出基于數(shù)據(jù)分區(qū)的NNAF算法。本文在上述研究的基礎(chǔ)上,基于MapReduce對NNAF算法進行改進。首先將其與Canopy算法結(jié)合,減少算法計算量,然后采用MapReduce編程框架對算法做并行化編程[13],使其能夠支持海量數(shù)據(jù)處理。

1 最近鄰優(yōu)先吸收聚類算法

NNAF算法是一種最短距離聚類的算法,它是基于“同類相近”的思想提出的,其基本設(shè)計思路是:空間中的每一個點和與之距離最近的那個點,屬于同一類的可能性是最大的。如果2個距離最近的點之間的距離小于d(距離閾值,由用戶自己指定),那么就把它們分在同一類,當聚類里面包涵的元素個數(shù)大于q(數(shù)量閾值,由用戶自己指定),則此數(shù)據(jù)集合就成為一個聚類。

NNAF算法的難點是2個閾值的選擇。距離閾值過大會出現(xiàn)內(nèi)圈稀疏、外圈密集的可能,不利于發(fā)揮出最好的聚類效果;距離閾值過小可能會使得聚類數(shù)量過多,起不到聚類應(yīng)有的作用。而數(shù)量閾值的設(shè)定不合理,則會出現(xiàn)聚類過大或者過小的問題。

NNAF算法首先選擇一個點,令其單獨成為一類,將該點的所有最近鄰點和以該點為最近鄰點的點歸入此類;然后以新加入的點為基準,將這些點的最近鄰點和以這些點為中心的最近鄰點的點歸到這一類。不斷重復(fù)上述步驟,直到點的數(shù)量滿足設(shè)定的數(shù)量閾值。具體步驟如下:

1)設(shè)定距離閾值d和數(shù)量閾值q,輸入數(shù)據(jù)集V。

2)調(diào)用SNN算法[14]計算出每一點的最近鄰點。

3)隨機選擇數(shù)據(jù)集中的某一點,將其賦給新的點集P(P原為空集),并將該點從原數(shù)據(jù)集V中刪除。

4)將該點的所有最近鄰點和以該點為最近鄰點的點都賦值給P,并將這些點從原數(shù)據(jù)集V中刪除。

5)將新加入點的最近鄰點和以這些點為最近鄰點的點都賦值給P,并將這些點從原數(shù)據(jù)集V中刪除。

6)當P中的個數(shù)滿足數(shù)量閾值q時,結(jié)束對這個類的訪問。

7)從V中選擇一個點,重復(fù)步驟3)～步驟6)。

8)直到所有的點都被聚類,即V變成空集,結(jié)束所有操作,輸出這些類。

2 最近鄰優(yōu)先吸收算法的改進

2.1 基于Canopy算法的改進

Canopy[15]算法是一種新的聚類方法,它可以通過使用一種簡單的距離計算方法把整個數(shù)據(jù)集合分成幾個相互重疊的子集,從而有效地減少數(shù)據(jù)的計算量。Canopy算法對處理海量數(shù)據(jù)有著極大幫助,其偽代碼如下:

Begin

canopy=[]

load list

[m,n]=size(list)/*獲取list中向量的數(shù)量*/

load T1,T2;T1>T2

for i=1:m;i++

A=randperm(list)/*隨機從list中取一點A*/

delete A from list

for j=1:m-1;j++

d=pdist2(A,list(j))/*計算A與list中其他某一向量的距離*/

if d<=T1

put A into canopy

S(i)=canopy

end

if d<=T2/*判斷距離是否小于T2*/

delete list(j) from list/*將其從list中刪除*/

end

end

if list=[]

break

end

本文提出的改進NNAF算法,通過Canopy算法得到子集之后,對子集中相互重疊的部分采用最近鄰優(yōu)先聚類算法進行計算,從而達到減少計算量和提升準確率的目的。具體步驟如下:

1)將數(shù)據(jù)集向量化,并按照任意的固定規(guī)則排序,得到一個list,然后再選擇2個距離閾值:T1和T2,其中T1>T2,T1和T2的值能夠用交叉校驗來確定。

2)從list中任取一點P,用低計算成本方法快速計算點P與list中所有向量之間的距離,如果點P與某個向量之間的距離在T1以內(nèi),則將點P和這個點加入到一個Canopy。

3)如果點P曾經(jīng)與某個Canopy的距離在T2以內(nèi),則需要把點P從list中刪除,此步認為點P已經(jīng)確認基本屬于該Canopy,因此,不可以再利用這個點去做其他Canopy的中心。

4)重復(fù)步驟2)和步驟3),直到list為空,結(jié)束。

5)采用SNN算法確定2個Canopy交叉部分的數(shù)據(jù)集V(如圖1所示)中每一點的最近鄰點,以及以數(shù)據(jù)集V中的點為最近鄰點的點。

圖1 聚簇交叉情況

6)隨機從數(shù)據(jù)集V中取一個點,找到其最近鄰點,依據(jù)這個最近鄰點所屬類別來判斷該點的類別。如果最近鄰點也沒有確定類別,則開始尋找以此點為最近鄰點的點,根據(jù)其所屬類別來判斷該點的類別。如果以此點為最近鄰點的點不止一個,且分屬不同的類,則依據(jù)它們到此點相對距離的遠近來判斷該點屬于哪一類。如果還是無法判斷,則換另外的一個點;如果數(shù)據(jù)集V中所有的點都無法判斷,則將數(shù)據(jù)集V單獨列為一類。

7)判斷完畢之后,將該點從數(shù)據(jù)集V中刪除,并歸入到所屬的數(shù)據(jù)集中。

8)從V中再隨機找到一個點,重復(fù)上述步驟,直到V為空,停止。

9)對數(shù)據(jù)子集進行歸并整理,得到的結(jié)果就是聚類結(jié)果。

在NNAF算法中,若起始點選取不當可能就會出現(xiàn)局部最優(yōu)解的問題,而使用Canopy算法則可以避免這個問題。在采用Canopy算法得到粗聚類結(jié)果之后,可以直接對聚簇交叉的地方進行起始點選取,避免起始點選擇不當?shù)膯栴}。

此外,NNAF算法的計算量較大,這主要是體現(xiàn)在計算每個點最近鄰點的時候,這種計算方式在處理少量的數(shù)據(jù)時,并無任何不當之處,但是當數(shù)據(jù)規(guī)模增大之后,其計算難度就會激增,計算時間也會變得極長,這也是它無法直接應(yīng)用在海量數(shù)據(jù)處理上的原因。而在采用Canopy算法進行改進之后,可以通過數(shù)據(jù)處理將數(shù)據(jù)集分成數(shù)據(jù)子集,并使用Canopy算法產(chǎn)生一定數(shù)量的Canopy中心,將各個數(shù)據(jù)子集的Canopy中心進行集合,然后再次利用Canopy算法處理這些中心點(此時使用的是新的T1、T2),得到的就是全局的Canopy中心集合,最后利用這些點對原始的數(shù)據(jù)集進行處理,生成多個相互之間有重疊的Canopy(聚簇),從而可以直接處理子集的重疊部分,減少計算量。

2.2 算法MapReduce化

MapReduce是Google提出的一種并行編程框架,它可以通過Map(映射)和Reduce(約減)2個過程來將具體的計算過程并行化,并分布在不同的機器上進行計算。

本文算法的MapReduce化主要應(yīng)用于2個方面:1)對整體數(shù)據(jù)集的分割,在整體數(shù)據(jù)集過大的情況下,可以通過MapReduce對數(shù)據(jù)集進行分割,然后對分割后的數(shù)據(jù)集進行并行處理,進而達到處理海量數(shù)據(jù)的效果;2)對Canopy交叉集合的處理,通過對交叉集合的同步并行處理,減少運行時間,達到實時性的要求。

“肖玉那樣一根筋的人，她說是不用我負責，要是犯了傻，完事再自殺呢？俺可擔不起這個責任，想得開的小妞有的是?！?/p>

本文改進算法的具體結(jié)構(gòu)框架如圖2所示,該算法主要分為2個階段:

階段1采用Canopy算法得到相互之間有交叉的聚簇,此部分的MapReduce化主要體現(xiàn)在對數(shù)據(jù)集本身的處理上:首先對數(shù)據(jù)集向量化,進行分割并確定閾值;然后將分割后的數(shù)據(jù)集分布在不同的平臺上,采用Canopy粗聚類得到所有聚簇的中心點;最后再將每個平臺產(chǎn)生的聚簇中心點匯總,確定新的閾值,并利用新的閾值對中心點的集合進行聚類,將最終得到的聚類結(jié)果應(yīng)用在總的數(shù)據(jù)集上。此時得到的結(jié)果是相互重疊的少量聚簇。

階段2此階段的主要任務(wù)是對所有聚簇的交叉部分進行處理,將交叉點歸類。這一階段的MapReduce化主要體現(xiàn)在對交叉集的處理上:在獲取所有交叉集合的信息后,將這些交叉集分布到不同的平臺上采用最近鄰優(yōu)先吸收聚類算法進行處理;然后將這些信息匯總,得到總的聚類結(jié)果。

圖2 改進的最近鄰優(yōu)先吸收聚類算法結(jié)構(gòu)

3 實驗

3.1 實驗數(shù)據(jù)來源和平臺

實驗的數(shù)據(jù)集來源于UC Irvine Machine Learning Repository數(shù)據(jù)庫。該數(shù)據(jù)庫是一個2008年出現(xiàn)的包括多個數(shù)據(jù)集在內(nèi)的詞匯數(shù)據(jù)集集合,本文采用其中3個大小區(qū)分明顯的數(shù)據(jù)集:

1)Enron Emails數(shù)據(jù)集,大小約為50 MB,包括39 861封郵件、28 102個單詞,總單詞數(shù)約為6 400 000個。

2)紐約時報新聞文章數(shù)據(jù)集,大小約為900 MB,包括300 000篇文章、102 660個單詞,總詞數(shù)約為100 000 000個。

3)PubMed摘要數(shù)據(jù)集,在Linux系統(tǒng)下壓縮包大小為7 GB,包括8.2×106條摘要、141 043個單詞,總詞數(shù)約為7.3×108個。

所有實驗均在Hadoop平臺完成,實驗平臺的配置為:雙核2.6 GHz CPU;4 GB內(nèi)存;30 GB硬盤;操作系統(tǒng)為Centos6.3;JDK為1.7.0_45;Hadoop版本為Hadoop-0.2-0.2。

3.2 實驗步驟

Job1:多次使用Canopy算法產(chǎn)生k個Canopy中心。

Job2:利用k個中心生成k個相互重疊的聚簇。

Job3:對于重疊部分采用改進的最近鄰優(yōu)先聚類算法判斷重疊部分的數(shù)據(jù)歸屬。

Job4:整理歸并,輸出最終結(jié)果。

3.3 實驗難點及解決方法

在實驗過程中,存在一些的難點,其內(nèi)容以及解決方法如下:

1)實驗數(shù)據(jù)集的屬性過多,必須進行降維處理,否則將會出現(xiàn)維度災(zāi)難并嚴重影響聚類效率。因此,采用高相關(guān)濾波和隨機森林相結(jié)合的降維方法對屬性進行處理。

2)對數(shù)據(jù)集進行分析,獲取用于比較算法效果的最近鄰優(yōu)先吸收聚類算法的距離閾值和數(shù)量閾值。由于數(shù)據(jù)集的規(guī)模過大,屬性過多,在設(shè)置2個閾值時需要進行大量的調(diào)整。但是在改進方法中,只需計算2個相交的Canopy的距離閾值和數(shù)量閾值。

3)聚類的數(shù)量的控制。在大規(guī)模數(shù)據(jù)集中采用Canopy算法得到的粗聚類的Canopy數(shù)較多,需要進行多重Canopy聚類。

4)均方誤差的計算。由于數(shù)據(jù)集的規(guī)模過大,在計算均方誤差時,很容易出現(xiàn)卡死的現(xiàn)象,因此分別針對每一個聚類結(jié)果采用分布式來對其進行計算,并將結(jié)果進行匯總,求取均值,得到整體聚類的均方誤差來衡量聚類效果。

3.4 實驗結(jié)果分析

為考察本文算法的聚類結(jié)果的質(zhì)量,采用改進后的最近鄰優(yōu)先吸收聚類算法分別針對上述3種規(guī)模不同的數(shù)據(jù)集進行處理,并將其與Mahout算法庫中的代表性聚類算法K-means算法和MapReduce框架下的最近鄰優(yōu)先吸收聚類算法進行比較,結(jié)果分別如表1～表3所示。由于算法的數(shù)據(jù)集規(guī)模過大,無法進行預(yù)聚類,因此無法對準確率進行精確衡量,只能用均方誤差代替。

表1 Enron Emails數(shù)據(jù)集實驗結(jié)果比較

表2 紐約時報新聞文章數(shù)據(jù)集實驗結(jié)果比較

表3 PubMed摘要數(shù)據(jù)集實驗結(jié)果比較

由表1～表3中的數(shù)據(jù)可以看出,在采用Canopy算法對最近鄰優(yōu)先算法改進后,運行時間相對未改進的最近鄰優(yōu)先算法有了很大的提升,尤其是在數(shù)據(jù)規(guī)模更大的情況下,提升更為明顯。在較小的Enron Emails數(shù)據(jù)集中,改進的最近鄰優(yōu)先吸收聚類算法的運行時間比最近鄰優(yōu)先吸收聚類算法提高了116.45%;但是在較大的PubMed摘要數(shù)據(jù)集中,提高了522.36%。而衡量聚類準確率的均方誤差在數(shù)據(jù)規(guī)模不大的情況下,區(qū)別并不是很大,在規(guī)模較小的Enron Emails數(shù)據(jù)集中,改進的最近鄰優(yōu)先吸收聚類算法的均方誤差比起最近鄰優(yōu)先吸收聚類算法高了2.14%,差別較低。但是當數(shù)據(jù)集規(guī)模逐漸變大時,改進的最近鄰優(yōu)先聚類算法的準確率還是會保持在一定的水平。而最近鄰優(yōu)先聚類算法由于閾值設(shè)置的問題,在數(shù)據(jù)集規(guī)模擴大的情況下,會更容易出現(xiàn)準確率下降的問題。如表2、表3所示,在規(guī)模處于中等的紐約時報新聞文章數(shù)據(jù)集中,改進的最近鄰優(yōu)先吸收聚類算法的均方誤差比起最近鄰優(yōu)先吸收聚類算法要低4.41%;在規(guī)模較大的PubMed摘要數(shù)據(jù)集中,改進的最近鄰優(yōu)先吸收聚類算法的均方誤差比起最近鄰優(yōu)先吸收聚類算法要低44.43%,聚類效果更優(yōu)。

與Mahout算法庫中的K-means算法相比,改進的最近鄰優(yōu)先吸收算法在運行速度上更占優(yōu)勢,提升幅度約為27%。在均方誤差的比較上,數(shù)據(jù)集較小的情況下,K-means算法的均方誤差較小,聚類效果更好,約為10%。但是隨著數(shù)據(jù)集規(guī)模的增加,K-means算法受局部最優(yōu)的影響,其均方誤差比起改進的最近鄰優(yōu)先吸收聚類算法更大,準確率更低。在數(shù)據(jù)規(guī)模中等的紐約時報新聞文章數(shù)據(jù)集中,改進的最近鄰優(yōu)先吸收聚類算法的均方誤差要比K-means算法低6.46%,在數(shù)據(jù)集規(guī)模極大的PubMed摘要數(shù)據(jù)集中,改進的最近鄰優(yōu)先吸收聚類算法的均方誤差要比K-means算法低24.85%。

為更直觀地顯示不同算法在不同規(guī)模數(shù)據(jù)集上的效果,本文進行了趨勢圖比較。不同算法在不同規(guī)模數(shù)據(jù)集上的運行時間如圖3所示。

圖3 3種算法的運行時間比較

不同算法針對不同規(guī)模數(shù)據(jù)集的均方誤差如圖4所示。可以看出,在數(shù)據(jù)集規(guī)模不斷變大的情況下,3種算法的運行時間和聚類效果的變化情況。最近鄰優(yōu)先吸收聚類算法的運行時間受數(shù)據(jù)集規(guī)模的影響最大,隨著數(shù)據(jù)集規(guī)模的增長,最近鄰優(yōu)先吸收聚類算法的運行時間比起另外2種算法,變化幅度最為明顯。這主要是因為數(shù)據(jù)集變大后采用SNN算法來計算所有向量之間的距離所需的時間大量增加。而K-means算法和改進的最近鄰優(yōu)先吸收聚類算法的運行時間雖然也有增加,但仍在正常的范圍內(nèi)。

圖4 3種算法的均方誤差比較

隨著數(shù)據(jù)集規(guī)模的增長,均方誤差上升,最近鄰優(yōu)先吸收算法的聚類效果下降最為嚴重,這是因為數(shù)據(jù)集規(guī)模的增加會使閾值的影響不斷變大,造成聚類效果的下降。其次是K-means算法,局部最優(yōu)現(xiàn)象也會造成聚類效果的下降。綜上所述,在處理大規(guī)模數(shù)據(jù)集時,改進的最近鄰優(yōu)先吸收聚類算法性能更優(yōu)。

4 結(jié)束語

本文借助Canopy算法提出基于MapReduce的改進最近鄰優(yōu)先吸收聚類算法,并將其應(yīng)用于海量數(shù)據(jù)處理平臺。實驗結(jié)果表明,本文算法可在快速處理大規(guī)模數(shù)據(jù)集的同時保持較好的聚類效果。下一步將從提高運行速率和準確率的角度出發(fā)對算法進行優(yōu)化,以期在改善聚類效果的同時提高聚類效率。

[1] 牛新征,佘 堃.面向大規(guī)模數(shù)據(jù)的快速并行聚類劃分算法研究[J].計算機科學(xué),2012,39(1):134-137.

[2] 陳東明,劉 健,王冬琦,等.基于MapReduce的分布式網(wǎng)絡(luò)數(shù)據(jù)聚類算法[J].計算機工程,2013,39(7):76-82.

[3] JI Yanqing,TIAN Yun,SHEN Fangyang,et al.Leveraging MapReduce to efficiently extract associations between biomedical concepts from large text data[J].Micro-processors and Microsystems,2016,46(B):202-210.

[4] PULGAR-RUBIO F,RIVERA-RIVAS A J,PéREZ-GODOY M D,et al.MEFASD-BD:multi-objective evolutionary fuzzy algorithm for subgroup discovery in big data environments-a MapReduce solution[J].Knowledge-Based Systems,2017,117(1):70-78.

[5] TSAI C F,LIN W C,KE S W.Big data mining with parallel computing:a comparison of distributed and MapReduce methodologies[J].The Journal of Systems and Software,2016,122(1):83-92.

[6] 馮麗娜.并行K-means聚類方法在簡歷數(shù)據(jù)中的應(yīng)用研究[J].計算機科學(xué),2009,36(8):276-279.

[7] 謝娟英,王艷娥.最小方差優(yōu)化初始聚類中心的K-means算法[J].計算機工程,2014,40(8):205-211,223.

[8] SHAHRIVARI S,JALILI S.Single-pass and linear-time K-means clustering based on MapReduce[J].Information Systems,2016,60(C):1-12.

[9] 冀素琴,石洪波.基于MapReduce的K-means聚類集成[J].計算機工程,2013,39(9):84-87.

[10] 趙 慶.基于Hadoop平臺下的Canopy-Kmeans高效算法[J].電子科技,2014,2(7):29-31.

[11] 胡建軍,唐常杰,李 川,等.基于最近鄰優(yōu)先的高效聚類算法[J].四川大學(xué)學(xué)報(工程科學(xué)版),2004,6(4):93-99.

[12] 王 鑫,王洪國,張建喜,等.基于數(shù)據(jù)分區(qū)的最近鄰優(yōu)先聚類算法[J].計算機科學(xué),2005,12(9):188-190.

[13] 程 苗,陳華平.基于Hadoop的Web日志挖掘[J].計算機工程,2011,41(11):37-39.

[14] SANDEEP P,MORGAN F,CAWLEY S,et al.Modular neural tile architecture for compact embedded hardware spiking neural network[J].Neural Processing Letters,2013,38(2):131-153.

[15] 冀素琴,石洪波.面向海量數(shù)據(jù)的K-means聚類優(yōu)化算法[J].計算機工程與應(yīng)用,2014,14(1):143-147.