2種加速K-近鄰方法的實(shí)驗(yàn)比較

翟俊海, 王婷婷, 張明陽(yáng), 王耀達(dá), 劉明明

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定 071002)

?

2種加速K-近鄰方法的實(shí)驗(yàn)比較

翟俊海, 王婷婷, 張明陽(yáng), 王耀達(dá), 劉明明

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定 071002)

K-近鄰(K-NN:K-nearest neighbors)是著名的數(shù)據(jù)挖掘算法，應(yīng)用非常廣泛.K-NN思想簡(jiǎn)單，易于實(shí)現(xiàn)，其計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度都是O(n)，n為訓(xùn)練集中包含的樣例數(shù).當(dāng)訓(xùn)練集比較大時(shí)，特別是面對(duì)大數(shù)據(jù)集時(shí)，K-NN算法的效率會(huì)變得非常低，甚至不可行.本文用實(shí)驗(yàn)的方法比較了2種加速K-NN的方法，2種加速方法分別是壓縮近鄰(CNN:condensed nearest neighbor)方法和基于MapReduce的K-NN.具體地，在Hadoop環(huán)境下，用MapReduce編程實(shí)現(xiàn)了K-NN算法，并與CNN算法在8個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)比較，得出了一些有價(jià)值的結(jié)論，對(duì)從事相關(guān)研究的人員具有一定的借鑒作用.

K-近鄰；數(shù)據(jù)挖掘；MapReduce；Hadoop

K-近鄰(K-NN:K-nearest neighbors)算法[1]是一種著名的數(shù)據(jù)挖掘算法，已成功應(yīng)用于模式識(shí)別[2]、文本分類(lèi)[3-4]、故障診斷[5]等.K-NN通過(guò)計(jì)算待分類(lèi)樣例與訓(xùn)練集中每一個(gè)樣例之間的距離，找到距離它最近的K個(gè)樣例，樣例最多的類(lèi)別，即為待分類(lèi)樣例的類(lèi)別.顯然，K-NN算法的計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度都是O(n)，n為訓(xùn)練集中包含的樣例數(shù).當(dāng)訓(xùn)練集比較大時(shí)，特別是面對(duì)大數(shù)據(jù)集時(shí)，K-NN算法需要大量的內(nèi)存和處理時(shí)間，其效率會(huì)變得非常低，甚至不可行.針對(duì)這一問(wèn)題，研究人員提出了許多改進(jìn)K-NN算法性能的方法，這些方法大致可分為加速近鄰搜索和降低訓(xùn)練集大小(或樣例選擇、樣例約簡(jiǎn))兩類(lèi)[6].

在加速近鄰搜索的方法中，最具代表性的方法是用近似最近鄰方法代替精確最近鄰，簡(jiǎn)稱(chēng)近似最近鄰方法[7-8].顧名思義，近似最近鄰方法是在整個(gè)訓(xùn)練集的一個(gè)子集中搜索目標(biāo)樣例的近似近鄰.在這類(lèi)方法中，有基于層次數(shù)據(jù)結(jié)構(gòu)的方法和基于哈希技術(shù)的方法.一般地，基于層次數(shù)據(jù)結(jié)構(gòu)的方法利用樹(shù)型結(jié)構(gòu)(如KD-樹(shù)[9]、VP-樹(shù)[10]等)改進(jìn)近鄰搜索的效率.基于哈希技術(shù)的方法[11-13]利用哈希變換將樣例空間映射到海明空間，并在海明空間中搜索目標(biāo)樣例的近似近鄰.因?yàn)樵诤Ｃ骺臻g中，每一個(gè)樣例都用0-1串表示，距離計(jì)算變成了簡(jiǎn)單的異或運(yùn)算，這樣可以加速近鄰搜索的速度.代表性的工作包括：Hou等[14]提出的基于樹(shù)的緊哈希近似近鄰搜索方法;Slaney和Casey[15]提出的局部敏感性哈希近似近鄰搜索方法;Pauleve等[16]對(duì)局部敏感哈希技術(shù)中的哈希函數(shù)的類(lèi)型和查詢(xún)機(jī)制進(jìn)行了全面的綜述.

