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

　　關(guān)鍵詞： KNN分類(lèi)算法；并行化；MapReduce編程模型；Hadoop；分布式緩存

0 引言

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

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

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

1 MapReduce編程模型

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

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

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

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

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

　　（3）在Mapper階段，被分配到Map任務(wù)的worker讀取輸入數(shù)據(jù)的對(duì)應(yīng)分片。Mapper與Split是一一對(duì)應(yīng)的。Mapper任務(wù)首先通過(guò)相關(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ū)，并寫(xiě)入本地磁盤(pán)。分區(qū)一一對(duì)應(yīng)于Reducer。Reducer會(huì)通過(guò)master獲得相對(duì)應(yīng)的分區(qū)在本地磁盤(pán)上的位置信息。

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

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

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

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

2 KNN算法描述

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

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

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

　　輸出：實(shí)例x所屬的類(lèi)y

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

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

　　（3）在Nk（x）中根據(jù)分類(lèi)決策規(guī)則（如多數(shù)表決）決定x的類(lèi)別y：

　　i=1，2，…N；j=1，2，…K

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

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

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

　　3.1 并行化KNN分析

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

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

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

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

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

　　輸入：<key，value>

　　輸出：<key，String>

　　ClassMapper{

　　使用UseDistributedCache（），獲得測(cè)試數(shù)據(jù)集Tests；

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

　　Map（key，value）{

　　訓(xùn)練樣本向量化，得到向量化的測(cè)試樣本test；

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

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

　　根據(jù)投票獲得測(cè)試樣本的類(lèi)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，它通過(guò)地質(zhì)變量來(lái)預(yù)測(cè)森林植被覆蓋類(lèi)型，是54維的7分類(lèi)數(shù)據(jù)集。共有58萬(wàn)個(gè)樣本，選取其中的30萬(wàn)個(gè)為訓(xùn)練樣本，其余的28萬(wàn)個(gè)為測(cè)試實(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ī)制帶來(lái)的性能提升，還實(shí)現(xiàn)了另一種基于MapReduce的并行化KNN方案[8]，采用內(nèi)存的機(jī)制傳遞邊數(shù)據(jù)。這種方案由于受到單節(jié)點(diǎn)PC內(nèi)存的限制，不能通過(guò)內(nèi)存來(lái)傳遞訓(xùn)練數(shù)據(jù)，只能將測(cè)試數(shù)據(jù)作為邊數(shù)據(jù)，由內(nèi)存?zhèn)鬟f給woker。因此，這種方法不僅需要經(jīng)過(guò)Mapper階段，還需要經(jīng)過(guò)Reducer階段。理論上，這種方案的效率要低于采用分布式緩存機(jī)制的并行化KNN。

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

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

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

　　通過(guò)實(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í)行過(guò)程中集群之間的信息交互以及中間數(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)并行化，取得更理想的效果，將是接下來(lái)研究的主要工作和方向。

　　參考文獻(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分類(lèi)算法的MapReduce并行化實(shí)現(xiàn)[J].南京航空航天大學(xué)學(xué)報(bào)，2013，45（4）：550-555.