一种面向大数据分析的快速并行决策树算法

陆旭 陈毅红 熊章瑞 廖彬宇

引用本文:
Citation:

一种面向大数据分析的快速并行决策树算法

    作者简介: 陆旭(1995−),男,四川人,硕士生,研究方向:云计算、大数据. E-mail:1475075634@qq.com;
    通讯作者: 陈毅红, cyhswpi@126.com
  • 中图分类号: TP301.6

A fast parallel decision tree algorithm for big data analysis

    Corresponding author: CHEN Yi-hong, cyhswpi@126.com ;
  • CLC number: TP301.6

  • 摘要: 为了提高基于大规模数据的决策树训练效率,提出了一种基于Spark平台的并行决策树算法(SPDT). 首先,采用数据按列分区的方法,把单个属性列完整地保留在一个分区内,使缓存该分区数据的数据节点能独立完成信息熵的计算,以减少数据节点之间的信息交流造成的网络资源的占用. 然后,数据在按列分区后以稠密向量的形式缓存于内存中,SPDT对数据进行压缩,以减少对内存的占用. 最后,SPDT采用基于边界点类别判定的连续属性离散化方法来处理连续属性,减少决策树训练过程中信息熵计算的频次,并提出使用信息增益比划分训练数据集的方法,以减少信息增益计算对多属性值属性的依赖. 实验结果表明,在树的训练效率方面,SPDT在保持分类精度的情况下,比Apache Spark-MLlib决策树算法(MLDT)以及基于Spark平台的垂直划分决策树算法(Yggdrasil)有明显的提升.
  • 图 1  边界点T存在的位置

    Figure 1.  The location of boundary point T

    图 2  按列分区

    Figure 2.  Partition by column

    图 3  不同方法平均分类精度(随机选择的训练数据集和测试数据集)

    Figure 3.  Average classification accuracy of different methods (randomly selected training data set and test data set)

    图 4  不同方法平均分类精度(相同的训练数据集和测试数据集)

    Figure 4.  Average classification accuracy of different methods (same training data set and test data set)

    图 5  随着实例数增加决策树训练时间的变化(28个属性)

    Figure 5.  Change in training time of the decision tree as the number of instances increases (28 attributes)

    图 6  随着属性数增加决策树训练时间的变化(120,000个实例)

    Figure 6.  Change in training time of the decision tree as the number of attributes increases (120,000 instances)

    表 1  选自UCI机器学习库的数据集

    Table 1.  Data set selected from UCI machine learning database

    数据集实例个数属性数
    HEPMASS10 500 000  28  
    YouTube Video120 000  1 000 000  
    URL Reputation2 396 130   3 231 961  
    下载: 导出CSV

    表 2  平均分类精度

    Table 2.  Average classification accuracy

    数据集MLDTYggdrasilSPDT
    HEPMASS0.8970.7020.874
    YouTube Games0.6890.6210.721
    URL Reputation0.7330.6140.708
    下载: 导出CSV

    表 3  平均训练时间(单位:s)

    Table 3.  Average training time (Unit: s)

    数据集MLDTYggdrasilSPDT
    HEPMASS163.2132.7 93.21
    YouTube Games380.5264.6182.7
    URL Reputation243.2 160.7 90.4
    下载: 导出CSV
  • [1] Kumar A, Singh T R. A new decision tree to solve the puzzle of Alzheimer's disease pathogenesis through standard diagnosis scoring system[J]. Interdisciplinary Sciences Computational Life Sciences, 2016, 275(4): 1-9. DOI:  10.1007/s12539-016-0144-0.
    [2] Rathore S S, Kumar S. A decision tree logic based recommendation system to select software fault prediction techniques[J]. Computing, 2017, 99(3): 255-285. DOI:  10.1007/s00607-016-0489-6.
    [3] Boukhris I, Elouedi Z, Ajabi M. Toward intrusion detection using belief decision trees for big data[J]. Knowledge & Information Systems, 2017, 53(3): 671-698. DOI:  10.1007/s10115-017-1034-4.
    [4] Xiao J, Stolkin R, Leonardis A. Dynamic multi-level appearance models and adaptive clustered decision trees for single target tracking[J]. Pattern Recognition, 2017, 69: 4 978-4 987. DOI:  10.1109/j.patcog.2017.04.001.
    [5] Asselt E D V, Noordam M Y, Pikkemaat M G, et al. Risk-based monitoring of chemical substances in food: prioritization by decision trees[J]. Food Control, 2018, 93: 112-120. DOI:  10.1016/j.foodcont.2018.06.001.
    [6] Han J, Kamber M, Pei J.Data mining: Concepts and techniques[M]. Amsterdam, The Netherlands: Elsevier, 2011.
    [7] 王熙照, 孙娟, 杨宏伟, 等. 模糊决策树算法与清晰决策树算法的比较研究[J]. 计算机工程与应用, 2003, 39(21): 72-75. DOI:  10.3321/j.issn:1002-8331.2003.21.024. Wang X Z, Sun J, Yang H W, et al. A comparison between fuzzy and crisp decision trees[J]. Computer Engineering and Applications, 2003, 39(21): 72-75.
    [8] Quinlan J R. Induction of decision trees[J]. Machine Learning, 1986, 1(1): 81-106. DOI:  10.1007/BF00116251.
    [9] Everitt B S. Classification and regression trees[M]. Encyclopedia of Statistics in Behavioral Science, John Wiley & Sons, Ltd, 2005.
    [10] Yuan Y, Shaw M J. Induction of fuzzy decision trees[J]. Fuzzy Sets & Systems, 1995, 69(2): 125-139. DOI:  10.1016/0165-0114(94)00229-z.
    [11] Wang X C, Liu X D, Witold P. Fuzzy rule based decision trees[J]. Pattern Recognition, 2015, 48(1): 50-59. DOI:  10.1016/j.patcog.2014.08.001.
    [12] Zeinalkhani M, Eftekhari M. Fuzzy partitioning of continuous attributes through discretization methods to construct fuzzy decision tree classifiers[J]. Information Sciences, 2014, 278: 715-735. DOI:  10.1016/j.ins.2014.03.087.
    [13] Apache Spark: Machine Learning Library (MLlib) Guide Decision Trees - spark.mllib[EB/OL]. http://spark.apache.org/docs/1.6.0/mllib-decision-tree.html, 2019-09-16.
    [14] Chen J, Wang T, Abbey R, et al. A distributed decision tree algorithm and its implementation on big data platforms[C]. IEEE International Conference on Data Science & Advanced Analytics. IEEE, Montreal, Canada,2016: 752-761. DOI: 10.1109/DSAA.2016.64.
    [15] Anitha M, Bharathi S D, Ilakiya K, et al. On distributed fuzzy decision trees for big data[J]. IEEE Transactions on Fuzzy Systems, 2018, 26(1): 174-192. DOI:  10.1109/TFUZZ.2016.2646746.
    [16] Abuzaid F, Bradley J K, Liang F T, et al. Yggdrasil: An optimized system for training deep decision trees at scale[C]. Advances in Neural Information Processing Systems. Barcelona, Spain. 2016: 3817-3825.
    [17] Chen J, Li K, Member S, 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. DOI:  10.1109/TPDS.2016.2603511.
    [18] Fayyad U M, Irani K B. On the handling of continuous-valued attributes in decision tree generation[J]. Machine Learning, 1992, 8(1): 87-102. DOI:  10.1007/BF00994007.
    [19] Li W L, Iranj K B. Discretization of continuous-valued attributes in decision tree generation[C]. International Conference on Machine Learning & Cybernetics. IEEE, Qingdao, China. 2010: 194-198. DOI: 10.1109/ICMLC.2010.5581069.
    [20] 魏赟, 丁宇琛. Spark中一种高效RDD自主缓存替换策略研究[J]. 计算机应用研究,2019,37(10):1-5. DOI: 10.19734/j.issn.1001-3695.2019.06.0213.

    Wei Y, Ding Y C. Research on efficient rdd self-cache replacement strategy in spark[J]. Application Research of Computers, 2019, 37(10):1-5. DOI: 10.19734/j.issn.1001-3695.2019.06.0213.
    [21] 于露, 杨亚宁. C4.5算法的研究与应用[J]. 云南大学学报: 自然科学版, 2010, 32(S2): 136-140. Yu L, Yang Y N. The research and application of C4.5 algorithm[J]. Journal of Yunnan University: Natural Sciences Edition, 2010, 32(S2): 136-140.
    [22] UC Irvine: Machine Learning Repository Classification Data[EB/OL]. https://archive.ics.uci.edu/ml/datasets.php, 2019-09-14.
  • [1] 和永军姚庆华缪应锋孙雪赵娜 . 基于大数据的云南省智慧城市交通建设研究. 云南大学学报(自然科学版), 2016, 38(S1): 50-. doi: 10.7540/j.ynu.2016d
    [2] 夏姜虹 . 数据挖掘技术的常用方法分析. 云南大学学报(自然科学版), 2011, 33(S2): 173-175.
    [3] 赵爽文瑾施心陵 . 基于逻辑描述的决策树算法及其Prolog实现. 云南大学学报(自然科学版), 2005, 27(3): 211-215.
    [4] 汪金花曹兰杰郭云飞赵礼剑吴兵 . 铁尾矿高−多光谱遥感特征分析与信息识别. 云南大学学报(自然科学版), 2019, 41(5): 974-981. doi: 10.7540/j.ynu.20180656
    [5] 陈涛王丽珍 . 基于时序数据的空间面向属性归纳算法. 云南大学学报(自然科学版), 2004, 26(5): 386-391.
    [6] 汪金钟宣武 . R-树聚集在空间数据仓库中的应用. 云南大学学报(自然科学版), 2003, 25(4): 328-331,334.
    [7] 赵东风丁洪伟杨志军 . 连续时间型轮询系统并行调度策略研究. 云南大学学报(自然科学版), 2003, 25(3): 212-216.
    [8] 杨继婷文乐吴俊孙亮汪源源徐丹罗华友舒若 . 基于改进型八叉树分解的三维超声图像数据抽样方法. 云南大学学报(自然科学版), 2020, 42(3): 444-451. doi: 10.7540/j.ynu.20190222
    [9] 罗洪严伟峰杨世兵 . 电网调度数据资源的主数据管理. 云南大学学报(自然科学版), 2013, 35(S2): 69-. doi: 10.7540/j.ynu.2013b59
    [10] 秦海林王丽珍谭晓玲陈克平 . 联机数据挖掘中的数据预处理. 云南大学学报(自然科学版), 2005, 27(4): 310-313.
    [11] 张文专石磊 . 数据矩阵条件指数的影响评价. 云南大学学报(自然科学版), 2004, 26(4): 292-296,300.
    [12] 胡茂胡盛 . 半结构数据中的结构推理. 云南大学学报(自然科学版), 2003, 25(1): 17-21.
    [13] 谭晓玲王丽珍 . 构建大型企业的数据仓库. 云南大学学报(自然科学版), 2004, 26(5): 401-405.
    [14] 卿跃周清张慧王敏 . 基于GPRS通信功能实现数据采集及传输. 云南大学学报(自然科学版), 2013, 35(S2): 75-. doi: 10.7540/j.ynu.2013b17
    [15] 何斌颖刘荣 . Oracel和SQL Server数据库安全基线审查. 云南大学学报(自然科学版), 2013, 35(S2): 63-. doi: 10.7540/j.ynu.2013b45
    [16] 周熙然邵振峰周寿章 . 基于地理本体的空间传感网数据处理. 云南大学学报(自然科学版), 2011, 33(S2): 196-201.
    [17] 陈骏张颂王靖洲朱聪 . 观测数据对宇宙透明度的限制. 云南大学学报(自然科学版), 2017, 39(3): 390-394. doi: 10.7540/j.ynu.20160324
    [18] 王丽珍王星群陈涛周丽华 . 基于时序数据挖掘的澜沧江流域气象预报系统. 云南大学学报(自然科学版), 2004, 26(6): 479-485,491.
    [19] 闵文文梅 端代婷婷胡光华 . 基于遗传算法SVM的基因表达谱数据分析. 云南大学学报(自然科学版), 2013, 35(4): 441-446. doi: 10.7540/j.ynu.20120663
    [20] 徐安伦孙绩华李建冯健武董保举刘劲松 . 大理涡动相关观测数据的处理及质量评价研究. 云南大学学报(自然科学版), 2014, 36(2): 224-232. doi: 10.7540/j.ynu.20130224
  • 加载中
