↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』原创

作者：华校专

作者信息：

华校专，曾任阿里巴巴资深算法工程师、智易科技首席算法研究员，现任腾讯高级研究员，《Python 大战机器学习》的作者。

编者按：

算法工程师必备系列更新啦！继上次推出了算法工程师必备的数学基础后，小编继续整理了必要的机器学习知识，全部以干货的内容呈现，哪里不会学哪里，老板再也不用担心你的基础问题!

决策树

决策树是一种基本的分类与回归方法。这里主要讨论决策树用于分类。
决策树模型是描述对样本进行分类的树形结构。树由结点和有向边组成：

内部结点表示一个特征或者属性。
叶子结点表示一个分类。
有向边代表了一个划分规则。

决策树从根结点到子结点的的有向边代表了一条路径。决策树的路径是互斥并且是完备的。

用决策树分类时，对样本的某个特征进行测试，根据测试结果将样本分配到树的子结点上。此时每个子结点对应该特征的一个取值。

递归地对样本测试，直到该样本被划分叶结点。最后将样本分配为叶结点所属的类。

决策树的优点：可读性强，分类速度快。

决策树学习通常包括3个步骤：

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

一、原理

1.1 基本概念

决策树模型可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树将特征空间划分为互不相交的单元，在每个单元定义一个类的概率分布，这就构成了一个条件概率分布。

决策树的每一条路径对应于划分中的一个基本单元。
设某个单元内部有 N_S 个样本点，则它定义了一个条件概率分布。
单元上的条件概率偏向哪个类，则该单元划归到该类的概率较大。即单元的类别为：
决策树所代表的条件概率分布由各个单元给定条件下类的条件概率分布组成。

决策树的学习目标是：根据给定的训练数据集构造一个决策树模型，使得它能够对样本进行正确的分类。

决策树最优化的策略是：损失函数最小化。决策树的损失函数通常是正则化的极大似然函数。

选择最优决策树的问题是个 NP 完全问题。一般采用启发式方法近似求解这个最优化问题，这时的解为次最优的。

决策树学习的算法通常递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类。

这一过程对应着特征空间的划分，也对应着决策树的构建。

1.2 生成

决策树生成算法：

构建根结点：将所有训练数据放在根结点。
选择一个最优特征，根据这个特征将训练数据分割成子集，使得各个子集有一个在当前条件下最好的分类。
若这些子集已能够被基本正确分类，则将该子集构成叶结点。
若某个子集不能够被基本正确分类，则对该子集选择新的最优的特征，继续对该子集进行分割，构建相应的结点。
如此递归下去，直至所有训练数据子集都被基本正确分类，或者没有合适的特征为止。

上述生成的决策树可能对训练数据有很好的分类能力，但是对于未知的测试数据却未必有很好要的分类能力，即可能发生过拟合的现象。

解决的方法是：对生成的决策树进行剪枝，从而使得决策树具有更好的泛化能力。
剪枝是去掉过于细分的叶结点，使得该叶结点中的子集回退到父结点或更高层次的结点并让其成为叶结点。

决策树的生成对应着模型的局部最优，决策树的剪枝则考虑全局最优。

如果学习任意大小的决策树，则可以将决策树算法视作非参数算法。但是实践中经常有大小限制（如限制树的高度、限制树的叶结点数量），从而使得决策树成为有参数模型。

二、特征选择

特征选择的关键是：选取对训练数据有较强分类能力的特征。若一个特征的分类结果与随机分类的结果没有什么差别，则称这个特征是没有分类能力的。
通常特征选择的指标是：信息增益或者信息增益比。这两个指标刻画了特征的分类能力。
对于分布，熵为。
定义数据集的经验熵为：。
其中：

样本的类别分别为。
类别的样本的数量为，所有样本的总数为。
因此有：。
是概率的估计。
就是熵的估计。它刻画了数据集中样本的类别分布情况。

对于特征，定义数据集在上的经验熵为。其中：

特征的取值范围为。
属性的样本的数量为。
因此有：
是概率的估计。
刻画了数据集中的样本在属性上的取值分布情况。

对于特征，其条件熵为：。

定义数据集关于特征的经验条件熵为：

其中：

属性且类别为的样本的数量为，所有样本的总数为。因此有：
是条件熵的估计。它刻画了数据集中，属性中的那些样本中的类别的分布情况。
是条件熵的估计。

2.1 信息增益

