周志华《Machine Learning》学习笔记(5)--决策树

上篇主要介绍和讨论了线性模型。首先从最简单的最小二乘法开始讨论输入属性有一个和多个的情形接着通过广义线性模型延伸开来将预测连续值的回归问题转化为分类问题从而引入了对数几率回归最后线性判别分析LDA将样本点进行投影多分类问题实质上通过划分的方法转化为多个二分类问题进行求解。本篇将讨论另一种被广泛使用的分类算法–决策树Decision Tree。4、决策树4.1 决策树基本概念顾名思义决策树是基于树结构来进行决策的在网上看到一个例子十分有趣放在这里正好合适。现想象一位捉急的母亲想要给自己的女娃介绍一个男朋友于是有了下面的对话女儿多大年纪了 母亲26。 女儿长的帅不帅 母亲挺帅的。 女儿收入高不 母亲不算很高中等情况。 女儿是公务员不 母亲是在税务局上班呢。 女儿那好我去见见。这个女孩的挑剔过程就是一个典型的决策树即相当于通过年龄、长相、收入和是否公务员将男童鞋分为两个类别见和不见。假设这个女孩对男人的要求是30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员那么使用下图就能很好地表示女孩的决策逻辑即一颗决策树。在上图的决策树中决策过程的每一次判定都是对某一属性的“测试”决策最终结论则对应最终的判定结果。一般一颗决策树包含一个根节点、若干个内部节点和若干个叶子节点易知* 每个非叶节点表示一个特征属性测试。 * 每个分支代表这个特征属性在某个值域上的输出。 * 每个叶子节点存放一个类别。 * 每个节点包含的样本集合通过属性测试被划分到子节点中根节点包含样本全集。4.2 决策树的构造决策树的构造是一个递归的过程有三种情形会导致递归返回(1) 当前结点包含的样本全属于同一类别这时直接将该节点标记为叶节点并设为相应的类别(2) 当前属性集为空或是所有样本在所有属性上取值相同无法划分这时将该节点标记为叶节点并将其类别设为该节点所含样本最多的类别(3) 当前结点包含的样本集合为空不能划分这时也将该节点标记为叶节点并将其类别设为父节点中所含样本最多的类别。算法的基本流程如下图所示可以看出决策树学习的关键在于如何选择划分属性不同的划分属性得出不同的分支结构从而影响整颗决策树的性能。属性划分的目标是让各个划分出来的子节点尽可能地“纯”即属于同一类别。因此下面便是介绍量化纯度的具体方法决策树最常用的算法有三种ID3C4.5和CART。4.2.1 ID3算法ID3算法使用信息增益为准则来选择划分属性“信息熵”(information entropy)是度量样本结合纯度的常用指标假定当前样本集合D中第k类样本所占比例为pk则样本集合D的信息熵定义为假定通过属性划分样本集D产生了V个分支节点v表示其中第v个分支节点易知分支节点包含的样本数越多表示该分支节点的影响力越大。故可以计算出划分后相比原始数据集D获得的“信息增益”information gain。信息增益越大表示使用该属性划分样本集D的效果越好因此ID3算法在递归过程中每次选择最大信息增益的属性作为当前的划分属性。4.2.2 C4.5算法ID3算法存在一个问题就是偏向于取值数目较多的属性例如如果存在一个唯一标识这样样本集D将会被划分为|D|个分支每个分支只有一个样本这样划分后的信息熵为零十分纯净但是对分类毫无用处。因此C4.5算法使用了“增益率”gain ratio来选择划分属性来避免这个问题带来的困扰。首先使用ID3算法计算出信息增益高于平均水平的候选属性接着C4.5计算这些候选属性的增益率增益率定义为4.2.3 CART算法CART决策树使用“基尼指数”Gini index来选择划分属性基尼指数反映的是从样本集D中随机抽取两个样本其类别标记不一致的概率因此Gini(D)越小越好基尼指数定义如下进而使用属性α划分后的基尼指数为4.3 剪枝处理从决策树的构造流程中我们可以直观地看出不管怎么样的训练集决策树总是能很好地将各个类别分离开来这时就会遇到之前提到过的问题过拟合overfitting即太依赖于训练样本。剪枝pruning则是决策树算法对付过拟合的主要手段剪枝的策略有两种如下* 预剪枝prepruning在构造的过程中先评估再考虑是否分支。 * 后剪枝post-pruning在构造好一颗完整的决策树后自底向上评估分支的必要性。评估指的是性能度量即决策树的泛化性能。之前提到可以使用测试集作为学习器泛化性能的近似因此可以将数据集划分为训练集和测试集。预剪枝表示在构造数的过程中对一个节点考虑是否分支时首先计算决策树不分支时在测试集上的性能再计算分支之后的性能若分支对性能没有提升则选择不分支即剪枝。后剪枝则表示在构造好一颗完整的决策树后从最下面的节点开始考虑该节点分支对模型的性能是否有提升若无则剪枝即将该节点标记为叶子节点类别标记为其包含样本最多的类别。上图分别表示不剪枝处理的决策树、预剪枝决策树和后剪枝决策树。预剪枝处理使得决策树的很多分支被剪掉因此大大降低了训练时间开销同时降低了过拟合的风险但另一方面由于剪枝同时剪掉了当前节点后续子节点的分支因此预剪枝“贪心”的本质阻止了分支的展开在一定程度上带来了欠拟合的风险。而后剪枝则通常保留了更多的分支因此采用后剪枝策略的决策树性能往往优于预剪枝但其自底向上遍历了所有节点并计算性能训练时间开销相比预剪枝大大提升。4.4 连续值与缺失值处理对于连续值的属性若每个取值作为一个分支则显得不可行因此需要进行离散化处理常用的方法为二分法基本思想为给定样本集D与连续属性α二分法试图找到一个划分点t将样本集D在属性α上分为≤t与t。* 首先将α的所有取值按升序排列所有相邻属性的均值作为候选划分点n-1个n为α所有的取值数目。 * 计算每一个划分点划分集合D即划分为两个分支后的信息增益。 * 选择最大信息增益的划分点作为最优划分点。现实中常会遇到不完整的样本即某些属性值缺失。有时若简单采取剔除则会造成大量的信息浪费因此在属性值缺失的情况下需要解决两个问题1如何选择划分属性。2给定划分属性若某样本在该属性上缺失值如何划分到具体的分支上。假定为样本集中的每一个样本都赋予一个权重根节点中的权重初始化为1则定义对于1通过在样本集D中选取在属性α上没有缺失值的样本子集计算在该样本子集上的信息增益最终的信息增益等于该样本子集划分后信息增益乘以样本子集占样本集的比重。即对于2若该样本子集在属性α上的值缺失则将该样本以不同的权重即每个分支所含样本比例划入到所有分支节点中。该样本在分支节点中的权重变为​