Spark平台加权分层子空间随机森林算法研究

来源:用户上传      作者:

　　摘 要：如何在各式大数据中更快更准确地挖掘有用信息是研究热点。随机森林算法作为一种重要的机器学习算法，适用于大部分数据集。随机森林算法可以并行运行，这是随机森林算法处理大数据集时的优势。将随机森林算法应用在大数据处理框架Spark上，提高了随机森林算法处理大数据集时的速度。首先对随机森林进行参数调优，找到当前数据集的最优参数组合，采用随机森林模型对特征进行重要度计算，筛选掉噪声数据;然后采用卡方检验对数据集的特征进行分层，实现分层子空间随机森林并验证准确率和袋外精度;最后在传统分层子空间随机森林基础上对分层子空间进行加权改进。实验证明改进后的随机森林算法准确率提高了3%，袋外估计精度提高了1%。
　　关键词：随机森林;Spark;大数据处理;特征选择
　　DOI：10. 11907/rjdk. 191691
　　中图分类号：TP312   文献标识码：A                 文章编号：1672-7800（2020）003-0120-05
　　Research of Random Forest Algorithm Using Weighted Stratified Subspace
　　Based on Spark Platform
　　JING Jing，ZHU Yong-zhi
　　（School of Information Science and Engineering，Qufu Normal University，Rizhao 276826，China）
　　Abstract：How to find useful information out of all kinds of big data faster and more accurately becomes an import problem in the time. As an important machine learning algorithm， random forest algorithm is flexible and suitable for most data sets. The random forest algorithm can run in parallel，this is an advantage when dealing with large data sets. The application of random forest algorithm to big data processing framework Spark can greatly improve the speed of running and processing big data of random forest algorithm. Firstly，the parameter of the random forest were optimized to find the optimal combination of parameters of the current data set. The importance of features are calculated to delete the useless feature by random forest model. Then， chi-square test is used to stratify the features of the data set to achieve the verification accuracy and out-of-bag accuracy of random forest using stratified subspace. Finally， on the basis of the traditional random forest using stratified subspace， the stratified subspace is improved by weighting. The experimental results show that the improved random forest algorithm improves the prediction accuracy by 3% and the out-of-bag estimation accuracy by 1%.
　　Key Words：random forest; Spark; big data processing; feature selection
　　0 引言
　　大数据具有数据量大、类型多样和价值密度低等特点，如何在大数据中快速且准确地挖掘信息成为亟待解决的问题。决策树算法作为一种经典的数据挖掘算法，既可作为分类算法，又可作为回归算法，但是单一的决策树在处理数据时容易产生过拟合问题，因此在2001年出现了随机森林算法。对运行在单机上的随机森林算法研究已经相对成熟，近年来的研究是将随机森林并行运行以提高其性能。Apache Spark是大数据机器学习中最受欢迎的平台之一，它受益于分布式架构和自动数据并行化。Apache Spark MLlib为各种机器学习任务提供支持，包括回归、降维、分类、聚类和规则提取[1]。
　　文献[2]将随机森林算法应用在Spark平台，并在投票时根据不同决策树预测准确度对其进行加权，有效提高了算法准确度。但是对于具有高维特征的大数据，随机森林在处理数据时运行时间过长，而且噪声数据也会对结果准确率产生影响;文献[3]在Spark平台上运用随机森林算法进行特征选择，对冗余数据和噪声数据进行筛选，并采用方差分析和后向序列选择进行降维，提高了随机森林算法的准确度。但方差分析和后向序列選择方法在进行特征筛选时，要自身把握度量标准，因而容易将有用特征删除;文献[4]针对不平衡大数据提出一种启发式自举抽样方法，结合保险大数据在Spark平台上实验，证明具有良好性能。但其只针对保险大数据集进行改进，只对某一类大数据集有效;文献[5]提出了一种基于Flayed边界点的随机森林算法，这种算法在处理具有离散连续属性的样本时可降低时间复杂度;文献[6]提出了基于粗糙集的随机森林算法，将粗糙集理论应用于特征选择中，但是仍然无法完全消除噪声数据的影响;文献[7]提出用分层子空间方式处理高维大数据，将特征分为强特征层和弱特征层，然后在不同的特征层进行取样，预测结果准确率有一定提高。但是其对不同层采用了等比例方式进行采样，也容易产生噪声数据。本文首先在Spark平台上对随机森林算法进行参数调优，采用特征评估方法对特征进行重要度计算，并删除噪声特征，然后对传统分层子空间进行实验，验证其准确率。针对传统分层子空间等比例抽样所得结果受噪声数据影响较大从而影响准确度的不足，对分层子空间进行加权，并对加权分层子空间随机森林的准确率与原始分层子空间随机森林算法准确率进行比较，发现加权抽样时所得结果最优。实验证明经过加权的随机森林算法准确率提升了3%，袋外估计准确率也有提升。 　　1 随机森林算法
　　随机森林（Random Forest，RF）是一种组合分类器，它首先训练多棵决策树，训练完成后将其组合成随机森林模型，然后运用随机森林模型进行预测。随机森林应用广泛，如用于预测疾病风险[8]、遥感社区[9]和保险[10]等等。
　　1.1 决策树
　　决策树（decision tree）指以树的形式进行分类预测的模型。决策树在节点划分时就是要寻找一种最纯净的划分方法，在数学中称之为纯度，分裂属性使得孩子节点的数据划分得最纯。
　　1.1.1 熵
　　熵（entroy）表示数据的混乱程度，熵与混乱程度呈正比，熵变大时混乱程度也变高。
　　定义1：对类别为随机变量X的样本集合D，假设X有k个类别，每个类别的概率为[CkD]，其中[Ck]表示类别k的样本个数，[D]表示样本总数，则样本集合D的熵公式如下：
　　1.1.2 基尼值
　　定义2：设[pi]为类别i在样本D中出现的概率，基尼指数公式如下：
　　基尼指数被定义用来衡量节点纯度，基尼指数与纯度成反比关系，即基尼指数变大时节点纯度会变低。
　　决策树理解起来比较简单，但是它可能会出现过度分割样本空间问题，导致决策树算法复杂度很高，并且会出现过拟合。为了解决这些问题，针对决策树缺点提出随机森林算法。随机森林算法是对决策树算法的一种集成，可以有效避免过拟合。
　　1.2 随机森林
　　定义3：假设数据集为D={Xi，Yj}，Xi∈R，Yi∈{1，2，…，C}，随机森林是在数据集上以M个决策树{g（D，θm}，m=1，2，…，M}为基分类器进行集成学习后得到的一个组合分类器。
　　随机森林算法创建过程分为3个步骤：①划分训练样本子集;②训练随机森林;③预测。随机森林算法的随机性体现在它不仅在取样时采用随机取样，在特征选择时也是随机抽取，然后从中采用最佳属性进行分裂。
　　1.2.1 卡方检验
　　卡方检验是衡量两个变量相关性的一种检验方法[11]。
　　定义4：对于数据集D，使用[X={x1，？，xk}]表示样本，使用[Y={y1，？，yq}]表示类别，使用[A={A1，？，AM}]表示特征，而对于每一个特征，假设特征[Ai]有p个不同取值，当[Ai=al]时， [Y=yj（j=1，？，q）]的D子集大小为[vallj]，特征[Ai]与类别之间的信息量公式如下：
　　其中，[vallj]为观察频数，即表示为实际发生的频数，[tlj]为期望频数。期望函数取值为：
　　特征和类别之间的相关性越强，特征分类新事物的能力也越强，因此将卡方检验应用在随机森林算法的特征选择中，检测特征与类别之间的关系。根据相关性将特征划分为强特征和弱特征层，在进行特征选择时在不同层进行抽样，增强单棵树的分类强度，不增加树之间的相关性。
　　傳统的分层子空间随机森林算法在不同层进行等比例取样，能保证结果最优。
　　1.2.2 随机森林特征评估
　　大数据价值很高，但也有许多问题，其中最重要的是降维，特别是特征选择[12]。对高维样本进行降维方法有多种，如T-test检测、序列后向选择[13]等，本文采用随机森林模型进行特征筛选，特征评估衡量标准为Gini指数变化量。
　　定义5：特征Xi在节点m上的重要性即节点m分枝前后的Gini指数变化量，其公式如下：
　　其中GIl和GIr分别表示以特征m进行分裂后左右两个孩子节点的Gini指数。
　　在使用卡方检验将特征子空间分层后，对每个特征进行特征评估得到一个评估值，对层内每个特征的重要度进行累加得到层的权重。
　　定义6：设每层有r个特征[Ai]（i=1，…r），定义层权重公式为：
　　1.2.3 袋外估计
　　袋外数据（OOB，out-of-bag）即未被抽取到的训练数据[14]。对随机森林每棵树而言，建树时采用随机并且有放回地进行抽取，所以每棵树大约有1/3的数据未被抽到，这些数据称为袋外数据。因为未参与建模过程，因此用这些数据对随机森林模型进行评估结果较为可信。
　　使用袋外数据进行评估得到的正确率称为袋外正确率。袋外估计可以作为泛化误差估计的一部分，使得随机森林算法不再需要交叉验证。
　　1.3 随机森林算法特点
　　现实生活中的大多数数据分析都是分类和回归问题，而随机森林算法既可作为分类算法，又可作为回归算法。近年来随机森林算法广受欢迎，应用在各种领域，如银行、股票市场和医药行业等等。随机森林在处理各种问题时发挥着强大的优势，它的优点主要有：①具有良好的准确率;②训练速度快，能够运行在大数据集上;③能够处理高维特征样本;④可以评估特征在模型中的重要程度;⑤可以在模型生成过程中取得真实误差的无偏统计;⑥容易并行化。
　　2 Spark
　　2.1 Spark介绍
　　因为数据量超过了单机所能处理的极限，所以用户需要新的架构将计算扩展到多个节点进行，以应对不同工作负载的新集群编程模型数量的飞速增长[15]。Spark自2010年发布以来已成为最活跃的大数据处理计算引擎，广泛应用在金融、生物技术和天文学等多个领域[16]。
　　Spark基于弹性分布式数据集（RDD）[17]。RDD是一种可并行计算的集合，它不可变并且可被分区，可以由存储的数据或其它RDD生成，是最基本的数据抽象。RDD？有转化和行动两种类型操作，转化操作主要由一个已知RDD转化为一个新的RDD。行动操作在应用一组操作后将记录/值返回给主程序。这两个操作之间的主要区别在于它们何时以及如何应用于数据。
　　Spark提供一系列组件支持数据处理。Spark shell提供多个API使得交互式数据分析更方便快捷。Spark SQL提供交互式查询。Spark streaming用于处理实时数据组件，提供流式数据计算;Mllib库支持数据分析等，包含大量机器学习算法[18];GraphX对图计算提供支持。这些组件提供给用户的都是jar包，使用时无需部署、维护等复杂操作，在Spark平台上可直接使用，充分体现了Spark的通用性。Spark可以独立安装使用，也可与其它平台配合使用。Spark架构如图1所示。 　　2.2 基于Spark的隨机森林算法
　　由于随机森林算法基于多个独立树定义，因此可以直接并行随机森林方法并更快地将其实现，其中许多树在不同的核上并行构建[19]。随机森林模型如图2所示。
　　基于Spark的随机森林建模过程：①从hdfs读取训练数据集并将其设置为广播变量，压缩为一个forest列表;②将不同的训练样本子集分发给不同的从机进行决策树训练。主机从各个从机收集训练完成的子森林组合成随机森林，将测试集分成一定大小的块并分发给从机进行预测，主机收集并返回预测结果。
　　基于Spark平台的随机森林主要对训练过程和预测过程进行并行化[20]，这样不仅增大了可处理的数据量，也加快了运行速度。
　　3 实验
　　3.1 实验数据与环境
　　本文采用Semeion手写字数据集，该数据每个记录代表一个手写字，有256个特征。实验环境为Windows上的ubuntu虚拟hadoop集群，集群包含3个节点，采用HDFS存储文件，集群管理器为YARN，编程语言为Python。
　　3.2 实验结果与分析
　　将数据集以7∶3拆分为训练集和测试集。对随机森林进行参数调优，包括控制树的数量和选择合适的特征比例两个方面，实验准确率如图3所示。
　　分别选取随机森林规模为10，50和100，特征选取比例分别为0.1，0.5和0.8进行实验。从实验结果可以看出，当特征比选为0.5时，随机森林预测准确度达到最高，当特征比例选择更大时，准确率不升反降，此时准确率可能受到噪声数据的影响。对随机森林规模选取进行测试，发现随着随机森林规模的变大准确率也会上升，但对于当前数据而言，随机森林规模在50和100的准确率并未增长，反而增加了程序运行时间，所以对特定数据集选取合适的森林规模对算法性能有很重要的影响。
　　对数据集进行特征评估操作，将评估结果归一化，对每个特征评估出一个重要度，所有特征重要度相加为1，计算出一些特征为0的噪声特征，将这些特征删除。有效降维使算法的准确度和运行时间都有提升，有利于提升算法性能。
　　降维后开始进行分层子空间随机森林实验。该实验分3组进行，分别为：①强弱特征层等比例抽样;②仅在强特征层抽样;③仅在弱特征层抽样。验证3组实验结果准确率，如图4所示。
　　从实验结果可以看出，强特征层和弱特征层的结果相差较大，在强特征层进行抽样时的实验结果优于等比例抽样，所以在强弱特征层进行等比例抽样算法有待优化。
　　对不同层进行特征重要度计算，然后记为层重要度，根据重要度比例进行抽样，实验结果与原始结果对比见图5。
　　从实验结果可以看出，加权后的分层子空间随机森林算法较原始随机森林算法准确度有所提升，袋外准确度也有提升。
　　由以上实验可知，优化后的随机森林算法预测精度有一定提升，有效降维减少了算法运行时间，提高了算法性能。将优化后的随机森林算法应用在Spark平台上，可对大数据进行高效处理。
　　4 结语
　　本文首先对随机森林进行参数调优，找到最合适的参数组合。在调参过程中发现过大的特征比使噪声对随机森林准确率有明显影响;然后使用随机森林模型对数据集进行特征评估，去除掉一些噪声数据，对筛选后的特征进行卡方检验操作，将特征分为强弱特征层;分层后对不同层进行权重计算，按照权重比例取样，训练随机森林模型，进行分类预测。实验结果表明随机森林预测准确度明显提升，袋外正确率也有一定提升。
　　本文在进行特征分层时没有考虑冗余数据影响，因为特征维度较大，冗余数据的计算量也较大。下一步将研究一种优化的冗余特征处理方式。
　　参考文献：
　　[1]ASSEFI M，BEHRAVESH E. Big data machine learning using Apache Spark MLLIB[C]. 2017 IEEE International Conference on Big Data （Big Data）.  IEEE， 2017： 3492-3498.
　　[2]CHEN J， LI K， TANG Z， et al. A parallel random forest algorithm for big data in a spark cloud computing environment[J]. IEEE Transactions on Parallel and Distributed Systems， 2017， 28（4）： 919-933.
　　[3]SUN K， MIAO W， ZHANG X， et al. An improvement to feature selection of random forests on spark[C]. 2014 IEEE 17th International Conference on Computational Science and Engineering，2014：774-779.
　　[4]DEL RíO S， LóPEZ V， BENíTEZ J M， et al. On the use of mapreduce for imbalanced big data using random forest[J]. Information Sciences， 2014（285）： 112-137.
　　[5]XY Y. Research and implementation of improved random forest algorithm based on spark[C]. 2017 IEEE 2nd International Conference on Big Data Analysis，2017： 499-503. 　　[6]罗元帅.  基于随机森林和Spark的并行文本分类算法研究[D]. 成都：西南交通大学，2016.
　　[7]牛志华.  基于Spark分布式平台的随机森林分类算法研究[D]. 天津：中国民航大学，2017.
　　[8]KHALILIA M，CHAKRABORTY S，POPESCU M. Predicting disease risks from highly imbalanced data using random forest[J].  BMC Medical Informatics and Decision Making， 2011， 11（1）： 51-59.
　　[9]BELGIU M，DRAGUT L.Random forest in remote sensing： a review of applications and future directions[J]. ISPRS Journal of Photogrammetry and Remote Sensing， 2016（114）： 24-31.
　　[10]LIN W， WU Z， LIN L， et al. An ensemble random forest algorithm for insurance big data analysis[J]. IEEE Access， 2017（5）： 16568-16575.
　　[11]张思琪. 基于改进贝叶斯分类的Android恶意软件检测[J]. 无线电通信技术，2014，40（6）：73-76.
　　[12]DAGDIA Z C， ZARGES C，BECK G，et al. A distributed rough set theory based algorithm for an efficient big data pre-processing under the Spark framework[C]. 2017 IEEE International Conference on Big Data （Big Data）.  IEEE， 2017： 911-916.
　　[13]RUAN F， QI J， YAN C， et al. Quantitative detection of harmful elements in alloy steel by LIBS technique and sequential backward selection-random forest （SBS-RF）[J]. Journal of Analytical Atomic Spectrometry，2017，32（11）： 2194-2199.
　　[14]馬晓东. 基于加权决策树的随机森林模型优化[D]. 武汉：华中师范大学，2017.
　　[15]ZAHARIA M， XIN R S， WENDELL P， et al. Apache Spark： a unified engine for big data processing[J]. Communications of the ACM， 2016， 59（11）： 56-65.
　　[16]梁彦.  基于分布式平台Spark和YARN的数据挖掘算法的并行化研究[D]. 广州：中山大学，2014.
　　[17]迟玉良，祝永志. 项目相似度与ALS结合的推荐算法研究[J]. 软件导刊，2018，17（6）：81-84.
　　[18]唐振坤. 基于Spark的机器学习平台设计与实现[D]. 厦门：厦门大学，2014.
　　[19]GENUER R，POGGI J M，TULEAUL C， et al. Random forests for big data[J].  Big Data Research， 2017（9）： 28-46.
　　[20]孙科.  基于Spark的机器学习应用框架研究与实现[D]. 上海：上海交通大学，2015.
　　（责任编辑：杜能钢）
　　收稿日期：2019-05-13
　　基金项目：山东省自然科学基金项目（ZR2013FL015）;山东省研究生教育创新资助计划项目（SDYY12060）
　　作者简介：荆静（1995-），女，曲阜师范大学信息科学与工程学院硕士研究生，研究方向为分布式计算、大数据;祝永志（1964-），男，曲阜师范大学信息科学与工程学院教授、硕士生导师，研究方向为并行与分布式计算、网络数据库。
转载注明来源:https://www.xzbu.com/8/view-15217858.htm