第四章决策树

决策树

基本流程

划分选择

剪枝处理

连续与缺失值

多变量决策树

决策树的决策过程

决策树学习基本算法

有三种情形导致返回

1）line2-line4：当前节点中样本均属于同一个类别，无需划分，直接标记为叶节点，分类为样本共同的类别

2）line5-line7：当前节点属性集为空或者当前节点所有样本在属性集A上的所有属性取值都一样，无法划分，标记为叶节点，分类为样本中样本数最多的类别

3）line11-line12：当前节点中样本集为空，标记为叶节点，使用父节点中样本数最多的类别作为分类

注意情况2）和3）是不同的，2）利用当前节点的后验分布，3）把父节点的样本分布作为当前节点的先验分布

算法的关键是如何选择最优划属性

随着划分的进行，决策树的分支节点所包含的样本应该尽可能属于同一类别，即节点的“纯度”越来越高

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

信息熵定义为

信息熵越小，样本集合的纯度越高

使用某个属性对样本集进行划分之后，信息熵减小的量称为信息增益

信息增益定义为

一般而言，使用某个属性来划分样本集的信息增益越大，意味着使用该属性进行划分所获得的“纯度”提升越大

因此可以使用信息增益来决定划分属性的选择，即line8选择属性a_*=\arg \max_{a\in A} Gain(D,a)

ID3决策树算法以信息增益为准则选择划分属性

一般来说属性值越多的属性，信息增益越大，这会导致选择属性具有选择属性值较多的属性的偏好

与之相对地，按照增益率来选择属性，具有选择属性值较少的属性的偏好

增益率定义为

其中

称为属性a的“固有值”，属性a的可能取值数目越多，则固有值通常会更大

C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

数据集的基尼指数定义为

直观来说，基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率，因此基尼指数越小，则数据集的纯度越高

采用属性a划分样本集合得到的几个集合的加权基尼指数定义为

选择划分后基尼指数最小的属性作为最优划分属性，即a_*=\arg\min_{a\in A}Gini\_index(D,a)

剪枝是决策树学习算法应对“过拟合”的主要手段。为了尽可能正确分类样本，节点划分将不断重复，有时会造成决策树分支过多，以至于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合，因此可以通过主动去掉一些分支来降低过拟合的风险。

在节点划分前进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前的节点标记为叶节点。

即用测试集分别测试划分与不划分的误差，如果划分后误差增加，则不划分。

优点：降低过拟合风险。显著减少训练时间和测试时间开销。

缺点：有些分支的当前划分虽然可能不能提升泛化性能，甚至导致泛化性能暂时下降，但是在其基础上的后续划分却有可能使泛化性能显著提高。预剪枝基于贪心策略，禁止将这些分支展开，给决策树带来了欠拟合风险。

先从训练集中生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。

优点：后剪枝比预剪枝保留了更多的分支，所以欠拟合的风险相对小。

缺点：但是需要自底向上对所有非叶节点进行考察，所以训练开销比未剪枝和预剪枝大得多。

假设属性a是连续属性，\{a^1,a^2,...,a^n\} 是从小到大排列的样本集合中出现的值

于是可以做如下划分：

则对连续属性a进行分支的时候，可以选择信息增益最优的一个划分点作为将该属性二分的分界点

于是信息增益可以这样定义：

需要解决两个问题

1）如何划分属性

2）如何划分样本

1）

2）

多变量决策树

决策树所形成的分类边界都是轴平行的，即与坐标轴平行，这导致决策树的分类边界是折线，在学习任务的真实分类边界比较复杂时，必需使用多段划分才能取得较好的近似，此时决策树会相当复杂

若能使用斜线作为划分边界，能将模型简化，多变量决策树就是使用斜划分的决策树