基于MapReduce編程模型的改進KNN分類算法研究

邱寧佳，郭暢，楊華民，王鵬，溫暖

（長春理工大學計算機科學技術學院，長春 130022）

基于MapReduce編程模型的改進KNN分類算法研究

邱寧佳，郭暢，楊華民，王鵬，溫暖

（長春理工大學計算機科學技術學院，長春 130022）

采用一種屬性約簡算法，將待分類的數據樣本進行兩次約簡處理--初次決策表屬性約簡和基于核屬性值的二次約簡。通過屬性約簡方法來刪除數據集中的冗余數據，進而提高KNN算法的分類精度。在此基礎上應用MapReduce并行編程模型，在Hadoop集群環境上實現并行化分類計算實驗。實驗結果表明，改進后的算法在集群環境下執行的效率得到很大提升，能夠高效處理實驗數據。實驗執行的加速比也有明顯提高。

KNN；屬性約簡；MapReduce編程模型；Hadoop

隨著信息技術以及“互聯網+”的快速發展，數據在大容量、多樣性和高增速方面爆炸式增長，給數據的處理和分析帶來了巨大挑戰［1］。數據的分類處理就變得尤為重要，在經典分類算法中KNN分類算法操作比較簡單，在諸多領域都有很廣泛的應用。不過KNN作為一種惰性算法在處理大容量數據集時，由于數據的屬性較多，會影響KNN算法的分類效率和分類精度，因此對KNN分類算法進行改進是很有必要的。

國內外的學者們對KNN算法已經有了一些研究，閆永剛等人提出了將KNN分類算法通過MapReduce編程模型實現并行化［2］；Papadimitriou等人提出了一重新的聚類分析算法DisCo［3］，且這種新算法應用在分布式平臺上進行并行化實驗研究；鮑新中等人應用了粗糙集權重確定方法來解決粗糙集信息上的權重確定問題［4］；汪凌等人應用了一種基于相對可辨識矩陣的決策表屬性約簡算法［5］來解決KNN算法中的數據冗余問題；張著英等人在研究KNN分類算法時將粗糙集理論應用到KNN算法中從而實現屬性約簡［6］；樊存佳等人提出了一種基于文本分類的新型改進KNN分類算法［7］，同時采用聚類算法裁剪對KNN分類貢獻小的訓練樣本，從而減少數據冗余；Zhu等人提出了一種基于哈希表的高效分類算法H-c2KNN［8］，應用在高維數據下的KNN分類算法中；Wang等人提出了一種基于內核改進的屬性約簡KNN分類算法［9］；吳強提出了一種基于概念格的屬性約簡方法［10］，將粗糙集理論的可辨識矩陣方法應用于概念格的約簡，從而提高效率簡化；魯偉明等人提出了一種基于近鄰傳播的改進聚類算法-DisAP［11］，并將其應用在MapReduce編程框架中；王煜將KNN文本分類算法進行了基于決策樹算法的改進并進行并行化研究［12］；梁鮮等人提出了一種全局K-均值算法［13］，解決了全局K-均值算法時間復雜度大的問題；王鵬等人提出了在MapReduce模型基礎上的K-均值聚類算法的實現問題［14］。本文在上述研究的基礎上，對實驗數據進行基于決策表和核屬性值的兩次屬性約簡改造并結合MapReduce編程框架進行KNN分類算法的并行化實現。

1 相關知識

1.1 KNN分類算法的基本原理

K最近鄰（K Nearest Neighbors，KNN）算法是一種基于實例的學習方法。其基本原理如下：通過將給定的檢驗樣本與和它相似的訓練樣本進行比較來分析結果，此為學習。訓練樣本通常用屬性來描述，一個訓練樣本包含多個屬性，每個屬性則代表n維空間的一個點。當輸入新的訓練樣本時，KNN算法即開始進行遍歷搜索，得到與新樣本最近鄰的k個訓練樣本，其示例如圖1所示。

圖1 KNN分類示例

