英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料

基于Spark云计算环境中的大数据并行随机森林算法

Jianguo Chen, Kenli Li, Senior Member, IEEE, Zhuo Tang, Member, IEEE,

Kashif Bilal, Shui Yu, Member, IEEE, Chuliang Weng, Member, IEEE, and Keqin Li, Fellow, IEEE

摘 要

随着大数据时代的到来，如何有效并准确的从数据集中获取有价值的信息引起了学术界和工业界越来越多的关注。本文提出了一种并行随机森林算法（PRF）用于在Apache Spark平台上的大数据处理。基于结合数据并行和任务并行的混合方法对PRF算法进行了优化。从数据并行优化的角度出发，执行垂直数据划分的方法有效降低了数据通信成本，并且执行数据复用方法使得训练数据集能够被再利用以及减少了数据量。从任务并行优化的角度出发，在RF的训练过程实施了双重并行方法，根据PRF的并行训练过程和弹性分布式数据集（RDD）对象的依赖关系创建了有向无环图（DAG）。然后，为DAG中的任务调用不同的任务计划程序。此外，为了提高算法对大型，高维和嘈杂数据的准确性，我们在训练过程中执行了降维方法以及在并行化前的预测过程中实行了加权决策方法。广泛的实验结果指出PRF算法相对于Spark MLlib实现的相关算法以及关于分类准确性，性能和可伸缩性的其他研究有着较大的优越性和显著的优势。

关键词：Apache Spark，大数据，云计算，并行数据，随机森林，并行任务

1 介绍

1.1 研究目的

随着很多新的信息传播方式的持续兴起以及云计算和物联网（IoT）技术的发展，数据不断高速增长。全球数据的规模以每两年两倍的速率不断增长[1]。数据在各个领域的应用价值变得极其重要。在可用的数据中存在大量有价值的信息。

除了明显的好处之外，大数据时代的出现也带来了严重的问题和挑战。由于业务需求和竞争压力，几乎每个业务对数据处理的实时性和有效性都有很高的要求[2]。因此，第一个问题是如何有效，准确地从海量数据中挖掘有价值的信息。同时，大数据具有高维度，复杂性和噪声等特征。大量数据通常在输入变量中包含数百或数千个级别的的属性，甚至每一个都包含一部分很小的信息。第二个问题是选择适当的技术，这些技术可能会为高维数据集带来良好的分类性能。考虑到上述事实，大数据的数据挖掘和分析已成为学术界和工业研究的热点。

大规模数据的数据挖掘和分析速度也引起了学术界和工业界的极大关注。基于云计算平台的分布式并行数据挖掘研究取得了丰硕的成果[3，4]。Hadoop[5]是一种常见的广泛用于数据挖掘的云平台。基于MapReduce模型提出了一些机器学习算法[6，7]，但是，当基于MapReduce实现这些算法时，在每次迭代中获得的中间结果将被写入Hadoop分布式文件系统（HDFS）并从中加载。这会花费大量时间进行磁盘I / O操作，并且还会花费大量资源用于通信和存储。Apache Spark[8]是另一个适用于数据挖掘的良好云平台。与Hadoop相比，Spark支持在内存计算框架上构建的弹性分布式数据集（RDD）模型和有向无环图（DAG）模型。它允许我们将数据缓存存储在内存中，并直接从内存中对相同数据执行计算和迭代。Spark平台节省了大量的磁盘I / O操作时间。因此，它更适合于具有迭代计算的数据挖掘。

随机森林（RF）算法[9]是适用于大数据的数据挖掘算法。这是一种使用特征子空间构建模型的集成学习算法。此外，所有决策树可以同时训练，因此也适合并行化。

1.2 本文贡献

在本文中，我们提出了一种在Apache Spark平台上实现针对大数据的并行随机森林（PRF）算法，PRF算法是基于结合了数据并行和任务并行优化的混合方法进行优化的。为了提高PRF的分类精度，在并行处理之前进行了优化。大量的实验结果表明了PRF的优越性，并且在分类精度和性能方面都比其他算法有明显的优势。我们在本文中的贡献总结如下。

bull;为了提高PRF的准确性，提出了一种优化方法，该方法包括训练过程中的降维方法和预测过程中的加权投票方法。

