大数据环境下决策树的研究

邓晓林，陈毅红，王登辉

（1.西华师范大学 计算机学院，四川 南充637000；2.物联网感知与大数据分析南充市重点实验室，四川 南充637000）

0 引言

近年来，IT技术、网络、可穿戴设备的迅速发展，为互联网网民在社交媒体、物联网、各种应用程序的使用打下了良好的基础.网民可以随时随地流畅地使用各种应用程序，这给生活带来了方方面面的便利，但便利的同时，网络数据量每天以TB、PB级增加，引起了数据量的暴涨.数据量的暴涨，使互联网进入了大数据时代.各行各业的应用程序对数据进行实时存储与响应，表明大数据具有实时性、多样性（音频、视频、文本、图片、语音等）、异构性、数据关系复杂性、信息量少的特点.基于大数据集的这些特点，怎样快、稳、准、有效地进行分析与预测，是现在大数据和人工智能研究的重要领域.

在大数据时代最根本的挑战是在海量的数据中分析出有价值的信息为下一步行动提供参考.在大多数情况下，大数据的分析过程必须非常高效且接近实时，因为用户可忍受的时间非常短已近似实时.为了实现大数据的快速响应和实时分类，需要使用到高效的数据分析算法和高效的应用平台.

目前分类算法可以分为有监督和无监督.无监督学习算法是通过算法把不知道分类标签的样本，把相似的样本归为一类.监督学习算法是先训练带有属性标签的样本，再预测不具有属性标签样本的分类情况.监督学习算法中常用的有决策树、KNN等，其中最具代表性的是决策树，因为简单易学、准确率高等特点备受关注.决策树根据属性标签是否确定，分为清晰决策树和模糊决策树.清晰决策树代表标签是明确，最典型是ID3、C4.5、CART、SLIQ和SPRINT.为了适应不确定、模糊环境，衍生了模糊决策树，具有代表性的是模糊ID3算法.传统决策树只能应用于中小型数据集，具有一定局限性，所以有必要基于大数据分布式平台对决策树进行深入研究.Hadoop和Spark的分布式并行化平台，可以支持大数据集的运算与处理，尤其是分布式集群方式，提高了算法的计算效率，为大数据的实时分析和预测提供了可能性.本文结构主要从以下三个方面进行深入分析：首先系统介绍决策树及各类决策树算法原理；其次，分析Hadoop和Spark平台下的分布式并行运算机制；最后从分布式决策树算法优化、平台并行机制方面深入分析大数据平台Hadoop和Spark下的分布式决策树的现状，为未来大数据平台下分布式决策树研究提供方向.

1 决策树基础算法

1.1 清晰决策树

决策树是数据挖掘和机器学习领域里非常有用的工具.它于1982年被提出，不仅应用领域广泛，比如被应用于医疗卫生［1］、故障预测［2］、入侵检测［3］、目标追踪［4］、食品安全［5］等领域，而且易于理解和使用.决策树根据分类是否明确分为清晰决策树和模糊决策树［6］.决策树通过训练数据集进行学习，得出一棵自顶向下的树模型，再将测试数据应用于这棵树模型得出预测分类结果［7］.这是一个包含根节点、中间节点和叶子节点的二叉树模型，每个节点根据每个属性的分裂标准进行判断和选择，叶子节点是样本的最终分类类别，如图1.从根节点到叶子节点完全可以解释数据分类，所以决策树最具解释性.

图1 二叉决策树

清晰决策树的属性值和分类值都是确定的.通常一颗决策树的构建需要几个步骤：数据准备，即将整个数据集基于一定规则划分成两个子数据集；其次由其中一个子数据集，构建出一颗决策树，再将另一个子数据集应用于已构建的决策树预测分类结果；最后根据生成的分类结果与数据集的原有分类结果进行比较，计算出所构建决策树的分类精度.构建决策树时最重要的环节是对属性分裂节点的选择.目前主要的分裂节点标准有信息增益、信息增益率和Gini指数.根据节点不同的分裂标准可以构建不同决策树.目前也针对已有的这些决策树提出了各种不同优化算法.

