周 翔，翟俊海*，黄雅婕，申瑞彩，侯璎真

（1.河北大学数学与信息科学学院，河北保定 071002；2.河北省机器学习与计算智能重点实验室（河北大学），河北保定 071002）

0 引言

在信息技术飞速发展的时代，不仅技术在快速发展，数据也在呈指数型上升。随着数据规模不断扩大，数据已经充斥了生活中的方方面面，如何从海量数据中去除冗余的和不重要的数据，或从大数据中选择重要的子集具有重要的研究价值。

样例选择是解决大数据问题的一种有效的方法，它从大数据集中选择一个子集，用选择出的子集代替大数据集进行学习，目标是在学习性能受很小影响的前提下，提高学习效率。历史上，第一个样例选择算法是Hart［1］于1968 年提出压缩最近邻（Condensed Nearest Neighbor，CNN）算法，研究人员提出的诸多样例选择算法根据样例选择过程可分为两类：增量算法和减量算法。

增量算法从原始数据集T中按照特定的选择规则，不断地选择重要的样例放入初始化为空集的子集S中，增量算法从T中选择样例的方法具有随机性，这种随机性对最终结果影响较大。CNN 就是一种增量样例选择算法。Carbonera 和Abel［2-3］提出了两种基于密度的样例选择算法：LDIS（Local Density Instance Selection）和CDIS（Central Density Instance Selection）。LDIS 算法选择样例的标准是在每个类中选择具有最高密度值的样例，而不是在整个数据集中进行全局搜索，这样保证了LDIS 算法具有较低的计算时间复杂度。CDIS 算法采用与LDIS 算法相同策略，不同之处在于给有K个最近邻的样例赋予一个更高的密度值。在这一框架下，Malhat 等［4］也提出了两种基于密度的样例选择算法：基于全局密度的样例选择和基于全局密度的增强样例选择算法。Arnaiz-González 等［5］提出了民主样例选择算法，并在Hadoop 平台上，用MapReduce编程实现了该算法。De Haro-Garcíada等［6］提出了一种基于遗传算法的样例选择算法。Guo 等［7］提出了一种基于Bagging 集成策略的关键样例选择算法，提出的方法比Bagging 方法更准确，比Boosting 方法更可靠。上面算法都是针对分类任务提出的，而Kordos 等［8］提出了一种针对回归任务的进化样例选择算法。

减量型算法初始化数据集S为原始数据集T，再使用某种启发式从S中删除不重要或冗余的样例，与增量型算法相比，减量型算法具有更高的时间复杂度，但是会提高分类器在子集上的测试精度。在CNN 算法的基础上，Gates［9］提出了约简最近邻（Reduced Nearest Neighbor，RNN）算法，RNN能从CNN选出的子集中进一步删除冗余的样例，但是需更多的处理时间。为了解决CNN 和RNN 都可能无法得到最小一致子集的缺点，Ritter 等［10］提出了SNN（Selective Nearest Neighbour）算法，SNN 将原数据集中每个样例与一致子集中最近同类别样例之间的距离设定为小于该样例到原数据集中的最近非同类样例之间的距离，选出更小距离的一致子集。Liao 等［11］提出一种去除文本文件中噪声样例选择的算法，通过计算文本文件的类别属性得分，来区分每一类中噪声样例和正常样例。受交叉验证思想的启发，Zhai 等［12］提出了一种交叉样例选择算法，该算法使用极限学习机算法构建由分类器组成的委员会，以投票熵作为评价样例重要性的准则进行样例选择。Abbasi 等［13］提出了一种基于ReliefF 的样例选择算法，该算法利用ReliefF 计算最近邻集合中每个样例的权重，选择出权重大的样例。Cavalcanti 等［14］提出了一种基于排名的样例选择，该算法根据每个样例与训练集中所有其他样例的关系来计算每个样例的得分，根据得分排名选择样例。Yang 等［15］提出了一种基于粗糙集的样例选择算法。Pang 等［16］提出了基于K-近邻的加权多类孪生支持向量机的样例选择算法，它通过删除已分类的样例子集中冗余的样例来得到有代表性的数据子集。Jiang 等［17］提出了基于深度学习的样例选择方法，根据本地数据集的重要性进行筛选，将筛选出的样例集合进行网络上传，来减小网络负载和训练时长，提高数据集的性能。