图(6)表(3)
计量
  • 文章访问数:  503
  • HTML全文浏览量:  411
  • PDF下载量:  37
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-09-16
  • 录用日期:  2019-11-29
  • 网络出版日期:  2019-12-12
  • 刊出日期:  2020-03-01

一种面向大数据分析的快速并行决策树算法

    作者简介:陆旭(1995−),男,四川人,硕士生,研究方向:云计算、大数据. E-mail:1475075634@qq.com
    通讯作者: 陈毅红, cyhswpi@126.com
  • 1. 西华师范大学 计算机学院,四川 南充 637002
  • 2. 物联网感知与大数据分析南充市重点实验室,四川 南充 637002

摘要: 为了提高基于大规模数据的决策树训练效率,提出了一种基于Spark平台的并行决策树算法(SPDT). 首先,采用数据按列分区的方法,把单个属性列完整地保留在一个分区内,使缓存该分区数据的数据节点能独立完成信息熵的计算,以减少数据节点之间的信息交流造成的网络资源的占用. 然后,数据在按列分区后以稠密向量的形式缓存于内存中,SPDT对数据进行压缩,以减少对内存的占用. 最后,SPDT采用基于边界点类别判定的连续属性离散化方法来处理连续属性,减少决策树训练过程中信息熵计算的频次,并提出使用信息增益比划分训练数据集的方法,以减少信息增益计算对多属性值属性的依赖. 实验结果表明,在树的训练效率方面,SPDT在保持分类精度的情况下,比Apache Spark-MLlib决策树算法(MLDT)以及基于Spark平台的垂直划分决策树算法(Yggdrasil)有明显的提升.

