2种加速K-近邻方法的实验比较
2017-01-10翟俊海王婷婷张明阳王耀达刘明明
翟俊海, 王婷婷, 张明阳, 王耀达, 刘明明
(河北大学 数学与信息科学学院,河北 保定 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) 输入:
算法3:Reduce函数1) 输入:
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
