Machine Learning (2): Decision Tree

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

决策树简介

决策树是一种分类和回归的基本模型，可从三个角度来理解它，即：

  • 树形结构
  • 可看成是if-then规则的集合，该集合是决策树上的每一条从根节点到叶节点的路径的集合，决策树的路径或其对应的if-then规则集合互斥且完备
  • 表示给定特征条件下类的条件概率分布。决策树实际上是将特征空间划分成了互不相交的单元，每个从根到叶的路径对应着一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。实际中，哪个类别有较高的条件概率，就把该单元中的实例划分为该类别

决策树的学习本质上就是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树可能有多个，也可能没有，我们需要的是一个与训练数据集矛盾较小的决策树，同时具有较好的泛化能力。
从另一个角度看，决策树学习也是由训练数据集估计条件概率模型。

决策树的损失函数通常是正则化的极大似然函数，学习的策略是以损失函数为目标函数的最小化。
当损失函数确定后，决策树学习的策略变为在损失函数意义下选择最优决策树的问题。由于从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中，我们通常采用启发式算法来近似求解这一最优化问题，得到的决策树是次最优的。
该启发式算法可分为三步：

  • 特征选择
  • 模型生成
  • 决策树的剪枝

特征选择

信息熵（information entropy）

  • 在信息论与概率论中，熵(entropy)用于表示随机变量不确定性的度量。
  • 熵越大，则随机变量的不确定性越大。
  • 当p=0.5时，熵取值最大，随机变量不确定性最大。
  • 表示 Ent(D)
  • 范围 [0, log2|y|] （|y| 是样本的类数）
  • Ent(D) 越小，D纯度越高

信息增益（information gain）

  • 信息增益表示的是：得知特征X的信息而使得类Y的信息的不确定性减少的程度。
  • 表示 Gain(D, a)
  • 信息增益越大，意味着使用属性a来进行划分所获得的“纯度提升”越大。

增益率（gain ratio）

  • 以信息增益作为特征选择准则，会存在偏向于选择取值较多的特征的问题。
  • 可以采用信息增益比对这一问题进行校正。
  • 特征A对训练数据集D的信息增益比定义为其信息增益与训练集D关于特征A的值的熵之比
  • 表示 Gain_ratio(D, a) = Gain(D, a)/ IV(a)
  • IV(a) 称为属性a的“固有值”（intrinsic value）
  • 属性a的可能取值数目越多（即V越大），则IV(a) 的值通常会越大。

基尼指数（Gini index）

  • Gini(D)
  • CART决策树使用基尼指数来选择划分属性
  • Gini(D) 反映了从数据集D中随机抽取两个样本，其类别标志不一致的概率。
  • 因此，Gini(D) 越小，数据集D的纯度越高。

信息增益准则对可取值数目较多的属性有所偏好（导致泛化能力较差），为了减少这种偏好带来的不利影响，C4.5 不直接使用信息增益，而是使用增益率来选择最优划分
注意：增益率准则对可取值数目较少的属性有所偏好。(因此C4.5并不直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。??)

决策树的生成

ID3算法

ID3算法的核心是在决策树的各个结点上应用信息增益准则进行特征选择。具体做法是：

  • 从根节点开始，对结点计算所有可能特征的信息增益，选择信息增益最大的特征作为结点的特征，并由该特征的不同取值构建子节点；
  • 对子节点递归地调用以上方法，构建决策树；
  • 直到所有特征的信息增益均很小或者没有特征可选时为止。

C4.5算法

C4.5算法与ID3算法的区别主要在于它在生产决策树的过程中，使用信息增益比来进行特征选择。

CART算法

分类与回归树（classification and regression tree,CART）与C4.5算法一样，由ID3算法演化而来。CART假设决策树是一个二叉树，它通过递归地二分每个特征，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。
CART算法中，对于回归树，采用的是平方误差最小化准则；对于分类树，采用基尼指数最小化准则。

剪枝

剪枝是决策树预防过拟合的主要手段。

预剪枝（prepruning）

  • 决策树生成过程中，对每个结点在划分前先进行评估
  • 若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点
  • 预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。
  • 但另一方面，有些分支的当前划分虽不能提升泛化性能，甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高
  • 预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝（postpruning）

  • 先从训练集中生成一棵完整的决策树
  • 自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
  • 后剪枝决策树通常比预剪枝决策树保留了更多的分支。
  • 一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。
  • 但后剪枝过程是在完全生成决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

优缺点

优点

  • 易于理解和解释，甚至比线性回归更直观；
  • 与人类做决策思考的思维习惯契合；
  • 模型可以通过树的形式进行可视化展示；
  • 可以直接处理非数值型数据，不需要进行哑变量的转化，甚至可以直接处理含缺失值的数据；

缺点

  • 对于有大量数值型输入和输出的问题，决策树未必是一个好的选择；
  • 特别是当数值型变量之间存在许多错综复杂的关系，如金融数据分析；
  • 决定分类的因素取决于更多变量的复杂组合时；
  • 模型不够稳健，某一个节点的小小变化可能导致整个树会有很大的不同。

其他

连续值处理

  • 最简单地策略是采用二分法（bi-partition）对连续值进行处理，这正是C4.5决策树算法中采用的机制
  • 与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。（例如父结点使用了“密度<=0.38”，不会禁止在子结点上使用“密度<=0.29”）

缺失值处理

  • 如果简单地放弃不完整样本，仅适用无缺失值的样本来进行学习，显然是对数据信息的极大的浪费。
  • 缺失值同时进入各个分支中，但权重有所不同。即让同一个样本以不同的概率划分到不同的子结点中去。

参考