翟俊海, 王婷婷, 張明陽, 王耀達, 劉明明

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

?

2種加速K-近鄰方法的實驗比較

翟俊海, 王婷婷, 張明陽, 王耀達, 劉明明

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

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

K-近鄰；數據挖掘；MapReduce；Hadoop

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

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

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

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

1 基礎知識

本節介紹將要用到的基礎知識，包括K-NN算法和MapReduce編程模型.

1.1 CNN算法

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

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

如果K>1，CNN算法只需初始化時，從訓練集T中隨機選擇K個樣例加入T′中,其他步驟不變.

說明：CNN算法的核心概念是一致子集.訓練集T的子集T′稱為一致子集，如果T′能夠正確分類T中的所有樣例.訓練集T的所有一致子集中，包含樣例數最少的一致子集，稱為T的最小一致子集.實際上，CNN算法試圖尋找訓練集T的最小一致子集，但該算法最終得到的子集T′未必是最小一致子集.

1.2 MapReduce編程模型

MapRecuce是針對大數據處理的一種并行編程框架，其基本思想包括以下3個方面：

1)MapRecuce采用分治策略自動地將大數據集劃分為若干子集，并將這些子集部署到不同的云計算節點上，并行地對數據子集進行處理.

2)基于函數編程語言LISP的思想，MapRecuce提供了2個簡單易行的并行編程方法,即Map和Reduce，用它們去實現基本的并行計算.

3)許多系統級的處理細節MapRecuce能自動完成，這些細節包括：①計算任務的自動劃分和自動部署；②自動分布式存儲處理的數據；③處理數據和計算任務的同步；④對中間處理結果數據的自動聚集和重新劃分；⑤云計算節點之間的通訊；⑥云計算節點之間的負載均衡和性能優化；⑦云計算節點的失效檢查和恢復.

MapRecuce處理數據的流程如圖1所示.

圖1 MapRecuce處理數據的流程Fig.1 Diagram of data processing by MapRecuce

2 基于MapReduce的K-NN算法

在Hadoop環境下，本文編程實現了基于MapReduce的K-NN算法.用MapReduce實現K-NN的關鍵是Map和Reduce這2個函數的設計，這2個函數的設計如算法2和算法3所示.

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

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

3 CNN與基于MapReduce的K-NN的實驗比較

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

實驗所用數據集的基本信息列于表2中，實驗所用的云平臺環境列于表3中，實驗結果列于表4中.

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

表2 實驗所用數據集的基本信息

表4中，符號“—”表示運行未能得到結果.從列于表4的實驗結果可以看出，在大數據集上，基于MapReduce的K-NN加速效果優于CNN算法，但是在一些中小型數據集上，如Statlog和Skin Segmentation，CNN的加速效果優于基于MapReduce的K-NN.原因有2點：

1)當數據集的大小小于1個block塊(默認為64 MB)時，由于單機的內存可以加載測試數據，此外，CNN算法對訓練樣本的大量壓縮提高了運行速度.

2)MapReduce運行過程中是要對數據文件進行分片，一個分片一個map任務，而每一個任務從建立、處理、提交到寫到本地以及節點間的通信都是需要時間的，也需要耗費一定的資源，而且在單機下map任務只能順序執行，所以map任務越多，時間運行越長，map任務除計算部分所要耗費的時間掩蓋了MapReduce并行計算的優勢，這也是為什么很多文獻都提到MapReduce框架不適用于中小數據文件的原因.

隨著數據集的增大，單機環境下加載困難，此時MapReduce將會發揮集群的優勢，可以通過MapReduce輕易地得出K-NN算法的結果，對數據集GAUSS1，MR-K-NN算法的運行速度是CNN的5.9倍，對數據集GAUSS2，MR-K-NN算法的運行速度是CNN的96.3倍，對于其他的幾個數據集，由于CNN算法在12 h內都沒得出結果，表4中用符號“—”表示.而基于MapReduce的K-NN都能得出結果，這對于從事相關研究的人員具有一定的借鑒價值.

4 結論

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

[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-近鄰相結合的文本分類方法[J].河北大學學報(自然科學版),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].河北大學學報(自然科學版),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] 李武軍,周志華.大數據哈希學習：現狀與趨勢[J].科學通報,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].合肥：中國科學技術大學,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.

(責任編輯：孟素蘭)

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

國家自然科學基金資助項目(71371063);河北省高等學校科學技術研究重點項目(ZD20131028)；河北大學研究生創新項目(X2016059)

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

TP18

A

1000-1565(2016)06-0650-07