降低訓(xùn)練集大小的方法，也稱(chēng)為樣例選擇或樣例約簡(jiǎn)的方法.壓縮近鄰算法(CNN：condensed nearest neighbor)[17]是歷史上第1個(gè)降低訓(xùn)練集大小的方法，CNN算法的核心概念是一致樣例子集.給定訓(xùn)練集D，其樣例子集S是一致子集，如果S能正確分類(lèi)D中所有的樣例.包含樣例數(shù)最少的一致子集稱(chēng)為最小一致子集.CNN算法試圖尋找訓(xùn)練集的最小一致子集，以降低訓(xùn)練集的大小.但是，用CNN算法選擇的樣例子集未必是最小一致子集.另外，CNN算法對(duì)噪聲非常敏感，其輸出也與樣例選擇的順序有關(guān).在CNN算法的基礎(chǔ)上，人們提出了許多改進(jìn)的算法.例如，Gates[18]提出了約簡(jiǎn)近鄰算法，Wilson[19]提出的編輯近鄰算法，Brighton等[20]提出的迭代過(guò)濾算法等.文獻(xiàn)[21]對(duì)樣例選擇算法進(jìn)行了全面的綜述，很有參考價(jià)值.

近幾年，由于MapReduce[22]的出現(xiàn)，出現(xiàn)了另一種加速K-NN算法的方法,即將K-NN算法用編程模型MapReduce實(shí)現(xiàn)，以加速對(duì)待分類(lèi)樣例K-近鄰計(jì)算的速度.本文在Hadoop平臺(tái)上，用MapReduce編程實(shí)現(xiàn)了K-NN算法(為描述方便，記為MR-K-NN)，并用實(shí)驗(yàn)的方法，在8個(gè)數(shù)據(jù)集實(shí)驗(yàn)比較了K-NN和MR-K-NN，得出了一些有價(jià)值的結(jié)論，這些結(jié)論對(duì)從事相關(guān)研究的人員具有一定的參考價(jià)值.

1 基礎(chǔ)知識(shí)

本節(jié)介紹將要用到的基礎(chǔ)知識(shí)，包括K-NN算法和MapReduce編程模型.

1.1 CNN算法

CNN是1967年Hart針對(duì)1-近鄰(K=1)提出的樣例選擇算法.設(shè)T是訓(xùn)練集，T′是選擇樣例的集合.初始時(shí)，從訓(xùn)練集T中隨機(jī)選擇1個(gè)樣例，加入到T′中.然后，遞歸地從訓(xùn)練集中選擇樣例.每次都是隨機(jī)地從T中選擇1個(gè)樣例，如果該樣例被T′中的樣例用1-近鄰(K=1)錯(cuò)誤分類(lèi)，則將其加入到T′中.否則，丟棄該樣例,直到下列條件之一滿足，算法終止.1)訓(xùn)練集為空；2)訓(xùn)練集中的樣例都能被T′中的樣例正確分類(lèi).CNN算法的偽代碼如算法1所示.

算法1:CNN算法1) 輸入:訓(xùn)練集T={(xi,yi)|xi∈Rd,yi∈Y,1≤i≤n}2) 輸出:T'?T3) 初始化T'=?;4) 從T中隨機(jī)地選擇一個(gè)樣例移動(dòng)到T'中;5) repeat6)for(eachxi∈T)do7)for(eachxj∈T')do8)計(jì)算xi到xj之間的距離;9)//尋找xi的1-NN10)尋找xi在T'中的最近鄰x*j;11)end12)if(xi的類(lèi)別和x*j的類(lèi)別不同)then13)//xi不能被T'用1-NN正確分類(lèi)14)T'=T'∪{xi};15)T=T-{xi};16)end17)end18) until(T=?或T中的所有樣例都能被T'用1-NN正確分類(lèi));19) 輸出T'

如果K>1，CNN算法只需初始化時(shí)，從訓(xùn)練集T中隨機(jī)選擇K個(gè)樣例加入T′中,其他步驟不變.