可以看出，給定的訓練樣本共有三種：正方形、圓形和五邊形。每給定一個新的檢驗樣本，就需要計算與其最近的K個訓練樣本，計算的方法通常采用歐式距離計算，再由計算出的K個訓練樣本的分類情況來確定新樣本的分類情況。由上圖中心圓所選出的即為離待分類樣本最近的六個訓練樣本，這六個樣本中有四個為五邊形，按照分類號進行“投票”，則可以將該訓練樣本分類為五邊形。

1.2 MapReduce框架

MapReduce是一種面向大數據并行處理的計算模式，它是基于集群的高性能并行計算平臺，也是并行計算與運行軟件的框架，同時也是一個并行程序設計的模型。MapReduce框架程序主要由Map函數和Reduce函數組成，首先由Map函數負責對數據進行分布計算，即將輸入的數據集切分為若干獨立的數據塊，各個Mapper節點在工作時不能夠實時的交互，框架會將Map輸出的數據塊進行排序；然后將輸入結果發送給Reduce函數，Reduce函數負責對中間結果進行處理，以得到最終結果并進行結果輸出，圖2為MapReduce程序執行示意圖。

圖2 MapReduce程序執行示意圖

1.3 屬性約簡方法

屬性約簡即通過刪除不相關屬性或者降低屬性維度從而減少數據冗余，提高數據處理的效率，節約數據計算成本。屬性約簡是計算最小屬性子集的過程，在此過程中還要保證其數據的分布概率基本保持不變或有較少改動。常見的屬性約簡方法有逐步向前選擇法、合并屬性法、決策樹歸納和主成分分析等方法。主成分分析是一種用于連續屬性的數據降維方法，構造了原始數據的一個正交變換，新空間的基底去除了原始空間基底下數據的相關性，這樣較少的新變量能夠刻畫出原始數據的絕大部分變異情況。在應用中，通常是選出比原始變量個數少，能解釋大部分數據中的幾個新變量，即主成分來代替原始變量進行建模。

其計算步驟如下：

設原始變量X1，X2，…，XP的n次觀測數據矩陣為：

對觀測的數據矩陣進行中心標準化，并將標準化后的數據矩陣仍然記為X。

求相關系數矩陣R，R=(rij)p×p，rij的定義為：

求R的特征方程det（R-λE）=0的特征根λ1≥λ2≥λp＞0；

計算m個相應的單位特征向量：

計算主成分：

Zi=β1iX1+β2iX2+…+βpiXp,i=1,2,…,m

再使用主成分分析降維的方法，可以得到特征方程的特征根，對應的特征向量以及各個成分各自的方差百分比（即貢獻率），貢獻率百分比越大，向量權重越大。通過此種方法可以在完成屬性歸約的同時保存與原始數據相配的數據信息。

2 改進KNN算法

2.1 基于屬性約簡的KNN分類算法

改進后的KNN分類算法即在進行KNN分類算法的基礎上利用屬性約簡的相關知識，將算法進行先基于決策表再基于核屬性值的兩次屬性約簡，將冗余的數據進行約簡，在不影響結果的情況下，提高分類的效率，下面給出改進后算法的形式化描述：

輸出：樣本數據的類別。

算法步驟：

（1）對輸入的訓練數據進行初次屬性約簡，并計算出核屬性值；

（2）根據樣本屬性進行基于核屬性的二次屬性約簡，通過信息熵理論，計算核屬性的重要度w(p)，若w(p)=0，則認為該屬性為冗余屬性，從核屬性中移除該屬性，得到二次約簡屬性集［4］；

（3）利用分布式處理平臺對樣本數據進行分塊處理，對每一塊樣本數據分別計算其與訓練數據屬性之間的距離d(X,Xi)，此處的距離采用歐式距離進行計算；

（4）對計算出的距離d(X,Xi)進行從小到大的排序，選取排在前K個訓練數據；

（5）統計前K個訓練數據的類別，將個數最多的類別預測為當前樣本的類別，進行結果分析。

2.2 改進后的KNN算法的MapReduce并行化

將改進后的KNN算法進行MapReduce并行化，主要分為三個階段來實現。

（1）下載文件系統中的訓練數據集和測試數據集到本地存儲節點。

