决策树算法算是一个很经典的算法了，既可以分类，也可以做回归，同时适合集成学习。
什么是决策树
一种对样本进行分类的树型结构，也可把它看成if-then规则的集合。
树中的内部节点代表一个属性，该节点引出的分支表示这个属性的全部取值，叶节点表示最终的分类结果。从根节点到叶节点的每条路径便构成if-then的一条规则，且具有互斥且完备的性质，即每一个样本均被且只被一条路径覆盖。
如何学习得到一颗决策树
决策树学习本质上是从训练数据上归纳出一种分类规则，使它与训练数据矛盾较小（即能对训练数据正确分类）的同时具有良好的泛化能力。（模型讲完，接下来就是策略与算法）
决策树学习的策略是以损失函数（通常是正则化的极大似然函数）为目标函数的最小化（同其他机器学习模型一致，区别就在于如何优化）。算法则采用启发式算法来近似求解最优化问题，主要分为三步：
- 特征选择
- 模型生成
- 决策树剪枝
具体讲解这三个步骤
决策树学习的算法是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使分割后的各个子集有一个最好分类的过程。这一过程就是划分特征空间，构建决策树的过程。
【如何选择最优特征】
直观上，如果一个特征具有更好的分类能力，即分割后各个子集中的样本尽可能属于同一类别，那么就更应该选择这个特征。特征分类能力的衡量有信息增益(ID3)、信息增益比(C4.5)、基尼系数(CART)。
【对信息增益、信息增益比、基尼系数的了解】
1. 信息增益
由熵引申而来。熵是表示随机变量不确定性（无序性）的度量，熵越大，随机变量的不确定性也越大。对于同一枚硬币，当抛正面、抛反面概率相等（概率分布为均匀分布）的情况下，此时不确性定最大，熵也最大。对有相同概率分布的不同随机变量来说，取值越多的随机变量熵越大。
随机变量$X$的熵的表达式如下：
其中n表示X的n种不同取值，而$p_i$表示X取值为i的概率。
而条件熵是指在已知随机变量$X$的情况下，随机变量$Y$剩下的不确定性。计算方式为：经过X分割过后，各个分支节点的信息熵乘以一个权重的加权求和。这个权重是为了考虑到不同的分支节点所包含的样本数不同，具体公式为：
信息增益表示的是：得知特征X的信息而使得分类Y信息的不确定性减少的程度。某个特征的信息增益比较大，就表示该特征分类能力也越大。特征A对数据集D的信息增益为：
2. 信息增益比
用信息增益选择最优划分特征有一个问题：偏向于选择取值较多的特征，这就导致训练出来的树非常宽且深度不深，容易过拟合。所以这里我们使用信息增益比，即把信息增益除以训练集$D$关于特征$A$的熵，公式表示为：
3. 基尼系数
无论是信息增益还是增益率都涉及到大量的对数运算，为了简化模型与运算量，我们使用基尼系数作为替代。基尼系数表示模型的不纯度，基尼系数越小，则不纯度越低，特征的分类效果就越好。
假设样本$D$有K个类别，第K个类别的概率为$p_k$，则样本$D$的基尼系数为：
特别的，对于样本$D$，如果根据特征$A$的某个值a，把$D$分成$D1$和$D2$两部分，则在特征$A$的条件下，$D$的基尼系数表达式为：
【递归的终止条件是什么】
主要有3个终止条件：
- 当前训练子集被正确分类，即全属于同一类别，无需划分
- 可用特征为空，即特征全部用完
- 可用特征的信息增益或增益率小于某个阈值$\epsilon$
【为什么要剪枝，如何剪枝】
为防止过拟合，要把过于复杂的树进行剪枝，进行简化。剪枝以极小化决策树整体的损失函数来实现。要注意的是：决策树的生成是学习局部的模型，而决策树剪枝是学习整体的模型。
损失函数如下：
其中，$|T|$ 是树$T$ 的叶节点个数，$t$ 是其中一个叶节点，$N_t$ 是这个叶节点的样本个数，$H_t(T)$ 是这个叶节点的熵，$α|T|$ 表示对模型复杂度的惩罚项（正则化）。
我们再仔细看一看这个损失函数，$C(T)$ 不就是以熵来表示各个叶节点的分类误差（如果某叶节点下的样本属于同一类，那么效果最佳，熵为0），并把所有叶节点的误差相加来表示模型对训练样本的预测误差。
一般剪枝算法
给定一个$\alpha$ 后，通过不断剪枝来减小模型的整体损失。具体为：
- 计算每个节点的熵
- 递归地从叶节点向上回缩：假设一叶节点在回缩到父节点之前的损失函数值$>=$ 回缩之后的损失函数值，则该剪，即父节点变成新的叶节点
常用的 ID3/C4.5/CART 算法区别在哪里
【ID3】
- 使用
信息增益选择最优划分特征，但会遇到问题：通常取值较多的特征信息增益大 - 未考虑过拟合问题，即没有剪枝
- 无法处理连续特征，大大限制的ID3的用途
- 没有考虑到数据缺失的情况
【C4.5】
C4.5算法在ID3的基础上改进了上述4个问题。
改进一：使用信息增益比替代信息增益。
改进二：引入了正则化系数进行初步的剪枝，防止过拟合
改进三：处理连续特征
解决思路是连续特征离散化，同时使用二分法。对特征$A$的m个不同取值从小到大排序为$a_1,a_2,…,a_m$, 不妨取每两个相邻节点的均值$T_i=\frac{a_i+a_{i+1}}{2}$作为划分点。对于这（m-1）个点，可像离散属性一样选取最优划分点。注意：若当前节点为连续属性，该属性还可参与后续的子节点产生过程。如先划分属性$A<=10$ ，后续还可继续划分属性$A<=5$。
改进四：处理缺失数据
这里需要解决两个问题：
- 如何在特征缺失的情况下选择划分属性
- 选定了划分属性之后，如何对样本进行划分
对于问题1，我们对在特征$A$ 上无缺失值的样本计算$A$ 特征对应的信息增益比，最后再乘以一个系数，这个系数是特征$A$ 无缺失的样本所占的比例。
对于问题2，将缺失特征的样本同时划入所有子节点，不过要乘以各个子节点所划入无缺失样本的比例。比如，特征A有3个特征值A1,A2,A3。3个特征值对应的无缺失A特征的样本个数为2,3,4。则缺失特征A的样本a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。
C4.5不足的地方：
- 使用了熵模型，涉及到大量的对数与排序运算，运算强度高
- 生成的是多叉树。若采用二叉树，可提高计算机运算效率
- 只能用于分类
- 剪枝算法有优化空间
【CART】
CART算法对C4.5算法的不足做出了改进。主要有CART分类树与CART回归树，下面先讲解分类树。
1. CART分类树的最优特征选择
使用基尼系数选择最优特征，二次运算比对数运算简单的多
2. CART分类树对于离散特征处理的改进
对离散特征进行二分。如特征$A$有$a1,a2,a3$ 三种类别，ID3与C4.5的做法是建立一个三叉的节点，生成的多叉树。而CART会考虑把$A$分成$\{a1\}$和$\{a2,a3\}$，$\{a2\}$和$\{a1,a3\}$ ，$\{a3\}$和$\{a1,a2\}$这三种情况，找基尼系数最小的组合，比如$\{a1\}$和$\{a2,a3\}$，然后建立二叉树，后续还有机会在子节点上继续选择特征$A$划分$\{a2,a3\}$。
3. CART回归树
相比于CART分类树，不同的地方是：
最优特征选择与连续值处理方式不同。对于回归模型，使用平方误差的度量方式，寻找最优特征A与最优切分点s，使得切分过后的数据集D1与D2各自均方差最小，且D1与D2的均方差之和最小，具体为：
其中c1为D1数据集的样本输出均值，c2为D2数据集的样本输出均值。
最后预测方式不同。分类树是以叶节点里概率最大的类别作为预测类别，而回归树输出的是一个值，采用最终叶节点的均值来预测输出结果。
4. CART树算法的剪枝
相比与一般剪枝，其优势在于不用一开始确定$\alpha$值，而是在剪枝的同时找到最优$\alpha$值。剪枝过程主要分两步：
- 从原始决策树$T_0$底端开始不断剪枝，直到$T_0$的根节点，形成以子树序列$\{T_0,T_1,…,T_n\}$
- 通过在独立的验证集上进行交叉验证，从中选出最优子树(同时$\alpha$也是确定下来的)
剪枝思路
【三类算法小结】
| 算法 | 支持模型 | 树结构 | 特征选择 | 连续值处理 | 缺失值处理 |
|---|---|---|---|---|---|
| ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 |
| C4.5 | 分类 | 多叉树 | 信息增益比 | 支持 | 支持 |
| CART | 分类，回归 | 二叉树 | 基尼系数，均方差 | 支持 | 支持 |
决策树算法小结
不纠结于ID3，C4.5还是CART，从整体上看决策树算法
【优点】
- 不用数据预处理，不用数据归一化，可以处理缺失数据
- 可同时处理离散型特征与连续性特征（许多算法两者并不能兼得）
- 决策树很直观，逻辑上好解释
【缺点】
- 容易过拟合，通常要设置节点最小样本数、限决策树深度来改进
- 启发式算法容易陷入局部最优，可通过集成方法改善
- 复杂的关系，决策树较难学习