bull;利用数据并行和任务并行优化相结合的PRF混合并行方法来提高算法的性能。在数据并行优化中，采用了垂直数据划分和数据多路复用的方法。

bull;基于数据并行优化，提出并在Spark上实现任务并行优化。基于RDD模型构造了PRF的训练任务DAG，并调用了不同的任务调度程序来执行DAG中的任务，从而显着提高了PRF的性能。

本文的其余部分安排如下。第2章回顾了相关工作。第3章从两个方面给出了RF算法的优化。在第4节章开发了在Spark上并行执行RF算法的方法，在第5章中显示了关于分类准确性和性能的实验结果和评估。最后，第6章介绍了结论和未来的工作。

2 相关工作

尽管传统的数据处理技术针对于小规模和低维的数据集取得了良好的成绩，但是它们很难有效地用于大规模的数据[10-12]。当处理的数据集更加复杂时，也即其具有复杂结构，高维度，以及规模较大的特点，那么传统的数据挖掘算法的准确性和效果将会显著地下降[13]。

由于需要解决高维和有噪声的数据，研究人员介绍了各种改进方法。Xu[14]提出了一种用于高维数据配准的降维方法。该方法将数据集结合起来，得到具有详细纹理的图像对，从而改进了图像配准。Tao[15]和Lin[16]等人介绍了集中分类算法用于高维数据的降维问题，这些算法利用多核学习框架和多级最大边缘特征，实现了二值分类问题的有效降维。Strobl [17]and Bernard [18]研究了RF的可变重要性度量并提出了一些改进模型。Taghi[19]等人比较了增长和捕获技术，提出来一种用于噪声和不平衡数据的算法。Yu[20]和Biau[21]专注于研究高维和嘈杂数据的RF算法并将RF算法应用到许多应用，比如多类动作检测和面部表情检测中，并且取得了不错的成果。根据现有的研究结果，我们在本文中提出了一种新的优化方案来解决高维和嘈杂数据的问题，他根据RF算法的结构减少了数据的维度并在更低的计算成本花费条件下提高了算法的准确度。

针对大规模数据分类算法的性能，人们提出了大量的并行/分布式计算与树模型学习的交叉研究。Basilico等人[22]提出了一种基于MapReduce的COMET算法，该算法在分布式数据块上建立多个RF信号群。Svore等人[23]提出了一种改进的决策树排序算法，该算法通过分布式计算来解决速度和内存的限制。Panda等人[24]提出了一种基于MapReduce的可扩展分布式框架，用于大型数据集上树模型的并行学习。[25]提出了一种并行增强回归树算法，对于web搜索排名，提出了一种基于数据分割和分布式计算的并行训练GBRT的新方法。

Warneke[26]等人主要关注并行和分布式环境中的资源分配和任务并行执行，实现了云环境中高效并行数据处理的动态资源分配。莉娜等人[27]为大数据应用程序执行了MapReduce作业的能源感知调度。路易斯等人[28]在数据集到达时间不确定的异构并行系统上，提出了一种稳健的数据处理资源分配方法。Zhang等人[29]提出了一种弹性云环境下大数据分析动态多任务工作负载的动态调度方法。同时，我们的团队也专注于异构集群和分布式系统的并行任务调度，并取得了积极的成果[30，31]。

Apache Spark Mllib[32]在数据并行优化的基础上，对RF算法（本文称为Spark MLRF）进行了并行化，提高了算法的性能。然而，Spark-MLRF存在许多缺点。首先，在确定连续特征的最佳分割段阶段，采用对数据集的每个分区进行采样的方法来减少数据传输操作。然而，这种方法的代价是其精度降低。另外，由于Spark-MLRF中的数据分割方法是水平分割，因此特征变增益比计算的数据通信是全局通信。

为了提高RF算法的性能，降低并行和分布式环境下大规模数据的数据通信成本和工作负载均衡问题，提出了一种基于Spark-RDD和DAG模型的数据并行与任务并行相结合的混合并行RF算法。与已有的研究结果相比，该方法在不降低算法精度的前提下，减少了训练数据集的体积。此外，我们的方法减轻了在并行和分布式环境中大数据的数据通信和工作负载不平衡问题。

