决策树

1 基本流程

决策树基于树结构进行决策，决策过程的每个判定问题都是对某个属性的“测试”。

一般的，一棵决策树包含一个根节点、若干内部节点和叶子结点。叶子结点对应的是决策结果，其它结点对应的是一个属性测试。每个几点所包含的样本集合根据属性的测试结果划分到不同的子结点中，根结点包含所有的样本集。其基本流程符合分而治之的策略。

决策树的生成是个递归的过程，显然能发现三种导致递归返回的情况：
1、当前节点所包含的样本全部属于同一类，无需划分 。这时将结点化为叶子结点，样本属于该类别。
2、属性集为空或者数据集在当前属性集上所有取值相同，无法划分 。这时将结点化为叶子结点并将样本归属于多数类。
3、当前节点所包含的样本集合为空，不能划分。这时将结点化为叶子结点并将样本归属于父节点的多数类。

2 划分选择

决策树学习的关键是选择最优的划分属性。我们希望通过该属性的划分，使得分支结点所包含的样本纯度能够尽可能的高。
我们以下几个方面对属性进行衡量：

信息增益

信息熵是度量样本集合纯度最常用的一种指标。

假定离散属性a有V个取值{a¹...a^V}。
若使用a对样本集D进行划分，会产生V个分支，其中第v个包含了D中在a属性上取值为a^v的所有样本，记为D^v。
再根据不同分支结点包含的样本数不同来给与权重：|D^v|/|D|
如此一来，属性a对样本进行划分所得的信息增益就表示为：

一般而言，信息增益越大，那么用属性a进行划分所得到的纯度提升就越大。著名的ID3决策树就使用该准则进行划分。

西瓜书中的西瓜实例有17个，以此为例对上述内容进行计算：

增益率

以编号为例，17个样本中有17个编号，显然可以以此为分支，且这些分支的纯度最大。然而，这样的决策树现在不具有泛化能力。
所以，信息增益对可取较多数目的属性有明显的偏好，为了减少这样的偏好带来的不利影响，C4.5使用增益率来选择最优划分属性。

IV(intrinsic value)称为固有值，属性a可取值越多，固有值就越大。

现在，增益率准则对属性较少的属性有所偏好，所以C4.5不直接使用增益率最大的候选划分属性，而是先选出信息增益高于平均值的属性，再从中选择增益率最高的一个。

基尼指数

CART决策树中，使用基尼指数来选择划分属性。
数据集D的纯度可以用基尼值来度量。

Gini(D)反应了从数据集D中随机选择两个样本，其类别标记不同的概率，因此，Gini指数越低，数据集D的纯度越高。属性a的基尼指数定义为：

基尼指数越小，属性越优。

3 剪枝处理

剪枝是决策树中处理过拟合的主要手段。决策树学习过程中，结点划分不断重复，有时会造成决策树分支过多，进而导致过拟合。因此，需要通过一些手段主动的去掉一些分支。
主要有两种手段，预剪枝和后剪枝

• 预剪枝
  是在决策树生成过程中，如果这个节点进行划分，不能带来泛化性能的提升，则停止划分并将该节点设置为叶子节点。

• 后剪枝则是先训练好一棵树，然后自底向上对非叶子节点进行考察，如果将该节点对应的子树替换为叶节点能不能带来泛化性能的提升，能就将该子树替换为叶节点。

其判断方法就是使用测试集进行测试，通过测试结果判断。

预剪枝

假定有未剪枝的决策树如下：

通过测试集对结点进行的分类结果进行测试，根据其结果判断剪枝与否。

• 优点：
  预剪枝使得决策树很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少来决策树的训练时间开销和测试时间开销。
• 缺点：
  虽然某次划分可能并不能带来性能上的提升，但是后序的划分可能会带来性能上的提升；预剪枝基于“贪心”的本质给决策树带来欠拟合的风险。

后剪枝

后剪枝在生成了完整的决策树后进行

• 优点：
  后剪枝通常比预剪枝保留更多的分支，所以后剪枝决策树的欠拟合风险较小，泛化性能往往犹豫预剪枝决策树。
• 缺点：
  因为在生成了完整的决策树后进行，所以其训练开销高于预剪枝决策树。

连续与缺失值

连续值处理

由于连续值的取值数目不再有限，因此不可直接根据连续属性取值来对结点进行划分，需要使用连续值处理技术。最简单的就是C4.5中使用的二分法。

假定连续值a在D上出现了n个不同的取值，分别为{a1,a2,...,an}，对于连续属性a我们考虑n-1个元素的候选划分点。

将集合T中的每一个取值t的信息增益加以计算，去信息增益最大的t作为划分点。下式中D_t^λ分为D_t⁺和D_t^-，其中D_t⁺表示，在属性a上取值大于划分点t的样本。

如此一来连续值就可以生成如下的决策树：

缺失值处理

不完整样本的出现非常常见，如果简单的放弃不完整的样本对数据信息而言是极大的浪费。
有两个问题需要考虑：

1. 如何在属性存在缺失的情况下，选择划分属性。
2. 给定划分属性，如何对该属性有缺失的样本进行划分。

对于第一个问题，通过对每个样本x赋予权重，得到信息增益的推广式。

其中，ρ为无缺样本占比，r_v为无缺样本中，在属性a中取值为a^v的比例，p_k为无缺样本中，第k类占比。
总体而言，就是在原始计算前添加了占比系数作为权重。

5 多变量决策树

决策树所形成的决策边界有个明显的特点：轴平行。这使得分类边界有很好的可解释性。但在任务分类边界较为复杂的时候，需要很多段线段才能获得较好的近似。

若能够使用斜的划分边界，就能够简化决策树模型。

多变量决策树就是实现斜划分甚至更复杂划分的决策树。与传统的单变量的决策树不同，多变量决策树的每个非叶子结点是对属性的线性组合进行测试，其每个非叶子结点是一个线性分类器，形如：

而多变量决策树在学习过程中是为每个非叶子结点建立合适的线性分类器。形如：