2021人工智能领域新星创作者，带你从入门到精通，该博客每天更新，逐渐完善机器学习各个知识体系的文章，帮助大家更高效学习。
一、概述
决策树是一类非常经典的算法，很多集成模型的基学习器都是基于决策树的，像xgboost、gbdt、rf等，本篇重点讲解下决策树的分类原理，尽管它相对于那些树的集成模型效果不是太好，但是有必要了解一些最基本的树模型是如何分类的。
决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART分类回归树算法。
决策树有点和数据结构中的树结构相似，都是有根节点和有向边的概念，然后不断进行分支，每个节点都会存在一定的约束条件，而最终的叶节点不同，它不存在约束条件，而是包含着分类结论，我们目标就是如何构建这样一棵树，然后利用根节点进行分类，重点就是学习每个节点的约束条件，以及树的路径。
简单来说，决策树每个节点的约束条件就是一个特征，如果满足该特征的什么条件就会分向哪个子节点，比如：
这就是一颗最简单的子树结构，接下来我们详细讲解树模型。
二、算法流程
1.决策树的if-then准则
上面我们说到，我们会根据每个特征中的取值进行判断，如果该取值满足不同的条件就会分到不同的子节点中，上面的不同天气就被分到 不同的节点中，说白了就是像编程中的if-else，如果满足一个条件怎么样，满足另外一个条件怎么样，这里执行的语句就是分配到相应的节点中去，对于一个样本来说，我们可以不断根据特征进行询问，每个特征满足什么，然后进行划分路径，最终划分到相应的叶子节点中去。
2.过拟合现象
所以说树模型天生过拟合，因为树模型可以针对每个样本做定制化服务，可以按照每个样本的特征进行生成一条属于它的路径，树模型有潜力将所有的样本进行完全分类，如果树生长的足够茂盛，极端情况就是最终生成的树，每个节点只包含一个样本，这样每个叶节点样本都会对应一个属于自己的路径，这样尽管会生长出一颗完全适合训练集的树，但是这样显然对未知数据的泛化能力较低，因为过拟合的树对于每个样本学习的太过具体，将一些噪声或者异常数据都会学习到，并生成对应的叶节点，没有学到每类样本的通性，因为我们同类的事物具有相同的体征，所以我们希望树模型会学习到同类样本的通性，那么就是说这颗树模型不能长的太深，太深学的就会太过细致，所以需要用到剪枝算法，将多余的枝叶进行修剪，具体怎么修下面会讲。
3.特征空间的划分
下面我们从另外一个角度来说明树的划分，上面我们看到其实我们是构建了一颗树，然后使用if——else准则来划分每个样本的，划分准则的标准就是每个节点都会有约束条件，就是某个特征满足什么就会分布到哪个节点，树中每个节点都是如此，所以当树模型生成完之后，我们每个叶节点上的数据就是经过了各种特征的约束，将不同的分配到不同节点，相同的分配到同一节点。
为了讲解方便，下面画了一幅平面图，仔细观察他，就是我们划分树的准则，某个区域代表样本的分类，如果在同一区域那么该区域内的样本类型相同，每个区域就是服从了不同的条件，根据坐标轴我们划分了4个区域，首先根据横轴特征，分界点a1将所有样本分成两类，即两个节点，然后每个节点根据纵轴，进而再进行分割。
上面的这个平面图就对应着下面这个树：
可以理解为就是将原来的特征空间分成多个小空间，然后每个小空间内的样本我们认为是相同的样本。
4.特征选择准则
其实决策树如果要是生长的话，会生成很多种决策树，如果每个节点采用选择不同特征的话，那么怎样去找到一颗最优的决策树呢？重点问题就是面对多个特征，我们选择谁作为第一个特征进行切分，为了衡量该问题，引出几个名词：
4.1 信息熵
“信息熵”是可以度量样本集合纯度的一种指标，它的公式定义为：
H ( x ) = − ∑ i = 1 n p i l o g p i H(x)=-\sum_{i=1}^np_ilog\ p_iH(x)=−i=1∑npilogpi
- n：样本的类别数
- p i p_ipi ：每个类别的概率，如果标签为离散值，那么就是每个类别数除以样本总数
该指标就可以衡量我们样本的纯度，熵越小，模型越纯。
你比如说样本的数据都为一个分类，那么此时该类别的概率就为1，且 l o g 1 = 0 log\ 1=0log1=0 ，所以此时的熵为0，特别约定当概率为0时，p i l o g l o g i = 0 l o g 0 = 0 p_ilog\ log_i=0log\ 0=0piloglogi=0log0=0，所以两个极端都为0，也就对应着样本分类越集中，熵越小，如果样本每个类别都有，那么此时的熵就会很大，样本很混乱，什么都有。
举个例子：你将来有两个选择，一是毕业工作，而是考研，如果你下定决定要工作，那么此时你的意志非常坚定，工作的概率也会很大，所以此时你的内心没有任何混乱，如果两个方向你拿不准，又想考研，又想找工作，所以此时你的内心就会很混乱。
所以，有了这个指标我们就可以判定每个节点中样本数据的纯度了，我们希望每个节点的样本非常纯，每个节点都是同类样本，这样就表明我们将同类样本进行完全区分，但是再搭建树的初期，显然每个节点都是混乱的，不可能完全纯，所以针对每个节点我们的熵都不为0，所以它们就会有个差值，我们把它叫做信息增益，这么说其实不太严格。
4.2 信息增益
信息增益是分割前该节点的熵减去分割后对应所有儿子节点的熵的概率期望值，公式定义为下：
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A)g(D,A)=H(D)−H(D∣A)
其中 g ( D , A ) g(D,A)g(D,A) 表示按照特征A进行分割的信息增益，H ( D ) H(D)H(D) 代表分割前父节点的熵，H ( D ∣ A ) H(D|A)H(D∣A) 表示分割后子节点的熵的期望
H ( D ) = − ∑ i = 1 K p i l o g p i = − ∑ i = 1 K ∣ C k ∣ ∣ D ∣ l o g ∣ C k ∣ ∣ D ∣ H(D)=-\sum_{i=1}^Kp_ilog\ p_i\\=-\sum_{i=1}^K\frac{|C_k|}{|D|}log\ \frac{|C_k|}{|D|}H(D)=−i=1∑Kpilogpi=−i=1∑K∣D∣∣Ck∣log∣D∣∣Ck∣
- K：样本的分类数
- ∣ C k ∣ |C_k|∣Ck∣：每个类别样本的数目
- ∣ D ∣ |D|∣D∣：样本总数
这样就可以求出每个类别的概率，求出对应的熵。
H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ H ( D i ) = − ∑ i = 1 n ∣ D i ∣ D ∑ j = 1 K ∣ D i j ∣ ∣ D i ∣ l o g ∣ D i j ∣ ∣ D i ∣ H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)\\=-\sum_{i=1}^n\frac{|D_i|}{D}\sum_{j=1}^K\frac{|D_{ij}|}{|D_i|}log\ \frac{|D_{ij}|}{|D_i|}H(D∣A)=i=1∑n∣D∣∣Di∣H(Di)=−i=1∑nD∣Di∣j=1∑K∣Di∣∣Dij∣log∣Di∣∣Dij∣
可以看到公式，分割后的 H ( D ∣ A ) H(D|A)H(D∣A) 就是每个子节点的熵期望，用每个节点的概率乘以自己的期望，自身的概率为每个节点的样本数除以父节点样本总数。
有时也把 H ( D ) H(D)H(D) 叫做经验熵，而 H ( D ∣ A ) H(D|A)H(D∣A) 经验条件熵，经验条件上就是一个条件概率的数学期望，意为在某个特征：
H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)H(Y∣X)=i=1∑npiH(Y∣X=xi)
这样我们就可以使用信息增益来衡量分别使用每个特征进行划分后的效果，如果该增益越大，说明划分后的熵与原来比越小，相差越大，该特征的划分能力越强。
4.3 信息增益比（增益率）
上面讲我们可以使用信息增益作为衡量每个特征的划分能力，但有时这样不太好，它偏向于向多特征值的进行划分，你比如有一个特征为学号，10个样本，我们按照这个特征划分，我们可以划分为10个子节点，那么划分之后每个节点的熵为0，因为我们可以按照学号将每个学生全部分割开，但是这样显然不行，这个例子有点牵强。
而且使用信息增益还有一个问题是没有考虑熵的相对大小，信息增益使用的是绝对大小，你比如说现在有两个学生，学生a在第一次考试考了10分，学生b在第二次考了60分，学生a在第二次考试考了20分，学生b第二次考了80分，这么看学生a进步了10分，而学生b进步了20分，显然学生b进步大，但是有的时候不能够这样进行比，这么比只是进步分数绝对大小。
我们换个角度考虑，学生a第一次考了10分，第二次考了20分，那么它进步了10分，但是相对于第一次来说，它进步了一倍，而学生b进步了20分，但是这20分只是第一次考试的1/3，所以从这个相对进步的角度来说，显然a进步大。
对于我们的信息增益也是，有些特征划分可能获得的信息增益较大，但是相对于没划分之前可能熵的纯度提升的比较小，有些特征信息增益小，但是它提升的倍数大，所以我们考虑使用这种相对大小进行衡量，这就是信息增益比，它的定义如下：
g R ( D , A ) = g ( D , A ) H A ( D ) g_R(D,A)=\frac{g(D,A)}{H_A(D)}gR(D,A)=HA(D)g(D,A)
- g R ( D , A ) g_R(D,A)gR(D,A) ：信息增益比
- g ( D , A ) g(D,A)g(D,A) ：信息增益
H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g ∣ D i ∣ ∣ D ∣ H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log\ \frac{|D_i|}{|D|}HA(D)=−i=1∑n∣D∣∣Di∣log∣D∣∣Di∣
其中的n代表子节点个数，就是每个特征的特征值个数。
三、ID3决策树
ID3算法的核心就是使用了信息增益进行选择特征，递归构建决策树，具体方法就是首先构建根节点，然后对于该节点计算所有特征的信息增益，选择信息增益最大的作为该节点的特征，然后每个节点不断递归执行该过程，直到所有节点特征的信息增益小于初始设定的阈值或者数据完全分类，或者没有特征可以选取位置。
算法流程：
输入：训练数据集D，特征集A和信息增益阈值 ϵ \epsilonϵ
输出：训练好的决策树
- 如果D中数据全部属于同一个类别，那么直接返回根节点，该节点的类型就为所有数据的类型，因为所有数据都是同一类别，没有继续分割的必要
- 对于该节点，分别计算所有特征的信息增益，选取信息增益最大的特征作为切分特征
- 如果信息增益小于设定的阈值说明按照该特征进行切分，没什么大的变化，所以不进行切分，将该节点做为叶子节点
- 递归上述步骤，对每个子节点继续计算信息增益进行划分，注意使用过的特征下面不能再次使用
- 直到所有节点完全分类或者没有多的特征可以使用或者所有特征的信息增益小于阈值，树生成完毕
四、C4.5决策树
对于C4.5就不详细说了，因为它和ID3决策树非常相似，只不过就是把衡量指标从信息增益变成了信息增益比。
五、剪枝算法
决策树天生就是一种会过拟合的算法，因为它会根据数据集无限制的生长，直到达到停止条件才会结束，这样的树会非常好的拟合我们的训练数据，因为极端情况下它会根据每个样本划分出一条树的路径，每个叶子都是一个样本，这样的树对训练集的准确率非常好，但是这样树的泛化能力就会很低。
过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决这个问题的方法就是在尽量不影响准确率的同时降低树的复杂度，对树模型进行简化。
一般情况下来说我们认为树的节点越多，层数越多，就越认为树模型的复杂度越高，所以我们可以使用剪枝算法对树进行修剪，说变了就是自下向上剪去一些分支。
针对于剪枝算法一般分为两种：预剪枝、后剪枝
1.预剪枝
预剪枝就是它会在生成树的过程中就进行考虑，比如说计算当前节点分割前和分割后的模型的损失函数，如果发现按照该特征分割后模型的损失函数升高，那么就说明此时该节点不应该分割，需要剪枝，该节点就不会进行拆分。
2.后剪枝
所谓的后剪枝就是先按照数据集生成一个过拟合的树，然后再自下向上的进行修剪，二者区别是一个是建造树的过程中，一个是建造完。
针对于剪枝来说，我们往往通过极小化决策树整体的损失函数，决策树的损失函数定义如下：
C a ( T ) = ∑ i = 1 ∣ T ∣ N i H i ( T ) + a ∣ T ∣ C_a(T)=\sum_{i=1}^{|T|}N_iH_i(T)+a|T|Ca(T)=i=1∑∣T∣NiHi(T)+a∣T∣
解释下不同变量的意思：
- ∣ T ∣ |T|∣T∣ ：代表整个树的叶子节点个数
- ∣ N i ∣ |N_i|∣Ni∣ ：代表每个叶子节点上的样本数
- H i ( T ) H_i(T)Hi(T) ：代表每个叶子节点的经验熵
上述的损失函数可以理解为模型的预测误差+模型的复杂度，前者是所有叶子节点的经验熵，该值越小说明每个叶子节点的纯度越高，分类越明确，后者是模型的复杂度，用叶子节点的个数来代表。
如果我们的树越茂密，此时经验熵即预测误差很小，但此时的复杂度很大，因为叶子节点数多，如果为了防止过拟合，适当剪枝，此时复杂度会减小，但是模型的预测误差又会上升，所以我们的目标就是找到一个完美的树模型能够平衡两者，既有较好的预测误差，又有较好的模型泛化能力，它和线性回归中加入正则项差不多，其中的a就是惩罚系数，人为设定。
算法流程：
输入：生成算法生成的整个树 T TT，参数a
输出：剪枝后的树 T a T_aTa
- 计算每个节点的经验熵
- 自底向上递归进行剪枝
- 剪枝前后的树分别为 T A T_ATA ，T B T_BTB ，分别计算剪枝前后的两个树的损失函数值 C a ( T A ) C_a(T_A)Ca(TA) 、C a ( T B ) C_a(T_B)Ca(TB)
- 如果发现 C a ( T A ) ≤ C a ( T B ) C_a(T_A)\leq C_a(T_B)Ca(TA)≤Ca(TB) ，就将其剪枝，说明剪枝带来的模型复杂度减小大于预测误差的上升
- 直到获得损失函数最小的决策子树
