决策树 (Decision Tree) 是一种有监督学习方法，通过特征和标签构造一棵决策树，学习特征之间的规则，以解决分类和回归问题。

使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树由以下 3 种元素构成：

• 根节点：包含样本全集
• 内部节点：对应特征属性测试
• 叶节点：决策结果 (标签)

决策树如何辨别好瓜和坏瓜？

(此图摘自周志华西瓜书，本人白板手绘版)

以上面的西瓜为例，我们要如何辨别一个瓜是好瓜。特点是：纹理清晰，根蒂稍蜷，触感青绿，恰好，你构建了一棵决策树，立马判断这是好瓜还是坏瓜？

判断步骤如下：

1. 根据纹理清晰，已知是清晰，那么向左边走，看步
2. 接着，由纹理清晰到达第 2 层，由决策树图，我们可以看到，根蒂是稍蜷
3. 接着到第 3 层，色泽的特征的青绿，由此，我们可以得出结论，这是一个好瓜。

根据上面的示例，我们可以很直观的得到一个实例的类别判断，只要告诉各个特征的具体值，决策树的判定过程就相当于从树中从根节点到某一个叶子节点的遍历。每一步如何遍历是由数据各个特征的具体特征属性决定。

那么，基于上面的一棵树，我们又有如下疑问，为什么根节点是纹理，而不是根蒂或者别的特征呢？

决策树又是基于什么标准来选择特征的？如果构建决策树？

决策树学习的 3 个步骤

基于上面的问题，为了构建一棵优质的决策树，决策树主要有3个步骤。

特征选择，决策树生成，决策树剪枝

特征选择

特征选择也即选择优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。我们希望在不断划分的过程中，决策树的分支节点所包含的样本尽可能属于同一类，即节点的 “纯度” 越来越高。而选择优划分特征的标准不同，也导致了决策树算法的不同。

• 信息熵 (information entropy)
• 信息增益 (information gain)
• 信息增益率 (information gain ratio)
• 基尼指数 (Gini index)

决策树基于树结构进行决策，可做分类，也可进行回归，有 ID3，C4.5，Cart 回归树。通常是递归选择优特征，并根据这个特征对训练数据进行分割，使得对各个子数据集有好的决策过程，决策树希望往快达到纯度更高子集合方向发展。

决策树生成

ID3

ID3 以信息增益大的特征作为节点进行划分，递归构建决策树，直到所有特征被划分。

信息增益表示得知特征 X 的信息而使得类 Y 的信息的不确定性减少程度。表示划分前和划分后的熵的差值，差值越大，增益越大。而划分前的熵是确定的，划分后的调减熵越小，则终的信息增益越大。

决策时总是希望往快达纯度更高子集合方向发展，而纯度越高怎么解释？纯度高，特征之间的差异越大，越利于特征选择。

具体方法

1. 从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益值大的特征作为节点的划分特征；
2. 由该特征的不同取值建立子节点；
3. 再对子节点递归地调用以上方法，构建决策树；
4. 到所有特征的信息增益都很小或者没有特征可以选择为止，得到终的决策树

信息增益偏向于取值较多的特征

信息增益在面对类别较少的离散数据时效果较好，但是面对取值较多的特征时效果会很不如人意。

关于信息增益对取值较多特征的偏向性，我认为原因是：当特征的取值较多时，根据此特征划分得到的子集纯度有更大的可能性会更高(对比与取值较少的特征)，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。

举个较为极端的例子可能更好理解：如果特征 A 的取值能将每一个样本都分到一个节点当中去的时候(如编号等特征)，条件熵部分会为 0，这意味着该情况下的信息增益达到了大值，故 ID3 算法一定会选择特征 A。但是，显然的，我们知道这个特征 A 显然不是佳选择。

那么为什么信息增益率就能改善这种情况呢？先来看一下信息增益率的计算公式：

又叫特征 A 的内部信息， 其实像是一个衡量以特征 A 的不同取值将数据集 D 分类后的不确定性的度量。如果特征 A 的取值越多，那么不确定性通常会更大，那么 的值也会越大，而 会越小，相当于是在信息增益的基础上乘上一个惩罚系数，即：

ID3 的特点

• 选择信息增益大的特征建立决策树，信息增益会偏向那些取值较多的特征(这也是C4.5采用信息增益率的原因)
• 只有树的生成过程，容易过拟合
• 只能处理离散数据
• 不能处理缺失值

C4.5

对 ID3 进行改进，选用信息增益率进行特征选择，递归构建决策树。

C4.5 特点

• 对 ID3 进行改进，选用信息增益率进行特征选择
• 能处理连续，离散类型
• 能处理缺失值
• 构造决策树进行剪枝

Cart

CART (classification and regression tree) 分类回归树算法，既可用于分类也可用于回归，在这一部分我们先主要将其分类树的生成。

CART 分类树

区别于 ID3 和 C4.5，CART 假设决策树是二叉树，内部节点特征的取值为 “是” 和 “否”，左分支为取值为“是”的分支，右分支为取值为”否“的分支。

这样的决策树等价于递归地二分每个特征，将输入空间(即特征空间)划分为有限个单元。

CART 的分类树用基尼指数来选择优特征的优划分点，具体过程如下

1. 从根节点开始，对节点计算现有特征的基尼指数，对每一个特征，例如 A，再对其每个可能的取值如 a，根据样本点对 A=a 的结果的”是“与”否“划分为两个部分，利用

2. 在所有可能的特征 A 及该特征所有可能的取值 a 中，选择基尼指数小的特征及其对应的取值作为优特征和优切分点，然后根据优特征和优切分点，将数据集二分，生成两个子节点。

3. 对两个子节点递归地调用上述步骤，直至节点中的样本个数小于阈值，或者样本集的基尼指数小于阈值，或者没有更多特征后停止。

4. 生成 CART 分类树。

CART 回归树

回归树是可以用于回归的决策树模型，一个回归树对应着输入空间（即特征空间）的一个划分以及在划分单元上的输出值。

与分类树不同的是，回归树对输入空间的划分采用一种启发式的方法，会遍历所有输入变量，找到优的切分变量 j 和优的切分点 s，即选择第 j 个特征 xj 和它的取值 s 将输入空间划分为两部分，然后重复这个操作。

而如何找到优的 j 和 s 是通过比较不同的划分的误差来得到的。一个输入空间的划分的误差是用真实值和划分区域的预测值的小二乘来衡量的，即

其中 f(xi) 是每个划分单元的预测值，这个预测值是该单元内每个样本点的值的均值。

那么，j 和 s 的求解可以用以下式进行

R1(j,s) 和 R2(j,s) 是被划分后的两个区域。

生成方法

1. 选择优的切分变量 j 和 优切分点 s，求解遍历所有特征，对固定的特征扫描所有取值，找到使得上式达到小值的 (j, s)
2. 用选定的 (j, s) 划分区域，并确定该区域的预测值
3. 继续对两个子区域继续上面的步骤，直至满足停止条件
4. 生成回归树

决策树剪枝

剪枝是为了避免决策树模型过拟合，因为决策树算法在学习过程中为了尽可能的正确分类训练样本，不停的对节点进行划分，因此这会导致整棵树分支过多，也就导致了过拟合。

决策树的剪枝有两种：预剪枝和后剪枝

预剪枝 (pre-pruning)

预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。

后剪枝 (post-pruning)

后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。