b. 河北大学 数学与信息科学学院, 河北 保定 071002
b. College of Mathematics and Information Science, Hebei University, Baoding 071002, Hebei, China
K-NN[1]是一种思想简单, 但应用却非常广泛的算法, 已成功应用于模式识别[2-5]、预测预报[6-8]、决策支持[9-10]等许多领域。K-NN算法的计算代价主要来源于计算测试样例与所有训练样例之间的距离。当训练集是大数据集时, 其计算时间复杂度非常高[11]。针对这一问题, 研究人员提出三类解决的方法, 这些方法大致可分为: (1)基于样例选择的方法, (2)基于近似搜索的方法, (3)分布式方法。
基于样例选择的方法大多利用某种启发式从大数据集中选择一个子集, 代替原来的大数据集进行分类。例如, 文献[12]提出基于MapReduce和随机权网络的大数据投票样例选择方法。该方法具有选择速度快、压缩比高和对样例选择算法没有限制的优点。受交叉验证思想的启发, 文献[13]提出交叉选择样例算法。基于局部敏感哈希技术[14], 文献[15]提出两种计算时间复杂度为O(n)的大数据样例选择算法，提出的算法利用局部敏感哈希方法在大数据集中寻找训练样例的近似近邻。文献[16]将样例约简算法推广到大数据环境，使之可以处理大数据分类问题。文献[17]提出改进的局部敏感哈希方法, 用于解决高维大数据的检索问题。文献[18]对利用哈希技术进行大数据的检索进行全面的综述, 具有很高的参考价值。分布式方法将寻找待分类样例的K-近邻的工作以并行方式进行, 这样可以解决大数据K-近邻分类问题。近几年, 随着MapReduce和Spark的盛行, 研究人员提出几种基于MapReduce或Spark的K-近邻算法。例如, 文献[19]利用MapReduce并行编程模型, 实现K-NN算法在Hadoop平台下的并行化。文献[20]提出基于Spark的大数据K-近邻分类算法。文献[21]对K-NN的两种加速算法进行比较。本研究将HBase和SimHash结合起来, 提出一种基于HBase和SimHash的大数据K-近邻算法。并在分类能力保持的前提下, 与基于MapReduce的K-NN和基于Spark的K-NN进行运行时间的试验比较。试验结果显示, 提出的算法的运行时间远远低于这两种方法。
1 基础知识 1.1 HBaseHBase[22]是建立在HDFS之上的分布式数据库, 可以用于存储海量的数据。HBase中每张表的行数可以多达几十亿条甚至更多, 每条记录可以拥有多达上百万的字段。而这样的存储能力却不需要特别的硬件, 普通的服务器集群就可以胜任。
HBase中的表是分布式的多维表, 表中的数据通过行健、列族、列名和时间戳来进行索引和定位查询。HBase通过行健、列族、列名和时间戳来确定一个存储单元, 即一个行键和值的二元对:{行键, 列族, 列名, 时间戳}→值。表 1是一个HBase数据表的例子, 在行键为key3的行中, 地址字段包含2个地址:t1时间戳下的地址为“北京”, t2时间戳下的地址为“上海”。
|
表 1 一个HBase数据表的例子 Table 1 An example of HBase data table |
下面介绍HBase数据存储逻辑模型中的行关键字、列族和列名、时间戳这几个概念:
行关键字 即rowkey, HBase中一张表可以有上亿行记录, 每一行都是由一个行关键字(rowkey)来标志的, HBase保证对所有行按照rowkey进行字典排序。表 1中的key1、key2、key3就是所谓的rowkey。
列族和列 HBase中的表在水平方向上由一个或者多个列族组成, 一个列族由任意多个列组成, 列是不需要事先静态定义的, 可以进行动态的增加和减少, 从本质上讲, HBase中的列族就是一个容器, HBase中的每个列, 都必须归属于某个列族。表 1中的个人信息和公司信息就是列族, 姓名、地址和手机等就是列。
时间戳 HBase中的每个存储单元都保存着同一份数据的多个版本。版本通过时间戳来索引, 并且在每个存储单元中, 不同版本的数据按照时间戳大小倒序排序, 即最新的数据排在最前面。这样在读取数据时, 用户将先读到最新的数据。
1.2 SimHash传统的Hash算法[23]的目标是将原始内容尽量均匀随机地映射为一个签名值, 原理上相当于伪随机数产生算法。传统Hash算法产生的2个签名, 如果相等, 说明原始的2个内容在一定概率上是相等的; 如果不相等, 除了说明原始的2个内容不相等外, 不再提供任何信息。因为即使原始内容只相差一个字节, 所产生的签名也很可能差别极大。从这个意义上来说, 要设计一个Hash算法, 对相似的内容产生的签名也相似, 是更为艰巨的任务, 因为它的签名值除了需要提供原始内容是否相等的信息外, 还需要额外提供不相等的原始内容的差异程度的信息。
SimHash算法是Google公司的研究人员Manku等人提出的一种网页去重的相似性估计方法。SimHash和普通Hash最大的不同在于传统的Hash函数虽然可以用于映射来比较文本的重复, 但是对于可能差距只有一个字节的文档也会映射成2个完全不同的哈希结果, 而SimHash对相似的文本的哈希映射结果也相似, 在Hamming空间中Hash签名的相似程度, 也能反映出原空间中样例的相似程度。
SimHash算法思想精巧、容易理解和实现。其输入是一个向量, 输出是一个f位的签名值。为了陈述方便, 假设输入的是一个样例的特征集合xi=(xi1, xi2, …, xid), SimHash算法描述如下:
(1) 对于xi的每一个特征分量, 用传统的Hash算法把该分量变换成一个f位的签名值b。
(2) 如果签名值b的第i位等于0, 则置为-1;否则置为1。
(3) 将xi所有特征分量的变换码按位相加, 如果和向量的某一维大于0, 则最终签名的对应位为1;如果和向量的某一维小于等于0, 则最终签名的对应位为0。这就是样例xi经过SimHash算法最终映射得到的f位签名值。
下面通过一个具体例子说明SimHash算法的执行过程。假设样例x1=(1, 2, 3, 4), 样例x2=(1, 2, 3, 5)。对样例x1, SimHash算法的执行过程包括4步:
第1步, 将x1的各个分量变换为二值码, 变换结果可用矩阵表示为
| $ \left[{\begin{array}{*{20}{l}} 1& \to &0&0&0&1 \\ 2& \to &0&0&1&0 \\ 3& \to &0&0&1&1 \\ 4& \to &0&1&0&0 \end{array}} \right]。$ |
第2步, 将矩阵中的0变为-1, 变换后的矩阵为
| $ \left[{\begin{array}{*{20}{l}} 1& \to &{-1}&{-1}&{-1}&1 \\ 2& \to &{ - 1}&{ - 1}&1&{ - 1} \\ 3& \to &{ - 1}&{ - 1}&1&1 \\ 4& \to &{ - 1}&1&{ - 1}&{ - 1} \end{array}} \right]。$ |
第3步, 对变换码按位求和, 得到(-4, -2, 0, 0)。
第4步, 将负数变为0, 正数变为1, 得到样例x1的SimHash值为(0, 0, 0, 0)。
类似地, 可得样例x2的SimHash值为(0, 0, 0, 1)。
从x1和x2的SimHash值可以看出, x1和x2在原样例空间是相似的(只第4个分量不同, 一个为4, 一个为5), 经过SimHash变换后, 在Hamming空间也是相似的。
2 基于HBase和SimHash的大数据K-近邻算法在提出的算法中, 用流行的大数据开源框架Hadoop和Spark计算测试样例到所有训练样例之间的距离。Hadoop为用户提供方便易用的MapReduce分布式计算框架, 可以对海量数据进行并行处理。MapReduce的功能主要通过map()函数和reduce()函数实现。map()函数将一组键值对转化成新的键值对, 分配给指定的reduce()函数。
Spark克服MapReduce计算框架在迭代算法和交互式数据挖掘方面的不足, 通过引入弹性分布式数据集(resilient distributed datasets, RDD), 用户可以轻松地使用Spark提供的API进行算法设计。与MapReduce相比, Spark在迭代算法和交互式数据挖掘方面效率有很大的提升。下面介绍算法的基本思想。
对于给定的大数据集, 首先利用SimHash算法将大数据集从原样例空间映射到Hamming空间, 得到二值码集合, 映射之后的格式为(样例的二值码, 样例的类别); 然后, 以样例的二值码值(即哈希签名值)作为行健rowkey, 类别作为value存储到HBase数据库中, 对于待测样例xi, 以其哈希签名值作为行健rowkey, 然后从HBase数据库中获取所有版本的value, 这里的value也就是之前存储的样例的类别值。通过对这些value进行多数投票即可以获得待测样例的类别label, 下面给出算法的伪代码。
算法1 基于HBase和SimHash的K-近邻算法
输入 经SimHash变换之后的样例
输出 测试样例x的类标
(1)//以测试样例x的哈希签名值作为行键rowkey, 从HBase数据库中获取所有版本的value值, 并将这些value存放到容器ArrayList中;
(2) Result result=hTable.get(x的哈希签名值Hamming code);
(3) ArrayList.add(result.getMaxVersions());
(4)//利用多数投票法对测试样例x进行分类;
(5) predictable=MostFrequent(ArrayList);
(6) 输出测试样例x的类标。
下面通过一个例子解释算法过程, 假如有5个训练样例:sample1、sample2、sample3、sample4和sample5。经SimHash算法, 这些训练样例由原样例空间映射到Hamming空间, 得到二值码集合, 映射之后的格式为(code1, label1)、(code2, label2)、(code3, label3)、(code4, label4)和(ode5, label5)。
然后, 以映射之后的code作为行健rowkey, 类别label作为value存储到HBase数据库中, 假设sample1、sample2和sample3映射之后的code相同, 记为code123。这样数据存储到HBbase数据表之后的格式见表 2, 列族中存储的信息是类别信息。
|
|
表 2 HBbase数据表的格式 Table 2 Format of HBbase data table |
假如有一个测试样例test1, 经SimHash映射之后的二值码为test1-code=code123=code1=code2=code3。于是, 此时就以哈希签名值test1 code=code123作为行健, 从HBase数据库中获取所有版本的value:即label1、label2、label3, 然后对这些labels进行多数投票即可以获得预测样例的类别label。
3 试验结果为了验证提出的算法的有效性, 在5个UCI数据集上, 与基于MapReduce的K-近邻算法[19]和基于Spark的K-近邻算法[20]在运行时间和测试精度上进行试验比较。5个数据集中包括2个中小型数据集和3个大数据集, 数据集的基本信息见表 3。对于每一个数据集, 按7:3的比例随机地划分为训练集和测试集。并将测试集随机地平均划分为6份, 作为每一次试验的输入使用。所有试验的源代码上传到以下网站:http://pan.baidu.com/s/1o82hdyi, 有兴趣的读者可以下载参考。
|
|
表 3 试验所用数据集的基本信息 Table 3 The basic information of the data sets used inthe experiments |
在试验中, 首先用2个中小型数据集, 在单机上利用伪分布模式模拟云计算环境, 验证算法的可行性, 试验结果见表 4、5。从表 4可以看出, 提出的算法在运行时间上明显优于其他两种算法, 从这2个中小型数据集上的试验结果可以证明提出的算法是可行的。然后, 在真实的云计算环境中, 用3个大型数据集进行了试验。为描述方便, 基于MapReduce的K-近邻算法记为MR-K-NN, 基于Spark的K-近邻算法记为Spark-K-NN, 基于HBase和SimHash的K-近邻算法记为HS-K-NN。云计算环境具有6个节点, 这些节点的基本配置信息见表 6。3种云计算平台(Hadoop、Spark和HBase)的具体规划见表 7~9。在3个大数据集上的试验结果见表 10~12。测试精度的试验结果见表 13。
|
|
表 4 在小型数据集Cmc上MR-K-NN、Spark-K-NN和HS-K-NN的运行时间 Table 4 Running time MR-K-NN, Spark-K-NN and HS-K-NN on small data set Cmc |
|
|
表 5 在中型数据集Statlog上MR-K-NN、Spark-K-NN和HS-K-NN运行时间比较 Table 5 Running time of MR-K-NN, Spark-K-NN andHS-K-NN on a medium-sized data set Statlog |
|
|
表 6 云计算平台节点的基本配置信息 Table 6 Basic configuration information for cloud computingplatform nodes |
|
|
表 7 Hadoop云计算平台节点功能规划 Table 7 Hadoop cloud computing platform nodefunction planning |
|
|
表 8 Spark云计算平台节点功能规划 Table 8 Spark cloud computing platform node function planning |
|
|
表 9 HBase云计算平台节点功能规划 Table 9 HBase cloud computing platform node function planning |
|
|
表 10 在大数据集Forest上MR-K-NN、Spark-K-NN和HS-K-NN运行时间 Table 10 Running time MR-K-NN, Spark-K-NN and HS-K-NN on large data set Forest |
|
|
表 11 在大数据集Skin上MR-K-NN、Spark-K-NN和HS-K-NN运行时间比较的试验结果 Table 11 Running time of MR-K-NN, Spark-K-NN and HS-K-NN on large data set Skin |
|
|
表 12 在大数据集Poker上MR-K-NN、Spark-K-NN和HS-K-NN运行时间 Table 12 Running time MR-K-NN, Spark-K-NN and HS-K-NN on large data set Poker |
|
|
表 13 3种算法在测试精度上的比较 Table 13 The comparison of three algorithms ontesting accuracy |
从以上试验结果可以看出, 在分类能力保持的前提下, 提出的算法在运行时间上远远低于另外两种算法, 其原因是提出的算法充分利用HBase数据库和SimHash算法的以下优点:
(1) 提出的算法充分利用HBase数据库的数据存储模型和实时性秒级查询的优点;
(2) 提出的算法充分利用了SimHash算法在Hamming空间中Hash签名的相似程度, 也能反映出原空间中样例的相似程度的优点。
4 结论针对大数据环境中K-NN算法的不足, 基于HBase和SimHash, 提出适用于大数据集分类的K-近邻算法。提出的算法集成了HBase和SimHash两者的优点, 不仅可以实现大数据集的K-近邻分类, 而且有很高的效率。与基于MapReduce的K-近邻及基于Spark的K-近邻两种算法相比, 在分类能力保持的前提下, 提出的算法在运行时间上远远低于这两种算法, 这说明提出的算法是行之有效的。提出的算法具有2个优点:(1)算法思想简单, 容易理解, 易于编程实现; (2)算法计算时间复杂度低, 运行效率高。本研究未来进一步的工作包括:(1)在更多更大的数据集上试验, 并对试验结果进行统计分析, 如对运行时间进行成对T-检验、Wilcoxon检验和Friedman检验等; (2)对SimHash算法做进一步的改进, 提高其计算精度。
| [1] | COVER T M, HART P E. 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] | BHATEJA A K, SHARMA S, CHAUDHURY S, et al. Iris recognition based on sparse representation and k-nearest subspace with genetic algorithm[J]. Pattern Recognition Letters, 2016, 73: 13-18 DOI:10.1016/j.patrec.2015.12.009 |
| [4] |
朱庆生, 唐汇, 冯骥. 一种基于自然最近邻的离群检测算法[J].
计算机科学, 2014, 41(3): 276-278 ZHU Qingsheng, TANG Hui, FENG Ji. Outlier dectection algorithm based on natural nearest neighbor[J]. Computer Science, 2014, 41(3): 276-278 |
| [5] |
肖春宝, 冯大政. 基于K近邻一致性的特征匹配内点选择算法[J].
计算机科学, 2016, 43(1): 290-293 XIAO Chunbao, FENG Dazheng. Inlier selection algorithm for feature matchiing based on K nearest neighbor consistence[J]. Computer Science, 2016, 43(1): 290-293 DOI:10.11896/j.issn.1002-137X.2016.01.062 |
| [6] | NIKOLOPOULOS K I, BABAI M Z, BOZOS K. Forecasting supply chain sporadic demand with nearest neighbor approaches[J]. International Journal of Production Economics, 2016, 177: 139-148 DOI:10.1016/j.ijpe.2016.04.013 |
| [7] | CHEN H L, YANG B, WANG G, et al. A novel bankruptcy prediction model based on an adaptive fuzzy K-nearest neighbor method[J]. Knowledge-Based Systems, 2011, 24(8): 1348-1359 DOI:10.1016/j.knosys.2011.06.008 |
| [8] | SINGH A, DAMIR B, DEEP K, et al. Calibration of nearest neighbors model for avalanche forecasting[J]. Cold Regions Science and Technology, 2015, 109: 33-42 DOI:10.1016/j.coldregions.2014.09.009 |
| [9] | LEE Y H, WEI C P, CHENG T H, et al. Nearest-neighbor-based approach to time-series classification[J]. Decision Support Systems, 2012, 53(1): 207-217 DOI:10.1016/j.dss.2011.12.014 |
| [10] | LTIFI H, BENMOHAMED E, KOLSKI C, et al. Enhanced visual data mining process for dynamic decision-making[J]. Knowledge-Based Systems, 2016, 112: 166-181 DOI:10.1016/j.knosys.2016.09.009 |
| [11] | WU X D, KUMAR V, QUINLAN J R, et al. Top 10 algorithms in data mining[J]. Knowledge & Information Systems, 2007, 14(1): 1-37 |
| [12] | ZHAI J H, WANG X Z, PANG X H. Voting-based instance selection from large data sets with mapreduce and random weight networks[J]. Information Sciences, 2016, 367: 1066-1077 |
| [13] | ZHAI J H, LI T, WANG X Z. A cross-selection instance algorithm[J]. Journal of Intelligent & Fuzzy Systems, 2016, 30(2): 717-728 |
| [14] | INDYK P, MOTWANI R. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, USA: ACM, 1998: 604-613. |
| [15] | ÁLVAR A G, DÍEZ-PASTOR J F, RODÍGUEZ J J, et al. Instance selection of linear complexity for big data[J]. Knowledge-Based Systems, 2016, 107: 83-95 |
| [16] | TRIGUEROI, PERALTA D, BACARDIT J, et al. MRPR: a MapReduce solution for prototype reduction in big data classification[J]. Neurocomputing, 2015, 150(Part A): 331-345 |
| [17] | GU X G, ZHANG Y D, ZHANG L, 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 |
| [18] | WANG J, LIU W, KUMAR S, et al. Learning to hash for indexing big data-a survey[J]. Proceedings of the IEEE, 2016, 104(1): 34-57 |
| [19] |
闫永刚, 马廷淮, 王建. K-NN分类算法的MapReduce并行化实现[J].
南京航空航天大学学报, 2013, 45(4): 550-555 YAN Yonggang, MA Tinghuai, WANG Jian. Parallel implementing K-NN classification algorithm using mapreduce programming mode[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2013, 45(4): 550-555 |
| [20] | MAILLO J, RAMIREZ S, TRIGUERO I, et al. K-NN-IS: an iterative spark-based design of the K-nearest neighbors classifier for big data[J]. Knowledge-Based Systems, 2016, 117: 3-15 |
| [21] |
翟俊海, 王婷婷, 张明阳, 等. 2种加速K-近邻方法的实验比较[J].
河北大学学报(自然科学版), 2016, 36(6): 650-656 ZHAI Junhai, WANG Tingting, ZHANG Mingyang, et al. Experimental comparison of two acceleration approaches for K-nearest neighbor[J]. Journal of Hebei University (Natural Science Edition), 2016, 36(6): 650-656 |
| [22] | 黄宜华, 苗凯翔. 深入理解大数据-大数据处理与编程实践[M]. 北京: 机械工业出版社, 2014. |
| [23] |
李武军, 周志华. 大数据哈希学习:现状与趋势[J].
科学通报, 2015, 60(5-6): 485-490 LI Wujun, ZHOU Zhihua. Learning to hash for big data: Current status and future trends[J]. Chinese Science Bulletin, 2015, 60(5-6): 485-490 |