特征对训练数据集的信息增益定义为：集合的经验熵与关于特征经验条件熵之差。即：。
由于熵也称作互信息，因此信息增益也等于训练数据集中类与特征的互信息。
决策树学习可以应用信息增益来选择特征。给定训练集和特征：

经验熵刻画了对数据集进行分类的不确定性。
经验条件熵刻画了在特征给定条件下，对数据集分类的不确定性。
信息增益刻画了由于特征的确定，从而使得对数据集的分类的不确定性减少的程度。

不同的特征往往具有不同的信息增益。

信息增益大的特征具有更强的分类能力。
如果一个特征的信息增益为0，则表示该特征没有什么分类能力。

2.2 信息增益比

以信息增益作为划分训练集的特征选取方案，存在偏向于选取值较多的特征的问题。
公式

中：

当极限情况下，特征在每个样本上的取值都不同，即。
① 此时特征将每一个样本都划分到不同的子结点。即：。
② 由于，因此有：。即：取值为 0 或者 1 。因此有：。
③ 最终使得。
④ 条件熵的最小值为 0，这意味着该情况下的信息增益达到了最大值。
然而很显然这个特征 A 显然不是最佳选择，因为它并不具有任何分类能力。
可以通过定义信息增益比来解决该问题。
特征对训练集的信息增益比定义为：信息增益与关于特征的熵之比：
表征了特征对训练集的拆分能力。
因为只考虑样本在特征上的取值，而不考虑样本的标记，所以这种拆分并不是对样本的分类。
信息增益比本质上是对信息增益乘以一个加权系数：

当特征的取值集合较大时，加权系数较小，表示抑制该特征。
当特征的取值集合较小时，加权系数较大，表示鼓励该特征。

三、生成算法

决策树有两种常用的生成算法：

ID3 生成算法。
C4.5 生成算法。

ID3 生成算法和 C4.5 生成算法只有树的生成算法，生成的树容易产生过拟合：对训练集拟合得很好，但是预测测试集效果较差。

3.1 ID3 生成算法

ID3 生成算法核心是在决策树的每个结点上应用信息增益准则选择特征，递归地构建决策树。
如果不设置特征信息增益的下限，则可能会使得每个叶子都只有一个样本点，从而划分得太细。

从根结点开始，计算结点所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征划分出子结点。
再对子结点递归地调用以上方法，构建决策树。
直到所有特征的信息增益均很小或者没有特征可以选择为止，最后得到一个决策树。

ID3 生成算法：

a. 输入：

① 训练数据集

② 特征集合

③ 特征信息增益阈值

b. 输出：决策树

c. 算法步骤：

① 若中所有样本均属于同一类，则为单结点树，并将作为该结点的类标记，算法终止。

② 若，则为单结点树，将中样本数最大的类作为该结点的类标记，算法终止。

否则计算选择信息增益最大的特征：

③ 若，则置为单结点树，将中样本数最大的类作为该结点的类标记，算法终止。

④ 若，则对特征的每个可能取值根据将划分为若干个非空子集。

将中样本数最大的类作为该子集的标记，构建子结点。

⑤ 对第个子结点，以为训练集，以为特征集，递归地调用前面的步骤来构建子树。

3.2 C4.5 生成算法

C4.5 生成算法与 ID3 算法相似，但是 C4.5 算法在生成过程中用信息增益比来选择特征。

四、剪枝算法

决策树生成算法生成的树往往对于训练数据拟合很准确，但是对于未知的测试数据分类却没有那么准确。即出现过拟合现象。
过拟合产生得原因是决策树太复杂。解决的办法是：对决策树剪枝，即对生成的决策树进行简化。
决策树的剪枝是从已生成的树上裁掉一些子树或者叶结点，并将根结点或者其父结点作为新的叶结点。
剪枝的依据是：极小化决策树的整体损失函数或者代价函数。
决策树生成算法是学习局部的模型，决策树剪枝是学习整体的模型。即：生成算法仅考虑局部最优，而剪枝算法考虑全局最优。

4.1 原理

设树的叶结点个数为。设为树的叶结点，该叶结点有个样本点，其中属于类的样本点有个，。这意味着：。
令为叶结点上的经验熵，令为参数，则决策树的损失函数定义为：
其中：

叶结点个数越多，表示决策树越复杂，则损失函数越大。
叶结点经验熵越大，表示叶结点的样本类别分布很分散，则损失函数越大。
叶结点经验熵还需要加权，权重为叶结点大小。即：越大的叶结点，其分类错误的影响越大。