說(shuō)明：CNN算法的核心概念是一致子集.訓(xùn)練集T的子集T′稱(chēng)為一致子集，如果T′能夠正確分類(lèi)T中的所有樣例.訓(xùn)練集T的所有一致子集中，包含樣例數(shù)最少的一致子集，稱(chēng)為T(mén)的最小一致子集.實(shí)際上，CNN算法試圖尋找訓(xùn)練集T的最小一致子集，但該算法最終得到的子集T′未必是最小一致子集.

1.2 MapReduce編程模型

MapRecuce是針對(duì)大數(shù)據(jù)處理的一種并行編程框架，其基本思想包括以下3個(gè)方面：

1)MapRecuce采用分治策略自動(dòng)地將大數(shù)據(jù)集劃分為若干子集，并將這些子集部署到不同的云計(jì)算節(jié)點(diǎn)上，并行地對(duì)數(shù)據(jù)子集進(jìn)行處理.

2)基于函數(shù)編程語(yǔ)言LISP的思想，MapRecuce提供了2個(gè)簡(jiǎn)單易行的并行編程方法,即Map和Reduce，用它們?nèi)?shí)現(xiàn)基本的并行計(jì)算.

3)許多系統(tǒng)級(jí)的處理細(xì)節(jié)MapRecuce能自動(dòng)完成，這些細(xì)節(jié)包括：①計(jì)算任務(wù)的自動(dòng)劃分和自動(dòng)部署；②自動(dòng)分布式存儲(chǔ)處理的數(shù)據(jù)；③處理數(shù)據(jù)和計(jì)算任務(wù)的同步；④對(duì)中間處理結(jié)果數(shù)據(jù)的自動(dòng)聚集和重新劃分；⑤云計(jì)算節(jié)點(diǎn)之間的通訊；⑥云計(jì)算節(jié)點(diǎn)之間的負(fù)載均衡和性能優(yōu)化；⑦云計(jì)算節(jié)點(diǎn)的失效檢查和恢復(fù).

MapRecuce處理數(shù)據(jù)的流程如圖1所示.

圖1 MapRecuce處理數(shù)據(jù)的流程Fig.1 Diagram of data processing by MapRecuce

2 基于MapReduce的K-NN算法

在Hadoop環(huán)境下，本文編程實(shí)現(xiàn)了基于MapReduce的K-NN算法.用MapReduce實(shí)現(xiàn)K-NN的關(guān)鍵是Map和Reduce這2個(gè)函數(shù)的設(shè)計(jì)，這2個(gè)函數(shù)的設(shè)計(jì)如算法2和算法3所示.

算法2:Map函數(shù)1) 輸入:,2) 輸出:.3) //利用setup函數(shù)進(jìn)行資源的初始化,將訓(xùn)練樣本添加到容器trainset中4) traninSet.add(trainInstance);5) //遍歷所有測(cè)試樣本xi,計(jì)算其與所有訓(xùn)練樣本之間的歐式距離6) for(i=1;i≤n;i=i+1)do7)for(j=0;j

算法3:Reduce函數(shù)1) 輸入:,2) 輸出:.3) //遍歷所有測(cè)試樣本4) for(i=1;i≤n;i=i+1)do5)//對(duì)于測(cè)試樣本xi,將與其前k個(gè)歐式距離最近的訓(xùn)練樣本的類(lèi)標(biāo)簽添加到容器中6)ArrayList.add(Knear-trainLabel);7)//應(yīng)用傳統(tǒng)K-NN算法對(duì)測(cè)試樣本xi進(jìn)行分類(lèi)8)predictLabel=MostFrequent(ArrayList);9)//將測(cè)試樣本與相應(yīng)的predictLabel進(jìn)行輸出10)context.write(testsample,predictLabel);11)end12) 輸出

3 CNN與基于MapReduce的K-NN的實(shí)驗(yàn)比較

