,,

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

0 概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6)當(dāng)P中的個(gè)數(shù)滿足數(shù)量閾值q時(shí),結(jié)束對(duì)這個(gè)類的訪問(wèn)。

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

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

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

2.1 基于Canopy算法的改進(jìn)

Canopy[15]算法是一種新的聚類方法,它可以通過(guò)使用一種簡(jiǎn)單的距離計(jì)算方法把整個(gè)數(shù)據(jù)集合分成幾個(gè)相互重疊的子集,從而有效地減少數(shù)據(jù)的計(jì)算量。Canopy算法對(duì)處理海量數(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)/*隨機(jī)從list中取一點(diǎn)A*/

delete A from list

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

d=pdist2(A,list(j))/*計(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

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

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

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

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

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

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

圖1 聚簇交叉情況

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

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

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

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

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

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

2.2 算法MapReduce化

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

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

“肖玉那樣一根筋的人，她說(shuō)是不用我負(fù)責(zé)，要是犯了傻，完事再自殺呢？俺可擔(dān)不起這個(gè)責(zé)任，想得開(kāi)的小妞有的是?！?/p>

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

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

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

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

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)來(lái)源和平臺(tái)

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

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

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

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

所有實(shí)驗(yàn)均在Hadoop平臺(tái)完成,實(shí)驗(yàn)平臺(tái)的配置為:雙核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 實(shí)驗(yàn)步驟

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

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

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

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

3.3 實(shí)驗(yàn)難點(diǎn)及解決方法

在實(shí)驗(yàn)過(guò)程中,存在一些的難點(diǎn),其內(nèi)容以及解決方法如下:

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

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

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

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

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

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

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

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

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

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

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

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

圖3 3種算法的運(yùn)行時(shí)間比較

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

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

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

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

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

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

[2] 陳東明,劉 健,王冬琦,等.基于MapReduce的分布式網(wǎng)絡(luò)數(shù)據(jù)聚類算法[J].計(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聚類方法在簡(jiǎn)歷數(shù)據(jù)中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué),2009,36(8):276-279.

[7] 謝娟英,王艷娥.最小方差優(yōu)化初始聚類中心的K-means算法[J].計(jì)算機(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].計(jì)算機(jī)工程,2013,39(9):84-87.

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

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

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

[13] 程 苗,陳華平.基于Hadoop的Web日志挖掘[J].計(jì)算機(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].計(jì)算機(jī)工程與應(yīng)用,2014,14(1):143-147.