随机森林（Random Forest，RF）由决策树算法归纳总结得出，决策树的并行化问题是先由Kufrin［18］提出的。Breiman［19］提出了应用非常广泛的随机森林算法。Yildiz 等［20］提出了并行化回归树算法。Wu 等［21］在Hadoop 平台上用MapReduce 编程实现了C4.5 决策树算法。Robnik-Sikonja［22］提出了改进的随机森林算法，使用边际权重加权投票代替普通投票选择子树。Del Rio 等［23］使用随机森林算法对大数据进行过采样、欠采样和成本敏感学习，并用在MapReduce 编程实现了提出的算法。Xu 等［24］提出了一种基于Fayyad 边界点原理的改进随机森林算法，以解决经典随机森林算法在连续属性离散化过程中的信息丢失问题。

综上所述，目前的参考文献中基于大数据的样例选择问题还比较少，本文拟在这一问题领域使用随机森林算法解决大数据样例选择问题。解决问题的思路是，在MapReduce［25］和Spark［26］框架上，将大数据集划分为若干个数据子集，将这些数据子集分发到不同的大数据计算平台的不同节点上，在各个节点上，通过随机森林算法进行分类处理，将其中被错误分类的样例子集S1选择出来。重复p次，得到p个样例子集S1，S2，…，Sp。最后用这p个样例子集进行投票，得到最终样例子集。

1 基础知识

本章简要介绍将要用到的基础知识，包括随机森林、开源的大数据处理平台Hadoop和Spark。

1.1 随机森林

随机森林［19］是一种由若干棵决策树构成的集成分类算法，其基础是决策树算法，其核心是如何用随机化的思想构建组成随机森林的多棵决策树。对于给定的包含n个样例的训练集T={(xi，yi)|xi∈Rd，yi∈Y}，假设随机森林的规模为l，随机森林算法中的随机性体现在两个方面：一是按一定比例从训练集T中随机地抽取样例，得到T的一个样例子集，重复l次，得到l个样例子集；二是按一定比例从d个属性中随机地抽取一个属性子集来划分样例。随机森林算法的伪代码如算法1所示。

算法1 随机森林算法。

输入 训练集T={(xi，yi)|xi∈Rd，yi∈Y}，1 ≤i≤n；随机森林的规模l，随机抽取的属性子集的大小m，测试样例x；

输出 测试样例x的类别标签y∈Y。

1.2 大数据处理平台Hadoop与Spark

Hadoop［25］是Apache 软件基金会负责管理维护的一个开源的分布式大数据处理平台，用于大数据的高可靠、可扩展的分布式计算。HDFS（Hadoop Distributed File System）和MapReduce 是Hadoop 的两个核心组件，HDFS 负责大数据的组织、存储和管理，MapReduce 用于实现用户对大数据的不同应用逻辑。实际上，MapReduce 是一个并行编程框架，这一框架可方便用户编写处理大数据的应用程序，封装了许多底层处理细节，如节点之间的通信、任务同步、负载均衡、失效检查与恢复等，都由MapRecuce 自动完成，不需要用户干预。MapRecuce 采用分而治之的思想处理大数据，将数据处理分成Map、Shuffle 和Reduce 三个阶段，与HDFS 配合共同完成大数据处理，MapReduce处理大数据的流程如图1所示。

图1 MapReduce处理大数据的流程Fig.1 Flowchart of big data processing by MapReduce

从程序设计语言的角度来看，Map 和Reduce 是两个抽象的编程接口，由用户编程实现，完成自己的应用逻辑。

Spark［26］是一个基于内存的大数据处理平台，2009年诞生于加州大学伯克利分校AMPLab（Algorithms，Machine，and People Lab），早期属于伯克利大学的研究性开发项目，采用Scala 编程语言开发，于2010 年正式开源，2013 年6 月成为Apeche 孵化项目，2014 年2 月成为Apache 顶级项目，现在Spark 已经成为一个功能完善的生态系统。其中，Spark Core是Spark的核心组件，具有任务调度、存储管理、错误恢复等功能。Spark 的主要操作对象为弹性分布式数据集（Resilient Distributed Dataset，RDD），RDD是一种抽象的数据模块结构。Spark 使用RDD 实现基于内存的计算，在计算过程中会优先考虑将数据缓存在内存中，如果内存容量不足的话，Spark 才会考虑将数据或部分数据缓存到磁盘上。Spark 为RDD 提供了一系列算子，以对RDD 进行有效的操作。实际上，Spark 对大数据的处理就是通过对RDD的处理实现的，将一种RDD经算子操作变换成另一种RDD 来实现数据的计算。Spark 对大数据的处理流程如图2所示。