在保持分類(lèi)能力的前提下，對(duì)2種加速K-NN的方法在8個(gè)數(shù)據(jù)集上，對(duì)運(yùn)行時(shí)間進(jìn)行實(shí)驗(yàn)比較，8個(gè)數(shù)據(jù)集包括2個(gè)人工數(shù)據(jù)集和6個(gè)UCI數(shù)據(jù)集.第1個(gè)人工數(shù)據(jù)集GAUSS1是一個(gè)3維4類(lèi)的數(shù)據(jù)集，每類(lèi)包含25 000個(gè)數(shù)據(jù)點(diǎn)，共100 000個(gè)數(shù)據(jù)點(diǎn).每類(lèi)服從的高斯分布為p(x|ωi)～N(μi∑i),i=1,2,3,4.其中，參數(shù)如表1所示.第2個(gè)人工數(shù)據(jù)集GAUSS2是一個(gè)2維3類(lèi)的數(shù)據(jù)集，每類(lèi)100 000個(gè)數(shù)據(jù)點(diǎn)，共300 000個(gè)數(shù)據(jù)點(diǎn).每類(lèi)服從的概率分布為

實(shí)驗(yàn)所用數(shù)據(jù)集的基本信息列于表2中，實(shí)驗(yàn)所用的云平臺(tái)環(huán)境列于表3中，實(shí)驗(yàn)結(jié)果列于表4中.

表1 高斯分布的均值向量和協(xié)方差矩陣

表2 實(shí)驗(yàn)所用數(shù)據(jù)集的基本信息

表4中，符號(hào)“—”表示運(yùn)行未能得到結(jié)果.從列于表4的實(shí)驗(yàn)結(jié)果可以看出，在大數(shù)據(jù)集上，基于MapReduce的K-NN加速效果優(yōu)于CNN算法，但是在一些中小型數(shù)據(jù)集上，如Statlog和Skin Segmentation，CNN的加速效果優(yōu)于基于MapReduce的K-NN.原因有2點(diǎn)：

1)當(dāng)數(shù)據(jù)集的大小小于1個(gè)block塊(默認(rèn)為64 MB)時(shí)，由于單機(jī)的內(nèi)存可以加載測(cè)試數(shù)據(jù)，此外，CNN算法對(duì)訓(xùn)練樣本的大量壓縮提高了運(yùn)行速度.

2)MapReduce運(yùn)行過(guò)程中是要對(duì)數(shù)據(jù)文件進(jìn)行分片，一個(gè)分片一個(gè)map任務(wù)，而每一個(gè)任務(wù)從建立、處理、提交到寫(xiě)到本地以及節(jié)點(diǎn)間的通信都是需要時(shí)間的，也需要耗費(fèi)一定的資源，而且在單機(jī)下map任務(wù)只能順序執(zhí)行，所以map任務(wù)越多，時(shí)間運(yùn)行越長(zhǎng)，map任務(wù)除計(jì)算部分所要耗費(fèi)的時(shí)間掩蓋了MapReduce并行計(jì)算的優(yōu)勢(shì)，這也是為什么很多文獻(xiàn)都提到MapReduce框架不適用于中小數(shù)據(jù)文件的原因.

隨著數(shù)據(jù)集的增大，單機(jī)環(huán)境下加載困難，此時(shí)MapReduce將會(huì)發(fā)揮集群的優(yōu)勢(shì)，可以通過(guò)MapReduce輕易地得出K-NN算法的結(jié)果，對(duì)數(shù)據(jù)集GAUSS1，MR-K-NN算法的運(yùn)行速度是CNN的5.9倍，對(duì)數(shù)據(jù)集GAUSS2，MR-K-NN算法的運(yùn)行速度是CNN的96.3倍，對(duì)于其他的幾個(gè)數(shù)據(jù)集，由于CNN算法在12 h內(nèi)都沒(méi)得出結(jié)果，表4中用符號(hào)“—”表示.而基于MapReduce的K-NN都能得出結(jié)果，這對(duì)于從事相關(guān)研究的人員具有一定的借鑒價(jià)值.

4 結(jié)論