1.1.1 信息增益

Quinlan提出了一种以信息增益作为特征分裂准则构建树模型的ID3［8］算法.ID3的核心是基于香农公式中的信息熵.在构建ID3决策树时，首先需要计算各个属性的信息熵，再计算各个属性的信息增益，把信息增益最高的属性作为节点分裂的标准.假设样本数据集X，这些样本有m个不同标签类别Ci（i=1，2，3，…，m），则目标类别熵为：

条件熵为：

当属性x在标签确定条件下的条件熵，属性x的信息增益为：

ID3算法理论清晰，使用简单，但也存在一些缺点，比如：逻辑表达能力差、计算量大、分类偏向属性值多的样本等.针对这些缺陷，提出了一些优化的ID3决策树算法.ID3根据信息增益构建树，仅仅考虑单层节点，当出现较多节点时，逻辑表达能力较差.针对ID3表达能力差问题，提出MID3［9］，该算法提出需考虑两层节点的信息增益包括当前节点和当前节点之后的一个节点［9］.MID3［9］算法的优化只考虑了离散型属性，还需要进一步针对连续型属性进行验证.ID3与K-Means方法结合，解决了K类均值的K的取值问题［10］.针对ID3不能处理离散属性，并且构建决策树时常偏向多值属性的问题提出了一些改进算法：AR-KOS算法［11］、熵值计算中引入权重值［12］、信息增益率［13］.

1.1.2 信息增益率

C4.5［14］是一种以信息增益率作为特征分裂标准的决策树，是ID3的一种进化.C4.5算法可以处理数字型属性，也能处理分类型属性，同时还解决了属性缺省值问题.

数据集S，特征属性A，则属性分裂信息公式为：

Si代表特征属性分割后的子数据集，则信息增益率公式为：

C4.5算法存在一些缺点：数字型属性离散化时比较耗时、整个数据集信息增益率计算量大、节点分裂后数据量减小呈碎片化后导致过拟合.针对C4.5这些缺陷提出了一些优化方法.

刘鹏［15］等针对决策树的空支与无意义支导致的过拟合问题，提出在离散属性上使用修正的信息增益的R-C4.5决策树模型.实验结果表明R-C4.5模型一定程度上解决了过拟合问题，提高了准确率.周剑峰［16］等提出采用数学公式里的等价无穷小理论代替基于对数运算的信息增益率的改进C4.5算法.实验表明该方式降低了计算量，加快了生成决策树速度，提高了效率，但其中的优化熵代替平均信息熵进行计算的方式并没有明显提高预测分类的精度.针对通过对数运算方式计算信息增益率耗时比较长问题，引用麦克劳公式和泰勒公式思想，使用简单运算替换对数计算方式，提高了效率，也保证了预测分类的准确率［17］.对连续属性离散化时采用Fayyad和Irani的边界定理，解决离散化比较耗时问题；离散化后节点分裂标准采用Gini指标，并通过再带入估计算法，解决了决策树过拟合问题，实验结果表明该优化在模型复杂度上有所下降［18］.

1.1.3 Gini指数

Gini指数代表属性分类不确定性，其值越小，代表不确定越低，即作为选择最优特征的标准.将Gini指数替换了原来的熵值计算，解决了对数复杂的计算，使运算变为简单的加减乘除，大大提高了计算效率.基于Gini指数作为属性分裂标准的决策树有CART、SLIQ和SPRINT.Gini公式如下（6），Pi代表了样本属于i类别的概率，样本被错分的概率为1-Pi.

CART［19］算法是一种分类回归二叉决策树，即当使用某个特征进行样本划分，只能划分为两个集合：等于给定样本特征的集合、不等于给定样本特征的集合.其中S为样本数据集，S1和S2为子样本集：

