决策树优点：模型具有可读性、分类速度快。

决策树的学习包括3个步骤：特征选择、决策树的生成、决策树剪枝。

1 决策树模型与学习

决策树的学习本质上是从训练数据集中归纳出一组分类规则。损失函数通常是正则化的极大似然函数。

决策树学习 的算法通常是一个递归地选择最有特征，并根据该特征对训练数据集进行分割，使得对各个子数据集有一个最好的分类过程。这一过程对应着特征空间的划分，也对应着决策树的构建。开始，构建根节点，将所有的训练数据都放在根节点。选择一个最优的特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶子节点，并将这些子集分到所对应的叶子节点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直到所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶子结点上，就生成了一棵决策树。

 

2 特征选择

信息增益

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个离散随机变量，其概率分布为：

随机变量X的熵定义为：

当随机变量只取两个值，1和0时，X的分布为:

熵

熵H(p)随着概率p变化的曲线如图所示：

条件熵

条件熵表示在已知随机变量X的条件下随机变量Y不确定性。

条件熵定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

信息增益

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。信息增益越大的特征具有更强的分类能力。

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题（某个特征取值越多，划分出来的节点越多，多，信息增益往往越大）。使用信息增益比可以对这一问题进行校正。

 

3 决策树的生成

3.1 ID3算法

从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一棵决策树。

 

3.2 C4.5的生成算法

 

4 决策树的剪枝

在剪枝中主要分为：前剪枝和后剪枝。

前剪枝是指在生成决策树的过程中，对树的深度进行控制，防止生成过多的叶子节点。

后剪枝是指将训练集分成两个部分，一部分用来训练决策树模型（训练数据），另一部分对生成的决策树进行剪枝（验证数据）。

决策树的生成只考虑了通过提高信息增益对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减小模型的复杂度。

 

5 CART算法

CART分类回归树，既可以用于分类也可以用于回归。

CART算法由以下两步组成：

1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；

2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

5.1 CART生成

决策树的生成是递归构建二叉决策树的过程。回归树用平方误差最小化准则，分类树用基尼指数最小化准则，进行特征选择。

1. 回归树的生成

2. 分类树的生成

5.2 CART剪枝

CART剪枝算法由两步组成：

a.从生成算法产生的决策树底端开始不断剪枝，直到的根节点，形成一个子树序列；

b.通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。