理解决策树
投稿声明
各位SIGAIer，SIGAI欢迎业内专家来平台投稿，大家一起共建专业的人工智能知识分享平台。投稿一旦接收，SIGAI将会赠送雷明老师的《机器学习与应用》签名书，并根据实际情况提供相应的报酬和福利。
投稿请联系：SIGAI_admin
决策树是什么？
决策树是最简单的机器学习算法，它易于实现，可解释性强，完全符合人类的直观思维，有着广泛的应用。决策树到底是什么？简单地讲，决策树是一棵二叉或多叉树（如果你对树的概念都不清楚，请先去学习数据结构课程），它对数据的属性进行判断，得到分类或回归结果。预测时，在树的内部节点处用某一属性值（特征向量的某一分量）进行判断，根据判断结果决定进入哪个分支节点，直到到达叶子节点处，得到分类或回归结果。这是一种基于if-then-else规则的有监督学习算法，决策树的这些规则通过训练得到，而不是人工制定的。
一个简单的例子
上面的说法过于抽象，下面来看一个实际的例子。银行要用机器学习算法来确定是否给客户发放贷款，为此需要考察客户的年收入，是否有房产这两个指标。领导安排你实现这个算法，你想到了最简单的线性模型，很快就完成了这个任务。
模型的决策边界：
-20 + 3*年收入 +20*是否有房 = 0
决策规则为：
-20 + 3*年收入 +20*是否有房 >= 0 可贷款
-20 + 3*年收入 +20*是否有房 < 0 不可贷款
你拿着精心设计出来的模型去跟领导讲，但是发现没人听得懂你在干嘛，领导认为你根本不懂得怎么评估客户。
这次碰壁之后，你冥思苦想，给出了另外一个方案。风控业务员是怎么判断是否给用户贷款的？他们的做法很简单：
1.首先判断客户的年收入指标。如果大于20万，可以贷款；否则继续判断。
2.然后判断客户是否有房产。如果有房产，可以贷款；否则不能贷款。
如果用图形表示这个决策过程，就是一棵决策树。决策过程从树的根节点开始，在内部节点处需要做判断，直到到达一个叶子节点处，得到决策结果。决策树由一系列分层嵌套的判定规则组成，是一个递归的结构。这个例子的决策树如下图所示：
在上图中，内部节点用矩形表示，叶子节点用椭圆表示。这个模型一目了然，领导一听就懂，而且觉得你非常专业。
基本概念
决策树出现于1980年代。决策树的实现有ID3，C4.5，CART（Classification and Regression Tree，分类与回归树）等方法，它们的区别在于树的结构与构造算法。决策树是一种判别模型，天然支持多类分类问题。如果用于分类问题，决策树称为分类树；如果用于回归问题，则称为回归树。
分类树对应的映射函数是多维空间的分段线性划分，即用平行于各个坐标轴的超平面对空间进行切分；回归树的映射函数是分段常数函数。决策树是分段线性函数但不是线性函数，它具有非线性建模的能力。只要划分的足够细，分段常数函数可以逼近闭区间上任意函数到任意指定精度，因此决策树在理论上可以对任意复杂度的数据进行分类或者回归。对于分类问题，如果决策树深度够大，它可以将训练样本集的所有样本正确分类。但如果特征向量的维数过高，可能会遇到维数灾难导致准确率下降。
下图是决策树进行空间划分的一个例子。在这里有红色和蓝色两类训练样本，用下面两条平行于坐标轴的直线可以将这两类样本分开：
这个划分方案对应的决策树如下图所示：
以上图像来自SIGAI的云端实验室。
训练算法
现在要解决的关键问题是怎样用训练样本建立决策树。如果对于分类问题，训练得到的决策树至少要让训练样本尽快能的被分正确。
直观的想法是从根节点开始构造，递归的用训练样本集建立起决策树，这棵树能够将训练集正确的分类，或者对训练集的回归误差最小化。为此要解决以下问题：
如果特征向量有多个分量，每个决策节点上应该选择哪个分量做判定？例如上图中有x和y两个分量，我们哪x做判定还是拿y做判定？这个判定会将训练样本集一分为二，然后用这两个子集构造左右子树。
在选定一个特征后，具体分裂的规则是什么？即满足什么条件时进入左子树分支。对数值型变量（可以比较大小，如收入，年龄）的做法是寻找一个分裂阈值进行判断，小于该阈值进入左子树，否则进入右子树。对于类别型变量（不能比较大小，只是对类型的编号，如将红色编成1，蓝色为2）则需要为它确定一个子集划分，将特征的取值集合划分成两个不相交的子集，如果特征的值属于第一个子集则进入左子树，否则进入右子树。
何时停止分裂，把节点设置为叶子节点？对于分类问题，当节点的样本都属于同一类型时停止，但是这样可能会导致树的节点过多、深度过大，产生过拟合问题。另一种方法是当节点中的样本数小于一个阀值时停止分裂。
如何为每个叶节点赋予类别标签或者回归值？即到达叶子节点时样本被分为哪一类或者赋予一个什么实数值。
下面给出这几个问题的答案以及训练算法。特征有数值型变量和类别型变量两种情况，决策树分分类树和回归树两种情况，限于篇幅，我们只对数值型变量进行介绍。
递归分裂过程
训练算法是一个递归的过程。首先创建根节点，然后建立左子树和右子树。如果练样本集为D，训练算法的整体流程为：
1.用样本集D建立根节点，找到一个判定规则，将样本集分裂成D1和D2两部分，同时为根节点设置判定规则。
2.用样本集D1递归建立左子树。
3.用样本集D2递归建立右子树。
4.如果不能再进行分裂，则把节点标记为叶子节点，同时为它赋值。
在确定这个递归流程之后，接下来要解决的核心问题是怎样对训练样本集进行分裂。
寻找最佳分裂
训练时需要找到一个分裂规则把训练样本集分裂成两个子集，因此要确定分裂的评价标准，根据它寻找最佳分裂。对于分类问题，要保证分裂之后左右子树的样本尽可能的纯，即它们的样本尽可能属于不相交的某一类或者几类。为此需要定义不纯度的指标：当样本都属于某一类时不纯度为0；当样本均匀的属于所有类时不纯度最大。满足这个条件的有熵不纯度，Gini不纯度，以及误分类不纯度，下面分别进行介绍。
不纯度指标用样本集中每类样本出现的概率值构造。因此首先要计算每个类出现的概率，这通过训练样本集中每类样本数除以样本总数得到：
其中Ni是第i类样本数，N为总样本数。根据这个概率值可以定义各种不纯度指标，下面分别介绍。
样本集的熵不纯度定义为
熵是信息论中的一个重要概念，用来度量一组数据包含的信息量大小。当样本只属于某一类时熵最小，当样本均匀的分布于所有类中时熵最大。因此，如果能找到一个分裂让熵最小，这就是我们想要的最佳分裂。
样本集的Gini不纯度定义为：
当样本属于某一类时Gini不纯度的值最小，此时最小值为0；当样本均匀的分布与每一类时Gini不纯度的值最大。这源自于如下的数学结论，在下面的约束条件下：
对于如下目标函数：
所有变量相等时它有极小值，只有一个变量为1其他变量为0时该函数有极大值，这对应于Gini不纯度的极小值。即所有样本都来自同一类时Gini不纯度的值最小，样本均匀的属于每一类时Gini不纯度的值最大。将类概率的计算公式代入Gini不纯度的定义，可以得到简化的计算公式：
样本集的误分类不纯度定义为：
之所以这样定义是因为我们会把样本判定为频率最大的那一类，因此其他样本都会被错分，故错误分类率为上面的值。和上面的两个指标一样，当样本只属于某一类时误分类不纯度有最小值0，样本均匀的属于每一类时该值最大。
上面定义的是样本集的不纯度，我们需要评价的是分裂的好坏，因此需要根据这个不纯度构造出分裂的不纯度。分裂规则将节点的训练样本集分裂成左右两个子集，分裂的目标是把数据分成两部分之后这两个子集都尽可能的纯，因此我们计算左右子集的不纯度之和作为分裂的不纯度，显然求和需要加上权重，以反映左右两边的训练样本数。由此得到分裂的不纯度计算公式为：
其中G(Dl)是左子集的不纯度，G(Dr)是右子集的不纯度，N是总样本数，Nl是左子集的样本数，Nr是右子集的样本数。
如果采用Gini不纯度指标，将Gini不纯度的计算公式代入上式可以得到：
其中Nl,i是左子节点中第i类样本数；Nr,i是右子节点中第i类样本数。由于N是一个固定值，要让Gini不纯度最小化等价于让下面的值最大化：
这个值可以看做是Gini纯度，它的值越大，样本越纯。寻找最佳分裂时需要计算用每个阈值对样本集进行分裂后的这个值，寻找该值最大时对应的分裂，它就是最佳分裂。如果是数值型特征，对于每个特征将l个训练样本按照该特征的值从小到大排序，假设排序后的值为：
接下来从x1开始，依次用每个xi作为阈值，将样本分成左右两部分，计算上面纯度值，该值最大的那个分裂就是此特征的最佳分裂。在计算出每个特征的最佳分裂阈值和上面的纯度值后，比较所有这些分裂的纯度值大小，该值最大的分裂为所有特征的最佳分裂。对单个变量寻找最佳分裂阈值的过程如下图所示：
如果是回归树，衡量分裂的标准是回归误差即样本方差，每次分裂时选用使得方差最小化的那个分裂。假设节点的训练样本集有l个样本(xi, yi)，其中xi为特征向量，yi为实数的标签值。节点的回归值为所有样本的均值，回归误差为所有样本的标签值与回归值的均方和误差，定义为：
把均值的定义带入上式，得到：
根据样本集的回归误差，我们同样可以构造出分裂的回归误差。分裂的目标是最大程度的减小回归误差，因此把分裂的误差指标定义为分裂之前的回归误差减去分裂之后左右子树的回归误差：
将误差的计算公式代入上式，可以得到：
由于N和
寻找最佳分裂时要计算上面的值，让该值最大化的分裂就是最佳分裂。回归树对类别型特征的处理和分类树类似，只是E值的计算公式不同，其他的过程相同。
叶子节点值的设定
如果不能继续分裂，则将该节点设置为叶子节点。如果是分类树，则叶子节点的值设置成本节点的训练样本集中出现概率最大的那个类；如果是回归树，则设置为本节点训练样本标签值的均值。
属性缺失问题
某些情况下样本特征向量中一些分量没有值，这称为属性缺失。例如晚上我们无法观察到物体的颜色值，颜色属性就缺失了。在决策树的训练过程中，寻找最佳分裂时如果某一个属性上有些样本有属性缺失，可以把这些缺失该属性的样本剔除掉，然后照常训练，这是最简单的做法。
除此之外还可以使用替代分裂规则。对于每个决策树节点除了计算出一个最佳分裂规则作为主分裂规则，还会生成一个或者多个替代分裂规则作为备选。在预测时如果主分裂规则对应的特征出现缺失，则使用替代分裂规则进行判定。需要注意的是，替代分裂对于分类问题和回归问题是做相同的处理。
现在的关键问题是怎样生成替代分裂规则。主分裂和替代分裂对所有样本的分裂结果有4种情况，分别是：
LL, LR, RL, RR
LL表示被主分裂、替代分裂都分到了左子树的样本数。LR表示被主分裂分到了左子树，被替代分裂分到了右子树的样本数。RL表示被主分裂分到了右子树，被替代分裂分到了左子树的样本数。RR表示被主分裂和替代分裂都分到了右子树的样本数。
因此LL+RR是被替代分裂正确分类的样本数，LR+RL是被替代分裂错分的样本数。由于可以将左右子树反过来，因此给定一个特征分量，在寻找替代分裂的分裂阈值时要让LL+RR或者LR+RL最大化，最后取它们的最大值：
max(LL + RR, LR + RL)
该值对应的分裂阈值为替代分裂的分裂阈值。对于除最佳分裂所用特征之外的其他所有特征，都找出该特征的最佳分裂和上面的值。最后取该值最大的那个特征和分裂阈值作为替代分裂规则。
剪枝算法
如果决策树的结构过于复杂，可能会导致过拟合问题，此时需要对树进行剪枝，消掉某些节点让它变得更简单。剪枝的关键问题是确定减掉哪些树节点以及减掉它们之后如何进行节点合并。决策树的剪枝算法可以分为两类，分别称为预剪枝和后剪枝。前者在树的训练过程中通过停止分裂对树的规模进行限制；后者先构造出一棵完整的树，然后通过某种规则消除掉部分节点，用叶子节点替代。
预剪枝可以通过限定树的高度，节点的训练样本数，分裂所带来的纯度提升的最小值来来实现，具体做法在前面已经讲述。后剪枝的典型实现有降低错误剪枝（Reduced-Error Pruning，简称REP）、悲观错误剪枝（Pesimistic-Error Pruning，简称PEP）、代价-复杂度剪枝（Cost-Complexity Pruning，简称CCP）等方案。分类与回归树采用的是代价-复杂度剪枝算法，下面重点介绍它的原理。
代价是指剪枝后导致的错误率的变化值，复杂度是指决策树的规模。训练出一棵决策树之后，剪枝算法首先计算该决策树每个非叶子节点的a值，它是代价与复杂度的比值。该值定义为：
其中E(n)是节点n的错误率，E(nt)是以节点n为根的子树的错误率。为子树的叶子节点数，即复杂度。a值是用树的复杂度归一化之后的错误率增加值，即将整个子树剪掉之后用一个叶子节点替代，相对于原来的子树错误率的增加值。该值越小，剪枝之后树的分类效果和剪枝之前越接近。上面的定义依赖于节点的错误率指标，下面对分类问题和回归问题介绍它的计算公式。对于分类问题，错误率定义为：
其中N是节点的总样本数，Ni是第i类样本数，这就是之前定义的误分类指标。对于回归问题，错误率为节点样本集的均方误差：
子树的错误率为树的所叶子节点错误率之和。计算出a值之后，剪掉该值最小的节点得到剪枝后的树，然后重复这种操作直到剩下根节点，由此得到一个决策树序列：
其中T0是初始训练得到的决策树，Ti+1在Ti的基础上剪枝得到的，即剪掉Ti中a值最小的那个节点为根的子树用一个叶子节点替代后得到的树。
整个剪枝算法分为两步完成：
第一步先训练出T0，然后用上面的方法逐步剪掉树的所有非叶子节点，直到只剩下根节点得到剪枝后的树序列。这一步的误差计算采用的是训练样本集。
第二步根据真实误差值从上面的树序列中挑选出一棵树作为剪枝后的结果。这可以通过交叉验证实现，用交叉验证的测试集对上一步得到的树序列的每一棵树进行测试，得到这些树的错误率，然后根据错误率选择最佳的树作为剪枝后的结果。
通过实验理解决策树的训练过程
在介绍完原理之后，下面我们通过实验来理解决策树的训练过程，核心是递归分裂创建二叉树，以及寻找最佳分裂特征与阈值。选定一个样本集之后，决策树的创建过程如下面的动画所示：
以上结果来自SIGAI云端实验室，如果你对此感兴趣，可以向SIGAI公众号发消息，申请使用。我们的实验室提供了强大的功能，可以帮助大家更容易，深刻的理解各种数学，机器学习，深度学习，以及应用领域的算法！
推荐文章
[1] 机器学习-波澜壮阔40年 SIGAI 2018.4.13.
[2] 学好机器学习需要哪些数学知识？SIGAI 2018.4.17.
[3] 人脸识别算法演化史 SIGAI 2018.4.20.
[4] 基于深度学习的目标检测算法综述 SIGAI 2018.4.24.
[5] 卷积神经网络为什么能够称霸计算机视觉领域？ SIGAI 2018.4.26.
[6] 用一张图理解SVM的脉络 SIGAI 2018.4.28.
[7] 人脸检测算法综述 SIGAI 2018.5.3.
[8] 理解神经网络的激活函数 SIGAI 2018.5.5.
[9] 深度卷积神经网络演化历史及结构改进脉络-40页长文全面解读 SIGAI 2018.5.8.
[10] 理解梯度下降法 SIGAI 2018.5.11.
[11] 循环神经网络综述—语音识别与自然语言处理的利器 SIGAI 2018.5.15
[12] 理解凸优化 SIGAI 2018.5.18
[13]【实验】理解SVM的核函数和参数 SIGAI 2018.5.22
[14] 【SIGAI综述】行人检测算法 SIGAI 2018.5.25
[15] 机器学习在自动驾驶中的应用—以百度阿波罗平台为例(上) SIGAI 2018.5.29
[16] 理解牛顿法 SIGAI 2018.5.31
[17]【群话题精华】5月集锦—机器学习和深度学习中一些值得思考的问题 SIGAI 2018.6.1
[18] 大话Adaboost算法 SIGAI 2018.6.2
[ 19] FlowNet到FlowNet2.0：基于卷积神经网络的光流预测算法 SIGAI 2018.6.4[20] 理解主成分分析(PCA) SIGAI 2018.6.6[21] 人体骨骼关键点检测综述 SIGAI 2018.6.8