（2）Map函數將測試樣本數據分塊，計算出測試數據到訓練數據的歐式距離，進行排序。

（3）將排序結果傳送給Reduce函數，Reduce函數將執行KNN分類算法進行規約操作并計算出分類結果。因為Map階段的關鍵為對應待分類樣本在文件中的偏移值，其在Map階段完成時會被MapReduce框架自動排序，所以Reduce階段輸出的分類號就對應了待分類樣本在原文件中的順序。本文中的Map函數和Reduce函數的算法步驟如下所示：

表1 Map函數的算法步驟

表2 Reduce函數的算法步驟

經過上述改進后，得出了一個基于屬性約簡的改進KNN算法，并對其進行MapReduce編程模型的搭建。

3 實驗分析

3.1 實驗環境及數據

實驗運行所需的云平臺由實驗室4臺電腦組成，每臺電腦裝有3臺虛擬機，共12個節點。Hadoop分布式云計算集群采用Centos6.0操作系統、hadoop-1.1.2版本的Hadoop。其中一個作為Master節點，其余作為Slave節點。本次實驗采用7個數據節點來進行實驗。

實驗數據采用標準數據集CoverType DataS-et，該數據具有54個屬性變量，58萬個樣本，7個類別。本文將數據分為測試數據（data1）和訓練數據（data2）兩部分，其中測試數據共20萬個樣本，大小約為500MB，訓練數據共38萬個樣本，大小約為1000MB。

3.2 實驗過程及分析

本實驗的主要內容分為兩部分：

（1）分析KNN算法在數據規模相同而在數據節點數目不同的情況下，數據執行時間的對比情況。首先對給定的訓練樣本進行初次屬性約簡和二次基于核屬性值的約簡，以達到刪除冗余數據的效果，然后在Hadoop分布式平臺上進行基于MapReduce的并行化實驗，依次導入訓練樣本和測試樣本，實驗數據節點數目依次從1個添加到7個，通過增加節點數目來對實驗執行時間進行比較，得出相應結論；

（2）研究數據在執行分類算法的過程中，不同數據節點數目所對應的加速比情況。此部分實驗是由實驗（1）的實驗結果分析而得出的，不用數據節點數目條件下對應的實驗結果加速比理論上應該是不同的，所以通過實驗來做真實的數據分析，得出具體的變化曲線。

實驗結果分別如圖3、4所示：

圖3 數據集的時間對比圖

圖3可以看出，兩組數據集分別為改進前和改進后的測試數據和訓練數據，由實驗可以驗證每組數據在進行屬性約簡改進后都其運行的時間都比沒有改進前有明顯減少，訓練數據約簡后執行時間平均縮短了2.28min，測試數據的執行時間平均縮減了1.71min，且數據量大的訓練數據時間減少的更為明顯，通過對數據進行屬性約簡后其運行的效率明顯提高，改進的KNN算法在分布式平臺上能夠高效運行，對于單個數據集而言隨著節點數增加數據在平臺上運行的時間相應減少，訓練數據在7個數據節點條件下執行的時間是單機條件的58.3%，測試數據僅僅為40%。測試結果說明改進后的KNN算法能滿足實際并行分布式環境下大數據處理的需求。由此可以看出將算法改造后，能夠很好的提高處理數據效率，進而降低對大數據的分類工作復雜度。

圖4 加速比對比圖

圖4看出，兩組數據的實驗運行加速比曲線都是成正相關的，即隨著數據節點個數的增加實驗運行加速比有明顯提高，可以看出分布式平臺在處理KNN分類算法上有很好的計算能力，可以看出，當數據量不夠大時，使用分布式平臺執行任務沒有單機環境下執行效率高，當數據規模足夠大時，并且每一個數據分片都在進行處理工作時，集群的效率最高，訓練數據和測試數據這兩組數據的加速比分別提高了140%和100%。實驗通過對兩組數據的運行加速比進行研究分析，表明分布式計算在集群環境下運行效率最高。

4 結論

本文在研究過程中主要實現了如下內容：對KNN分類算法的研究與分析，提出了基于決策表和核屬性值的兩次屬性約簡的改造，對改造后的KNN算法進行MapReduce并行化研究實驗。通過研究過程及實驗分析得出了如下結論：

