决策树算法（Decision Tree，DT）是一种可用于分类与回归的方法分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类（针对连续数据而言是回归）的过程。
决策树方法兴起于上世纪60年代到70年代末，其中J Ross Quinlan提出了ID3算法，此算法的目的在于减少树的深度，但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。而CART分类回归树，同样是在ID3的基础上进行优化的决策树，顾名思义即是分类树，又是分类树，它与C4.5不同的是采用了二叉树。
决策树算法需要构造决策树来发现数据中蕴涵的分类规则，如何构造精度高、规模小的决策树是决策树算法的核心内容。无论何种决策树，其构造大致可分两步进行：第一步，决策树的生成，指由训练样本集生成决策树的过程；第二步，决策树的剪枝。决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修正的过程，是后续决策树不断优化得到的结果，主要是用新的样本数据集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预测准确性的分枝剪除。通过生成与剪枝，形成准确性与泛化性适合的决策树模型。
决策树模型呈树形结构，如图1所示。在分类问题中，表示基于特征对实例进行分类的过程，因此它需要事先确定选择哪些特征，按照何种顺序使用这些特征，工作过程可以认为是if-then规则的嵌套使用，也可以认为是定义在特征空间与类空间上的条件概率分布，由节点与有向边组成，节点分为内部节点（图中圆角矩形，代表一个属性或者特征）和叶节点（矩形节点，代表一个类）。决策树从另一个角度看也是一种条件概率模型，决策树可能存在一个或多个，甚至不存在，从多个决策树中选择最优解属于NP问题，因此是近似解。
图1 决策树示例目前决策树的典型算法有ID3、C4.5、CART等，本章也重点讲解这三种。
ID3即Iterative Dichotomiser 3，迭代二叉树3代，虽然名称上是二叉树，但是允许多叉树。ID3是Ross Quinlan发明的一种典型的基于奥卡姆剃刀原理的决策树算法，即用尽量少的东西做更多的事，C4.5、CART都是在其基础上发展而来。决策树的叶子节点表示类标号，非叶子节点作为属性判别条件。从树的根节点开始，将判别条件用于数据集，根据判别结果选择恰当的分支，循环直至满足迭代结束条件而到达叶子节点，叶子节点的类标号即为该样本的类别。从泛化性来说，小型的决策树优于大决策树，但过小的树型结构又不利于预测分类，实际上这是一个启发式过程。
ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂，算法采用自顶向下的贪婪搜索遍历可能的决策空间。
信息增益（information gain，IG），因为信息增益是互信息的无偏估计，在决策树的训练过程中两者是等价的，因此也称互信息。ID3采用IG作为分裂属性的度量，最佳分裂等价于求解最大的信息增益，因此先简单介绍信息增益。
信息增益是针对一个特征而言的，计算系统（数据集）有它和去掉它时的信息量，两者的差值就是这个特征给系统带来的信息量，即信息增益，它可以用来确定谁是根节点，并选择后续分裂的属性。选取特征T下集合S的信息增益计算公式如下：
img 其中
表示特征
已知：数据集α
待求：多叉树，其中树枝为特征，树叶为类别
步骤：
（1）根据数据集
（2）若某一分节点下的所有样本对应的类标签相同或信息增益小于阈值，该节点记为树叶，不再分解；
（3）若该节点信息增益大于阈值，其下还存在不同的特征分类，则将该特征下相同属性值对应的所有样本抽出来组成新的样本集，在该样本集下再去除该特征，计算其它特征分类对标签的信息增益，最大的作为第二个节点；
（4）依此类推，直到满足结束条件。
ID3算法只注重树的生成，分叉可能过细而产生过拟合，因此Ross Quinlan对之前开发的ID3算法进行了一个扩展得到了C4.5算法，它采用了信息增益比来替换信息增益，相对更合理，避免了偏向于选择较多取值的特征的问题（当一个属性取值特别多时，其对应的信息增益往往更容易突出，造成其他特征没法与之抗衡，从而使算法过于偏向该特征）。
信息增益比定义为：
img 其中，D为数据集，A为某一特征，g为信息增益【与前面的IG写法不统一】，
img
分类与回归树（Classification And Regression Tree, CART）模型是应用广泛的决策树学习方法，同样由特征选择、树的生成和剪枝组成，既可以用于分类也可以用于回归。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。
CART对决策树进行了剪枝，目的是为了防止决策树出现过拟合，裁掉部分树枝或树叶可提高使用准确率。对决策树是否进行剪枝的度量标准是决策树的损失函数是否降低，定义CART的损失函数为：
img 、 、
、 α
剪枝流程：
（1）计算所有点的信息熵；
（2）依次选择某个叶节点，退到其父节点，剪掉该父节点后，得到新的决策树，若新的决策树具有更小的损失函数Cα(T)，则将该父节点变成叶节点；
（3）依次继续，直到损失函数最小的子树出现。
剪枝主要预剪枝和后剪枝。预剪枝是在决策树生成过程中，在划分节点时，若该节点的划分没有提高其在训练集上的准确率，则不进行划分。后剪枝决策树先生成一棵完整的决策树，再从底往顶进行剪枝处理。
CART包括二叉决策树生成（尽可能大）与剪枝（需要验证集）操作。注意，它与ID3和C4.5不同，要求必须是二叉树。
（1）二叉树生成
回归树用平方误差最小化准则，而分类树用基尼指数最小化准则。
1）回归树生成
回归问题针对连续变量而言，一般是指最小二乘回归树。
a）选定某个特征（
） 、
img img b）遍历所有输入向量的所有特征，算出最佳的切分变量
其中，，
， 、
c）继续对两个子区域调用步骤、
d）将输入空间分为
img 这里的I是指示函数，当
回归树构建完成后，就完成了对整个输入空间的划分（即完成了回归树的建立）。将整个输入空间划分为多个子区域，每个子区域输出为该区域内所有训练样本的平均值。
2）分类树生成
用基尼指数替换信息增益或者信息增益比，成为衡量节点的指标。基尼指数定义：
img K为分类问题中的类总数，
img D1、D2是由特征A取得某一值而被分割的两部分。这个式子显示了可以通过根据某个特征划分的多个子集的基尼指数计算出父集的基尼指数。
基尼指数越大，样本集合的不确定性越大，与熵相似。具体流程：
a）对于每一个特征
b）记下得到的基尼指数最小的特征
c）针对这两个子集重复以上1、2步骤，直到完成停止条件；
d）生成CART决策树。
（2）剪枝
在CART最后，一般需要进行剪枝，有预剪枝和后剪枝两种，基本都可以分为两步：
①找到所有的决策树子树；
先回到上述损失函数上，将其重新写成
img 第二项是控制模型复杂度的，和决策树的剪枝有一定关系。当α特别小时，该项影响不大，损失函数会忽视模型复杂的限制，会选择更加复杂的模型；当α特别大时，又十分重视复杂度，这时决策树就必须简化，因此α取不同值意味着决策树的剪枝程度。
考虑某个分支根节点
img 应当变成（即等于）：
img 这里t为叶节点，节点数量
α α
img 本着叶节点α
采用同样的方法在新的决策树上不断执行，最后直至走到起始的根节点。
②在新的验证数据集上采用交叉验证的方法，平方误差或基尼指数最小的为最优决策树。
上面介绍了三种算法的简单流程，这里将其抽取出共性特征进行说明，无论哪种决策树方法，基本步骤满足以下几步：
1）根据指标从训练样本的所有特征中选择一个作为树的根节点，如图1中的outlook；
2）检查在该特征分类下各分支的样本是否在同一个类，是则该结点成为叶节点，分支结束，并用该类标记，如图1中的overcast节点；
3）若分支后，某一个或多个分支下具有不同类的样本，在剩余的特征中依据指标再次选择最有分类能力的属性作为决策树的当前新分支结点，如图1中的sunny下又选择了humidity属性；
4）针对上一步得到的一个子集，重复进行先前步骤，递归形成每个划分样本上的决策树。一旦一个属性出现在一个结点上，就不必在该结点的任何后代考虑它。
5）递归划分步骤仅当下列条件之一成立时停止：
①属性与样本均被使用完，即给定结点的所有样本属于同一类，图1属于这种情况；
②属性被使用完，但某一属性下还存在不同类别的多个样本。在这种情况下，使用多数表决，将给定的结点转换成叶节点，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布；
③属性还有，但某一分枝已经没有满足该分支中已有分类的样本，则以样本的多数类创建一个树叶。
决策树构造的输入是一组带有类别标记的例子，构造的结果是一棵二叉树或多叉树。二叉树或多叉树的内部节点（非叶子节点）一般表示为一个逻辑判断，如形式为
由于数据表示不当、有噪声或者由于决策树生成时产生重复的子树等原因，都会造成产生的决策树过大。因此，简化决策树是一个不可缺少的环节。寻找一棵最优决策树，主要应解决以下3个最优化问题：①在横向上优化，即生成最少数目的叶子节点；②在纵向上优化，即生成的每个叶子节点的深度最小；③生成的决策树叶子节点最少且每个叶子节点的深度最小。
表1 天气预报数据集
order outlook temperature humidity windy play or not play 1 sunny hot high FALSE no 2 sunny hot high TRUE no 3 overcast
hot high FALSE yes 4 rain mild high FALSE yes 5 rain cool normal FALSE yes 6 rain cool normal TRUE no 7 overcast cool normal TRUE
yes 8 sunny mild high FALSE no 9 sunny cool normal FALSE yes 10 rain mild normal FALSE yes 11 sunny mild normal TRUE yes
12 overcast mild high TRUE yes 13 overcast hot normal FALSE yes 14 rain mild high TRUE no
例如上表中，针对决策目标是play来说，yes有9个，no有5个，整个系统S的熵为：
img 此时系统未考虑任何特征，因此是最不稳定的，熵也是最大的。
如果考虑特征Outlook的信息增益，首先计算加上Outlook单个特征系统的熵，这是由于添加了一个特征，熵公式中的i增加，系统稳定性增加，可以预见熵S将会降低。
（1）确定根节点
Outlook特征的稳定性贡献体现在将决策play又细分为下图三种。
img 系统S有三种情况，sunny、overcast和rainy，则新系统
的熵：
而
img img img 信息增益
img 有：
img 最终得到特征属性T带来的信息增益为：
同样可以求得特征属性temperature、humidity、windy的条件熵分别为：0.91106、0.78845、0.82073，信息增益分别为：0.02922、0.15184、0.11956。很明显，outlook的信息增益是最大的，取其为根节点。组成的决策树是：
img （2）确定第二级分支
根据上图可知，overcast已经分类完毕，但rain和sunny下仍然有不同类，因此抽出两个子数据集：
order outlook temperature humidity
windy play or not play 4 rain mild high FALSE yes 5 rain cool normal FALSE yes 6 rain cool normal TRUE no 10 rain mild normal FALSE yes 14 rain mild high TRUE no
order outlook temperature humidity windy play or not play 1 sunny hot high FALSE no 2 sunny hot high TRUE no 8 sunny mild high FALSE no 9 sunny cool normal FALSE yes 11 sunny mild normal TRUE yes
首先考虑rain的分支。
去掉rain属性后得到的是：
temperature humidity windy play or not play
mild high FALSE yes cool normal FALSE yes cool normal TRUE no mild normal FALSE yes mild high TRUE no
新的标签集合S【三个yes和两个no】的总信息熵为：
Entropy（S）=
先考虑T为temperature属性，mild含两个yes和一个no，cool含一个yes和一个no，条件熵：
考虑humidity属性，high含一个yes和一个no，normal含两个yes和一个no，条件熵明显和temperature一样，为0.95098：
最后考虑windy属性，false含3个yes，true含两个no，条件熵为0，很明显其信息增益最大，因此rain的分支属性为windy；
再考虑sunny的分支。
去掉sunny属性后得到的是：
temperature humidity windy play or not play hot high FALSE no hot high TRUE no mild high FALSE no cool
normal FALSE yes mild normal TRUE yes
标签集合S【三个no和两个yes】的总信息熵为：
Entropy（S）=
先考虑temperature属性，hot含两个no，mild含一个yes和一个no，cool含一个yes，条件熵：
Entropy（S|T）=0+2/5+0 =0.4
考虑humidity属性，high含三个no，normal含两个yes条件熵明显为0：
最后考虑windy属性，false含1个yes和2个no，true含一个no和一个yes，条件熵为0.95098。很明显humidity属性其信息增益最大，因此sunny的分支属性为humidity；
综上最终将得到如图5- 6的决策树。至此所有的样本已经被分完，虽然还有属性值如temperature没进入到决策树，但树叶节点已经都有确定类别，即play或not play某一项数量为0，决策树构建完毕。
C4.5只是在ID3基础上增加了分母项Entropy(S)，其它计算与分析过程与上述示例一致。
ID3算法的算例相对较为简洁，无法用于剪枝，选择新的西瓜分类数据集，其中训练集如下所示。
order color root knocks texture navel
touch label 1 dark_green curl_up little_heavily distinct sinking hard_smooth 1 2 black curl_up heavily distinct sinking hard_smooth 1 3 black curl_up little_heavily distinct sinking hard_smooth 1
4 dark_green little_curl_up little_heavily distinct little_sinking soft_stick 1 5 black little_curl_up little_heavily little_blur little_sinking soft_stick 1 6 dark_green stiff clear distinct even soft_stick 0 7 light_white little_curl_up heavily
little_blur sinking hard_smooth 0 8 black little_curl_up little_heavily distinct little_sinking soft_stick 0 9 light_white curl_up little_heavily blur even hard_smooth 0 10 dark_green curl_up heavily little_blur little_sinking hard_smooth
0 11 dark_green curl_up heavily distinct sinking hard_smooth 1
验证集为：
order color root knocks texture navel touch label 12 light_white curl_up little_heavily distinct sinking hard_smooth
1 13 black little_curl_up little_heavily distinct little_sinking hard_smooth 1 14 black little_curl_up heavily little_blur little_sinking hard_smooth 0 15 light_white stiff clear blur even hard_smooth 0 16
light_white curl_up little_heavily blur even soft_stick 0 17 dark_green little_curl_up little_heavily little_blur sinking hard_smooth 0
（1）基本决策树
首先得到未剪枝的决策树，使用ID3的算法流程，将Gini指数作为划分标准，计算训练集的基尼指数：
计算在特征color下【dark_green:5, black:4, light_white:2】集合的基尼指数：
=0.3544
同理计算其他特征下的基尼指数：
Gini（D, root）=
Gini（D, knocks）=
Gini（D, navel）=
Gini（D, touch）=
基尼指数最小的是navel，根节点首先为navel，得到的决策树是：
img 其他过程按照此循环，得到的决策树为：
img 可以看到，每个分支叶结点都只有一个样本（共11个），这很可能已经出现了过拟合，需要剪枝。
（2）预剪枝的决策树
预剪枝是边构建决策树边检查基尼指数是否降低，若剪完之后基尼系数降低了，则实施剪枝操作。由于表示基尼系数降低程度的阈值会因不同问题类型难以设定，因此多采用验证集来判定是否需要剪枝，使用验证集来验证如果剪枝后决策树对验证集的准确率得到了提升，则实施剪枝。基于此策略，得到的预剪枝决策树是：
img （3）后剪枝的决策树
后剪枝是在总的决策树构建完之后进行修剪。同样可以使用验证集验证准确率是否提升来确定是否剪枝，得到的剪枝结果是：
img （一）单一变量回归树
训练数据见下表，x的取值范围为区间[0.5,10.5]，y的取值范围为区间[5.0,10.0]，学习这个回归问题的最小二叉回归树。
x 1 2
3 4 5 6 7 8 9 10 y 5.56 5.70 5.91 6.40 6.80 7.05 8.90 8.70 9.00 9.05
根据所给数据，考虑如下切分点：
1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5。
对各切分点，根据公式，不难求出相应的R1、R2、c1、c2。例如，当s=1.5时，R1={1}，R2={2,3,...,10}，根据
img 得出c1=5.56，c2=7.50，则利用公式
同理，可将s及m(s)的所有计算结果列表如下：
s
1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5 m(s) 15.72 12.07 8.36 5.78 3.91 1.93 8.01 11.73 15.74
由上表可知，当x=6.5的时候达到最小值，此时R1={1,2,3,4,5,6}，R2={7,8,9,10}，c1=6.24，c2=8.9，所以回归树T1(x)为：
对两个子区域R1、R2继续调用前述步骤：
对R1继续进行划分：
x 1 2 3 4
5 6 y 5.56 5.7 5.91 6.4 6.8 7.05
取切分点[1.5, 2.5, 3.5, 4.5, 5.5]，则各区域的输出值c如下表：
s 1.5 2.5 3.5 4.5 5.5 c1 5.56 5.63 5.72 5.89 6.07 c2
6.37 6.54 6.75 6.93 7.05
计算m(s)：
s 1.5 2.5 3.5 4.5 5.5 m(s) 1.3087 0.754 0.2771 0.4368 1.0644
得到当s=3.5时，m(s)最小。
对R2继续进行划分的过程不再赘述。
假设在生成3个区域之后停止划分，最终生成的回归树形式如下：
img （二）多变量回归树
当x变成多变量时，还需要在每个属性之间进行对比，确定优先进行二分叉的属性。
根据下表属性来预测y。
序号 xi,1 xi,2 y x1 1 22 2.0 x2 1 23 2.6 x3 1 29 3.0 x4 2 23 1.2 x5 2
25 1.4
从数据特征可以发现，每个样本有两个特征，且第一个特征只有两类，类似离散数据，第二类特征则更多样化，类似连续数据。
首先以属性1为切分点，则1、2、3样本为一组，4、5样本为一组：
均值c1=(2.0+2.6+3.0)/3=2.53，均值c2=1.3。
平方误差=(2.0-2.53)2+(2.60-2.53)2+(3.0-2.53)2+(1.2-1.3)2+(1.4-1.3)2=0.517+0.02=0.537
其次，以属性2为划分：
以年龄22切分点，c左-均值=2.0，c右-均值=(2.6+3.0+1.2+1.4)/4=2.05，平方误差=(2.0-2.0)**2+(2.6-2.05)** 2+(3.0-2.05)** 2+(1.2-2.05)** 2+(1.4-2.05)** 2=2.35
以年龄23切分点，c左-均值=(2.0+2.6+1.2)/3=1.93，c右-均值值=(3.0+1.4)/2=2.20，平方误差=(2.0-1.93)** 2+(2.6-1.93)** 2+(3.0-2.2)** 2+(1.2-2.2)** 2+(1.4-2.2)** 2=2.73
以年龄25切分点，c左-均值=(2.0+2.6+1.2+1.6)/4=1.85，c右-均值=3.0，平方误差=(2.0-1.85)** 2+(2.6-1.85)** 2+(3.0-1.85)** 2+(1.2-1.85)** 2+(3.0-3.0)** 2=2.33
根据上述总体划分情况，以属性1作为第一次分裂，左子树为1、2、3三个样本，右子树为4、5两个样本。
CART既能由于分类，也能由于回归，被很多其它算法作为基函数使用，比如梯度提升决策树（Gradient Boosting Desicion Tree，GBDT）。GBDT将在后续Xgboost、LightGBM算法中均由提及，这里简单介绍，具体可参考后续章节。
GBDT算法的基本流程是：
已知：训练数据集
代求：提升树
（1）初始化
（2）对于m=1,2,...,M；
（a）计算残差
（b）将残差作为新的样本标签值，组成新的样本数据集T(x,θm)
（c）更新
θ
（3）输出最终回归提升树
img 针对不同的损失函数和树的类型，提升树有不同的用途，对于前向分布算法（见Adaboost、Xgboost相关解释）来说，当损失函数取指数损失，基函数取二叉分类树，前向分布算法就变成了用于分类的提升树算法;当损失函数取平方损失，基函数取二叉回归树，前向分布算法就变成了用于回归的提升树算法。
ID3和C4.5用于分类，生成的决策树可以是多叉，每个节点下的叉树由该节点特征的取值种类而定，比如特征年龄分为（青年，中年，老年），那么节点下可分为3叉。CART与ID3和C4.5相同，都由特征选择、树的生成、剪枝三步组成，CART可用于分类与回归，与ID3和C4.5的决策树所不同的是，CART假设决策树为二叉树，内部结点特征取值为”是”和”否”，等价于递归地二分每一个特征，将输入空间划分为有限个单元，并在这些单元上预测概率分布，也就是在输入给定的条件下输出条件概率分布。
算法优缺点比较：
ID3算法优缺点：
（1）不能对连续数据进行处理，只能通过连续数据离散化进行处理；
（2）采用信息增益进行数据分裂容易偏向取值较多的特征，准确性不如信息增益率；
（3）缺失值不好处理；
（4）没有采用剪枝，决策树的结构可能过于复杂，出现过拟合。
C4.5算法优缺点：
（1）产生的规则易于理解、准确率较高、实现简单；
（2）对数据进行多次顺序扫描和排序，效率较低；
（3）只适合小规模数据集，需要将数据放到内存中。
CART算法优缺点：
（1）无论是ID3，C4.5还是CART，在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树（multi-variate decision tree）。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。
（2）如果样本发生一点点的改动，就会导致树结构的剧烈改变，后期可通过集成学习，如随机森林方法解决。
