决策树基于统计学习方法书ppt课件.ppt

决策树 决策树 决策树 DecisionTree 是一种基本的分类与回归方法 决策树模型呈树形结构 在分类问题中 表示基于特征对实例进行分类的过程 可以认为是if then规则的集合 可以认为是定义在特征空间与类空间上的条件概率分布 决策树模型 if then规则 内部节点 特征和属性 叶节点 类 树 由节点和有向边组成 路径互斥且完备 可以认为是if then规则的集合 由决策树的根结点到叶结点的每一条路径构建一条规则 路径上内部结点的特征对应着规则的条件 而叶结点的类对应着规则的结论 决策树 条件概率分布 决策树还表示给定特征条件下类的条件概率分布此处条件概率分布 定义在特征空间的一个划分 partition 上 将特征空间划分为互不相交的单元 cell 或区域 region 并在每个单元定义一个类的概率分布就构成了一个条件概率分布 决策树 条件概率分布 学习目的 从训练数据集中归纳出一组分类规则 可能有多个 可能没有 需要的是一个与训练数据矛盾较小的决策树 同时具有很好的泛化能力 从训练数据集估计条件概率模型 基于特征空间划分的类的条件概率模型有无穷多个 我们选择的条件概率模型应该不仅对训练数据有很好的拟合 而且对未知数据有很好的预测 学习步骤 特征的选择决策树的生成 递归地选择最优特征 并根据该特征对训练数据进行分割 使得对各个子数据集有一个最好的分类的过程 剪枝 利用损失函数最小原则进行剪枝 用正则化的极大似然估计进行模型选择 学习步骤一 特征的选择 如果特征数量很多 在决策树学习开始时对特征进行选择 只留下对训练数据有足够分类能力的特征选择的原则 信息增益或者信息增益比 设有随机变量 X Y 其联合概率分布为 熵 表示随机变量不确定性的度量条件熵 H Y X 表示在已知随机变量X的条件下随机变量Y的不确定性 定义为X给定条件下Y的条件概率分布的嫡对X的数学期望 学习步骤一 特征的选择 当嫡和条件嫡中的概率由数据估计 特别是极大似然估计 得到时 所对应的嫡与条件嫡分别称为经验熵和经验条件嫡极大似然估计 只是一种概率论在统计学的应用 它是参数估计的方法之一 说的是已知某个随机样本满足某种概率分布 但是其中具体的参数不清楚 参数估计就是通过若干次试验 观察其结果 利用结果推出参数的大概值 极大似然估计是建立在这样的思想上 已知某个参数能使这个样本出现的概率最大 我们当然不会再去选择其他小概率的样本 所以干脆就把这个参数作为估计的真实值 学习步骤一 特征的选择 信息增益 g D A 特征A对训练数据集D的信息增益H D 集合D的经验嫡H D A 特征A给定条件下D的经验条件嫡改进 信息增益值的大小是相对于训练数据集而言的 并没有绝对意义 在分类问题困难时 也就是说在训练数据集的经验嫡大的时候 信息增益值会偏大 反之 信息增益值会偏小 信息增益比 学习步骤二 决策树的生成 ID3算法 基于信息增益选择特征C4 5算法 基于信息增益比选择特征 C4 5并不一个算法 而是一组算法 C4 5 非剪枝C4 5和C4 5规则 ID3算法例子 1 特征的选择 计算信息增益 并选择结果最大时所对应的特征 ID3算法例子 2 树的生成 学习步骤三 剪枝 决策树的生成算法容易构建过于复杂的决策树 可能只是对已知数据很好分类 对未知数据分类效果不清楚 产生过拟合在决策树学习中将已生成的树进行简化的过程称为剪枝 具体地 剪枝从下而上 从已生成的树上裁掉一些子树或叶结点 并将其根结点或父结点作为新的叶结点 从而简化分类树模型 此处介绍一种简单的算法实现 极小化决策树整体的损失函数 lossfimction 或代价函数 costfunction 损失函数 lossfimction 对于单个训练样本的误差代价函数 costfunction 对于整个训练集 所有样本误差总和的平均 学习步骤三 剪枝 设树T的叶结点个数为 T t是树T的叶结点 该叶结点有Nt个样本点 其中k类的样本点有Ntk个 k 1 2 K Ht T 为叶结点t上的经验嫡 决策树的损失函数 C T 模型对训练数据的预测误差 即模型与训练数据的拟合程度 T 模型复杂度正则化参数a 0控制两者之间的影响 剪枝实质上是当a确定时 选择损失函数最小的模型 即损失函数最小的子树 此时 损失函数正好表示了对模型的复杂度和训练数据的拟合两者的平衡 学习步骤三 剪枝 决策树生成只考虑了通过提高信息增益 或信息增益比 对训练数据进行更好的拟合 学习局部的模型 决策树剪枝通过优化损失函数还考虑了减小模型复杂度 学习整体的模型 CART算法 CART classificationandregressiontree 分类回归树1 生成树回归树 用平方误差最小化准则分类树 基尼指数 Giniindex 最小化准则 进行特征选择ps 基尼指数Gini D 表示集合D的不确定性 基尼指数Gini D A 表示经A a分割后集合D的不确定性 基尼指数值越大 样本集合不确定性就越大 因此不同于之前选信息增益和信息增益比最大 此算法选基尼指数最小的特征2 剪枝 CART算法 剪枝 1 剪枝 形成一个子树序列在剪枝过程中 计算子树的损失函数 可以用递归的方法对树进行剪枝 将a从小增大 a0 a1 an 无穷 产生一系列的区间 ai ai 1 i 0 1 n 剪枝得到的子树序列对应着区间 ai ai 1 i 0 1 n的最优子树序列 T0 T1 Tn 序列中的子树是嵌套的 对T0中每一内部结点t 计算表示剪枝后整体损失函数减少的程度 在T0中剪去g t 最小的Tt 将得到的子树作为T1 同时将最小的g t 设为a1 T1为区间 a1 a2 的最优子树 如此剪枝下去 直至得到根结点 在这一过程中 不断地增加a的值 产生新的区间 CART算法 剪枝 2 在剪枝得到的子树序列T0 T1 Tn中通过交叉验证选取最优子树Ta具体地 利用独立的验证数据集 测试子树序列T0 T1 Tn中各棵子树的平方误差或基尼指