针对CART算法不能处理递增式数据，引入了递增式学习里的测试函数提升思想，从实验表明确实证明了其准确性和有效性，但该算法也有些局限性，需要对参数不断进行设置尝试，不具有普遍推广性［20］.对连续属性划分区域计算分裂值的离散化方式降低了计算频次.改进后的CART算法针对连续属性的离散化采用了Fayyad边界定理［21］，实验表明该方法改进在准确率方面得到大大提升［22］.为了降低CART决策树误判率，通过剪枝改进了CART决策树，分别有CCP剪枝和AIC剪枝算法.实验表明通过AIC剪枝不仅提高了准确率而且具有良好的扩展性［23］.

传统决策树在处理大数据时，可能会出现精度下降或者性能下降的问题，IBM提出了基于内存读取的SLIQ［24］算法，它也是一种基于Gini指数作为属性分裂标准的决策树.该算法是一种快速、可伸缩并且能处理大数据的算法.SLIQ是以属性表、内表和直方图作为其数据结构，数据预处理阶段需要属性值进行预排序，构建决策树时结合宽度优先增长策略，最后剪枝时采用最小描述长度原则（MDLP），实验表明这种方式提高了效率［24］.但SLIQ算法存储类表的内存有限，也就决定了单机环境下是不适合处理大数据集的.

SPRINT［25］也是以Gini指数作为属性分裂标准，是基于SLIQ算法优化而来的一种算法.由于单机内存有限，它去掉了SLIQ的数据结构中的类别列表结构，节约了内存.针对SPRINT算法在寻找最佳分割点时涉及计算量极大问题，学术界提出了一些优化方法.刘友军等［26］提出将数值型区间分割为纯区间和非纯区间，纯区间即已确定分类的进行规约，不纯区间即需要精确计算，明显减少了计算量也得到了相应的准确率，但不足之处就是对所划分区间进行整体性的扫描需要消耗相当一部分时间.彭程等［27］提出根据如果连续属性表中确定分割点v的两个元祖的类别相同，至少存在另一个分割点的V1求得最小分割点，但这种方式只是通过减少分割点数目而达到提高效率目的.

1.2 模糊决策树

模糊决策树结合了模糊集理论，适应了不确定性的环境，增强了决策树的应用性，也是清晰决策树的一种推广.在模糊决策树中最经典的是基于ID3的模糊决策树.模糊决策树最开始是通过ID3与模糊集理论结合，应用到分析石油中的气体来分析电势变压器，取得一定效果［28］.模糊决策树构建时，首先通过隶属函数对属性进行模糊化，再对模糊化的属性计算模糊信息熵和模糊信息增益，选取模糊信息增益最大值作为模糊决策树节点分裂标准.目前主要是三角形、梯形和高斯隶属函数，最典型的是三角隶属函数，公式如下：

在三角隶属度函数时，需要将数据集（x）划分为几个数据区域，a、b、c分别为数据集边界，参数b为最高点，参数a、c为三角形的下方的左右两个点.

1.2.1 模糊ID3决策树

模糊ID3决策树是把ID3算法应用到了模糊环境的融合模型，比如：吉林丰满水电数字仿真系统的考核系统，既分析处理了大数据问题，又解决了不确定性数据的问题［29］.

模糊ID3需要使用模糊属性和模糊标签属性，所以在数据预处理阶段需要对属性进行模糊化.针对模糊化时有可能会损失有用信息，翟俊海［30］等提出了一种结合模糊粗糙集技术的模糊决策树归纳算法（RFDT），它直接处理不需要模糊化，仍然把Kosko模糊熵作为终止条件，没有信息丢失.RFDT算法的模糊熵定义为：

F是定义在论域U上的模糊集，其中Fc是F的模糊补集.这一方法是否对连续型属性有相关影响后续还待验证.针对模糊决策树在进行数据模糊化可能丢失有用信息提出了容差粗糙模糊集（TRFDT）［31］，它可以直接利用连续型属性和模糊值的模糊决策表生成模糊决策树，也是利用了Kosko模糊熵作为终止条件，仿真结果表明该算法不仅学习速度快，而且收敛性和泛化能力都比较强，但也只是理论上得到证实，具体实际应用还需要进一步验证.

