面向海量數據的改進最近鄰優先吸收聚類算法

,,

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

0 概述

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

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

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

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

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

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

1 最近鄰優先吸收聚類算法

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

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

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

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

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

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

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

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

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

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

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

2 最近鄰優先吸收算法的改進

2.1 基于Canopy算法的改進

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

Begin

canopy=[]

load list

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

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算法得到子集之后,對子集中相互重疊的部分采用最近鄰優先聚類算法進行計算,從而達到減少計算量和提升準確率的目的。具體步驟如下:

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

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

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

4)重復步驟2)和步驟3),直到list為空,結束。

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

圖1 聚簇交叉情況

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

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

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

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

在NNAF算法中,若起始點選取不當可能就會出現局部最優解的問題,而使用Canopy算法則可以避免這個問題。在采用Canopy算法得到粗聚類結果之后,可以直接對聚簇交叉的地方進行起始點選取,避免起始點選擇不當的問題。

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

2.2 算法MapReduce化

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

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

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

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

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

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

圖2 改進的最近鄰優先吸收聚類算法結構

3 實驗

3.1 實驗數據來源和平臺

實驗的數據集來源于UC Irvine Machine Learning Repository數據庫。該數據庫是一個2008年出現的包括多個數據集在內的詞匯數據集集合,本文采用其中3個大小區分明顯的數據集:

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

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

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

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

3.2 實驗步驟

Job1:多次使用Canopy算法產生k個Canopy中心。

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

Job3:對于重疊部分采用改進的最近鄰優先聚類算法判斷重疊部分的數據歸屬。

Job4:整理歸并,輸出最終結果。

3.3 實驗難點及解決方法

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

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

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

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

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

3.4 實驗結果分析

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

表1 Enron Emails數據集實驗結果比較

表2 紐約時報新聞文章數據集實驗結果比較

表3 PubMed摘要數據集實驗結果比較

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

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

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

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

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

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

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

4 結束語

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

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

[2] 陳東明,劉 健,王冬琦,等.基于MapReduce的分布式網絡數據聚類算法[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聚類方法在簡歷數據中的應用研究[J].計算機科學,2009,36(8):276-279.

[7] 謝娟英,王艷娥.最小方差優化初始聚類中心的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] 胡建軍,唐常杰,李 川,等.基于最近鄰優先的高效聚類算法[J].四川大學學報(工程科學版),2004,6(4):93-99.

[12] 王 鑫,王洪國,張建喜,等.基于數據分區的最近鄰優先聚類算法[J].計算機科學,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] 冀素琴,石洪波.面向海量數據的K-means聚類優化算法[J].計算機工程與應用,2014,14(1):143-147.