基于MapReduce編程模型的改進(jìn)KNN分類算法研究

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

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

基于MapReduce編程模型的改進(jìn)KNN分類算法研究

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

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

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

KNN；屬性約簡(jiǎn)；MapReduce編程模型；Hadoop

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

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

1 相關(guān)知識(shí)

1.1 KNN分類算法的基本原理

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

圖1 KNN分類示例

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

1.2 MapReduce框架

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

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

1.3 屬性約簡(jiǎn)方法

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

其計(jì)算步驟如下：

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

對(duì)觀測(cè)的數(shù)據(jù)矩陣進(jìn)行中心標(biāo)準(zhǔn)化，并將標(biāo)準(zhǔn)化后的數(shù)據(jù)矩陣仍然記為X。

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

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

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

計(jì)算主成分：

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

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

2 改進(jìn)KNN算法

2.1 基于屬性約簡(jiǎn)的KNN分類算法

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

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

算法步驟：

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

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

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

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

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

2.2 改進(jìn)后的KNN算法的MapReduce并行化

將改進(jìn)后的KNN算法進(jìn)行MapReduce并行化，主要分為三個(gè)階段來(lái)實(shí)現(xiàn)。

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

3.2 實(shí)驗(yàn)過(guò)程及分析

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

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

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

實(shí)驗(yàn)結(jié)果分別如圖3、4所示：

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

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

圖4 加速比對(duì)比圖

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

4 結(jié)論

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

（1）實(shí)驗(yàn)通過(guò)對(duì)數(shù)據(jù)進(jìn)行兩次屬性約簡(jiǎn)，大大減少了數(shù)據(jù)冗余，提高了實(shí)驗(yàn)的運(yùn)行效率；

（2）對(duì)改造后的算法使用MapReduce編程模型進(jìn)行實(shí)驗(yàn)設(shè)計(jì)，并在Hadoop平臺(tái)上進(jìn)行并行化實(shí)驗(yàn)分析；

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

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

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

［2］閆永剛，馬廷淮，王建.KNN分類算法的MapReduce并行化實(shí)現(xiàn)［J］.南京航空航天大學(xué)學(xué)報(bào)，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］.中國(guó)管理科學(xué)，2009，17（3）：131-135.

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

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

［7］樊存佳，汪友生，邊航.一種改進(jìn)的KNN文本分類算法［J］.國(guó)外電子測(cè)量技術(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］吳強(qiáng).采用粗糙集中可辨識(shí)矩陣方法的概念格屬性約簡(jiǎn)［J］.計(jì)算機(jī)工程，2004，30（20）：141-142.

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

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

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

［14］王鵬，王睿婕.K-均值聚類算法的MapReduce模型實(shí)現(xiàn)［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(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ā)展計(jì)劃重點(diǎn)科技攻關(guān)項(xiàng)目（20150204036GX）

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