（1）實驗通過對數據進行兩次屬性約簡，大大減少了數據冗余，提高了實驗的運行效率；

（2）對改造后的算法使用MapReduce編程模型進行實驗設計，并在Hadoop平臺上進行并行化實驗分析；

（3）實驗表明在大數據環境下，屬性約簡后的數據在集群環境下執行算法提高了KNN算法的加速比和可擴展性，算法效率也隨著集群規模的擴大而變高。

實驗證實了通過對現有經典KNN算法的改進可以大大提高其執行效率，減少工作量，在下一步的研究過程中還將對數據量進行擴大，研究對比數據量變大時算法的執行效率是否會有所影響，以及再次改良后算法的執行情況。

［1］王元卓，靳小龍，程學旗.網絡大數據：現狀與展望［J］.計算機學報，2013，36（6）：1125-1138.

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

［3］Papadimitriou S，Sun J.DisCo：Distributed Co-clustering with Map-Reduce［C］.Data Mining，IEEE International Conference on.IEEE，2015：512-521.

［4］鮑新中，張建斌，劉澄.基于粗糙集條件信息熵的權重確定方法［J］.中國管理科學，2009，17（3）：131-135.

［5］汪凌，吳潔，黃丹.基于相對可辨識矩陣的決策表屬性約簡算法［J］.計算機工程與設計，2010，31（11）：2536-2538.

［6］張著英，黃玉龍，王翰虎.一個高效的KNN分類算法［J］.計算機科學，2008，35（3）：170-172.

［7］樊存佳，汪友生，邊航.一種改進的KNN文本分類算法［J］.國外電子測量技術，2015（12）：39-43.

［8］Zhu P，Zhan X，Qiu W.Efficient k-Nearest neighborssearchinhighdimensionsusingMapReduce［C］.Fifth International Conference on Big Data and Cloud Computing.IEEE，2015：23-30.

［9］Xueli W，Zhiyong J，Dahai Y.An improved KNN algorithm based on kernel methods and attribute reduction［C］.Fifth International Conference on Instrumentation and Measurement，Computer，Communication and Control.IEEE，2015.

［10］吳強.采用粗糙集中可辨識矩陣方法的概念格屬性約簡［J］.計算機工程，2004，30（20）：141-142.

［11］魯偉明，杜晨陽，魏寶剛，等.基于MapReduce的分布式近鄰傳播聚類算法［J］.計算機研究與發展，2012，49（8）：1762-1772.

［12］王煜.基于決策樹和K最近鄰算法的文本分類研究［D］.天津：天津大學，2006.

［13］梁鮮，曲福恒，楊勇，等.一種高效的全局K-均值算法［J］.長春理工大學學報：自然科學版，2015，38（3）：112-115.

［14］王鵬，王睿婕.K-均值聚類算法的MapReduce模型實現［J］.長春理工大學學報：自然科學版，2015，38（3）：120-123. wirless channels［C］.Rhodes：Vrhicular Technology Conference，2001：680-692.

The Research of Modified KNN Classification Algorithm Based on MapReduce Model

QIU Ningjia，GUO Chang，YANG Huamin，WANG Peng，WEN Nuan
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

An attribute reduction algorithm is proposed.The algorithm will be classified data samples for the two reduction processing--attribute reduction of the initial decision table and second reduction based on kernel attribute value. The method of attribute reduction is to delete the redundant data，and then to improve the classification accuracy of KNN algorithm.On the basis of the application of the MapReduce parallel programming model，the parallel computing experiments are implemented in the Hadoop cluster environment.The experimental results show that the efficiency of the improved algorithm in the cluster environment has been greatly improved，which can effectively deal with the experimental data.Experimental implementation of the speedup is also significantly improved.

KNN；attribute reduction；MapReduce programming model；hadoop

TP391

A

1672-9870（2017）01-0110-05

2016-08-01

吉林省科技發展計劃重點科技攻關項目（20150204036GX）

邱寧佳（1984-），男，博士后，講師，E-mail：269212811@qq.com