3 随机森林算法的优化

由于提高了对高维和大规模数据的分类精度，我们提出了一种针对RF算法的优化方法。首先，在训练过程中执行降维方法。其次，在预测过程中构造了加权投票方法。经过这些优化，算法的分类精度明显提高。

3.1 随机森林算法

随机森林算法是基于决策树模型的集成分类器算法。它使用引导抽样方法从原始数据集中生成k个不同的训练数据子集，然后通过训练这些子集构建k个决策树。这些决策树最终构成了一个随机森林。测试数据集的每个样本都由所有决策树预测，并且最终分类结果将根据这些决策树的决策返回。

原始训练数据集形式化为S=，其中x是一个样本，y是S的特征变量。即，原始训练数据集包含N个样本，每个样本中有M个特征变量。RF算法构建的主要过程如图1所示。

图1. RF算法构建的过程

随机算法的构建步骤如下。

第一步，采样K个训练子集。

在该步骤中，以bootstrap采样方式从原始训练数据集S中采样k个训练子集。即，在每个采样时间中通过随机采样和替换方法从S中选择N个记录。在当前步骤之后，将k个训练子集构建为训练子集的集合。

.

同时，将在每个采样周期中不选择的记录组合成袋外（OOB）数据集。这样，将k个OOB集构造为的集合。

.

此时有且. 为了获得每个树模型的分类精度，这些OOB集在训练过程后用作测试集。

第二步，创建每个决策树模型。

在RF模型中，通过C4.5或CART算法从每个训练子集S 1创建每个元决策树。在每棵树的生长过程中，从M个变量中随机选择m个数据集Si的特征变量。在每个树节点的拆分过程中，将计算每个特征变量的增益比率，并选择最佳的一个作为拆分节点。重复该拆分过程，直到生成叶节点为止。最后，以相同的方式从k个训练子集中训练k个决策树。

第三步，将k个树收集到一个RF模型中。

将k个树收集到一个RF模型中是由公式1决定的。

其中是元决策树分类器，是训练数据集的输入特征向量，而是确定树的生长过程的独立且分布均匀的随机向量。

3.2 高维数据的降维

为了提高针对高维数据的RF算法的准确性，我们提出了一种新的降维方法，以根据特征变量的重要性减少维数。在每个决策树的训练过程中，训练子集的每个特征变量的增益比（GR）均按降序计算和排序。选择有序列表中的前k个变量（）作为主变量，然后，从其余（）个变量中随机选择（）个其他变量。因此，数据集的维数从M减少到m。降维过程如图2所示。

图2. 训练过程中的降维

首先，在每个决策树的训练过程中，每个特征变量的熵是在节点拆分过程之前计算的。在训练子集中目标变量的熵由公式2决定。

其中c1是中目标变量的不同值的数量，是目标变量子集中所有类型中值a的类型的概率。

第二，计算除了目标变量以外的每个输入变量的熵，每个输入变量的熵由公式3决定。

其中公式3的元素描述在表1中。

图表1 公式3元素的描述

第三，计算每个输入变量的自分裂信息，由公式4得到。

其中c2是不同值的数量，是变量中所有类型中值a的类型的概率。然后，计算每个特征变量的信息增益，如公式5所示。

（5）

其中)。

通过使用信息增益来测量特征变量，可以很容易地选择最大值，但这会导致过度拟合的问题。为了克服这个问题，采用增益比值来测量特征变量，并选择具有最大值的特征。特征变量的增益比在公式6中定义。

为了减少训练数据集的维数，我们根据变量的增益比来计算每个特征变量的重要性。然后，我们选择最重要的功能并删除不重要的功能。每个特征变量的重要性定义如下。

定义1：训练子集中每个特征变量的重要性是指特征变量的增益比与总特征变量相比的部分。特征变量的重要性在公式7中定义为：

所有特征变量的重要性值按降序排列，并且前k个（）值被定义为最重要。然后，我们从其余（M-k）个中随机选择（m-k）个其他特征变量。因此，数据集的维数从M减少到m。以训练子集Si为例，算法3.1中给出了训练过程中降维的详细步骤。