在处理不均衡数据时，采用犹豫模糊集理论结合模糊ID3算法，因为在模糊集里隶属度只能取一个值，但在真实案例处理时隶属度可能取多个值.针对这一情况采用犹豫模糊集，构建决策树时，首先对数据集进行模糊化，其次计算隶属度，再计算出模糊熵、模糊信息增益和犹豫模糊信息增益，但该方法在处理二分类性能良好，但是没有对多分类问题进行验证［32］.

1.2.2 其他模糊决策树

与模糊ID3算法相比使用分类歧义来选择模糊决策树的根节点处的拆分属性，并使用信息增益来选择其他树节点中的拆分属性，实验结果表明该方法具有更高效率［33］.Chandra等［34］提出模糊SLIQ决策树算法FS-DT，通过构造模糊二进制决策树，决策树的规模变小，在效率上提高了74%，但是在精确率上提高的比较少，因为裁剪了部分中间节点.

2 大数据平台

2.1 Hadoop分布式计算框架

大数据时代背景下需要对大数据集进行实时存储与响应，包含文件存储和计算两个部分.Hadoop［35］是一个生态圈，它主要包含的组件Common、Hive、HDFS、YARN、MapReduce等.Hadoop集群采用主从（Master／Slave）模式，其中Master（即NameNode）节点在集群中只有一个，而Slave（即DataNode）节点在集群中可以有多个.分布式文件管理系统（HDFS）和分布式计算框架（MapReduce）有效地解决了大数据的实时存储与计算问题.

分布式文件管理系统（HDFS）采用主从集群模式，其中NameNode主要是管理分布式文件管理系统，DataNode节点主要是对文件进行存储与分析.数据从HDFS系统读取到NameNode节点后，需要对数据进行分块，并将不同分块分配到不同的DataNode节点，通过这种方式，一个大数据文件就会被分成多个小数据文件存储在不同机器，从而达到分布式文件的存储.

MapReduce［36］是Hadoop分布式集群计算框架的核心，它最早由Google公司提出并实现.MapReduce封装了对用户来说比较复杂的细节，用户调用接口即可应用，所以编码和部署会变得简单高效.MapReduce包含Map和Reduce两部分，用户只需要处理好Map和Reduce阶段即可实现对海量数据的并行处理［37］.当数据被分成多个小块并分配到不同节点时，只需要读取当前节点的数据执行Map和Reduce任务，当所有节点的计算完成后，再对所有节点进行聚合并输出结果.整个MapReduce过程的执行都是并行、单独的运行，以此实现了分布式计算，提高了效率.

Hadoop平台基于MapReduce框架具有很强的分布式可操作性，但将所有的操作都抽象为Map和Reduce任务，具有一定的局限性，为后面Spark的提出奠定了基础.

2.2 Spark分布式计算框架

Spark［38］是Hadoop的进化版本，继承了Hadoop的优点，也优化了MapReduce缺陷，比如Hadoop频繁进行读取I／O、节点通信等.Spark是基于内存进行计算，随时读取，降低延迟，提高效率，也减少了磁盘开销.Spark的核心是基于RDD弹性数据集进行操作，而DAG有向无环图则记录了RDD数据集的来龙去脉，若RDD数据丢失或出错，可以根据DAG图重建RDD，无需重头开始，提高了容错性.Spark不仅有Hadoop里面的Map和Reduce操作，还有Transformation和Action操作.Transformation主要是对Spark里特有的RDD弹性数据集之间进行变换操作，而Action则是操作RDD得到一个数据结果，具有较高的通用性.