令

则：

其中为正则化项，表示预测误差。

意味着，即每个结点内的样本都是纯的，即单一的分类。

决策树划分得越细致，则的叶子结点越多。当叶结点的数量等于样本集的数量时，树的每个叶子结点只有一个样本点。此时每个叶结点内的样本都是纯的，从而。

这样的决策树其实是没有什么实用价值的，所以必须使用正则化项来约束决策树的复杂程度。

参数控制预测误差与模型复杂度之间的关系。

较大的会选择较简单的模型。
较小的会选择较复杂的模型。
只考虑对训练集的拟合，不考虑模型复杂度。

决策树剪枝的准则是：考虑当确定时，最小化。这等价于正则化的极大似然估计。

4.2 算法

决策树的剪枝算法：
a. 输入：
① 生成算法产生的决策树
② 参数
b. 输出：修剪后的决策树
c. 算法步骤：
① 对树每个结点，计算其经验熵。
② 递归地从树的叶结点向上回退：设一组叶结点回退到父结点之前与之后的整棵树分别为与，对应的损失函数值分别为与。若，则进行剪枝，将父结点变成新的叶结点。
③ 递归回退直到不能继续为止，得到损失函数最小的子树。

五、CART 树

CART:classification and regression tree ：学习在给定输入随机变量条件下，输出随机变量的条件概率分布的模型。

它同样由特征选取、树的生成、剪枝组成。
它既可用于分类，也可用于回归。

CART 假设决策树是二叉树：

内部结点特征的取值为 是 与 否 。其中：左侧分支取 是，右侧分支取 否 。
它递归地二分每个特征，将输入空间划分为有限个单元。

CART 树与ID3 决策树和 C4.5 决策树的重要区别：

由于是二叉树，因此 CART 树的拆分不依赖于特征的取值数量。因此CART 树也就不像ID3 那样倾向于取值数量较多的特征。

而后两者的特征是离散的。如果是连续的特征，则需要执行分桶来进行离散化。

CART 树处理连续特征时，也可以理解为二分桶的离散化。

CART 树的特征可以是离散的，也可以是连续的。
CART 树是二叉树，而后两者是N 叉树。

CART算法分两步：

决策树生成：用训练数据生成尽可能大的决策树。
决策树剪枝：用验证数据基于损失函数最小化的标准对生成的决策树剪枝。

5.1 CART 生成算法

CART生成算法有两个生成准则：

CART 回归树：用平方误差最小化准则。
CART 分类树：用基尼指数最小化准则。

5.1.1 CART 回归树

5.1.1.1 划分单元和划分点

一棵CART 回归树对应着输入空间的一个划分，以及在划分单元上的输出值。
设输出 y 为连续变量，训练数据集。
设已经将输入空间划分为个单元，且在每个单元上有一个固定的输出值。则CART 回归树模型可以表示为：
其中为示性函数。
如果已知输入空间的单元划分，基于平方误差最小的准则，则CART 回归树在训练数据集上的损失函数为：
根据损失函数最小，则可以求解出每个单元上的最优输出值为：上所有输入样本对应的输出的平均值。
即：，其中表示单元中的样本数量。
定义上样本的方差为
问题是输入空间的单元划分是未知的。如何对输入空间进行划分？
设输入为维：
a. 选择第维和它的取值 s 作为切分变量和切分点。定义两个区域：
b. 然后寻求最优切分变量 j 和最优切分点 s 。即求解：
c. 首先假设已知切分变量 j ，则遍历最优切分点 s，则到：
其中和分别代表区域和中的样本数量。
d. 然后遍历所有的特征维度，对每个维度找到最优切分点。从这些(切分维度,最优切分点) 中找到使得损失函数最小的那个。
依次将输入空间划分为两个区域，然后重复对子区域划分，直到满足停止条件为止。这样的回归树称为最小二乘回归树。

5.1.1.2 生成算法

CART 回归树生成算法：
a. 输入：
① 训练数据集
② 停止条件
b. 输出：CART回归树
c. 步骤：
选择最优切分维度和切分点。
即求解：
d. 用选定的划分区域并决定响应的输出值
其中和分别代表区域和中的样本数量。
① 对子区域递归地切分，直到满足停止条件。
② 最终将输入空间划分为个区域，生成决策树：。

5.1.2 CART 分类树