图2 Spark处理大数据的流程Fig.2 Flowchart of big data processing by Spark

2 基于随机森林的大数据投票样例选择算法

本章首先介绍基于随机森林的大数据样例选择算法，简记为RF-IS（Random Forest Instance Selection），然后分别介绍在MapReduce 平台和Spark 平台上实现基于随机森林的大数据选择算法的具体思路。

本文提出的基于随机森林的大数据投票样例选择算法，其基本思路是将大数据集分为训练集D1和测试集D2，在D1上用随机森林算法训练出随机森林分类器，在D2上使用训练出的随机森林分类器进行分类，把错误分类的样例选择出来记为S1，重复p次，得到p个子集S1，S2，…，Sp，对得到的p个子集进行投票选择，得到最终的样例子集S。提出的算法的基本思想如图3所示，算法的伪代码如算法2所示。

图3 所提算法的基本思想Fig.3 Basic idea of the proposed algorithm

算法2 基于随机森林的大数据投票样例选择算法。

输入 大数据集D；

输出 选择的样例子集S。

2.1 随机森林大数据投票样例选择算法的MapReduce实现

根据对随机森林算法的分析，由于需要处理的数据集为大数据集，故将算法在MapReduce 计算框架中实现，将数据集并行地在大数据计算平台进行建树和分类的操作，不仅提高了建模的效率，还提升了容错率。数据集中样例数的增多，可以通过增加MapReduce 的计算节点，来缩短运算的处理时间，将大数据集划分成多个数据子集，对每个数据子集进行样例选择，提高了算法的可扩展性。算法3 是基于MapReduce的随机森林大数据投票样例选择算法，简记为MR-RF-IS（MapReduce Random Forest Instance Selection）。

算法3 MR-RF-IS算法。

在MapReduce 计算平台中，Mahout 库也提供了随机森林算法实现的方法，分为三部分组成。首先生成描述性文件，不仅要了解数据特征属性的数据格式是离散还是连续的，还要知道训练集中每条的输入输出记录在哪个属性列；然后生成随机森林模型，包括建立一棵决策树，把建立好的决策树转换成为随机森林模型和把随机森林模型存入文件系统；最后评估随机森林模型，主要是对随机森林模型的分类正确率进行评估。

2.2 随机森林大数据投票样例选择算法的Spark实现

基于随机森林的大数据样例选择算法是运用集成学习（bagging）的思想，将多棵树集成的一种算法，所以在MR-RFIS 的基础上，在Spark 大数据计算平台上对其进行实现。在Spark 平台上实现随机森林算法，简记为Spark-RF-IS（Spark Random Forest Instance Selection）。Spark 随机森林算法采用了多种优化处理：

切分点抽样式统计 在local 模式中决策树对连续值进行划分点（split）进行分裂时，都是通过对特征进行排序，然后取相邻的两个数据间作为数据的划分点。假如在standalone模式中，进行相同的操作会带来大量的网络通信操作，当数据量巨大时，算法的效率将极为低下。为了避免排序操作，MLlib库中的随机森林在建树的过程中，通过对各个分区进行一定的子特征抽样策略，生成每个分区的统计数据来获取划分点，此策略虽然牺牲了部分的精度，但对模型的整体影响不大。

特征装箱（Binning） 根据抽样策略得到划分点后，将特征进行装箱操作将计算出最优的划分点，划分出来的区域（Bin）由相邻的数据划分点构成，Bin的个数很小，一般采用30个左右，通过计算每个Bin 中不同类型的比例，可以快速计算出最优的划分点

分区统计 在Bin 数据进行单独统计后，可以通过Reduce 阶段进行数据的合并来得到总的Bin 数据，合并的数据为统计数据，不会带来很大的网络通信负载。