在Spark分布式计算框架上，RDD是核心，而且整个框架的并行性是通过RDD实现分布式的.在Spark平台上，首先RDD读取数据集，根据按行分区规则对数据集进行分区，每个分区包含一定量的子数据集，最后将每个分区分布到集群节点，由此可见每个分区是独立、并行运行的，从而实现集群的并行计算，如图2.

图2 Spark的分布式并行图

3 基于大数据平台的决策树

决策树因其预测分类准确率高、参数少、易理解的特点在数据挖掘领域占据重要位置.传统决策树的实现是在单机上对属性进行反复迭代的计算过程，但单机无论在计算能力还是存储能力上都比较局限，所以传统决策树已不能适应当今大数据集环境，继而发展了并行决策树.并行决策树是在单机基础上使用串行的方式实现.这种方式主要是依赖于消息传递，底层的代码实现复杂又困难，更重要的是只能处理计算密集型问题，不能处理数据密集型问题，依然不能完全适应大数据环境.Spark和Hadoop两大主流大数据运行平台是通过将任务和数据进行分块，并将不同分块分配到不同节点执行计算任务，最后将不同结果进行统计，实现预测分类，整个过程即为并行分布式处理.Hadoop和Spark的这种并行分布式处理为单机并行决策树的发展提供了契机，继而提出了分布式决策树.Hadoop平台的MapReduce和Spark的MLlib都封装了很多API，编码时可以直接使用，既便于管理也提高了实现代码的效率.

3.1 基于Hadoop平台的分布式决策树

3.1.1 清晰分布式决策树

分布式并行清晰决策树主要是基于ID3、C4.5、CART、SPRINT等基础算法的分布式，从而提高算法在大数据集上的准确率和效率，但仍然还需考虑决策树算法本身的计算复杂性、驻留内存等特点进行优化后再实行分布式.在Hadoop的并行机制中核心是MapReduce框架，Map对数据进行处理，经过Shuffle后将Map阶段合成的数据再经Reduce阶段进行整合.Map是根据分区独立并行而Reduce也是分区独立运行，提高了效率.

针对ID3偏向多值取向问题，陆秋［39］等提出使用属性相似度作为属性选择标准进行优化.属性相似度越大，表明决策属性与条件属性越相似，即可作为最优属性分割点.优化后的ID3算法，通过Hadoop的Map和Reduce的并行实现，具体实现过程如下：

a.首先需要对读取的数据集进行分块，并将分块的元数据分配到不同的DataNode，而DataNode之间是独立的，以并行的方式进行计算处理.

b.Hadoop将为分配到每个节点的数据分片创建map任务，并以＜key，value＞形式作为输出结果.

c.在shuffle阶段对map输出结果进行归并操作即对具有相同key的value进行归并处理，输出＜key，value＿list（）＞.

d.Reduce任务，则是将shuffle后的＜key，value＿list（）＞形式数据进行计算处理，最后输出的结果就存到HDFS文件系统.

在整个过程中不同的Map任务和Reduce任务之间不进行通信与数据交换，即具有独立性.基于这样的机制，可以实现分布式并行模式，如图3.实验将分布式ID3决策树与非分布式决策树在精确度、加速比和可扩展性三个指标上进行比较分析，得出分布式ID3决策树在这三个指标上都有较好的表现.

图3 MapReduce框架下分布式决策树计算图

