《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > 基于MapReduce和分布式緩存的KNN分類算法研究
基于MapReduce和分布式緩存的KNN分類算法研究
2015年微型機(jī)與應(yīng)用第2期
涂敬偉1,,2,,皮建勇1,2
(1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院,,貴州 貴陽 550025,; 2.貴州大學(xué) 云計(jì)算與物聯(lián)網(wǎng)研究中心,,貴州 貴陽 550025)
摘要: 隨著大數(shù)據(jù)時(shí)代的到來,,K最近鄰(KNN)算法較高的計(jì)算復(fù)雜度的弊端日益凸顯,。在深入研究了KNN算法的基礎(chǔ)上,結(jié)合MapReduce編程模型,,利用其開源實(shí)現(xiàn)Hadoop,,提出了一種基于MapReduce和分布式緩存機(jī)制的KNN并行化方案。該方案只需要通過Mapper階段就能完成分類任務(wù),,減少了TaskTracker與JobTracker之間的通信開銷,,同時(shí)也避免了Mapper的中間結(jié)果在集群任務(wù)節(jié)點(diǎn)之間的通信開銷。通過在Hadoop集群上實(shí)驗(yàn),,驗(yàn)證了所提出的并行化KNN方案有著優(yōu)良的加速比和擴(kuò)展性,。
Abstract:
Key words :

  摘  要: 隨著大數(shù)據(jù)時(shí)代的到來,K最近鄰(KNN)算法較高的計(jì)算復(fù)雜度的弊端日益凸顯,。在深入研究了KNN算法的基礎(chǔ)上,,結(jié)合MapReduce編程模型,利用其開源實(shí)現(xiàn)Hadoop,,提出了一種基于MapReduce和分布式緩存機(jī)制的KNN并行化方案,。該方案只需要通過Mapper階段就能完成分類任務(wù),減少了TaskTracker與JobTracker之間的通信開銷,,同時(shí)也避免了Mapper的中間結(jié)果在集群任務(wù)節(jié)點(diǎn)之間的通信開銷,。通過在Hadoop集群上實(shí)驗(yàn),驗(yàn)證了所提出的并行化KNN方案有著優(yōu)良的加速比和擴(kuò)展性,。

  關(guān)鍵詞KNN分類算法,;并行化;MapReduce編程模型,;Hadoop,;分布式緩存

0 引言

  在數(shù)據(jù)挖掘中,,分類算法是基礎(chǔ)和核心的研究內(nèi)容,如何實(shí)現(xiàn)對(duì)事物的自動(dòng)歸檔和分類是其主要的研究內(nèi)容,。經(jīng)典的分類算法主要有決策樹,、貝葉斯分類器、最近鄰,、SVM,、神經(jīng)網(wǎng)絡(luò)等。這些算法在電子商務(wù),、通信,、互聯(lián)網(wǎng)、醫(yī)療以及科學(xué)研究等領(lǐng)域起到了非常重要的決策支撐作用,。其中,,K最近鄰(KNN)分類法是一種簡潔、易實(shí)現(xiàn),、分類準(zhǔn)確率較高的算法,,在文本分類、圖像及模式識(shí)別等方面有著廣泛的應(yīng)用,。但是,,隨著大數(shù)據(jù)時(shí)代對(duì)分類任務(wù)要求的提高,傳統(tǒng)的KNN分類算法已經(jīng)不能滿足人們的需求,。

  針對(duì)KNN算法的時(shí)間復(fù)雜度高,、運(yùn)算速度慢等不足,眾多學(xué)者從不同的方向?qū)λ惴ㄟM(jìn)行了改進(jìn)研究,。比如參考文獻(xiàn)[1]中所提到KD樹,,建立了一種對(duì)K維空間中的實(shí)例進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的數(shù)據(jù)結(jié)構(gòu),減少了計(jì)算距離的次數(shù),;參考文獻(xiàn)[2]中,,通過建立低維的特征向量空間來降低計(jì)算開銷;參考文獻(xiàn)[3]則是通過減少訓(xùn)練樣本來降低計(jì)算開銷,。這些改進(jìn)的算法或以犧牲算法的分類準(zhǔn)確率為代價(jià),,或在降低樣本相似度計(jì)算代價(jià)的同時(shí),引入了新的計(jì)算代價(jià),,同時(shí)也降低了模型易讀性,。然而,Google分布式計(jì)算模型MapReduce的提出,,為KNN處理大數(shù)據(jù)集提供了一種新的可能,。Apache基金會(huì)的開源項(xiàng)目Hadoop的發(fā)布,使得這種可能成為了現(xiàn)實(shí)。

  本文簡單介紹了MapReduce編程模型,,對(duì)傳統(tǒng)的KNN算法進(jìn)行了簡單扼要的介紹和分析,;提出并實(shí)現(xiàn)了基于MapReduce模型的并行化方案。通過實(shí)驗(yàn)驗(yàn)證了并行化KNN方法的高效性,,并分析了其不足與以后的研究方向,。

