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

（長春理工大學(xué)計算機科學(xué)技術(shù)學(xué)院，長春 130022）

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

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

（長春理工大學(xué)計算機科學(xué)技術(shù)學(xué)院，長春 130022）

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

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

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

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

1 相關(guān)知識

1.1 KNN分類算法的基本原理

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

圖1 KNN分類示例

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

1.2 MapReduce框架

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

圖2 MapReduce程序執(zhí)行示意圖

1.3 屬性約簡方法

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

其計算步驟如下：

設(shè)原始變量X1，X2，…，XP的n次觀測數(shù)據(jù)矩陣為：

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

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

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

計算m個相應(yīng)的單位特征向量：

計算主成分：

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

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

2 改進KNN算法

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

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

輸出：樣本數(shù)據(jù)的類別。

算法步驟：

（1）對輸入的訓(xùn)練數(shù)據(jù)進行初次屬性約簡，并計算出核屬性值；

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

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

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

（5）統(tǒng)計前K個訓(xùn)練數(shù)據(jù)的類別，將個數(shù)最多的類別預(yù)測為當前樣本的類別，進行結(jié)果分析。

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

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

（1）下載文件系統(tǒng)中的訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集到本地存儲節(jié)點。

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

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

表1 Map函數(shù)的算法步驟

表2 Reduce函數(shù)的算法步驟

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

3 實驗分析

3.1 實驗環(huán)境及數(shù)據(jù)

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

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

3.2 實驗過程及分析

本實驗的主要內(nèi)容分為兩部分：

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

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

實驗結(jié)果分別如圖3、4所示：

圖3 數(shù)據(jù)集的時間對比圖

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

圖4 加速比對比圖

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

4 結(jié)論

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

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

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

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

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

［1］王元卓，靳小龍，程學(xué)旗.網(wǎng)絡(luò)大數(shù)據(jù)：現(xiàn)狀與展望［J］.計算機學(xué)報，2013，36（6）：1125-1138.

［2］閆永剛，馬廷淮，王建.KNN分類算法的MapReduce并行化實現(xiàn)［J］.南京航空航天大學(xué)學(xué)報，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］鮑新中，張建斌，劉澄.基于粗糙集條件信息熵的權(quán)重確定方法［J］.中國管理科學(xué)，2009，17（3）：131-135.

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

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

［7］樊存佳，汪友生，邊航.一種改進的KNN文本分類算法［J］.國外電子測量技術(shù)，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］.計算機研究與發(fā)展，2012，49（8）：1762-1772.

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

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

［14］王鵬，王睿婕.K-均值聚類算法的MapReduce模型實現(xiàn)［J］.長春理工大學(xué)學(xué)報：自然科學(xué)版，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

吉林省科技發(fā)展計劃重點科技攻關(guān)項目（20150204036GX）

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