5.1.2.1 基尼系数

CART 分类树采用基尼指数选择最优特征。
假设有个分类，样本属于第类的概率为。则概率分布的基尼指数为：
基尼指数表示：样本集合中，随机选中一个样本，该样本被分错的概率。基尼指数越小，表示越不容易分错。
样本被选错概率 = 样本被选中的概率样本被分错的概率。
对于给定的样本集合，设属于类的样本子集为，则样本集的基尼指数为：
其中为样本总数，为子集的样本数量。
对于最简单的二项分布，设，则其基尼系数与熵的图形见下图。

可以看到基尼系数与熵一样，也是度量不确定性的度量。
对于样本集越小，说明集合中的样本越纯净。

若样本集根据特征 A 是否小于 a 而被分为两个子集:和，其中：
则在特征的条件下，集合的基尼指数为：
其中为样本总数，分别子集的样本数量。它就是每个子集的基尼系数的加权和，权重是每个子集的大小（以子集占整体集合大小的百分比来表示）。

5.1.2.2 划分单元和划分点

一棵CART 分类树对应着输入空间的一个划分，以及在划分单元上的输出值。
设输出为分类的类别，是离散变量。训练数据集。
设已经将输入空间划分为个单元，且在每个单元上有一个固定的输出值。则CART 分类树模型可以表示为：
其中为示性函数。
如果已知输入空间的单元划分，基于分类误差最小的准则，则CART 分类树在训练数据集上的损失函数为：
根据损失函数最小，则可以求解出每个单元上的最优输出值为：上所有输入样本对应的输出的众数。
即：。

5.1.2.3 生成算法

CART 分类树的生成算法：
a. 输入：
① 训练数据集
② 停止计算条件
b. 输出：CART 决策树
c. 步骤：
① 选择最优切分维度和切分点。
即求解：。
它表示：遍历所有可能的维度和该维度所有可能的取值，取使得基尼系数最小的那个维度和切分点。
② 用选定的划分区域并决定响应的输出值：
其中和分别代表区域和中的样本数量。
③ 对子区域递归地切分，直到满足停止条件。
④ 最终将输入空间划分为个区域，生成决策树：。

5.1.3 其它讨论

CART 分类树和CART 回归树通常的停止条件为：

结点中样本个数小于预定值，这表示树已经太复杂。
样本集的损失函数或者基尼指数小于预定值，表示结点已经非常纯净。
没有更多的特征可供切分。

前面讨论的CART 分类树和CART 回归树都假设特征均为连续值。

连续的特征也可以通过分桶来进行离散化，然后当作离散特征来处理。
实际上CART 树的特征可以为离散值，此时切分区域定义为：

5.2 CART 剪枝

CART 树的剪枝是从完全生长的CART 树底端减去一些子树，使得CART 树变小（即模型变简单），从而使得它对未知数据有更好的预测能力。

5.2.1 原理

定义CART 树 T 的损失函数为。其中：

为参数是时树 T 的整体损失。
为树 T 对训练数据的预测误差。
为子树的叶结点个数。

对固定的，存在使最小的子树，令其为。可以证明是唯一的。

当大时，偏小，即叶结点偏少。
当小时，偏大，即叶结点偏多。
当时，未剪枝的生成树就是最优的，此时不需要剪枝。
当时，根结点组成的一个单结点树就是最优的。此时剪枝到极致：只剩下一个结点。

令从生成树开始剪枝。对任意非叶结点，考虑：需不需要对进行剪枝？

以为单结点树：因为此时只有一个叶结点，即为本身，所以损失函数为：。
以为根的子树：此时的损失函数为：。

可以证明：

当及充分小时，有。即此时倾向于选择比较复杂的，因为正则化项的系数太小。
当增大到某个值时，有。
当再增大时，有。即此时倾向于选择比较简单的，因为正则化项的系数太大。

令，此时与有相同的损失函数值，但是的结点更少。因此比更可取，于是对进行剪枝。

对内部的每一个内部结点，计算。

它表示剪枝后整体损失函数增加的程度（可以为正，可以为负）。则有：

因为是个内部结点，所以，因此有：

时，，表示剪枝后，损失函数增加。
时，，表示剪枝后，损失函数不变。
时，，表示剪枝后，损失函数减少。

对内部的每一个内部结点，计算最小的：

设对应的内部结点为，在内减去，得到的子树作为。

它也是所有内部结点剪枝结果中，减少的最多的。因此是内的最优子树。