张晶星［40］等提出一种基于Hadoop平台的C4.5的不确定概率误差剪枝算法（C4.5-IEP），该算法解决了驻留内存和剪枝问题.首先，为了比较不同剪枝算法在处理嘈杂数据上的能力，分别在单机下对经典的悲观剪枝算法（PEP）、条件误差剪枝算法（CEP）和不确定概率误差剪枝算法（C4.5-IEP）进行对比实验［40］，实验结果表明IEP比另外两种算法在规模上稍小，但在三个算法准确率都不理想的情况下，IEP有明显优势；将C4.5-IEP应用于MapReduce框架下进行分布式行实验，并通过加速比、可扩展性指标进行比较分析，表明分布式的C4.5-IEP在处理大数据集上性能有了明显的提升［40］.黄刚［41］等将SPRINT算法应用于Hadoop大数据计算平台，实验结果从执行效率和准确率两个指标进行对比分析，得出分布式SPRINT决策树比单机下的SPRINT更有优势.杨长春［42］等提出并行SLIQ算法，由于SLIQ算法需要逐一遍历属性计算伸缩性指标进行节点分裂太耗时.为了实现并行化SLIQ，首先将所有的类表复制到每个节点的内存；在树构建阶段主要是寻找最佳分裂点、并根据分裂点创建新节点，所以需要记录每个样本的类表、直方图，根据直方图计算Gini值，为了比较分割节点两侧的值，引入一个哈希表进行存储两侧数据，为并行性提高依据.仿真实验表明并行化SLIQ具有可行性.Shivaraju［43］等提出一种基于属性划分的并行决策树.首先将整个数据集按照一定规则划分为构建决策树的训练集和测试决策树模型的测试集，再对这两个数据集的属性分区，每个分区至少两列属性，保持测试集分区数与训练集的分区数一致.在训练集上，根据每个分区生成一颗训练树；根据测试集的分区结合训练树生成测试树，在生成的测试树上，使用加权投票法，生成最终的预测分类结果，并在Reduce阶段统计正确率.但是实验只使用了小数据集，并未在大数据集上进行验证.Yuan［44］等为了解决C4.5算法中信息增益率计算比较耗时问题，提出了麦克劳林公式进行计算信息增益，通过改进的C4.5与传统C4.5在Hadoop平台上进行对比实验，分析了他们的时间复杂度和准确率，实验结果表明改进C4.5具有更高的准确率和效率.

3.1.2 分布式模糊决策树

目前基于Hadoop平台的模糊决策树研究相对少一些.Mu［45］提出并行融合模糊规则分类，通过Map-Reduce（MR-FFRCS）显示如何从数据中并行提取模糊规则并以整体学习的方式评估模糊规则.然后以MRFFRCS为基础模块，我们提出了基于并行模糊规则库的决策树（MR-FRBDT），以改进原始FRDT算法，从实验结果上看，既提高了性能，并避免了内存限制.

3.2 基于Spark平台的分布式决策树

Spark分布式平台是基于内存计算，即将数据集缓存到内存，随时读取，减少了磁盘操作，提升了效率.但决策树算法移植到Spark平台，不仅仅是算法在平台的实现，还需要对原算法重新进行设计以适应分布式处理.Spark MLlib（机器学习库）中已实现了分布式决策树，可以直接调用.在Spark兴起后，也有不少学者将不同决策树迁移到Spark平台进行研究，主要是通过平衡数据移动、负载平衡和通信开销方面对基于Spark的分布式决策树进行优化.

3.2.1 Spark分布式清晰决策树

Desai［46］等提出对分布式决策树进行可扩展性的研究.在第一版分布式决策树［47］中，提出了决策树基于Hadoop的DDT和基于Spark的ST的分布式实现，在分布式决策树中影响的主要因素是树的大小和准确度.树的大小与分区树一致，即生成树数等于分区数.分区的大小影响树的准确度，如果分区数太多，每个分区的样本数就偏小，即从小样本中进行学习，最后预测的准确率受影响；如果分区数少，那每个分区的样本偏多，有可能内存无法完全加载，如果能加载即有更高的准确度.由此可见，分区大小是另一个需要考虑的优化参数.

图4 DDT生成图

DDTv2是需要对之前的DDT和ST进行优化，需要在分区与准确度之间进行权衡，即在不损失精度的情况下，实现并行性.在DDTv2中实行“保持模型”，如图5，每颗决策树从两个分区的数据集中进行学习，训练的数据集增大了，所以提高了训练的准确性，而每颗决策树从两个分区中进行训练，则树数是分区数一半.实验结果从树规模、准确率、叶子节点数目等指标进行分析，DDTv2的中间树和叶数都更小，平均建模时间也更短，具有更高的精度.所以，DDTv2不仅能适应大数据集，同时树的规模明显缩小，准确率也有所提升.

