wordpress漫画站,网站建设合同属于购销吗,手机移动开发技术,做时时的网站4.1 决策树基本流程
决策树模型 基本流程 在第⑵种情形下#xff0c;我们把当前结点标记为叶结点#xff0c;并将其类别设定为该结点所含样本最多的类别#xff1b;在第⑶种情形下#xff0c;同样把当前结点标记为叶结点#xff0c;但将其类别设定为其父结点所含样本最多…4.1 决策树基本流程
决策树模型 基本流程 在第⑵种情形下我们把当前结点标记为叶结点并将其类别设定为该结点所含样本最多的类别在第⑶种情形下同样把当前结点标记为叶结点但将其类别设定为其父结点所含样本最多的类别.注意这两种情形的处理实质不同情形⑵是在利用当前结点的后验分布而情形⑶则是把父结点的样本分布作为当前结点的先验分布.
基本算法 由算法4 .2可看出决策树学习的关键是第8 行即如何选择最优划分属性.一般而言随着划分过程不断进行我们希望决策树的分支结点所包含的样本尽可能属于同一类别即结点的“纯度”(purity)越来越高.
4.2 信息增益划分
信息增益
信息论中最重要的理论——熵
信息熵度量一个集合的纯度
自信息对于随机变量大X它每个取值x都有它的概率p(x) 信息熵是自信息的期望
从公式可以看出信息熵最小纯度最高的情况有一个所占比例是1其他所占比例都是0此时信息熵为0
当X的各个取值的概率均等时样本中每一个的概率均等时信息熵最大也就是最不确定纯度最低
为什么要使用信息熵来算 ——
信息增益在已知属性特征a的取值后y的不确定性减少的量也即纯度的提升
计算出D^v的信息熵,再考虑到不同的分支结点所包含的样本数不同给分支结点赋予权重|D ^v|/|D|,即样本数越多的分支结点的影响越大于是可计算出用属性a对样本集D 进行划分所获得的“信息增益”
ID3决策树以信息增益为准则来选择划分属性的决策树
可以用信息增益的方式来度量用这种方式划分的价值
信息增益 的定义划分前的信息熵 - 划分后的信息熵
最优化的属性要让信息增益最大即每一步划分后的结果只要最少的信息。尽可能的干净
一个例子 首先求出未划分前当前样本集合根节点的信息熵 如果以属性“色泽”划分对于D1色泽青绿3条正类3条负类因此信息熵公式如上
4.3 其他属性划分准则
信息增益准则对可取值数目较多的属性有所偏好即偏好了分枝多的属性分到每个分枝上的数目就会越少
例如若把“编号””也作为一个候选划分属性则根据式(4.2)可计算出它的信息增益为0.998,远大于其他候选划分属性.这很容易理解“编号”将产生17个分支每个分支结点仅包含一个样本这些分支结点的纯度已达最大.然而这样的决策树显然不具有泛化能力无法对新样本进行有效预测.
基于ID3C4.5现在的改进不再以 信息增益 作为划分的准则而是使用 增益率
增益率 分母IV是分支越少越好而分子是信息增益越大越好
那么两者折中的点在哪里呢没有一个绝对正确的权衡无法找到一个完美的决策树
增益率准则对可取值数目较少的属性有所偏好因此通常在C4.5中的做法——启发式先把信息增益做一个标准把高于平均水平的找出来再其中挑增益率最大的而不是直接由增益率排序而来因为增益率对可能取值数目较少的属性有所偏好
规范化把原先不可比较的东西变得可以比较了 归一化是规范化的特殊形式是针对数值属性的。规范化至0与1之间
基尼指数
基尼值 和 基尼指数
基尼值越小碰到异类的概率就越小纯度自然就越高
按属性划分后的基尼值我们称为 基尼指数
CART决策树选择基尼指数最小的属性作为最优划分属性 实际操作时CART决策树二叉树和前面按信息增益的决策树不一定是二叉树在具体选划分点时有所区别和前面的基尼公式也有所不同 划分选择 vs 剪枝 4.4 决策树的剪枝
为何剪枝对决策树泛化性能影响更显著 ——剪枝 是决策树对付“过拟合”的主要手段 4.5 预剪枝与后剪枝
现在我们假定使用“留出法”来在剪枝过程中评估剪枝前后决策树的优劣即预留一部分数据用作“验证集”以进行性能评估
数据集 预剪枝
预剪枝是指在决策树生成过程中对每个结点在划分前先进行估计若当前结点的划分不能带来决策树泛化性能提升则停止划分并将当前结点标记为叶结点 这就是预剪枝最终得到的决策树 在用属性“脐部”划分之后图4.6中的结点2、3、4分别包含编号为1,2,3,14、6,7,15,17、10,16的训练样例因此这3 个结点分别被标记为叶结点“好瓜”、 “好瓜”、 “坏瓜”.此时验证集中编号为(4,5,8,11,12)的样例被分类正确验证集精度为5/7 x 100% 71.4% 42.9%.于是用 “脐部”进行划分得以确定.
对比图4.6和图4.5可看出预剪枝使得决策树的很多分支都没有“展开”这不仅降低了过拟合的风险还显著减少了决策树的训练时间开销和测试时间开销.但另一方面有些分支的当前划分虽不能提升泛化性能、甚至可 能导致泛化性能暂时下降但在其基础上进行的后续划分却有可能导致性能显 著提高预剪枝基于“贪心”本质禁止这些分支展开给预剪枝决策树带来了 欠拟合的风险.
后剪枝
后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升则将该子树替换为叶结点.
后剪枝先生成一颗完整的决策树然后看中间做属性决策的结点能否用叶节点来替换它 注意是从最深的开始考虑因为越深的越可能是受到overfitting的影响的结果 ——如果剪枝了 对比图4.7和图4.6可看出后剪枝决策树通常比预剪枝决策树保留了更多的分支.一般情形下后剪枝决策树的欠拟合风险很小泛化性能往往优于预 剪枝决策树.但后剪枝过程是在生成完全决策树之后进行的并且要自底向上 地对树中的所有非叶结点进行逐一考察因此其训练时间开销比未剪枝决策树 和预剪枝决策树都要大得多.
预剪枝 vs 后剪枝 4.6 连续值的处理
到目前为止我们仅讨论了基于离散属性来生成决策树.现实学习任务中常会遇到连续属性有必要讨论如何在决策树学习中使用连续属性.由于连续属性的可取值数目不再有限因此不能直接根据连续属性的可取值来对结点进行划分.此时连续属性离散化技术可派上用场.最简单的策略是采用二分法(bi-partition)对连续属性进行处理这正是C4.5决策树算法中采用的机制[Quinlan, 1993].
给定样本集D 和连续属性a.假定a在D上出现了 n个不同的取值将这些值从小到大进行排序 显然对相邻的属性取值a_i与a_i1 来说t在区间[a^i,a ^i1)中取任意值所产生的划分结果相同.因此,对连续属性a,我们可考察包含n- 1个元素的候选划分点集合
即把区间[a^i,a ^i1)的中位点(a ^i,a ^i1)/2作为候选划分点.然后我们就可像离散属性值一样来考察这些划分点选取最优的划分点进行样本集合的划分.例如, 可对式(4.2)信息增益稍加改造
4.7 缺失值的处理
缺失值 其中“权重划分”指的是给定划分属性若样本在该属性上的值缺失会按权重同时进入所有分支
一个例子 区别变化是在计算总的信息增益时前面乘上 无缺失值样例占比 选其中最大的信息增益
把有值的样本进入各个属性的划分结果当作了没有值的样本进入的先验
