决策树

1.决策树基础

决策树结构

决策树学习过程

2.集合纯度

【问题】什么样的划分属性才是最优的？评判标准是什么？
如果经过一个属性划分后，分支结点包含的样本尽可能属于同一个类别（纯度高），这个属性就是好的划分属性。

2.1信息增益、增益率

是样本集合D中第k类样本所占的比例。
信息熵（entropy）：
当时（全为同一类），，当时（各类别数量相同），。信息熵的值越小，样本纯度越高。
离散属性 a 有 v 个取值：，使用 a 对样本集D进行划分。

样本子集：D中所有在属性a上取值为的样本。

信息增益（information gain）：
信息增益越大，通过属性 a 获得的纯度提升越大。
ID3决策树算法（Iterative Dichotomiser）：以信息增益为准则来划分属性。
【注意】

• 对于划分属性为离散属性的，父节点中已经使用过用于划分的属性，在子节点中不再作为候选划分属性。对于划分属性是连续属性的，后代节点还可以使用该属性作为划分属性。
• 信息增益准则对取值数目较多的属性有所偏好，因为这些分支结点的纯度更大（信息熵小），信息增益较大；但此时得到的决策树的泛化能力更弱了。

增益率（gain ratio）：
C4.5决策树算法：以增益率为准则来划分属性。当属性是连续值时，使用二分法处理属性的划分。
【注意】

• 增益率对可取值较少的属性有所偏好。
• 使用增益率来划分属性时，先找出信息增益高于平均水平的属性，再从这些属性中选择增益率最高的。

  2.2基尼指数

  基尼值：
  基尼值反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。基尼值越小，数据集的纯度越高。
  基尼指数（Gini index）：，
  基尼指数越小，数据集的纯度越高。

CART决策树算法（Classfication and Regression Tree）：使用基尼指数来划分属性；分类和回归任务都可以使用。

分类树

CART算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。
每一次选择使基尼系数最小的属性作为切分点（划分的数据集纯度越高）直到满足停止条件为止。算法的停止条件是节点中的样本个数小于预定阈值，或者样本集的基尼系数小于预定阈值（样本基本属于同一类），或者没有更多特征。
下图显示二分类问题中基尼系数、熵（单位比特）之半1/2*H(p)和分类误差率的关系。横坐标表示概率p，纵坐标表示损失。可以看出基尼系数和熵之半曲线很接近，都可以近似的代表分类误差率。

回归树

假设训练数据集为D：，输出变量是连续变量。将输入空间划分为M个单元，每个单元上都有一个固定输出。
则一个回归树对应着输入空间上的一个划分以及划分单元上的输出值，即

选择以第j个特征/属性以及它的取值s作为切分变量和切分点，可将数据集划分为两个区域：
，
采用平方误差损失来求解最优的切分变量和切分点：
，对应每个区域的平均值。
然后每个(j,s)对里找出使总误差最小的对作为最终的切分变量和切分点，对切分后的子区域重复这一步骤，直到满足停止条件为止。这样就生成了一颗回归树。此时的回归树成为最小二乘回归树（least squares regression tree）。

3.决策树中的问题

3.1过拟合

预剪枝（prepruning）

• 属性划分前估计：在验证集上评估分类精度。
• 属性划分后估计：在验证集上评估分类精度。
• 决定是否根据当前属性对数据集做出划分：如果划分前的精度更高，就停止划分，将当前节点标记为叶节点，类别是当前节点数据集中样本数量最多的那个类别。

预剪枝是自上而下的。
【问题】预剪枝“贪心”的禁止了很多分支的展开，尽管后续的分支可能会提升泛化的性能，所以预剪枝有欠拟合的风险。

后剪枝（postpruning）

• 生成一棵完整的决策树。
• 剪枝前估计：在验证集上评估分类精度。
• 剪枝后估计：在验证集上评估分类精度。
• 如果剪枝后估计的精度更高，就将结点领衔的分支剪除，替换为叶节点，类别是叶节点上数据集中样本数量最多的那个类别。

后剪枝是自下而上的。
【问题】后剪枝需要先生成决策树，再对非叶节点进行考察，时间开销较大。

3.2连续值

连续属性时，没有明确的界限，无法根据属性的可取值来划分数据集。

二分法（bi-partition）

二分法：连续属性的离散化。对连续属性 a 的n个取值，取出（n-1）个中位点作为候选划分点。

• 在每个划分点进行二分，计算数据纯度（比如以信息增益为准则去计算）。

• 选择最优的划分点。划分点就是中位点，或者设为该属性在训练集中出现的不大于中位点的最大值。

  3.3缺失值

  【问题】属性值缺失时，怎么进行最优属性的评判？
  
  使用信息增益对含有缺失值的属性进行划分评判时：
  
  【问题】属性值缺失时，样本怎么根据属性来划分？

• 当某个样本的属性取值已知时，将样本划入对应子节点，样本权重不变。

• 当某个样本的属性取值未知时，将样本划入所有子节点，样本权重在对应的子节点中为。

C4.5决策树算法使用以上的缺失值处理方案。

3.4多变量

决策树的分类边界是“轴平行”的：

【问题】分类边界的每一段都对应一个属性取值，当分类边界比较复杂时，需要进行大量的属性测试，时间开销较大。
【解决】非叶节点/划分属性不再是单一属性，而是多变量（例如：线性组合），寻找一个线性分类器是划分边界简化。
多变量决策树的算法有：OC1，最小二乘法，神经网络等。

线性分类器

在每个非叶节点上使用线性分类器来进行划分，
例如：，w是属性a的权重，w 和 t 通过在相应节点所含的样本集和属性集上学得。

6.1.树和森林的生成
bagging
boosting
6.2.优缺点

参考： 1.周志华《机器学习》