小学英语全英教案>有空i决策树（decisiontree）（⼀）——构造决策树⽅法
决策树（decision tree）（⼀）——构造决策树⽅法
说明：这篇博客是看周志华⽼师的《机器学习》（西⽠书）的笔记总结，虽然⾃⼰写了很多总结性⽂字包括⼀些算法细节，但博客中仍有部分⽂字摘⾃周⽼师的《机器学习》书，仅供学习交流使⽤。转载博客务必注明出处和作者，谢谢。
决策树系列博客：
决策树算法起源于E.B.Hunt等⼈于1966年发表的论⽂“experiments in Induction”，但真正让决策树成为机器学习主流算法的还是Quinlan（罗斯.昆兰）⼤神（2011年获得了数据挖掘领域最⾼奖KDD创新奖），昆兰在1979年提出了ID3算法，掀起了决策树研究的⾼潮。现在最常⽤的决策树算法是C4.5是昆兰在1993年提出的。（关于为什么叫C4.5，还有个轶事：因为昆兰提出ID3后，掀起了决策树研究的⾼潮，然后ID4，ID5等名字就被占⽤了，因此昆兰只好让讲⾃⼰对ID3的改进叫做C4.0，C4.5是C4.0的改进）。现在有了商业应⽤新版本是C5.0。
⼀、决策树的基本概念
顾名思义，决策树就是⼀棵树，⼀颗决策树包含⼀个根节点、若⼲个内部结点和若⼲个叶结点；叶结点
对应于决策结果，其他每个结点则对应于⼀个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到⼦结点中；根结点包含样本全集，从根结点到每个叶⼦结点的路径对应了⼀个判定测试序列。下⾯直接上个图，让⼤家看下决策树是怎样决策的（以⼆元分类为例），图中红线表⽰给定⼀个样例（表中数据）决策树的决策过程：
（该图为原创）
⼆、如何⽣成决策树
信息增益
updatedata决策树学习的关键在于如何选择最优的划分属性，所谓的最优划分属性，对于⼆元分类⽽⾔，就是尽量使划分的样本属于同⼀类别，即“纯度”最⾼的属性。那么如何来度量特征（features）的纯度，这时候就要⽤到“信息熵（information entropy）”。先来看看信息熵的定义：假如当前样本集D中第k类样
本所占的⽐例为， 为类别的总数（对于⼆元分类来说，）。则样本集的信息熵为：
的值越⼩，则D的纯度越⾼。（这个公式也决定了信息增益的⼀个缺点：即信息增益对可取值数⽬多的特征有偏好（即该属性能取得值越多，信息增益，越偏向这个），因为特征可取的值越多，会导致“纯度”越⼤，即ent（D）会很⼩，如果⼀个特征的离散个数与样本数相等，那么Ent（D）值会为
0）。再来看⼀个概念信息增益（information gain），假定离散属性 有 个可能的取值，如果使⽤特征 来对数据集D进⾏划分，则会you rai me up 歌词>雅思口语话题
产⽣V个分⽀结点， 其中第v（⼩v）个结点包含了数据集D中所有在特征 上取值为 的样本总数，记为。因此可以根据上⾯信息熵的公式计算出信息熵，再考虑到不同的分⽀结点所包含的样本数量不同，给分⽀节点赋予权重，即样本数越多的分⽀节点的影响越⼤，因此，能够计算出特征 对样本集D 进⾏划分所获得的“信息增益”:
⼀般⽽⾔，信息增益越⼤，则表⽰使⽤特征 对数据集划分所获得的“纯度提升”越⼤。所以信息增益可以⽤于决策树划分属性的选择，其实就是选择信息增益最⼤的属性，ID3算法就是采⽤的信息增益来划分属性。ig是什么意思
下⾯来举个例⼦说明具体是怎样操作的，只贴公式没多⼤意义，还是有不利于⼤家理解。举例⼦⽤的数据集为：
显然该数据集包含17个样本，类别为⼆元的，即。则，正例（类别为1的样本）占的⽐例为：，反例（类别为0的样本）占的⽐例为：。根据信息熵的公式能够计算出数据集D的信息熵为：
latest
从数据集中能够看出特征集为：{⾊泽、根蒂、敲声、纹理、脐部、触感}。下⾯我们来计算每个特征的信息增益。先看“⾊泽”，它有三个可能的离值：{青
resignation
实习医生格雷第九季
绿、乌⿊、浅⽩}，若使⽤“⾊泽”对数据集D进⾏划分，则可得到3个⼦集，分别为：（⾊泽=青绿）、（⾊泽=乌⿊）、（⾊泽=浅⽩）。共包
含6个样本{1，4，6，10，13，17}，其中正例占，反例占。包含6个样本{2，3，7，8，9，15}，其中正例占，反例占。包含了5个样本{5，11，12，14，16}，其中正例占，反例占。因此，可以计算出⽤“⾊泽”划分之后所获得的3个分⽀结点的信息熵为：
因此，特征“⾊泽”的信息增益为：
同理可以计算出其他特征的信息增益：
⽐较发现，特征“纹理”的信息增益最⼤，于是它被选为划分属性。因此可得：
第⼆步、继续对上图中每个分⽀进⾏划分，以上图中第⼀个分⽀结点{“纹理=清晰”}为例，对这个结点进⾏划分，设该结点的样本集
{1，2，3，4，5，6，8，10，15}，共9个样本，可⽤特征集合为{⾊泽，根蒂，敲声，脐部，触感}，因此基于 能够计算出各个特征的信息增益：
⽐较发现，“根蒂”、“脐部”、“触感”这3个属性均取得了最⼤的信息增益，可以随机选择其中之⼀作为划分属性（不防选择“根蒂”）。因此可得：
第三步，继续对上图中的每个分⽀结点递归的进⾏划分，以上图中的结点{“根蒂=蜷缩”}为例，设该结点的样本集为{1，2，3，4，5}，共5个样本，但这5个样本的class label均为“好⽠”，因此当前结点包含的样本全部属于同⼀类别⽆需划分，将当前结点标记为C类（在这个例⼦中为“好⽠”）叶节点，递归返回。因此上图变为：
第四步，接下来对上图中结点{“根蒂=稍蜷”}进⾏划分，该点的样本集为 {6，8，15}，共有三个样本。可⽤特征集为{⾊泽，敲声，脐部，触感}，同样可
雅思需要多少词汇量
以基于 计算出各个特征的信息增益，计算过程如下（写的⽐较详细，⽅便⼤家弄懂）：
（注：该图⽚版权所有，转载或使⽤请注明作者（天泽28）和出处）不妨选择“⾊泽”属性作为划分属性，则可得到：
继续递归的进⾏，看“⾊泽=青绿”这个节点，只包含⼀个样本，⽆需再划分了，直接把当前结点标记为叶节点，类别为当前样本的类别，即好⽠。递归返
回。然后对递归的对“⾊泽=乌⿊”这个节点进⾏划分，就不再累述了。说下“⾊泽=浅⽩”这个节点，等到递归的深度处理完“⾊泽=乌⿊”分⽀后，返回来处理“⾊泽=浅⽩”这个节点，因为当前结点包含的样本集为空集，不能划分，对应的处理措施为：将其设置为叶节点，类别为设置为其⽗节点（根蒂=稍蜷）所含样本最多的类别，“根蒂=稍蜷”包含{6,8,15}三个样本，6,8为正样本，15为负样本，因此“⾊泽=浅⽩”结点的类别为正（好⽠）。最终，得到的决策树如下图所⽰：
注：上图红⾊框起来的部分，是西⽠书印刷错误，上图已改正。周⽼师在他的勘误⽹站也有说明，详见
说了这么多，下⾯就来看看⽤决策树算法跑出来的效果，本⼈主要⽤weka的ID3算法（使⽤的信息增益），以供⼤家参看，后⾯还会放出⾃⼰实现的版本，后⾯再说。（之所以不要sklearn库⾥的决策树，是因为sklearn库⾥的决策树提供的是使⽤Gini指数优化后的CART，并不提供ID3和C4.5算法）。
由于新版本weka⾥已经不再提供ID3算法了，只能下载另外的安装包，把下载⽅法也贴出来吧，打开weka的Tools->package manager在⾥⾯找到包simpleEducationalLearningSchemes安装即可。安装好后就可以把西⽠数据集2.0来测试了，不过要想在weka中构建模型，还要先把.txt格式转换为.arff格式，转换的代码以及转换好的数据集，详见。 另外simpleEducationalLearningSchemes提供的ID3并不像J48那样⽀持可视化，因此参考基于以前weka⽼版本写的可视化，但该代码在新版本中⽆法使⽤，我修改了下整合到ID3上了，现在可以⽀持可视化了，测试西⽠数据集，⽣成的可视化树如下，具体代码也放到了上，有兴趣的可以看看。