1 MapReduce編程模型

  簡單地說,MapReduce[4]編程模型采用了“分而治之”的思想,,將一個(gè)大而復(fù)雜的作業(yè)分割成眾多小而簡單的獨(dú)立任務(wù),,然后將這些任務(wù)分發(fā)給集群中各節(jié)點(diǎn)獨(dú)立執(zhí)行。

  在Map和Reduce中,,數(shù)據(jù)通常以<key,,value>鍵值對(duì)的形式存在。

  MapReduce編程模型的執(zhí)行過程如圖1所示,。具體流程大致可分為以下幾個(gè)部分:

 ?。?)用戶提交任務(wù)后,MapReduce首先將HDFS上的源數(shù)據(jù)塊邏輯上劃分為若干片,。隨后,,將切片信息傳送給JobTacker,并通過Fork創(chuàng)建主控進(jìn)程(master)和工作進(jìn)程(worker),。

 ?。?)由主控進(jìn)程負(fù)責(zé)任務(wù)調(diào)度,根據(jù)數(shù)據(jù)本地化策略,,為空閑的worker分配任務(wù)。

 ?。?)在Mapper階段,,被分配到Map任務(wù)的worker讀取輸入數(shù)據(jù)的對(duì)應(yīng)分片。Mapper與Split是一一對(duì)應(yīng)的,。Mapper任務(wù)首先通過相關(guān)的函數(shù),,以行為單位,將Split轉(zhuǎn)化為Map能夠處理的<key,,value>鍵值對(duì)的形式傳遞給Map,,Map產(chǎn)生的中間鍵值對(duì)緩存在內(nèi)存之中。

 ?。?)當(dāng)緩存溢出時(shí),,緩存的中間鍵值對(duì)根據(jù)用戶定義的Reducer的個(gè)數(shù)R,分成R個(gè)區(qū),,并寫入本地磁盤,。分區(qū)一一對(duì)應(yīng)于Reducer。Reducer會(huì)通過master獲得相對(duì)應(yīng)的分區(qū)在本地磁盤上的位置信息,。

 ?。?)Reducer階段,,Reducer首先讀取與之相對(duì)應(yīng)的分區(qū)數(shù)據(jù),隨后根據(jù)鍵值對(duì)<key,,value>的key值對(duì)其進(jìn)行排序,,將具有相同key值的排在一起。

 ?。?)Reduce函數(shù)遍歷排序后的中間鍵值對(duì),。對(duì)于每個(gè)唯一的鍵,根據(jù)用戶重寫的Reduce,,處理與之相關(guān)聯(lián)的value值,。Reduce的輸出結(jié)果以鍵值對(duì)的形式寫入到該分區(qū)的輸出文件中。

 ?。?)當(dāng)所有的Map和Reduce任務(wù)都完成以后,,master會(huì)喚醒用戶程序,用戶程序?qū)apReduce平臺(tái)的調(diào)用由此返回,。

001.jpg

  由此可見,,MapReduce為用戶提供了一個(gè)極其簡單的分布式編程模型。用戶只需關(guān)心與任務(wù)相關(guān)的Map和Reduce即可,,其他的對(duì)用戶而言都是透明的,。