逐层训练（level-wise training） 在local 模式中建树的过程使用深度优先的递归调用策略，需要移动数据，将相同节点的数据汇总到一起，但是在分布式处理系统中无法有效地执行此操作，同时数据过大也会导致操作无法存储在一起，所以需要分布式存储。MLlib 采用的是广度优先的逐层构建树节点的策略，遍历所有数据的次数等于决策树的最大层数，每次遍历只需要计算每个节点上特征的Binning统计参数，遍历完成后，根据节点的Binning统计数，决定是否切分和如何切分。Spark-RF-IS算法的伪代码如算法4所示。

算法4 Spark-RF算法。

输入 大数据集T；

输出 数据子集S；

3 实验结果与分析

3.1 实验环境

实验所用到MapReduce和Spark大数据平台，两个平台都为主从式结构，设定1台为主机为主节点和7台主机作为从节点，7 台计算机都在同一局域网内，并通过端口速率为100 Mb/s 的H3C S5100 交换机连接。集群的操作系统均为CentOS 6.4，CPU 为Intel E5 2.20 GHz，实验使用Hadoop 版本为2.7.1，Spark 版本为2.3.1。客户端开发环境为Idea，JDK版本为jdk-1.8.0_144-windows-x64，表1为集群环境配置的详细信息表，计算机型号均为Dell PowerEdge R820。

表1 大数据计算平台节点规划Tab.1 Node configuration of big data computing platform

3.2 实验数据

实验采用3 个人工大数据集和3 个UCI 大数据集进行实验，所使用的数据集的基本信息见表2，每个数据集都被随机分成了两部分，数据集的80%作为训练集，20%作为测试集，将由下面描述的实验指标，将MR-RF-IS 和Spark-RF-IS 进行比对分析，三个Gaussian人工数据集的具体参数见表3。

表2 数据集基本信息Tab.2 Basic information of datasets

表3 三个人工数据集服从的概率分布Tab.3 Probability distributions followed by three synthetic datasets

3.3 实验分析

本节主要是对在MapReduce 和Spark 平台上实现的基于随机森林的大数据样例选择进行实验对比。实验指标为测试精度、选择比、算法执行时间。

测试精度 将原数据集分为测试集和训练集，将训练集经过样例选择的数据子集进行训练为分类器，用测试集对该分类器的测试精度进行测试，测试精度越高，代表样例选择的算法越好。

选择比 选择比是所选择的样例数与原始数据集的比值，选择比的值越低，证明选择出的子集更有代表性，说明样例选择的性能好。

运行时间 样例选择算法从开始到执行结束所花费的时间。

实验结果如表4。由表4实验结果发现，在人工数据集和UCI 数据集上，MR-RF-IS 和Spark-RF-IS 算法在测试精度和选择比上数值近似相同，是因为MR-RF-IS和Spark-RF-IS在算法结构和运行逻辑上基本秉承同种思想，算法在执行样例选择时所选择的样例子集也是大致相同的，选择出的样例子集重要程度也近乎相似；但两种算法的在不同的平台上所运行的时间有着很大的差距，造成这种差距的主要原因是在MapReduce 和Spark大数据处理平台上对数据的处理采取截然不同的策略。基于随机森林的大数据样例选择在大数据计算平台上算法主要在I/O 操作和中间数据传输上消耗过多时间，其运行时间T可以分为文件读取时间Tread、中间数据传输时间Ttran、中间数据排序时间Tsort和文件输出时间Twrite；其中，文件读取时间Tread受文件读取速度和文件的影响，文件输出时间Twrite受文件输出速度和文件数量的影响。在MapReduce和Spark平台上，文件的输入输出速度和数据的数量的差异主要是受到不同平台的运行机制和读写方法影响，所以只对中间数据传输时间Ttran和中间数据排序时间Tsort造成的影响进行分析。

表4 在6个数据集上实验指标的对比Tab.4 Comparison of experimental indexes on 6 datasets

中间数据传输时间Ttran指的是将Map 执行的任务输出到Reduce 阶段作为输入所消耗的时间，主要由Map 阶段输出的文件大小和I/O 传输速度所决定，MapReduce 在处理大数据集时，首先将数据集在HDFS 进行存储，然后在Map 阶段对放在HDFS 中的数据集进行处理后再将中间数据输出到HDFS 等待Reduce阶段的处理，在Reduce阶段会根据数据的键值对数据集进行计算。而Spark作为基于内存的大数据处理平台，将Spark计算中的中间数据直接在内存中储存，只有在中间数据溢出时才会把HDFS 作为备仓库进行储存，这样会大幅度减少网络I/O操作，导致因此基于MapReduce的中间数据传输时间远大于基于Spark的中间数据传输时间。

