决策树完整学习教案

《决策树完整学习教案》由会员分享，可在线阅读，更多相关《决策树完整学习教案（40页珍藏版）》请在金锄头文库上搜索。

1、会计学1决策树完整决策树完整(wnzhng)第一页，共40页。第第第第4 4章章章章 决策树决策树决策树决策树根据训练数据是否拥有根据训练数据是否拥有(yngyu)(yngyu)标记信息标记信息学习任务学习任务决策树（决策树（decision tree）模型常常）模型常常(chngchng)用来解决分类用来解决分类和回归问题。常见的算法包括和回归问题。常见的算法包括 CART (Classification And Regression Tree)、ID3、C4.5等。等。半监督学习：输入数据部分被标识，部分没有被标识，介于监督学习与非监督学习之间。分类、回归聚类监督学习(supervised

2、 learning)无监督学习(unsupervised learning)半监督学习(semi-supervised learning)强化学习(reinforcement learning)第1页/共39页第二页，共40页。二分类学习(xux)任务属性属性值根结点：包含全部(qunb)样本叶结点：对应决策结果 “好瓜” “坏瓜”内部结点：对应属性测试决策树学习的目的：为了产生一颗泛化能力(nngl)强的决策树，即处理未见示例能力(nngl)强。第2页/共39页第三页，共40页。无需划分无法划分不能划分无需划分无法划分不能划分Hunt算法：第3页/共39页第四页，共40页。1,2,3,4,5

3、,6,8,10,151,2,3,4,56,8,151068,15815第（2）种情形：设定为该结点所含样本最多的类别利用当前结点的后验分布第（3）种情形：设定为其父结点所含样本最多的类别把父结点的样本分布作为当前结点的 先验分布第4页/共39页第五页，共40页。决策树学习的关键是算法的第8行：选择最优划分属性什么样的划分属性是最优的？我们希望决策树的分支结点所包含的样本尽可能属于同一(tngy)类别，即结点的“纯度”越来越高，可以高效地从根结点到达叶结点，得到决策结果。三种度量结点“纯度(chnd)”的指标：信息增益增益率基尼指数第5页/共39页第六页，共40页。1. 信息信息(xnx)增益增

4、益香农提出了“信息熵”的概念，解决了对信息的量化度量问题。香农用(nn yn)“信息熵”的概念来描述信源的不确定性。信息熵信息熵对于二分类任务第6页/共39页第七页，共40页。一个事件的信息量信息量就是这个事件发生的概率的负对数。信息熵信息熵是跟所有事件的可能性有关的，是平均而言发生一个事件得到的信息量大小。所以信息熵其实是信息量的期望。假设我们已经知道衡量不确定性大小的这个量已经存在了，不妨就叫做“信息量信息量”不会是负数不确定性函数是概率的单调递减函数；可加性：两个独立符号所产生的不确定性应等于各自不确定性之和，即同时满足这三个条件的函数是负的对数函数，即第7页/共39页第八页，共40页。

5、信息信息(xnx)增益增益一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升(tshng)”越大。决策树算法第8行选择属性著名(zhmng)的ID3决策树算法第8页/共39页第九页，共40页。举例：求解(qi ji)划分根结点的最优划分属性根结点(ji din)的信息熵：以属性“色泽”为例计算其信息增益数据集包含17个训练样例：8个正例（好瓜）占9个反例（坏瓜）占对于二分类任务第9页/共39页第十页，共40页。用“色泽(sz)”将根结点划分后获得3个分支结点的信息熵分别为：属性(shxng)“色泽”的信息增益为：第10页/共39页第十一页，共40页。第11页/共39页第十二

6、页，共40页。第12页/共39页第十三页，共40页。若把“编号”也作为一个候选划分(hu fn)属性，则属性“编号”的信息增益为：根结点(ji din)的信息熵仍为：用“编号”将根结点划分(hu fn)后获得17个分支结点的信息熵均为：则“编号”的信息增益为：远大于其他候选属性信息增益准则对可取值数目较多的属性有所偏好第13页/共39页第十四页，共40页。2. 增益增益(zngy)率率增益率准则对可取值数目较少的属性有所偏好著名的C4.5决策树算法综合了信息增益准则和信息率准则的特点：先从候选(hu xun)划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。第14页/共39页第