如果损失函数是减少的，它也没有减少的多。

对任意一个非内部结点的剪枝，得到的子树的损失函数有可能是增加的，也可能是减少的。
对于剪枝，得到的子树的损失函数一定是减少的。

如此剪枝下去，直到根结点被剪枝。

此过程中不断产生的值，产生新区间
此过程中不断产生最优子树
其中是由产生的、内的最优子树；是由产生的、内的最优子树；...

上述剪枝的思想就是用递归的方法对树进行剪枝：计算出一个序列，同时剪枝得到一系列最优子树序列。其中。其中是时的最优子树。

上述剪枝的结果只是对于训练集的损失函数较小。

交叉验证的本质就是为了挑选超参数。

验证过程：用独立的验证数据集来测试子树序列中各子树的平方误差或者基尼指数。
需要用交叉验证的方法在验证集上对子树序列进行测试，挑选中出最优子树。

六、连续值、缺失值处理

6.1 连续值

现实学习任务中常常会遇到连续属性，此时可以使用连续属性离散化技术将连续特征转换为离散特征。
最常用的离散化技术为二分法bi-partition ：
给定样本集和连续属性，假设该属性在中出现了个不同的取值。
这也是 C4.5 算法采取的方案。

将这些值从小到大进行排列，记作。
选取个划分点，依次为：。
然后就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集和的划分。

事实上划分点的数量可以是任意正整数，划分点的位置也可以采取其它的形式。

事实上，划分点的数量、划分点的位置都是超参数，需要结合验证集、具体问题来具体分析。

6.2 缺失值

现实任务中经常会遇到不完整样本，即样本的某些属性值缺失。
如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，则是对数据信息的极大浪费。
这里有两个问题：

如何在属性值缺失的情况下选择划分属性？
给定划分属性，如果样本在该属性上的值缺失，则如何划分样本？

6.2.1 划分属性选择

给定训练集和属性，令表示中在属性上没有缺失的样本子集。则可以仅根据来判断属性的优劣。
假定属性有个可能的取值。令：

表示：中在属性上取值为的样本的子集
表示：中属于第类的样本子集（一共有个分类）。
根据定义有：

为每个样本赋予一个权重，定义：

其物理意义为：

表示：无缺失值样本占总体样本的比例。
表示：无缺失值样本中，第类所占的比例。
表示：无缺失值样本中，在属性上取值为的样本所占的比例。

将信息增益的计算公式推广为：

其中：。

6.2.2 样本划分

基于权重的样本划分：
a. 如果样本在划分属性上的取值已知，则：
① 将划入与其对应的子结点。
② 的权值在子结点中保持为。
b 如果样本在划分属性上的取值未知，则：
① 将同时划入所有的子结点。
② 的权值在所有子结点中进行调整：在属性值为对应的子结点中，该样本的权值调整为。
直观地看，基于权重的样本划分就是让同一个样本以不同的概率分散到不同的子结点中去。

这一做法依赖于：每个样本拥有一个权重，然后权重在子结点中重新分配。
C4.5使用了该方案。

七、多变量决策树

由于决策树使用平行于坐标轴的拆分，使得它对于一些很简单的问题很费力。
比如：当时为正类；否则为反类。这种拆分边界并不平行于坐标轴，使得决策树会用许多层的拆分来逼近这个边界。
解决方案是：多变量决策树multivariate decision tree 。

传统的单变量决策树的分类边界每一段是与坐标轴平行的，每一段划分都直接对应了某个属性的取值。
多变量决策树的分类边界可以为斜线，它可以大大简化了决策树的模型。

多变量决策树中，内部结点不再是针对某个属性，而是对属性的线性组合。即：每个内部结点是一个的线性分类器。其中：

是属性的权重。
d 为变量的数量。
t 表示这些变量的约束。

与传统的单变量决策树不同，在多变量决策树的学习过程中，不是为每内部结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

本文福利

可以在本公众号后台 回复关键词：“ DS ”获取大量由我平台编辑精心整理的学习资料，如果觉得有用，请勿吝啬你的留言和赞哦！

—— 完 ——

文章须知

文章作者：华校专

责任编辑：周岩 Logic 征帆

审核编辑：阿春

微信编辑：Logic

本文由『运筹OR帷幄』原创发布

如需转载请在公众号后台获取转载须知

数据科学 | 算法工程师必备的机器学习--决策树

决策树

一、 原理