[数据结构与算法]决策树（Decision Tree）

定义

决策树是一种基于规则的方法，它用一组嵌套的规则进行预测。在树的每个决策节点处，根据判断结果进入一个分支，反复执行这种操作直到到达叶子节点，得到预测结果。这些规则是通过训练得到的，而不是认为设定的。
规则是每一次分裂时的特征及其阀值。

基本原理

先列举决策树算法最有名的几个版本，版本之间最明显的差异就是用于分裂节点的特征的选择标准不同，另外在应用场景（自变量离散或连续、因变量离散或连续）、剪枝、缺失值处理等操作上也有区别。

• 函数假设：分段函数（分类树的映射是多为空间的分段线性划分，即用平行于各坐标轴的超平面对空间进行切分；回归树的映射函数是分段函数。决策树是分段线性函数而不是线性函数，它具有非线性建模能力。）

• 损失函数：
  

• 学习方法：贪心算法

ID3

Step 1.计算在当前节点上的数据集的信息熵和未用于过节点分裂的特征的条件熵，选择信息增益最大的特征进行节点分裂，选择的特征有多少个取值则分裂为多少个叶子节点；
Step 2.继续下一个节点分裂，并进行Step 1，直至节点只包含单一特征或单一样本则停止分裂；

• 应用场景：自变量离散（多叉树），因变量离散（分类）
• 分裂节点的特征选择标准：信息增益
  信息增益：
  $Gain(D,A)=H(D)?H(D|A)$
  其中$H(D)$为数据集$D$的信息熵，$H(D|A)$为数据集$D$基于特征$A$的条件熵，即数据集$D$在用特征A进行数据划分前提下的信息熵。
  信息熵是度量数据集信息量大小的指标，信息量越大，代表数据集不纯度越高：
  $H(D)=?{\sum }_{k=1}^K{p}_{k}lo{g}_2{p}_k$，$p_k=\frac{|C_k|}{|D|}$，
  其中$K$为数据集$D$的类别数，$C_k$为数据集D属于类别$k$的样本集合，$|.|$表示数据集样本数。
  条件熵是度量数据集在某种划分下的信息量大小，这里是按特征A的特征值划分：
  $H(D|A)=?{\sum }_{m=1}^M{p}_{m}H(D_m)=?{\sum }_{m=1}^M{p}_m(?{\sum }_{k_m=1}^K{p}_{k_m}lo{g}_2{p}_{k_m})$，$p_m=\frac{|C_m|}{|D|}$，$p_{k_m}=\frac{|C_{k_m}|}{|D|}$，
  其中$M$为特征$A$的特征值取值数量即用特征$A$划分的类别数，$C_m$为数据集$D$特征$A$取值为$A$的第$m$个取值的样本集合，$C_{k_m}$为数据集$D$属于类别$k$且特征$A$取值为$m$的样本集合，$|.|$表示数据集样本数。
  故信息增益体现的是数据集D用特征A划分前后的信息量变化值，信息增益越大，说明利用特征$A$划分节点使数据集的不纯度降低的越多。
  信息增益的缺点是当特征$A$取值数量较多时会偏大：数据划分越细不纯度降低越快。
• 剪枝策略：无
• 缺失值处理：无

C4.5

• 应用场景：自变量离散或连续（多叉树），因变量离散（分类）
  若特征$A$为连续性取值，共m个取值，则从小到大排序，相邻两数取中间值作为节点划分候选值，再遍历每个值作为划分值时的信息增益、取信息增益最大的进行划分（此处有细节考虑）。
• 分裂节点的特征选择标准：信息增益率
  信息增益率：
  $Gai{n}_{ratio}(D,A)=\frac{Gain(D,A)}{H_A(D)},H_A(D)={\sum }_{m=1}^M{p}_{m}lo{g}_2{p}_m$，$p_m$同上
  这样信息增益率就避免了信息增益对取值种类多的特征有利的缺点，但又会偏好取值种类少的特征。因此会采用先用启发式算法：先找信息增益高于平均水平的特征，再选择信息增益率最大的那个特征。
• 剪枝策略：后剪枝策略
  待决策树构建完成后，利用递归自底向上针对非叶子节点进行剪枝，若剪枝后错误率更小则进行剪枝。
  ps：没采用的另一种剪枝策略是预剪枝，即贪心方法，在节点划分前来确定是否继续增长，比如节点样本数量低于阈值、划分后准缺率下降。
  两者相比，预剪枝降低过拟合风险、训练时间段但欠拟合风险又变大，后剪枝欠拟合风险小、泛化性通常比预剪枝好但训练时间长。