图5 DDTv2生成图

Chen［48］等提出对随机森林PRF进行优化，随机森林算法中，所有决策树同时训练，所以适合并行化.在效率方面通过数据并行和任务并行进行优化；在预测准确度方面，并行化之前需要对大数据量、高维数据和噪声数据进行降维；最后根据生成的多颗决策树采用加权投票法得出最终的决策树分类，通过这种方式提高预测准确率.首先，选取数据集，从数据集S中采用bootstrap抽样方式选择K个训练集.其次，针对大数据高维、高噪声特点，构建决策树时需要根据各个特征变量的重要性计算增益比，并按降序排序，选出前K个，也就是最重要的前K个（K＜＜M，k＜m）.从余下的M-k个特征变量选出m-k个变量.所以，数据集的维度就从M降到m了.这在特征变量的多样性和准确度下取得平衡，解决了分类过度拟合问题.

G（yij）为第j个特征变量的信息增益，GR（yij）为第j个特征变量的信息增益率.

对第j个 特征变量，对a取不同值时的重要性进行计算.为了降低训练集的维度，根据变量的信息增益比来衡量每个特征变量的重要性，然后，选择最重要的特征变量，删除不重要的特征变量.

然后，用加权投票法，计算每颗决策树hi的分类精度CAi.

y是正确类中的值，z是错误类中的值（z不等于y）.在数据并行化方面，PRF的构建是基于多颗决策树，而每颗树的构建依赖于特征的信息增益率的计算值，所以计算相当庞大繁杂，因此采用了数据垂直划分、数据多路复用技术.数据垂直划分通过将训练集划分为多个特征子集，每个特征子集分配到Spark集群.而数据多路复用，则是数据抽样过程中，通过记录他们的索引到数据样本索引（DSI）表里，再将DSI表和它对应的特征集一起分配给所有的从节点，避免数据重复复制到不同节点.基于Spark平台方面，使用双偶并行方式，训练过程中创建了DAG任务和相互依赖的RDD对象，最后在不同DAG上执行不同任务调度.实验表明基于Spark计算平台下的分布式PRF在准确率、效率和可扩展性方面都有较大的提高.

陆旭［49］等提出基于Spark的并行决策树（SPDT），在数据预处理阶段，由于连续属性计算频次太多，采用了Fayyad等的基于边界点类别判定的方法对连续属性离散化，减少了计算频次.在决策树构建阶段：通过信息增益比的计算，解决了节点分裂偏向多值属性问题.Spark并行计算平台本身是基于内存进行计算，并且构成Spark集群的PC机都是普通机器，内存有限，为了避免内存不足，提出了数据压缩方式来节约存储空间.SPDT采用了数据的Bitset结构的数据压缩方式，特征的所有值由0或1代替，但会忽略重复值，所以将每个属性列的取值与数量做了一个映射，确保取值正确.属性的信息增益的计算是需要特征列属性和目标属性的值进行计算，如果还是按Spark的按行分区，需要频繁从不同节点去获取同列属性的不同样本取值，增加了网络通信资源占用，降低了效率，为此，提出了垂直划分即基于属性列进行存储，将一列或多列的特征子集存储在一个节点，便于计算.实验结果表明，并行决策树比原来的MLDT和Yggdrasil的效率提高了，只是准确率提高的较少，主要原因可能是数据压缩后，取值不对应问题.