本文用實(shí)驗(yàn)的方法對(duì)2種加速K-NN的方法進(jìn)行了比較，得出了一些有意義的結(jié)論：1)CNN算法有壓縮的優(yōu)勢(shì)，MapReduce框架有并行的優(yōu)勢(shì)，人們期望的是MapReduce框架下的K-NN運(yùn)行效率更高，但是對(duì)于中小型的數(shù)據(jù)集，結(jié)果恰好相反.2)1個(gè)MapReduce任務(wù)的運(yùn)行往往需要經(jīng)歷很多步驟，比如split數(shù)據(jù)片的劃分、mapper任務(wù)的分配、reducer任務(wù)的分配、各種運(yùn)行資源的分配、數(shù)據(jù)在網(wǎng)絡(luò)中傳輸時(shí)間的消耗等，此時(shí)的MapReduce就不如單機(jī)版程序的運(yùn)行.3)隨著數(shù)據(jù)集的增大或計(jì)算復(fù)雜性的提高，MapReduce的并行處理機(jī)制所帶來(lái)的優(yōu)勢(shì)將超過(guò)CNN，而且這一優(yōu)勢(shì)相當(dāng)明顯.

[1] COVER T,HART P.Nearest neighbor pattern classification [J].IEEE Transactions on Information Theory,1967,13(1):21-27.DOI:10.1109/TIT.1967.1053964.

[2] SAVCHENKO A V.Maximum-likelihood approximate nearest neighbor method in real-time image recognition [J].Pattern Recognition,2017,61:459-469.DOI:10.1016/j.patcog.2016.08.015.

[3] 霍亮,楊柳,張俊芝.貝葉斯與k-近鄰相結(jié)合的文本分類(lèi)方法[J].河北大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,32(3):316-319.DOI:1000-1565(2012)03-0316-04.

HUO L,YANG L,ZHANG J Z.On Bayesian combined withk-NN text classification method [J].Journal of Hebei University(Natural Science Edition),2012,32(3):316-319.DOI:1000-1565(2012)03-0316-04.

[4] 湛燕,陳昊,袁方,等.文本挖掘研究進(jìn)展[J].河北大學(xué)學(xué)報(bào)(自然科學(xué)版),2003,23(2):221-226.DOI:1000 -1565(2003)02 -0221 -06.

ZHAN Y,CHEN H,YUANG F,et al.The advance of research in text mining [J].Journal of Hebei University(Natural Science Edition),2003,23(2):221-226.DOI:1000 -1565(2003)02 -0221-06.

[5] BARALDI P,CANNARILE F,MAIO F D,et al.Hierarchicalk-nearest neighbors classification and binary differential evolution for fault diagnostics of automotive bearings operating under variable conditions [J].Engineering Applications of Artificial Intelligence,2016,56:1-13.DOI:10.1016/j.engappai.2016.08.011.

[6] BELIAKOV G,LI G.Improving the speed and stability of thek-nearest neighbors method [J].Pattern Recognition Letters,2012,33(10):1296-1301.DOI:10.1016/j.patrec.2012.02.016.

[7] ANDONI A,INDYK P.Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions [J].Communication ACM,2008,51 (1):117-122.DOI:10.1109/FOCS.2006.49.

[8] GU X G,ZHANG Y D,ZHANG Y,et al.An improved method of locality sensitive hashing for indexing large-scale and high-dimensional features [J].Signal Processing,2013,93(8):2244-2255.DOI:10.1016/j.sigpro.2012.07.014.

[9] HERRANZ J,NIN J,SOLE M.KD-trees and the real disclosure risks of large statistical databases [J].Information Fusion,2012,13(4):260-273.DOI:10.1016/j.inffus.2011.03.001.

[10] LIU S G,WEI Y W.Fast nearest neighbor searching based on improved VP-tree [J].Pattern Recognition Letters,2015,60-61:8-15.DOI:10.1016/j.patrec.2015.03.017.

[11] 李武軍,周志華.大數(shù)據(jù)哈希學(xué)習(xí)：現(xiàn)狀與趨勢(shì)[J].科學(xué)通報(bào),2015,60(5):485-490.DOI:10.1360/N972014-00841.

LI W J,ZHOU Z H.Learning to hash for big data:Current status and future trends [J].Chinese Science Bulletin,2015,60(5):485-490.DOI:10.1360/N972014-00841.