• 缺失值处理：特征值缺失样本不参与分裂特征选择，但利用不缺失样本计算信息增益率后会乘上非缺失样本占比；若仍选择该含缺失特征分裂，则分裂后缺失样本以每个节点上非缺失样本占总非缺失样本比例作为概率分配。

CART

• 多叉树改为二叉树，提高构建效率

• 应用场景：自变量离散或连续（二叉树），因变量离散或连续（分类）

  • 自变量连续同C4.5
  • 因变量连续时使用的分裂标准改为平方误差

• 分裂节点的特征选择标准：

  • 基尼指数：
    $Gini(D)={\sum }_{k=1}^K{p}_k(1?p_k)$，$p_k=\frac{|C_k|}{|D|}$，
    其中$K$为数据集$D$的类别数，$C_k$为数据集D属于类别$k$的样本集合，$|.|$表示数据集样本数。
    基尼指数可以为随机取两个样本、两个样本不属于同一类的概率，这里是按特征A的特征值划分,且注意这里是二叉树：
    $Gini(D|A)={\sum }_{m=1}^M{p}_{m}Gini(D_m)=p_{left}（1?p_{left})+p_{right}（1?p_{right})$，
    其中$M$为特征$A$的特征值取值数量即用特征$A$划分的类别数，$C_m$为数据集$D$特征$A$取值为$A$的第$m$个取值的样本集合，$C_{k_m}$为数据集$D$属于类别$k$且特征$A$取值为$m$的样本集合，$|.|$表示数据集样本数。
    这里取$Gini(D|A)$最小（等价于$Gini(D)$-$Gini(D|A)$）的特征作为分裂特征，且分裂特征可重复选取。
    基尼指数优点是省去了复杂的log计算；缺点是仍然偏向取值种类多的特征。
  • 平方误差：
    $mi{n}_{s}mi{n}_{c_1,c_2}{\sum }_{x_i<=s}(y_i?c_1{)}^2+{\sum }_{x_i>s}(y_i?c_2{)}^2=mi{n}_s{\sum }_{x_i<=s}(y_i?{\overline{y}}_1{)}^2+{\sum }_{x_i>s}(y_i?{\overline{y}}_2{)}^2$
    其中$s$为特征的划分值，$c_1$和$c_2$为左右节点的预测结果，对$c_1$和$c_2$求导可得$c_1$和$c_2$分别代表左右子节点上的平均值${\overline{y}}_1$和${\overline{y}}_2$

• 剪枝策略：基于代价复杂度剪枝

  • 代价复杂度参数$\alpha$计算公式如下，其中e(T)为错分率，p(T)为该节点所覆盖的样本量占总样本量的比例，L(T)为T节点的叶子节点的个数。俗话说，$\alpha$表示T节点进行分裂后，带来的错误率降低效果平均到所有叶子节点的结果，代表了误差降低程度和叶子节点数之间的平衡系数，$\alpha$越大，说明T节点分裂的“性价比”更高，每个叶子节点能均分到更大的误差降低”成就”，反之越小、“性价比”越低、更容易考虑取消分裂从而提高泛化性。
    
  • 计算每个非叶子节点的$\alpha$，循环对$\alpha$最小的节点进行剪枝（有多个节点同时取到最小值时取叶子节点最多的节点），直到只剩下根节点，可得到一系列的剪枝数{T0, T1, T2, …, Tm}，其中T0为原始的决策树，Tm为根节点，Ti+1为Ti剪枝后的结果。在这一系列的剪枝树中，根据实际的误差估计决定最优的决策树。

• 缺失值处理：存在代理特征，即若分裂特征的特征值缺失，则用基尼指数第二小的特征对应的特征值进行左右子节点分配，若第二小的特征特征值也缺失就用第三小的…

• 样本不均衡处理：分类场景下，一个叶子节点的最终预测结果为叶节点该类别样本数除以根节点该类别样本数得到比例更大的类别。

优缺点

决策树有两个优点：
一是得到的模型很容易可视化，非专家也很容易理解，
二是算法完全不受数据缩放的影响。由于每个特征被单独处理，而且数据的划分也不依赖于缩放，因此决策树算法不需要特征预处理，如果归一化或标准化。特别是特征的尺度完全不一样时或者二元特征和连续特征同时存在时，决策树的效果很好。

控制决策树模型复杂度的参数是预剪枝参数，它在树完全展开之前停止树的构造。通常来说，选择一种预剪枝策略（设置max_depth、max_leaf_nodes或min_samples_leaf）足以防止过拟合。

决策树的主要缺点在于，即使做了预剪枝，它也经常会过拟合（贪心策略），泛化性能很差。因此，在大多数应用中，往往使用bagging或者boosting集成方法来替代单颗决策树。

其他问题

决策树分裂标准、损失函数、误差率之间的关系

参考资料

【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）
模型算法基础——决策树剪枝算法（三）