黄廷辉［50］等提出梯度优化决策树（GBDT）.传统决策树是一个分类器进行预测，为了提高准确率，GBDT使用多个分类器融合成一个分类器进行预测分类，最后通过Boosting投票方式对多分类器结果，使用少数服从多数原则确定最终分类结果.GBDT是决策树与Boosting相融合的一种决策树应用，即利用损失函数对前面决策树的分类错误结果进行训练.损失函数中采用了梯度下降值进行优化.对连续属性的离散化采用了切分点抽样方法，即在一定子特征策略上进行抽样，然后生成各个分区结果，最后聚合计算纯度，取纯度最低的点为切分点.在特征数据的选取上，因为特征不算多，分析交通的每个特征、每个特征的取值，控制了数据样本的噪音，提高了准确率.传统决策树是按深度、宽度进行迭代，GBDT结合了Spark分布式原理通过逐层构建，充分利用了平台并行性，提高了效率.实验表明，基于Spark平台的分布式GBDT对交通预测系统的实时性提供了强有力的技术支持.而梯度优化决策树在效率和准确率上得到一个平衡，但决策树并未进行剪枝，所以存在过拟合问题.在数据分析上，针对每个特征进行分析，只能应用于小数据集，并不能适应于大数据集.王晓楠［51］提出根据CART算法整个树的构建过程：数据预处理、属性选取、剪枝进行整个过程实行并行化.实验分为两部分：一部分基于CART算法改进和一部分基于改进的CART算法并行化到Spark平台，从实验结果来看单独的算法改进在效率上得以提高，但是并行化后效率提升并不明显，主要是因为计算量大，也没有对Spark平台运行进行调优.

3.2.2 Spark分布式模糊决策树

为了适应大数据集的不确定环境，也有将模糊决策树迁移到Spark平台上进行实现的研究.分布式模糊决策树在模糊环境下具有重大意义，尤其是在医学研究领域.构建分布式模糊决策树时，第一步是对数据的模糊化，但模糊化对整个模糊决策树的构成的性能有较大影响.模糊决策树中存在模糊分区，提出比较八种不同模糊分区方法在准确性和数据执行效率上，PCR和NPCR优于其他几种方法［52］.Segatori［53］等基于Spark平台首次对模糊决策树的广泛性研究，提出基于离散化算法的两步数据生成算法.离散化时采用基于模糊分区的模糊熵.基于模糊信息熵的离散化会生成多个候选分裂点，再通过最小描述长度原则对多个候选分裂点进行判断是接收还是拒绝，确定最终分裂点，这个点会生成最小化后的权重熵.这种新颖的分布式模糊离散器，是基于模糊信息熵为每个连续属性生成强大的模糊分区.通过比较基于Spark平台的FDT（模糊决策树）、Spark MLlib库中的DDT（分布式决策树）、MapReduce基于分布式模糊规则的分类系统Chi-FRBCS-BigData算法、基于MapReduce的模糊二进制决策树（FBDT）和模糊多路决策树（FMDT）在数据集的准确性，复杂性和执行时间三个指标进行分析，模糊二进制决策树在准确性方面和统计上优于FMDT，DDT和Chi-FRBCS-BigData.模型复杂性上得出FBDT和DDT使用的节点数比FMDT少.

4 结论

关于在大数据平台下的分布式决策树已有较多研究，相比而言，Spark是Hadoop的升级版本，发展的时间并不长，所以针对Spark平台下的研究稍微少一些.模糊决策树在处理不确定性环境下有较大的实际意义，希望后面有更多关于大数据平台下的模糊决策树的研究.部分文献针对属性进行了分析，但在小数据集上明显提高了准确率，但如何将属性分析应用到大数据集需要进一步研究.针对各行各业产生的数据集也许有不同特征，比如是有序、无序、连续型或者离散型，分析数据集，对不同数据集的特征结合不同的优化方式，再结合决策树，也许能产生更高的准确率.分布式决策树评价指标上，不能仅仅参考分类准确率、效率，而应多角度进行比较分析.在性能优化方面，不仅是对算法的优化，还要针对算法所应用的平台应用时分区数、分区大小、节点参数等需要设置，但想要一个较好的配置，将耗费大量时间，可以结合粒子群算法，通过多方面优化，分布式决策树将会有更好的表现.