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

　　關鍵詞： KNN分類算法；并行化；MapReduce編程模型；Hadoop；分布式緩存

0 引言

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

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

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

1 MapReduce編程模型

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

　　在Map和Reduce中，數據通常以<key，value>鍵值對的形式存在。

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

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

　　（2）由主控進程負責任務調度，根據數據本地化策略，為空閑的worker分配任務。

　　（3）在Mapper階段，被分配到Map任務的worker讀取輸入數據的對應分片。Mapper與Split是一一對應的。Mapper任務首先通過相關的函數，以行為單位，將Split轉化為Map能夠處理的<key，value>鍵值對的形式傳遞給Map，Map產生的中間鍵值對緩存在內存之中。

　?。?）當緩存溢出時，緩存的中間鍵值對根據用戶定義的Reducer的個數R，分成R個區(qū)，并寫入本地磁盤。分區(qū)一一對應于Reducer。Reducer會通過master獲得相對應的分區(qū)在本地磁盤上的位置信息。

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

　?。?）Reduce函數遍歷排序后的中間鍵值對。對于每個唯一的鍵，根據用戶重寫的Reduce，處理與之相關聯的value值。Reduce的輸出結果以鍵值對的形式寫入到該分區(qū)的輸出文件中。

　?。?）當所有的Map和Reduce任務都完成以后，master會喚醒用戶程序，用戶程序對MapReduce平臺的調用由此返回。

　　由此可見，MapReduce為用戶提供了一個極其簡單的分布式編程模型。用戶只需關心與任務相關的Map和Reduce即可，其他的對用戶而言都是透明的。

2 KNN算法描述

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

　　輸入數據：訓練數據集T={（x1，y1），（x2，y2），…，（xN，yN）}

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

　　輸出：實例x所屬的類y

　?。?）計算實例x與每個訓練實例的距離；

　?。?）令K是最近鄰數目，根據計算的距離度量，在訓練集中找出與x最近鄰的K個點的集合Nk（x）；

　?。?）在Nk（x）中根據分類決策規(guī)則（如多數表決）決定x的類別y：

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

　　其中，I為指示函數，即當yi=cj時I為1，否則I為0。

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

3 并行化KNN的分析與實現

　　3.1 并行化KNN分析

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

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

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

　　3.2 并行化KNN的實現

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

　　輸入：<key，value>

　　輸出：<key，String>

　　ClassMapper{

　　使用UseDistributedCache（），獲得測試數據集Tests；

　　創(chuàng)建KNNnode對象node，存儲訓練樣本與測試樣本的距離和訓練樣本的類別；

　　Map（key，value）{

　　訓練樣本向量化，得到向量化的測試樣本test；

　　遍歷本節(jié)點訓練樣本集Trains，得到測試樣本與每一個訓練樣本的距離distanc以及相應訓練樣例的類標示catalog，并賦值給node對象；

　　通過PriorityQueue得到與測試樣距離最近的K個node對象的隊列pq；

　　根據投票獲得測試樣本的類c；

　　輸出結果output.collct（test，c）；

　　}

　　}

4 實驗結果與分析

　　4.1 實驗環(huán)境

　　并行化KNN實驗是在Hadoop平臺下完成的。硬件設備為6臺X86架構的PC，主設備節(jié)點采用Intel志強四核處理器，內存為4 GB；從設備節(jié)點采用AMD四核處理器，主頻為2.7 GHz，內存為4 GB。

　　4.2 實驗數據集

　　實驗采用標準數據集CoverType，它通過地質變量來預測森林植被覆蓋類型，是54維的7分類數據集。共有58萬個樣本，選取其中的30萬個為訓練樣本，其余的28萬個為測試實例，數據集大小為70 MB。

　　4.3 結果分析

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

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

　　圖3顯示了三種算法在處理相同任務時所需要的時間。從圖中可以看到，在單臺和雙臺PC的情況下，并行化KNN方案一（采用分布式緩存機制）和方案二（采用內存機制）并沒有表現出其高效性，反而因為需要啟動JVM以及信息交互的原因，運行時間比傳統(tǒng)KNN算法的時間更長。當集群的節(jié)點數大于3臺時，隨著節(jié)點數量的增加，并行化KNN的運行時間開始大幅度地減少，體現出并行化的KNN算法的高效性。

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

　　通過實驗得出，基于分布式緩存機制的并行化KNN算法在運行效率和擴展性上均要優(yōu)于基于內存的并行化KNN。

5 結論

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

　　參考文獻

　　[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] 劉莉，郭艷艷，吳揚揚.一種基于基本信息單元的索引[J].計算機工程與科學，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)計學習方法[M].北京：清華大學出版社，2012.

　　[7] TOM W. Hadoop： the definitive guide（second editon）[M]. O′Reilly Media， Inc.， 2011.

　　[8] 閆永剛，馬廷淮，王建.KNN分類算法的MapReduce并行化實現[J].南京航空航天大學學報，2013，45（4）：550-555.