7、十五页，共40页。3. 基尼指数基尼指数(zhsh)基尼值基尼值基尼指数基尼指数(zhsh)著名(zhmng)的CART决策树算法第15页/共39页第十六页，共40页。过拟合：学习器学习能力过拟合：学习器学习能力(nngl)过于强大，把训练样本自身的一些特点当过于强大，把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，导致泛化性能下降。作了所有潜在样本都会具有的一般性质，导致泛化性能下降。欠拟合：学习器学习能力欠拟合：学习器学习能力(nngl)低下，对训练样本的一般性质尚未学好。低下，对训练样本的一般性质尚未学好。过拟合无法彻底避免(bmin) ，只能做到“缓解”。第16页/共39

8、页第十七页，共40页。剪枝，即通过主动去掉一些分支来降低过拟合的风险。预剪枝预剪枝决策树的剪枝策略后剪枝后剪枝预剪枝预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点后剪枝后剪枝：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。留出法：将数据集D划分为两个互斥的集合：训练集S和测试集T且第17页/共39页第十八页，共40页。第18页/共39页第十九页，共40页。预剪枝预剪枝1,2,3,14训练集训练集：好瓜好瓜

9、 坏瓜坏瓜1,2,3,6,7,10,14,15,16,176,7,15,1710,16精度：正确分类的样本占所有样本的比例4,5,13(T,T,F)8,9(T,F)11,12(T,T)验证集验证集：4,5,8,9,11,12,13第19页/共39页第二十页，共40页。不足：不足：基于基于“贪心贪心”本质禁止某些分支展开，带来了欠拟合本质禁止某些分支展开，带来了欠拟合(n h)的风险的风险预剪枝使得决策树的很多分支都没有“展开”优点：降低过拟合的风险减少了训练时间(shjin)开销和测试时间(shjin)开销第20页/共39页第二十一页，共40页。后剪枝后剪枝先从训练集生成一棵完整的决策树，然后

10、自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。验证集验证集：4,5,8,9,11,124,13(T,F)5(F)9(F)8(F)11,12(T,T)验证集精度：考察结点顺序：6,7,15,176,7,151767,157158,9(T,F)减去结点验证集变为：训练训练(xnlin)集：好瓜集：好瓜 坏瓜坏瓜1,2,3,6,7,10,14,15,16,17第21页/共39页第二十二页，共40页。后剪枝后剪枝(jin zh)决策树决策树预剪枝预剪枝(jin zh)决策树决策树保留了更多的分支欠拟合(n h)风险很小泛化能力优于预剪枝

11、决策树训练时间开销比未减枝和预剪枝决策树大得多生产完全决策树所有非叶节点逐一考察第22页/共39页第二十三页，共40页。知识回顾：知识回顾：四类学习任务四类学习任务Hunt算法算法3种递归返回情形、种递归返回情形、第第8行行3种度量结点种度量结点“纯度纯度”的指标：的指标：信息增益信息增益ID3增益率增益率C4.5基尼指数基尼指数CART过拟合过拟合(n h)、欠拟合、欠拟合(n h)决策树剪枝决策树剪枝预剪枝预剪枝后剪枝后剪枝第23页/共39页第二十四页，共40页。离散属性：脐部 根蒂 色泽连续属性：密度 含糖率第24页/共39页第二十五页，共40页。连续属性离散化技术：二分法C4.5决策树