[12] 王建峰.基于哈希的最近鄰查找[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué),2015.DOI:10.1145/2502081.2502100.

WANG J F.Hashing-based nearest neighbor search [D].Hefei:University of Science and Technology of China,2015.DOI:10.1145/2502081.2502100.

[13] CHANG C C,WU T C.A hashing-oriented nearest neighbor searching scheme[J].Pattern Recognition Letter,1993,14(8):625-630.DOI:10.1016/0167-8655(93)90047-H.

[14] HOU G D,CUI R P,PAN Z,et al.Tree-based compact hashing for approximate nearest neighbor search [J].Neurocomputing,2015,166:271-281.DOI:10.1016/j.neucom.2015.04.012.

[15] SLANEY M,CASEY M.Locality-sensitive hashing for finding nearest neighbors [J].IEEE Signal Processing Magazine,2008,25:128-131.DOI:10.1109/MSP.2007.914237.

[16] PAULEVE L,JEGOU H,AMSALEG L.Locality sensitive hashing:A comparison of hash function types and querying mechanisms [J].Pattern Recognition Letters,2010,31(11):1348-1358.DOI:10.1007/978-3-319-13168-9_32.

[17] HART P E.The condensed nearest neighbor rule [J].IEEE Transaction on Information Theory,1968,14(5):515-516.DOI:10.1109/TIT.1968.1054155.

[18] GATES G W.The reduced nearest neighbor rule [J].IEEE Transactions on Information Theory,1972,18(3):431-433.DOI:10.1109/TIT.1972.1054809.

[19] WILSON D R,MARTINEZ T R.Reduction techniques for instance-based learning algorithms [J].Machine Learning,2000,38(3):257-286.DOI:10.1023/A:1007626913721.

[20] BRIGHTON B,MELLISH C.Advances in instance selection for instance-based learning algorithms [J].Data Mining and Knowledge Discovery,2002,6(2):153-172.DOI:10.1023/A:1014043630878.

[21] SALVADOR G,JOAQUIN D,JOSE R C,et al.Prototype selection for nearest neighbor classification:taxonomy and empirical study [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(3):417-435.DOI:10.1109/TPAMI.2011.142.

[22] DEAN J,GHEMAWAT S.MapReduce:Simplified data processing on large clusters [J].Communications of the ACM,2008,51(1):107-113.DOI:10.1145/1327452.1327492.

(責(zé)任編輯：孟素蘭)

Experimental comparison of two acceleration approaches forK-nearest neighbors

ZHAI Junhai,WANG Tingting,ZHANG Mingyang,WANG Yaoda,LIU Mingming

(College of Mathematics and Information Science,Hebei University,Baoding 071002,China)

K-NN (K-nearest neighbors) is a famous data mining algorithm with wide range of applications.The idea ofK-NN is simple and it is easy to implement.Both computational time and space complexity ofK-NN are allO(n),where,nis the number of instances in a training set.WhenK-NN encountered larger training sets,especially faced with big data sets,the efficiency ofK-NN becomes very low,evenK-NN is impracticable.Two acceleration approaches forK-nearest neighbors are experimentally compared on 8 data sets.The two acceleration approaches are the CNN and MapReduce basedK-NN.Specifically,in Hadoop environment,this paper implementsK-NN with MapReduce,and experimentally compares with CNN on 8 data sets.Some valuable conclusions are obtained,and may be useful for researchers in related fields.

K-nearest neighbors;data mining;MapReduce;Hadoop

10.3969/j.issn.1000-1565.2016.06.013

2016-07-11

國(guó)家自然科學(xué)基金資助項(xiàng)目(71371063);河北省高等學(xué)?？茖W(xué)技術(shù)研究重點(diǎn)項(xiàng)目(ZD20131028)；河北大學(xué)研究生創(chuàng)新項(xiàng)目(X2016059)

翟俊海(1964—),男,河北易縣人，河北大學(xué)教授,博士,主要從事機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘方向研究.E-mail:mczjh@126.com

TP18

A

1000-1565(2016)06-0650-07