Spark MLlib中决策树算法不同特征选择标准比较

杜小芳，陈毅红

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

0 引言

Apache Spark是一个开源分布式数据处理平台，使用分布式内存抽象来高效地处理海量数据.Spark MLlib[1]是Spark的组件之一，其中包含了许多机器学习算法，如决策树[2]、k-meas、随机森林、SVM和协同过滤等.决策树算法根据应用环境不同大致可以分为两大类，一类是模糊决策树算法[3]，这类算法将模糊集理论和决策树算法相结合并将其应用到模糊领域中.Chang R L P等人提出了FDT算法，该算法证明了模糊决策树算法在分类方面表现良好.另一类是清晰决策树算法[4],此类算法的特征分裂标准使用信息熵或者基尼指数，如ID3[5]、C4.5[6]和CART[7]，该类算法被广泛应用于医疗安全、入侵检测和食品卫生等领域.在大数据时代，大部分研究领域使分类精度保持在可以接受的范围内主要追求模型训练效率，但某些对精度要求较高的领域会更倾向于追求分类精度而不是效率.因此本文通过对比Spark-MLlib 中分类决策树实现的两种方法，来研究面对不同规模数据，在保持训练效率的情况下，哪种算法的模型分类精度更高.

1 基础概念

1.1 决策树

决策树是一种树形结构，如图1所示，由根节点、父节点、子节点、叶节点构成.在理想状态下，每个叶节点都表示一个无法再继续切分的数据集合，即叶子节点只表示众多分类中的一类.但在现实世界中，每次分割后不可能得到那么纯的数据.因此，决策树算法也是一种贪心策略，力求在每一次子节点完成分裂后，其中的数据比上一次更纯.决策树的构建首先从根节点开始，把训练数据集S除目标属性外的各属性列看作根节点.然后，遍历每个属性的所有分裂方式，选取其中信息熵值或基尼值最小的分裂点作为待分裂点.列出所有属性列的待分裂点，再进行比较，选出其中信息增益最大或者基尼指数最小的待分裂点.最后以其所在的属性作为当前树深度的树节点来划分数据集.更新数据并重复上述步骤，直到当前节点中的实例数小于某个阈值时停止.

1.2 Spark MLlib

Spark是目前大数据领域中常用的分布式处理框架，以有向无环图(DAG)和弹性分布式数据集(RDD)为核心.MLlib是Spark中提供机器学习算法的库，并利用Spark自身特性为这些算法提供了分布式实现.首先把数据以RDD的形式表示，然后在分布式数据集上调用各种算法.机器学习的模型训练过程一般为：接受RDD中的LabeledPoint数据作为输入，调用相应的算法生成模型，利用生成的模型进行预测.在Spark MLlib中，决策树被认为是不采取特征抽样的随机森林中只包含一颗树的特殊情况.所以训练决策树也就是训练随机森林模型，最后从随机森林中抽出一棵树.

图1 决策树

2 算法相关数学原理

信息墒和基尼值都是衡量样本集合纯度的指标，假设当前有训练数据集S，S中第k类样本所占比例为pk(k=1,2,...,x)，则数据集S的信息熵和基尼指数分别定义为：

(1)

(2)

对于同一个二元分裂，熵和基尼系数的关系如图2所示.

图2 熵和基尼系数的关系

2.1 ID3算法

ID3算法使用信息增益来划分训练数据集.首先根据信息熵来选择最佳特征，信息熵的值越小，则样本集的纯度越高，然后根据信息增益最大原则来选择最优切分点.ID3算法只能处理离散属性，所以对于连续属性，Spark MLlib会对其进行箱化处理，把连续属性离散化.该算法建立的树模型是多类树，并且在特征选择时会偏向属性值较多的特征，其后的C4.5算法通过使用信息增益比来弥补了该缺陷.但Spark Mllib中决策树API默认使用的是ID3算法，因此本文在训练决策树模型时，使用的是信息增益来作为分裂准则.样本集S的信息增益定义为：

(3)

其中a表示离散属性并且有V个可能取值{a1,a2,…,aV}

2.2 CART算法

CART算法训练的模型是二叉分类回归树，在本文中用作分类模型.该算法使用基尼指数来划分训练数据集，在选择最优特征和最佳分裂点时，根据基尼指数值最小原则来选择.样本集S的基尼指数定义为：

(4)

其中v(0

3 实验

3.1 环境准备

本文实验在虚拟机Ubuntu5.4中搭建的Spark伪分布式环境中进行，该环境由一个主节点和两个从节点组成，每个节点的配置为8核Intel(R) Core(TM)@ 3.00GHz和4GB内存.实验环境所采用的软件版本为：Hadoop 2.6.4、Spark 1.6.0和Scala 2.10.4，实验所用数据来自UCI机器学习库[8]并作做了数据清洗及标准化处理，如表1所示.

表1 数据集

3.2 实验结果

本实验进行时，规定了树的最大深度为8，最大箱化数为32.实验结果表明使用gini和entropy两种方法训练模型的时间差距很小，都保持了训练效率.原因在于虽然使用gini训练模型时不像entropy需要做对数运算，理论上使用gini的训练效率应高于使用entropy.但由于Spark自身特性，其拥有强大高速的计算处理能力，在树模型训练过程中是否有对数运算对其而言，差距几乎可以忽略不计.表2记录了使用基尼指数和信息熵两种分裂标准训练决策树模型时，两种方法在8个数据集上的平均分类精度.从表中所示数据来看，对于小数据集，使用基尼指数来划分训练数据集得到的模型其分类精度和使用信息熵训练所得模型的分类精度的差距不大.随着数据规模增大，使用信息熵作为划分准则其模型分类精度高于使用基尼指数训练的模型的分类精度，提高了约0.2.

表2 平均分类精度

图3 平均分类精度

我们使用数据集Machine Stoppage来验证使用ID3和CART两种算法在不同树深度时的分类精度，实验结果如图3所示.在保持训练效率的情况下，随着树深度的不断增加，使用ID3算法的分类精度始终高于CART算法的分类精度.

4 总结

本文通过实验来对比Spark MLlib中决策树算法的两种实现方式，实验结果表明：在保持训练效率的情况下，随着数据规模增大，使用信息熵划分训练数据集所得模型的分类精度高于使用基尼系数.这对于某些对精度要求较高的领域来说，在进行大规模数据分析建立树模型时，此实验结果可以为其提供参数选择参考，减少其工作量.