中间数据排序时间Tsort主要是针对MapReduce平台，为了保证每一个Map 任务都对应一个有序的中间数据，Shuffle 过程会对中间数据进行排序和归并操作，当有m个Map任务时，每个Map 任务有n条数据，则在MapReduce 上对中间数据的传输时间为O(m· logn)。而在Spark 大数据处理平台上，不需要中间数据有序排列，所以其排序时间为0。所以从不论中间数据排序时间Tsort和中间数据传输时间Ttran，Spark的算法运行时间都优于MapReduce算法处理时间。

对于文件数目来讲，算法运行过程产生的中间数据会以文件形式存储，过多的数据既带来大量的I/O操作也会占用内存的存储空间，也会导致算法的运行时间增加。在MapReduce 在执行操作时，Shuffle 过程会将每个Map 节点所产生的文件都进行排序和归并操作来使数据能存储在一个文件中，但在Spark中，不需要对中间数据进行排序和归并操作，只是对数据进行合理分区，虽然会产生比MapReduce 更多的文件，但是从一定程度上减少了运行时间。

对于同步次数来说，MapReduce 是典型的同步模型，只有当所有的Map 任务完成后才可以进行Reduce 任务，而Spark是异步模型，多个节点可以单独地执行计算，这使得算法的执行效率得到了很大的提升。

综上所述，虽然在MR-RF-IS 和Spark-RF-IS 算法的程序设计上思想相同，但两个平台的计算逻辑相差较大，Spark 上虽对数据进行分区操作导致Spark 所产生的文件数远远多于MapReduce 的文件数，但在数据的传输调度上，Spark 采用导管式传输，大幅减少了同步的次数，随着迭代次数的增加在中间数据传输上优于MapReduce，所以Spark 在算法运行时间上有更好的表现。

3.4 与其他大数据样例选择算法对比

表5 是本文算法与CNN 算法和RNN 算法对相同的大数据集进行样例选择的实验结果。

表5 3种算法在各数据集上的实验结果Tab.5 Experimental results of three algorithms on different datasets

从测试精度上来看，本文提出的算法在测试精度上在大部分数据集上都能够超越CNN 和RNN 经典算法。因为随机森林分类器是集成的强学习器，有良好的泛化能力，且自身精度比其他单个算法更高，但计算开销很小，所以本文使用的随机森林分类器较KNN（KNearest Neighbor）分类器性能更好，在处理大规模数据时有很大优势。

从运算时间上来看，CNN 算法作为经典算法在规模较小的数据集的时间复杂度有一定的优势，但是在处理规模较大的数据集时，所花费的时间较多；而RNN 算法在随着数据规模的扩大，时间复杂度也随之大幅增长，当数据集到达一定规模后就无法对其进行处理；而本文提出的RF-IS 算法在规模较小的数据集中算法在运行时间上表现稳定，当数据达到一定规模后，也能在保证选择比足够小的情况下，可以花费比较少的时间处理大规模的数据集。

综上所述，本文提出的RF-IS 算法在保证测试精度和一定选择比的情况下，RF-IS算法对规模更大的数据集表现稳定并且算法运行时间更短，代表RF-IS 算法在大数据样例选择性能上更加出色，表现更加稳定。

4 结语

本文提出了基于随机森林的大数据投票样例选择算法，并分别在MapReduce和Spark大数据处理平台上进行了实现，在此基础上不仅对两个大数据处理平台进行了实验比较，而且还与经典样例选择算法CNN 和RNN 进行了实验比较。从对两个大数据平台的实验对比来看，因为平台差异，在算法运行时间上有较为明显的差异，在其余的实验指标上均近似相同。从提出的算法与CNN和RNN的实验比较的结果来看，在保证测试精度和一定的选择比的情况下，本文提出的算法对规模更大的数据集进行计算时，表现更加稳定且具有更低的计算时间复杂度，RF-IS算法在大数据样例选择上性能更加稳定，表现更加出色。综上所述，本文提出的算法是行之有效的。