12、算法样本集连续属性 ，有n个不同的取值，将n个取值从小到大排序：划分点t（数值）（数值）将划分为两个子集和显然，对相邻的属性取值来说，t在区间中取任意值所产生的划分结果都相同第25页/共39页第二十六页，共40页。第26页/共39页第二十七页，共40页。根结点的信息熵仍为：根结点包含17个训练样本，密度有17个不同取值候选划分点集合包含16个候选值每一个划分点能得到一个对应的信息增益第27页/共39页第二十八页，共40页。选择“纹理”作为根结点划分属性与离散属性不同，若当前结点划分属性为连续属性，该连续属性还可被再次选作后代结点的最优划分属性。第28页/共39页第二十九页，共40页。现实任务中

13、，尤其在属性数目较多时，存在大量样本出现缺失值。出于成本和隐私的考虑第29页/共39页第三十页，共40页。属性值缺失时，如何进行划分属性选择(xunz)？（如何计算信息增益）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？（对于缺失属性值的样本如何将它从父结点划分到子结点中）训练集训练集中在属性a上没有缺失值的样本子集被属性a划分后的样本子集中属于第k类的样本子集无缺失值样本(yngbn) 中在属性上取值的样本(yngbn) 所占比例无缺失值样本所占比例无缺失值样本中第k类所占比例第30页/共39页第三十一页，共40页。无缺失值的样本子集上的信息增益第31页/共39页第三十二页，共

14、40页。对于问题2：对于有缺失值的样本如何将它从父结点划分到子结点中若样本在划分属性a上的取值已知，则将划入与与其取值对应的子结点其取值对应的子结点，且样本权值在子结点中保持为若样本在划分属性a上的取值未知，则将同时划入所有子结点所有子结点，且样本权值在子结点中调整为，就是让同一个样本以不同的概率划入不同的子结点中。其中，是为每个样本赋予的一个权重运用：运用：问题问题1属性值缺失时，如何进行划分属性值缺失时，如何进行划分(hu fn)属性选择？属性选择？=属性值缺失时，如何计算缺失属性的信息增益？属性值缺失时，如何计算缺失属性的信息增益？无缺失值样本(yngbn) 中在属性上取值的样本(yng

15、bn) 所占比例第32页/共39页第三十三页，共40页。无缺失值样本中第k类所占比例根结点包含样本集中全部17个样本属性“色泽”无缺失值的样例子集包含14个样例：好瓜好瓜(6个)坏瓜坏瓜(8个)无缺失值样本所占比例第33页/共39页第三十四页，共40页。无缺失值样本中在属性上取值的样本所占比例无缺失值样本所占比例“纹理”被用于对根结点进行划分问题2给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？第34页/共39页第三十五页，共40页。样本划分原则：属性值已知，划入与其取值对应的子结点，样本权值不变，仍为属性值未知，划入所有子结点 ，样本权值调整为，让同一个样本以不同的概率划入不同的

16、子结点中无缺失(qu sh)值样本中在属性上取值的样本所占比例“纹理”属性值缺失的样本编号为： 8,10权值为：8和10同时进入三个分支中，权值分别为：第35页/共39页第三十六页，共40页。0.3810.205每个属性d个属性描述的样本对样本分类坐标空间中的一个坐标轴d维空间中的一个数据点在坐标空间中寻找不同类样本之间的分类边界决策树形成的分类边界的明显特点：轴平行，分类边界由若干个与坐标轴平行的分段组成。优点：优点：学习结果解释性强，每个划分都对应一个属性取值2个属性二维平面第36页/共39页第三十七页，共40页。不足：不足：第37页/共39页第三十八页，共40页。可以从该结点所含的样本集D和属性集A上学得第38页/共39页第三十九页，共40页。内容(nirng)总结会计学。可加性：两个独立符号所产生的不确定性应等于各自不确定性之和，即。欠拟合：学习器学习能力低下，对训练样本的一般性质尚未学好。第17页/共39页。(T,T)。不足：。减少了训练时间开销和测试时间开销。过拟合、欠拟合。根结点包含17个训练样本，密度有17个不同取值。候选划分点集合(jh)包含16个候选值。每一个划分点能得到一个对应的信息增益。可以从该结点所含的样本集D和属性集A上学得。第38页/共39页第四十页，共40页。