机器学习算法实践-决策树

决策树是一种基本的分类与回归方法。

在分类问题中，表示基于特征对实例进行分类的过程，可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布[1]。

在回归问题中，回归树总体流程类似于分类树，分枝时穷举每一个特征的每一个阈值，来寻找最优切分特征j和最优切分点s，衡量的方法是平方误差最小化。分枝直到达到预设的终止条件(如叶子个数上限)就停止。

0 决策树主要学习内容

1. 决策树模型：掌握决策树模型：根结点，子结点，叶结点。

2. 特征选择：如何从特征空间中选择最优特征作为结点，常用方法信息熵，信息增益，信息增益比，基尼指数。

3. 不同特征选择对应不同算法:

ID3(基于信息增益作为特征选择的度量）

C4.5(基于信息增益比作为特征选择的度量)

CART(基于基尼指数作为特征选择的度量)

4. 决策树的修剪：缩小树结构规模、缓解训练集上的过拟合，提高模型的泛化能力。

1、决策树模型

决策树呈树形结构，由结点和有向边组成。结点有两种类型：内部结点和叶结点，内部节点表示一个特征或属性，叶结点表示一个类别。

决策树分类，从根结点开始，对实例进行特征选择，根据最优特征选择将实例分配到其子结点(如何求最优特征，这将是决策树的重中之重)，这时，每一个子结点对应着该特征的一个取值，如此递归地对实例进行测试并分配，直到达到叶结点，将实例全部分到叶结点的类中。

决策树在逻辑上以树的形式存在，包含根结点、内部结点(子结点)和叶结点。

1）根结点：包含数据集中的所有数据的集合 ，根结点有且仅有一个。

2）内部结点：每个内部结点可看作一个判断条件，并且包含数据集中满足从根节点到该结点所有条件的数据的集合。根据内部结点的判断结果，将内部结点所包含的数据集分到两个或多个子结点中。

3）叶结点：叶结点为最终的类别，包含在该叶结点的数据属于该类别。

例：

提出问题：

为何要用特征“香不香”为根节点呢?为何不选“辣不辣”或者“甜不甜”为根节点呢？

答:这是因为“香不香”这一特征相比其他特征更具有将训练数据分类的能力。

那是如何判断这一特征更具有将训练数据分类的能力呢？

答:这需要进行特征选择，常用方法有信息增益、信息增益比、基尼指数。

2、特征选择及用其分类的算法

2.1 前期准备工作

首先需要介绍一下信息熵，条件熵。

2.1.1信息熵

在信息论中，一个特征所带的信息量又称信息熵，熵度量了事物的不确定性，越不确定的事物，它的熵就越大。

当概率为0.5时，熵的取值最大，也就是说，随机变量不确定性最大。

2.1.2 条件熵

如有两个随机变量呢？

设有随机变量(X,Y),其联合概率分布为：

 2.2 信息增益[1]

信息增益，主要看一个特征能够为分类系统带来多少信息，带来的信息越多，则该特征越重要。没它和有它的信息量（信息熵）差值就是这个特征给系统带来的信息量，也称信息增益。简单来说就是在现有训练集包含的信息熵和已知某特征下的信息熵的差值即该特征的信息增益。

由于熵和条件熵中的概率通常无法直接得到，所以在实际中用频率代替概率。使用频率的熵和条件熵也分别称经验熵和条件经验熵。

2.2.1 基于信息增益的ID3算法[1]

ID3算法的核心：是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树。

选择信息增益最大的特征A2(有工作)作为结点的特征，由于A2有两个可能取值，从这一结点可引发两个子结点，一个“是”有工作，一个“否”有工作。据实例，在D2训练集下(9个人)，有工作的3人属于同类(批准贷款申请)，所以为一个叶结点。类标记为“是”，另一个无工作的6人也属于同类(未批准贷款申请)，也可为一个叶结点，类标记为“否”。

该决策树模型图为：

该实例的ID3决策树构建完成。 

2.3.1 基于信息增益比的C4.5算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法做了改进，在进行特征选择时，采用信息增益比来代替信息增益进行特征选择。

2.4.1 基于基尼指数的CART算法[1]

CART同样由特征选择、树的生成、修剪组成。既可以用于分类也可以用于回归。该算法下是递归地构建二叉树决策树的过程。

对于分类树，用基尼指数最小化准则进行特征选择，生成二叉树。

对于回归树，使用平方误差最小化方法。

例

如下表2，需要利用实例数据对年龄进行预测，若将j属性选为职业，则有三种划分情况，

1）{老师,上班族}，{学生}

2）{学生,上班族}，{老师}

3）{老师,学生}，{上班族}

最小平方误差计算得：

m=42+226.8=268.8

2.5 决策树剪枝[1]

决策树生成算法递归地产生决策树，直到不能继续下去为止，这样的树往往对训练数据集有很好的拟合，但对未知的测试数据的分类就不太理想，这就是出现了过拟合现象，出现这一问题，解决方法就是要考虑决策树的复杂度，对已有的决策树进行简化，简称剪枝。

剪枝往往通过极小化决策树整体的损失函数或代价函数来减小模型复杂度，提高全局学习效果。

2.5 决策树剪枝[1]

决策树生成算法递归地产生决策树，直到不能继续下去为止，这样的树往往对训练数据集有很好的拟合，但对未知的测试数据的分类就不太理想，这就是出现了过拟合现象，出现这一问题，解决方法就是要考虑决策树的复杂度，对已有的决策树进行简化，简称剪枝。

剪枝往往通过极小化决策树整体的损失函数或代价函数来减小模型复杂度，提高全局学习效果。

3 决策树算法总结

3.1 决策树算法(贪心算法)

• 有监督的学习

• 非参数学习算法

• 自顶向下递归方式构造决策树

• 在每一步选择中都采取在当前状态下最好的选择

3.2 决策树的优点：

(1)速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下一直走到叶，沿途的分裂条件就能够唯一确定一条分类的路径。

(2)准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰的显示哪些字段比较重要，即可以生成可以理解的规则。

(3)适合高维数据

(4)可以处理连续变量和种类字段

(5)不需要任何领域知识和参数假设

3.3 决策树的缺点：

(1)对于各类样本数量不一致的数据，信息增益偏向于那些具有更多数值的特征。

(2)易于过拟合

(3)忽略属性之间的相关性

4 决策树的运用

第一：决策树法作为一种决策技术，已被广泛地应用于企业的投资决策之中，它是随机决策模型中最常见、最普及的一种规策模式和方法，有效地控制了决策带来的风险。所谓决策树法，就是运用树状图表示各决策的期望值，通过计算，最终优选出效益最大、成本最小的决策方法。

第二：信用评分

第三：工厂生产能力计划

第四：随机森林的基础

参考文献

[1]李航，《统计学习方法》.

[2] https://www.cnblogs.com/yjd_hycf_space/p/6940068.html

[3] https://blog.csdn.net/gzj_1101/article/details/78355234

[4] 常用数据挖掘算法总结及python实现.

(部分文字、图片来自网络，如涉及侵权，请及时与我们联系，我们会在第一时间删除或处理侵权内容。电话：4006770986  邮箱：zhangming [at]eefung.com  负责人：张明）