English Abstract

  • 决策树是一种基本的分类技术,被广泛应用于医疗卫生[1],故障预测[2],入侵检测[3],目标追踪[4]和食品安全[5]等领域. 决策树被广泛应用的原因有2点:①决策树的训练过程很容易被理解,因为决策树是一个经典的二叉树模型,在树的生长没有结束之前,分裂每一个树节点只需要进行“是”与“否”两种判定,在决策树的训练过程中,这样的判定过程以递归的方式进行,直到决策树停止生长[6]. ②用户可以根据自己的需求在训练决策树之前设置超参数,通过不同的超参数值设置,可以训练出不同的模型.

    在近几十年中,研究者提出了很多决策树算法,大体上可以分为两大类:第一类是布尔决策树,在假定数据集的属性值和分类标签确定的条件下,使用信息增益或基尼系数作为启发式,创建出每一个叶节点表示一种分类的决策树[7],它们大多数是ID3[8]和CART[9]的改进算法. 第二类是模糊决策树算法,该类算法在数据集属性值有不确定值时,利用模糊集理论把决策树算法推广到模糊环境,如FDT[10]、FRDT[11]和FEBFP[12]. 这两类算法适用于现实世界中不同的场景,都能表现出很好的分类效果,但它们更适用于小型数据集.

    随着数据规模的不断扩大,受单处理器计算能力的限制,传统的决策树算法难以满足快速地训练决策树模型的需求. 基于并行分布式计算平台Spark的强大计算能力,科学工作者着手研究Spark的并行决策树算法以提高训练效率. MLDT[13]是最早出现在Spark平台的决策树算法,该算法利用Spark基于内存计算的特性,大幅度地提高了决策树训练的效率. 在此之后,研究者为了提高基于Spark平台决策树的分类精度,又相继提出了基于Spark平台的KS-tree算法[14]和模糊决策树算法[15],虽然这两种算法在分类精度上有一定程度的提升,但是它们的训练效率却低于MLDT. 在大数据时代,决策树的训练效率是从大规模数据中快速获取有用信息的一个重要保障,因此很有必要对决策树的训练效率进行研究.

    2016年,在第30届神经信息处理系统会议上,Abuzaid等提出了一种基于Spark平台的深度决策树算法Yggdrasil[16]. 该算法在对数据的处理过程中采用了数据垂直划分和数据压缩的方法,有效地解决了Spark平台的数据水平分区方式所造成的占用大量网络资源的问题[17],大幅度地提高了决策树训练的效率. 但是,由于该算法数据压缩方式的缺陷,导致在训练大规模数据集时分类精度会下降. 此外,Yggdrasil和MLDT一样,在对连续属性进行离散化时需要进行大量的信息增益计算,如果数据样本太大,就会严重影响决策树训练的效率. 因为这些信息增益的计算频次等于每个属性的离散点(Split)的数量,而离散点的数量取决于分裂区间(Bin)的数量. Bin的数量在最坏的情况下为连续属性的所有取值的类别个数,但是Split数只比Bin的个数少1个. 也就是说,信息增益的计算频次会接近数据样本的数量.

    针对上述决策树缺点,本文提出了一种基于Spark平台的并行决策树算法(SPDT),以达到提高决策树训练效率的目的. 本文的主要贡献如下:

    (1)采用按属性列进行分区的方法,确保每个数据节点在信息熵的计算中都是完整的属性列来参与,每个数据节点只完成自己的计算任务互不干预,有效地减少了网络资源的占用;

    (2)在Spark平台上提出了应用位图(Bitset)结构来进行数据压缩,减少数据对内存空间的占用,同时对Bitset结构压缩有重复值属性进行了优化,以保持决策树的分类精度;

    (3)在Spark平台上提出了使用基于边界点类别判定的连续属性离散化方法,减少决策树训练过程中信息熵计算的频次,并使用信息增益比划分训练数据集,减少信息增益计算对多属性值属性的依赖.

    • Apache Spark是专门为大规模数据处理而设计的分布式计算引擎. Spark拥有Hadoop MapReduce 并行框架的优点,但不同于MapReduce的是Spark的计算以弹性分布式数据集(RDD)为核心. RDD是一个可分区且不可变的分布式数据集,这个数据集的全部或部分以及其计算的中间结果都可以缓存在内存中,在多次计算中重用. 因此不需要进行频繁地读写HDFS的操作,大幅度提高了运算的效率.

    • 为了将数据集S划分成两个数据集 ${S_1}$${S_2}$ 之后评估其结果类熵,Fayyad等[18]定义了求结果类熵的加权平均值的方式和类别的边界点,定义如下:

      定义1:训练数据集S,按升序排序的连续属性A和一个边界点T. ${S_1} \subset S$${S_1}$S的子集,但是在属性A的取值范围内 ${S_1}$ 不包含T${S_2}{\rm{ = }}S - {S_1}$. 由T作为划分点而得到的信息类熵定义为 $E(A,T;S)$

      $E(A,T;S) = \frac{{\left| {{S_1}} \right|}}{N}E({S_1}) + \frac{{\left| {{S_2}} \right|}}{N}E({S_2}),$

      其中N为训练数据集的实例数,E(S1) 和 E(S2)分别表示边界点两边数据集的信息熵,T是边界点,在定义2中说明.

      Fayyad等[18]证明了当属性A中的一个边界点 ${T_A}$ 使得 $E(A,{T_A};S)$ 取得最小值时,${T_A}$ 就是当前属性A的最佳划分点,也作为当前属性构建决策树时的二分点.

      定义2:数据集的一个连续属性A按升序排列,如果在A的属性值取值范围内存在两个实例 ${e_1},{e_2} \in S$ 是不同的类别,使得 $A({e_1}) < T < A({e_2})$,且不存在其它实例 ${e^{'}} \in S$ 满足 $A({e_1}) < A({e^{'}}) < A({e_2})$,那么T就是属性A的一个边界点.

      假设T是连续属性A的一个区间 ${n_j}$${n_j}$ 属于同一类别 ${C_k}$)中的一个划分点,${n_j} \geqslant 2$${T_1}$${T_2}$ 分别是区间 ${n_j}$ 的两个边界点. 设有L个实例在属性A中的取值小于 ${T_1}$R个实例在属性A中的取值大于 ${T_2}$,其中 $0 \leqslant L$$R \leqslant N - {n_j}$. 设左边的L个实例的类别为 ${C_i},i = 1,\cdots,k$,每个类别数量表示为 ${L_i}$,与左边相似右边的R个实例的类别也为 ${C_i},i = 1,\cdots,k$,每个类别数量表示为 ${R_i}$,其中 $0 \leqslant {L_i} \leqslant L$$0 \leqslant {R_i} \leqslant R$$\displaystyle\sum {{L_i}} = L$$\displaystyle\sum {{R_i}} = R$. 假设有 ${n_c}$ 个实例在属性A中的取值在 ${T_1}$${T_2}$ 之间,如图1所示.

      图  1  边界点T存在的位置

      Figure 1.  The location of boundary point T

      Fayyad等[18]证明了当 ${n_c} = 0$ 或者 ${n_c} = {n_j}$ 时平均类信息熵取得最小值.

    • Fayyad等[18]的方法展示了连续属性的最佳划分点存在于当 ${n_c} = 0$ 或者 ${n_c} = {n_j}$ 的其中一个边界点上. 但是,并不是所有的边界点都是最小点.

      Li等[19]对该方法进行了改进,记 ${\left( {{L_k} + {n_c}} \right)} / $$ {\left( {L + {n_c}} \right)}$ 为一个实例在 ${S_1}$ 中的类别为 ${C_k}$ 的概率,${{\left( {{R_k} + {n_j} - {n_c}} \right)} / {\left( {R + {n_j} - {n_c}} \right)}}$ 是一个实例在 ${S_2}$ 中的类别为 ${C_k}$ 的概率. 设 ${{\left( {{L_k} + {n_c}} \right)} / {\left( {L + {n_c}} \right)}}{\rm{ = }}{p_1}$${\left( {{R_k} + {n_j} - {n_c}} \right)} / $$ {\left( {R + {n_j} - {n_c}} \right)}{\rm{ = }}{p_2}$,这里的

      $ \dfrac{{{L_k}}}{L} \leqslant {p_1} \leqslant \dfrac{{{L_k} + {n_c}}}{{L + {n_c}}},\dfrac{{{R_k}}}{R} \leqslant {p_2} \leqslant \dfrac{{{R_k} + {n_j} - {n_c}}}{{R + {n_j} - {n_c}}}$I(x)=xlog2(x),在E(A,T;s)的两边同时乘上N,然后对nc 求导得:

      $\frac{{{\rm d}\left( {NE\left( {A,T;S} \right)} \right)}}{{{\rm d}{n_c}}} \!=\! {\log _2}{p_2} \!-\! {\log _2}{p_1} \!=\! {\log _2}\left( {\frac{{{p_2}}}{{{p_1}}}} \right), $

      $\dfrac{{{\rm d}\left( {N{\rm{E}}\left( {A,T;S} \right)} \right)}}{{{\rm d}{n_c}}} = 0$,当 ${p_1}$ = ${p_2}$ 时;

      $\dfrac{{{\rm d}\left( {N{\rm{E}}\left( {A,T;S} \right)} \right)}}{{{\rm d}{n_c}}} > 0$,当 ${p_1}$ < ${p_2}$ 时;

      $\dfrac{{{\rm d}\left( {N{\rm{E}}\left( {A,T;S} \right)} \right)}}{{{\rm d}{n_c}}} < 0$,当 ${p_1}$ > ${p_2}$ 时;

      在划分点由 ${T_1}$${T_2}$ 移动的过程中,${p_1}$ 增加,${p_2}$ 减少,总共存在如下3种情况:

      (1)对于所有 ${n_c}$${p_1}$ 都小于 ${p_2}$

      (2)对于所有 ${n_c}$${p_1}$ 都大于 ${p_2}$

      (3)对于所有 ${n_c}$${p_1}$ 先小于 ${p_2}$,然后大于 ${p_2}$

      相应的,两个边界点之间的间隔也分为3种情况:

      第1类:${{\left( {{L_k} + {n_j}} \right)} / {\left( {L + {n_j}} \right) < \left( {{{{R_k}} / R}} \right)}}$,对于所有的 ${n_c}$${p_1}$ 都小于 ${p_2}$,极小值在左边界 ${n_c}{\rm{ = }}0$ 处取得.

      第2类:$\left( {{{{L_k}} / L}} \right) > {{\left( {{R_k} + {n_j}} \right)} / {\left( {R + {n_j}} \right)}}$,对于所有的 ${n_c}$${p_1}$ 都大于 ${p_2}$,极小值在右边界 ${n_c}{\rm{ = }}{n_j}$ 处取得.

      第3类:${\left( {{L_k} \!+\! {n_j}} \right)} / \left( {L \!+\! {n_j}} \right) \!>\! \left( {{{{R_k}} / R}} \right)\& \left( {{{{L_k}} / L}} \right) \!<\! ( {R_k} \!+\!$$ {n_j} ) / \left( {R + {n_j}} \right) $${p_1}$ 先小于 ${p_2}$,然后大于 ${p_2}$,极小值在两个点 ${n_c}{\rm{ = }}0$${n_c}{\rm{ = }}{n_j}$ 处取得.

      如果边界点是一个极小值点,它必须满足左区间单调递减,右区间单调递增. 所以极小值点在左边应该满足第2类和第3类条件,极小值点在右边该满足第1类和第3类的条件.

    • 假设训练数据集SN个实例,M个属性. Spark读取数据集S生成RDD对象,S中的实例被读取为RDD的元素,即S中有N个实例,生成的RDD对象就有N个元素. 由于RDD的分区是以水平方式按元素进行的,这N个元素按照分区规则被分为 $V(0 < V)$ 个分区,且分别缓存于不同的数据节点上[20]. 在决策树训练的过程中,由于信息熵的计算只需要目标属性和当前属性参与,而在各个分区上缓存的数据只有S的部分实例,并没有完整的属性列存在. 为了完成训练决策树的任务,需要对各个分区的数据进行聚合操作(Shuffle),以获得有N个属性值的属性列. 但是,Shuffle操作的代价是昂贵的,缓存分区数据的数据节点会因为这个操作在节点之间产生大量的信息通信,这样的信息通信会占用大量的网络资源,严重地影响训练的效率. 为了减少数据节点间的信息通信,根据各个属性的独立性和计算任务的需求,我们采用了对数据进行按列分区的方法.

      首先把训练数据集S的目标属性 ${y_{M - 1}}$ 选取作为全局广播变量. 然后,把剩余的 $M - 1$ 个属性列进行分区,即把每一列属性读取为RDD的一个元素. 根据RDD分区持久化原则,每一个数据节点会把参与计算的对应分区数据缓存到内存或者磁盘中,而按列分区过后的RDD总共有 $M - 1$ 个元素,每个分区可缓存多个完整的属性列,如图2所示. 在这种分区方式中数据的每个属性列完整地存在于一个分区当中,缓存分区数据的数据节点只需要完成自己缓存的属性列的信息熵计算,而不需要别的数据节点参与,减少了节点之间信息传递.

      图  2  按列分区

      Figure 2.  Partition by column

      按列分区算法过程如算法1.

      算法1:按列分区

      输入:S //训练数据集;

      输出:${S_{\rm{column}} }$  //按列分区的数据集;

      1. 导入数据集S生成 ${\rm{RD}}{{\rm D}_s}$

      2. 获取RDD的分区数 $N_{\rm{partition}}$

      3. 获取数据集的属性列数 $N_{\rm{column}}$

      4. 计算按列分区的每个分区的属性列数 $N_{\rm{column}1}$

      5. $N_{\rm{column}1} = N_{\rm{column}}/N_{\rm{partition}}$

      6. 在每个分区依次选取 $N_{\rm{column}1}$ 个属性列,并与分 区数组成映射(分区序号,$N_{\rm{column}1}$ 个属性列);

      7. 通过groupByKey命令聚合各个分区的属性列;

      8. 返回按列分区的数据集 ${S_{\rm{column}}}$.

    • 数据按列分区后,每一列属性表示为RDD对象的一个稠密向量元素. 因此,可以对属性列进行压缩优化. 但是,如果采用传统的压缩方式,在使用数据时要进行解压缩. 而Spark平台的运算机制是计算任务向数据靠拢,数据始终缓存在数据节点的内存中没有移动,压缩和解压的过程会在同一内存中进行. 这样的优化方案不会提高运算的效率,反而会因为压缩和解压的过程占用更多的时间.

      在Yggdrasil算法中,Abuzaid等[16]使用了RLE编码的方式进行数据的压缩,并且采用对属性值进行排序的方式,巧妙地避开了数据解压的过程,使得压缩过后的数据不用解压就可以直接使用. 但Yggdrasil的压缩方式存在缺陷:①当一列属性的取值种类数多且重复次数较少时,RLE编码方式反而会因为插入的重复属性值的记录而占用更多的空间. ②使用RLE编码后,数据集的分类标签和每个属性的属性值对应关系不明确,造成了一个标签对应于一个属性值压缩块的场景,使得原数据集的标签类别减少,导致数据集训练出的决策树分类精度下降.

      为了解决数据压缩的问题,SPDT采用了位图(Bitset)结构对每个属性进行压缩. Bitset结构的优点在于可以处理海量数据,而且可以很大程度上的节省内存空间. 举个例子,在计算机中一个字节(byte)占8位(bit),而Bitset结构对位进行操作,其值只有0或1即(true或false). 如果把Int类型的数存储为Bitset,那么相比于原来的Int类型,就相当于32byte的数据只需要1byte就能存储,这是一个很高效的压缩过程. 此外,Bitset结构在训练决策树时不用进行解压操作,我们只需要在决策树训练过程中,保持目标属性和当前属性的排序匹配,就能正常地使用数据.

      虽然,Bitset结构减少了数据对内存空间占用,但是该结构在压缩数据时会去掉重复值. 然而,在数据集中,一列属性的属性值可能重复,但是重复的属性值对应的目标属性的标签并不一定相同. 如果直接使用该结构压缩后的属性列,那么就相当于给重复的属性值加上了相同的标签,会导致目标属性标签的多样性下降,从而影响决策树的分类精度,这一点与Yggdrasil的压缩方式类似. 因此,SPDT在使用Bitset结构时做了一个改进,即在把属性列转换为Bitset结构之前,对每个属性列的属性取值与每个取值对应的数量做一个映射,这样在后续决策树训练中,可以根据索引找到每个属性值对应的分类标签,确保决策树的分类精度.

      数据压缩的算法过程如算法2.

      算法2:数据压缩

      输入:A //一列属性;

      输出:$A_{\rm{compress}}$//压缩过后一列属性;

          m //每列属性的属性值和其取值个数的    映射;

      1. 创建一个Bitset结构 Bs

      2. 创建一个Map结构m

      3. 对属性列A进行升序排序;

      4. 计算每个属性值出现的次数;

      5. 把属性值与该属性值的个数组成的映射添加到 m中;

      6. for $x = 0$ to (A.length-1) do

      7.    Bs.set(A(x));

      8. end for

        //把属性转换为Bitset结构

      9. 返回 $A_{\rm{compress}}$m.

    • 在MLDT和Yggdrasil算法中,一列连续属性如果有h$\left( {0 < h \leqslant N - 1} \right)$ 个离散点,信息熵的计算将会达到h次,最多计算 $N - 1$ 次. 如果数据实例足够多,就会非常耗时. 为了优化这一问题,SPDT在Spark平台上实现了一种基于边界点类别判定的连续属性离散化方法,并且在决策树的训练过程中使用信息增益比划分数据集,有效地避免在树节点分裂时选择偏向于属性取值较多的属性的问题[21].

      数据集S的信息熵定义为:

      $H(S) = - \sum\limits_{a = 1}^d {{p_a}\log_2 {p_a}} ,$

      其中 $d(1 < d \leqslant N)$ 是数据集类别数,${p_a}$ 表示所有类别中取得类别a的概率.

      当前属性A的信息熵定义为:

      $H(A) = - \sum\limits_{b = 1}^{{d_1}} {{p_{b}}\log_2 {p_{b}}} ,$

      其中 ${d_1}(0 < d \leqslant N)$ 表示当前连续属性A的属性取值类别数,${p_{b}}$ 表示当前属性值取得 $b$ 的概率.

      连续属性A的一个边界点 ${T_A}$ 的信息增益定义为:

      $G({T_A}) = H(S) - E(A,{T_A};S),$

      连续属性A的一个边界点 ${T_A}$ 的信息增益比定义为:

      $GR({T_A}) = \frac{{G({T_A})}}{{H(A)}}.$

      在确定了边界点后,并不是立即在各个边界点计算信息增益比,而是先进行边界点邻近区间的类别判定,选择满足Li等[19]提出的判定条件的边界点计算信息增益比. 假设一个连续属性存在 $X(0 < X < N - 1)$ 个边界点,设需要进行的信息增益比次数为Q. 在不进行类别判定时,计算次数 $Q = X$;当进行边界点的类别判定后,每一次只需要选择满足判定条件的一个点进行计算,其它的点不需要进行计算,只有在最坏的情况下才需要计算所有的边界点,因此计算次数 $Q \leqslant X$.

      SPDT模型并行训练的过程如算法3.

      算法3:SPDT算法

      输入:Scolumn//按列分区的数据集;

         S  //训练数据集;

      输出:$\rm {SPD}{\rm{T}_{od }}$ //SPDT模型;

      1. 导入训练数据集生成 ${\rm{RDD}}_s$

      2. 把目标属性作为广播变量Bc

      3. ${\rm{RDD}}_{GR} \leftarrow S_{\rm{column}}.{\rm{map}}$

      4.  压缩当前属性列得到Acompressm

      5.  遍历m中各个属性值和其对应的个数

      6. 在当前属性列中寻找离散点(Split);

      7. 确定当前属性的边界点T

      8. if (${c_a}$ and ${c_{\rm{c}}}$) then

      9.  计算 ${n_c} = 0$ 信息增益比

        $GR({T_{{n_c} = 0}})$

      10. else if (${c_b}$ and ${c_c}$) then

      11.  计算 ${n_c} = n_j$ 处的信息增益比

        $GR({T_{{n_c} = {\rm{n_j}}}})$

      12. end if

      13. end map

      14. 选取最佳信息增益比所在的边界点为分裂点 ${\rm{node}}_A$

      15. 把节点 ${\rm{node}}_A$ 添加到SPDT模型中;

      16. 判断该树节点是否满足停止分裂条件;

      17. 如果满足,停止决策树的生长返回SPDTmod

      18. 如果不满足,更新数据,重复3~16;

      19. 返回 ${\rm{SPDT}}_{od }$.

      算法3展示了SPDT决策树算法的过程,其中 ${c_a}$${c_b}$${c_c}$ 分别对应于1.2.2节中的3种判定情况. 在一般情况下,数据集的属性有离散属性和连续属性2种分类,这些分类在数据输入之初指定,如果没有指定各列属性的类别,那么统一当连续属性处理.

    • 本次实验在Spark完全分布式环境下进行,我们创建了1个主节点和6个从节点,每个节点的配置为Centos 7.4版本操作系统,20核Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20 GHz,8 GB内存. 所有节点均配置了Hadoop 2.6.4和Spark 1.6.0环境,实现算法的语言是Scala 2.10.7,参与实验的数据均来自UCI机器学习库[22],如表1所示. 表2表3分别记录了3个数据集分别使用3种方法的平均分类精度和平均训练时间.

      数据集实例个数属性数
      HEPMASS10 500 000  28  
      YouTube Video120 000  1 000 000  
      URL Reputation2 396 130   3 231 961  

      表 1  选自UCI机器学习库的数据集

      Table 1.  Data set selected from UCI machine learning database

      数据集MLDTYggdrasilSPDT
      HEPMASS0.8970.7020.874
      YouTube Games0.6890.6210.721
      URL Reputation0.7330.6140.708

      表 2  平均分类精度

      Table 2.  Average classification accuracy

      数据集MLDTYggdrasilSPDT
      HEPMASS163.2132.7 93.21
      YouTube Games380.5264.6182.7
      URL Reputation243.2 160.7 90.4

      表 3  平均训练时间(单位:s)

      Table 3.  Average training time (Unit: s)

      表2所示的数据来看,面对3个数据集,Yggdrasil的分类精度相对较低,而SPDT和MLDT精度差距并不大. 造成Yggdrasil精度下降的原因是Yggdrasil的压缩方式减少了数据集标签的类别,使得每个属性具有相同属性值的实例对应于同一个标签,从而使决策树在分类过程中把具有相同属性值的实例都归为了一类. 表3展示了分别对应3种算法的平均训练时间,SPDT算法对应于3个不同的数据集,其训练时间要比MLDT和Yggdrasil少,其中训练效率比MLDT提高了约50%,相比于同样采用了数据压缩的算法Yggdrasil训练效率提高了30%左右.

    • 为了检验在整个数据增大的过程中SPDT的精度的变化,我们使用数据集HEPMASS进行了控制实例个数的实验,并记录随着实例个数的增加使用3种方法分类精度的变化,如图3所示. 可以看到,随着实例个数的增加Yggdrasil的精度始终低于SPDT和MLDT. SPDT的分类精度和MLDT的分类精度差距保持在0.02以内. 在这0.02的精度差距中,其中很大一部分来源于每次选取数据集的随机性造成的数据集差异,因为在实验中为了避免数据集选取的偶然性,我们每一次实验都会重新从HEPMASS数据集中随机选取相同数量的样本实例来进行3个算法的验证,这就使得参与3种算法的验证的训练数据集和测试数据集不同,从而决策树的分类精度也存在差异;另一部分差距则是因为在数据集划分时使用的划分标准不同而造成的,因为MLDT使用的是信息增益进行划分,而SPDT采用的是信息增益比进行划分,两种划分规则选择的属性不同,所以最后的精度也会不同.

      图  3  不同方法平均分类精度(随机选择的训练数据集和测试数据集)

      Figure 3.  Average classification accuracy of different methods (randomly selected training data set and test data set)

      我们使用相同训练数据集和测试数据集对MLDT和SPDT产生精度差距的原因进行了验证,验证结果如图4所示. 可以看到,在去除数据集随机性后,随着实例个数的增加,Yggdrasil的精度还是低于SPDT和MLDT. 而MLDT和SPDT的精度差距缩小了,但始终存在一定的差距,这个差距来源于信息增益和信息增益比这两种不同的数据集划分规则.

      图  4  不同方法平均分类精度(相同的训练数据集和测试数据集)

      Figure 4.  Average classification accuracy of different methods (same training data set and test data set)

    • 为了验证SPDT在少量属性的大数据下的训练效率,我们控制数据的属性数为28,随着实例数的增加分别使用SPDT、MLDT和Yggdrasil 3种方法训练决策树,记录平均训练时间,如图5所示. 可以看到随着数据实例的增加,SPDT的训练时间要低于MLDT和Yggdrasil. 当数据实例数达到1 000 000时,MLDT的训练时间从31.2 s增加到了145.7 s,Yggdrasil的训练时间从22.3 s增加到了116.9 s,而SPDT的训练时间只是从20.1 s增加到了83.4 s,SPDT的训练时间增幅小于MLDT和Yggdrasil.

      图  5  随着实例数增加决策树训练时间的变化(28个属性)

      Figure 5.  Change in training time of the decision tree as the number of instances increases (28 attributes)

      此外,我们还讨论了有大量属性的大数据集使用SPDT、MLDT和Yggdrasil 3种方法训练决策树的效率,把数据集的实例数限定为120 000,如图6所示. 可以看到,随着数据属性数的增加,3种算法所消耗的时间都有所增加,但MLDT训练决策树所需要的时间增长速率要比Yggdrasil和SPDT快. SPDT整体上的训练效率要高于其它两种算法,且其增长速率要比Yggdrasil和SPDT快. SPDT整体上的训练效率要高于其它两种算法,且其增加的幅度相对较为缓和,因此在面对高维数据时SPDT占用一定的优势.

      图  6  随着属性数增加决策树训练时间的变化(120,000个实例)

      Figure 6.  Change in training time of the decision tree as the number of attributes increases (120,000 instances)

    • 本文提出了一种基于Spark平台的并行决策树算法(SPDT),通过数据的按列分区、数据的压缩和连续属性的离散化优化方法,提高了决策树训练的效率. 我们在实验过程中应用不同的数据集对该算法进行了验证,并且讨论了数据集属性数和实例数对决策树训练效率的影响. 实验结果表明,SPDT显著提高了决策树的训练效率,并且随着属性数和实例数的增加SPDT的训练效率都要高于同类型决策树算法. 但由于训练数据集和划分规则的不同,分类精度与MLDT有少许的差异. 在后续的研究中,我们将把该算法应用于随机森林,并且考虑数据的分区数对分类精度的影响.

参考文献 (22)

目录

    /

    返回文章
    返回