2 KNN算法描述

  K近鄰法[5]是在1968年由COVER T和HART P提出的,它沒有顯式的學(xué)習(xí)過程,。分類時(shí),,對(duì)新的實(shí)例,根據(jù)其K個(gè)最近鄰的訓(xùn)練實(shí)例的類別,,通過多數(shù)表決等方式進(jìn)行預(yù)測,。所以,實(shí)際上K近鄰法是利用訓(xùn)練集對(duì)特征向量空間進(jìn)行劃分,,并作為其分類的“模型”[6],。具體算法描述如下:

  輸入數(shù)據(jù):訓(xùn)練數(shù)據(jù)集T={(x1,y1),,(x2,,y2),…,,(xN,,yN)}

  其中,xi∈XRn為實(shí)例的特征向量,,yi∈{c1,,c2,…cK}為實(shí)例的類別,i=1,,2,,…N;實(shí)例特征向量x,。

  輸出:實(shí)例x所屬的類y

 ?。?)計(jì)算實(shí)例x與每個(gè)訓(xùn)練實(shí)例的距離;

 ?。?)令K是最近鄰數(shù)目,,根據(jù)計(jì)算的距離度量,在訓(xùn)練集中找出與x最近鄰的K個(gè)點(diǎn)的集合Nk(x),;

 ?。?)在Nk(x)中根據(jù)分類決策規(guī)則(如多數(shù)表決)決定x的類別y:

  30K`BB]SDD[O[%LZG1KY3I4.jpg

  i=1,2,,…N,;j=1,2,,…K

  其中,,I為指示函數(shù),即當(dāng)yi=cj時(shí)I為1,,否則I為0,。

  從算法描述可以看到,算法的原理和實(shí)現(xiàn)非常簡單,。但是,,由于每判定一個(gè)輸入實(shí)例都要遍歷一次所有的訓(xùn)練樣本,并計(jì)算該輸入實(shí)例到所有訓(xùn)練樣本的距離,,因此,,對(duì)于具有海量和高維的訓(xùn)練數(shù)據(jù)集以及分類任務(wù)時(shí),K近鄰法的計(jì)算開銷會(huì)以驚人的速度增加,。總的分類任務(wù)所需時(shí)間將遠(yuǎn)遠(yuǎn)超出人們的預(yù)期,,使得K近鄰法失去了用武之地,。


3 并行化KNN的分析與實(shí)現(xiàn)

  3.1 并行化KNN分析

  單節(jié)點(diǎn)情況下,針對(duì)一個(gè)分類任務(wù),,訓(xùn)練樣本和測試樣本的大小一般情況下是固定的,。所有的工作量由一臺(tái)PC獨(dú)立承擔(dān)。在集群環(huán)境下,,借鑒MapReduce“分而治之”的思想,,將海量的數(shù)據(jù)集進(jìn)行分割,上傳至Hadoop集群的分布式文件系統(tǒng)HDFS。然后將大的樣本相似性計(jì)算和分類決策規(guī)則分割到存有訓(xùn)練樣本的節(jié)點(diǎn)上進(jìn)行并行處理,。這是并行化KNN算法的基本思想,。

  一般情況下,MapReduce編程模型處理的是單一數(shù)據(jù)源的任務(wù),,比如WordCount任務(wù),。但是,KNN分類是有導(dǎo)師的學(xué)習(xí),,需要兩個(gè)數(shù)據(jù)源:訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集,,且要求在Map任務(wù)開始前,能夠讀取到這兩個(gè)數(shù)據(jù)集,。為了解決雙數(shù)據(jù)源的問題,,本文采用了Hadoop提供的分布式文件緩存拷貝機(jī)制[7],它能夠在任務(wù)運(yùn)行過程中及時(shí)地將文件復(fù)制到任務(wù)節(jié)點(diǎn)以供使用,。當(dāng)集群PC的內(nèi)存有限,、文件無法整個(gè)放入到內(nèi)存中時(shí),使用分布式緩存機(jī)制進(jìn)行復(fù)試是最佳的選擇,。

002.jpg

  將測試文件散布到集群的各個(gè)節(jié)點(diǎn)中,,將訓(xùn)練數(shù)據(jù)作為邊數(shù)據(jù)分發(fā)給存有測試集的節(jié)點(diǎn)。在Mapper階段,,雖然每個(gè)測試樣例仍要遍歷整個(gè)訓(xùn)練數(shù)據(jù)集,,但是,每個(gè)Mapper只需要完成1/n個(gè)測試集與整個(gè)訓(xùn)練集的相似性計(jì)算,,如圖2(b)所示,。所以在Mapper階段,測試樣本即可獲得與訓(xùn)練數(shù)據(jù)集全局的相似性,。從而在本地就能夠得到測試樣例的K個(gè)最近鄰居,,并根據(jù)投票選出測試樣例的類別。不需要經(jīng)過Reducer階段,、集群間的數(shù)據(jù)傳輸,、與master進(jìn)程之間的信息交互,進(jìn)而節(jié)約任務(wù)運(yùn)行的時(shí)間,,提高了算法的效率,。

  3.2 并行化KNN的實(shí)現(xiàn)

  根據(jù)上一小節(jié)的分析,只通過Mapper就能夠完成分類任務(wù),。首先,,Mapper讀取到的分片數(shù)據(jù)由InputFormat對(duì)象,生成<key,,value>鍵值對(duì),。其中,,key為測試樣本在分片中的偏移量,value為每個(gè)樣本的內(nèi)容,,數(shù)據(jù)類型為Text,。同時(shí),在運(yùn)行Map之前,,將訓(xùn)練數(shù)據(jù)上傳至HDFS或本地文件系統(tǒng),,借助分布式緩存機(jī)制,將訓(xùn)練集分發(fā)給每一個(gè)slave節(jié)點(diǎn),,然后Mapper通過一個(gè)靜態(tài)的方法UseDistributedCache()實(shí)現(xiàn)對(duì)緩存數(shù)據(jù)的調(diào)用,。之后,通過Map計(jì)算每一個(gè)測試樣本與每一個(gè)訓(xùn)練樣本的距離,,獲得每一個(gè)訓(xùn)練樣本的類別標(biāo)志,;找出測試實(shí)例的K個(gè)最近鄰,根據(jù)投票得到測試實(shí)例的類別,;最后將結(jié)果以<key,,value>的形式輸出到指定的目錄。具體偽代碼如下:

  輸入:<key,,value>

  輸出:<key,,String>

  ClassMapper{

  使用UseDistributedCache(),獲得測試數(shù)據(jù)集Tests,;

  創(chuàng)建KNNnode對(duì)象node,,存儲(chǔ)訓(xùn)練樣本與測試樣本的距離和訓(xùn)練樣本的類別;

  Map(key,,value){

  訓(xùn)練樣本向量化,,得到向量化的測試樣本test;

  遍歷本節(jié)點(diǎn)訓(xùn)練樣本集Trains,,得到測試樣本與每一個(gè)訓(xùn)練樣本的距離distanc以及相應(yīng)訓(xùn)練樣例的類標(biāo)示catalog,,并賦值給node對(duì)象;

  通過PriorityQueue得到與測試樣距離最近的K個(gè)node對(duì)象的隊(duì)列pq,;

  根據(jù)投票獲得測試樣本的類c,;

  輸出結(jié)果output.collct(test,c),;

  }

  }

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

  4.1 實(shí)驗(yàn)環(huán)境

  并行化KNN實(shí)驗(yàn)是在Hadoop平臺(tái)下完成的,。硬件設(shè)備為6臺(tái)X86架構(gòu)的PC,主設(shè)備節(jié)點(diǎn)采用Intel志強(qiáng)四核處理器,,內(nèi)存為4 GB;從設(shè)備節(jié)點(diǎn)采用AMD四核處理器,,主頻為2.7 GHz,,內(nèi)存為4 GB,。

  4.2 實(shí)驗(yàn)數(shù)據(jù)集

  實(shí)驗(yàn)采用標(biāo)準(zhǔn)數(shù)據(jù)集CoverType,它通過地質(zhì)變量來預(yù)測森林植被覆蓋類型,,是54維的7分類數(shù)據(jù)集,。共有58萬個(gè)樣本,選取其中的30萬個(gè)為訓(xùn)練樣本,,其余的28萬個(gè)為測試實(shí)例,,數(shù)據(jù)集大小為70 MB。

  4.3 結(jié)果分析

  實(shí)驗(yàn)首先對(duì)傳統(tǒng)的KNN算法和本文提出的并行化KNN的運(yùn)行效率進(jìn)行了驗(yàn)證,。另外,,為了驗(yàn)證采用分布式緩存機(jī)制帶來的性能提升,還實(shí)現(xiàn)了另一種基于MapReduce的并行化KNN方案[8],,采用內(nèi)存的機(jī)制傳遞邊數(shù)據(jù),。這種方案由于受到單節(jié)點(diǎn)PC內(nèi)存的限制,不能通過內(nèi)存來傳遞訓(xùn)練數(shù)據(jù),,只能將測試數(shù)據(jù)作為邊數(shù)據(jù),,由內(nèi)存?zhèn)鬟f給woker。因此,,這種方法不僅需要經(jīng)過Mapper階段,,還需要經(jīng)過Reducer階段。理論上,,這種方案的效率要低于采用分布式緩存機(jī)制的并行化KNN,。

  在分布式環(huán)境下,由于數(shù)據(jù)分布的不確定性,,實(shí)驗(yàn)結(jié)果具有一定的顛簸,,以下實(shí)驗(yàn)數(shù)據(jù)均為在多次實(shí)驗(yàn)后所取得的合理值。

003.jpg

  圖3顯示了三種算法在處理相同任務(wù)時(shí)所需要的時(shí)間,。從圖中可以看到,,在單臺(tái)和雙臺(tái)PC的情況下,并行化KNN方案一(采用分布式緩存機(jī)制)和方案二(采用內(nèi)存機(jī)制)并沒有表現(xiàn)出其高效性,,反而因?yàn)樾枰獑?dòng)JVM以及信息交互的原因,,運(yùn)行時(shí)間比傳統(tǒng)KNN算法的時(shí)間更長。當(dāng)集群的節(jié)點(diǎn)數(shù)大于3臺(tái)時(shí),,隨著節(jié)點(diǎn)數(shù)量的增加,,并行化KNN的運(yùn)行時(shí)間開始大幅度地減少,體現(xiàn)出并行化的KNN算法的高效性,。

004.jpg

  圖4為方案一和方案二的加速比對(duì)比圖,,從圖中可以看到,隨著節(jié)點(diǎn)數(shù)量的增加,,方案二的加速比也迅速地增加,,明顯優(yōu)于方案一,。

  通過實(shí)驗(yàn)得出,基于分布式緩存機(jī)制的并行化KNN算法在運(yùn)行效率和擴(kuò)展性上均要優(yōu)于基于內(nèi)存的并行化KNN,。

5 結(jié)論

  本文根據(jù)傳統(tǒng)KNN算法的特點(diǎn),,提出了一種基于Mapreduce和分布式緩存機(jī)制的并行化KNN算法的實(shí)現(xiàn)。減少了任務(wù)執(zhí)行過程中集群之間的信息交互以及中間數(shù)據(jù)的傳輸時(shí)延,,從而使得本文提出并實(shí)現(xiàn)的并行化KNN算法在效率上有了進(jìn)一步的提高,。但是本文提出的并行化方案只是對(duì)傳統(tǒng)KNN算法最基本的并行化的實(shí)現(xiàn),效率提升受到KNN算法本身特性的約束,。借鑒前人的研究成果,,對(duì)算法本身的K近鄰查找策略進(jìn)行研究,在此基礎(chǔ)上實(shí)現(xiàn)并行化,,取得更理想的效果,,將是接下來研究的主要工作和方向。

  參考文獻(xiàn)

  [1] SAMET H. The design and analysis of spatial data structures[M]. MA: Addison-Wesley,, 1990.

  [2] FRANKLIN M,, HALEVY A, MAIER D. A first tutorial on dataspaces[J]. Proceedings of the VLDB Endowment,, 2008,,1(2):1516-1517.

  [3] 劉莉,郭艷艷,,吳揚(yáng)揚(yáng).一種基于基本信息單元的索引[J].計(jì)算機(jī)工程與科學(xué),,2011(9):117-122.

  [4] DEAN J, GHENAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ADM-50th Anniversary Issue:1958-2008,,2008,,51(1):107-113.

  [5] COVER T, HART P. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory,,1967,,13(1):21-27.

  [6] 李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京:清華大學(xué)出版社,2012.

  [7] TOM W. Hadoop: the definitive guide(second editon)[M]. O′Reilly Media,, Inc.,, 2011.

  [8] 閆永剛,馬廷淮,,王建.KNN分類算法的MapReduce并行化實(shí)現(xiàn)[J].南京航空航天大學(xué)學(xué)報(bào),,2013,45(4):550-555.


此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載,。