周志华机器学习读书笔记——决策树_决策树 机器学习 周志华

第四章 决策树

（1）基本流程：

    这一章中，将介绍决策树有关的问题，决策树是机器学习中一类常见的方法。

    举个例子：

    针对“这是好瓜吗？”这样的问题进行决策时，通常会进行一系列的判断或子决策：先看“它是什么颜色？”，如果是“青绿色”，再看“它的根蒂是什么形态？”，如果是“蜷缩”，再判断“它敲起来是什么声音？”最后做出决策：这是一个好瓜。    

    决策过程如下：

    一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。

    决策树的生成是一个递归过程，有三种情形会导致递归返回：

    （1）当前结点包含的样本全属于同一类别，无需划分；

    （2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；

    （3）当前结点包含的样本集合为空，不能划分。

（2）划分选择：

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

    假设当前样本集合D中第k类样本所占比例为p_k（k=1,2，…，|У|），则D的信息熵定义为：

    Ent(D)的值越小，则D的初度越高。

    假定离散属性a有V个可能的取值，若用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所以在属性a上取值为a^v的样本，记为D^v。考虑不同的分支结点所包含的样本数不同，给分支结点赋予权重|D^v|/|D|，即样本数越多的分支结点的影响越大，于是可计算出用属性a对样本集D进行“信息增益”：

    一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。

    实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，使用“增益率”来选择最优划分属性，增益率的定义为：

    其实IV(a)称为属性a的“固有值”。属性a的可能取值数目越多（即V越大），则IV(a)的值通常越大。需要注意的是增益率准则对可取值数目较少的属性有所偏好。

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

    它反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则数据集D的纯度越高

（3）剪枝处理：

    剪枝是决策树学习算法对付“过拟合”的主要手段，基本策略有“预剪枝”和“后剪枝”。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该孩子树替换为叶结点。

生成的未剪枝决策树

生成的预剪枝决策树

    预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树发来了欠拟合的风险。

生成的后剪枝决策树

    后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此训练时间开销比未剪枝决策树和预剪枝决策树要大得多。

（4）连续与缺失值：

    连续值处理

    之前讨论的都是基于离散属性来生成决策树。现实学习任务中常会遇到连续属性，由于连续属性的可取值数目不再有限，因此不能直接根据连续属性的可取值来对结点进行划分，最简单的策略可以采用二分法对连续属性进行处理。

    给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为{a¹,a²,…,aⁿ}。基于划分点t可将D分为子集D_t^-和D_t⁺，其中D_t^-包含那些在属性a上取值不大于t的样本，而D_t⁺则包含那些在属性a上取值大于t的样本。对相邻的属性取值aⁱ与aⁱ⁺¹来说，t在区间[aⁱ, aⁱ⁺¹)中取任意值所产生的划分结果相同。因此，对连续属性a，可考察包含n-1个元素的候选划分点集合：

    则把区间[aⁱ, aⁱ⁺¹)的中位点作为候选划分点，考察这些划分点，选取最优的划分点进行样本集合的划分，将之前的信息增益公式稍加改造：

    其中是样本集D基于划分点t二分后的信息增益，这样就可以选择使最大化的划分点。

    缺失值处理

    现实任务中常会遇到不完整的样本，即样本的某些属性值缺失。如果放弃不完整的样本，仅使用无缺失值的样本进行学习，是对数据信息的极大浪费，有必要考虑利用有缺失值的训练样本进行学习，考虑解决两个问题：

    （1）如何在属性值缺失的情况下进行划分属性选择？

    （2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

    给定训练集D和属性a，令表示D中在属性a上没有缺失值的样本子集.

    对问题（1），显然可以根据来判断属性a的优劣。假定属性a有V个可取值，令表示中在属性a上取值为a^v的样本子集，表示中属于第k类（k=1,2，…，|У|）的样本子集，显然有。假定为每个样本x赋予一个权重，定义：

    对属性a，ρ表示无缺失值的样本所占的比例，表示无缺失值样本中第k类所占的比例，则表示无缺失值样本中在属性a上取值a^v的样本所占的比例。显然，。基于上述定义，可以将信息增益公式推广为：

    对问题（2），若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子结点，且样本权值在子结点中保持为。若样本x在划分属性a上的取值未知，则将x同时划入所有子结点，且样本权值与属性值a^v对应的子结点中调整为；这就是让同一个样本以不同的概率划入到不同的子结点中去。

（5）多变量决策树

    若把每个属性视为坐标空间中的一个坐标轴，对样本分类意味着在这个坐标空间中寻找不同样本之间的分类边界。决策树形成的分类边界特点：它的分类边界由若干个与坐标轴平行的分段组成，如下图：

    如果在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，如下图：

    若能够使用斜的划分边界，如上图中的红色线段，则决策树模型将大为简化，“多变量决策树”就是能实现这样的“斜划分”甚至更复杂的决策树。与传统的“单变量决策树”不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器，下面试根据西瓜的数据生成的多变量决策树和分类边界：