决策树的构造——一个手工例子
这个数据集来自Mitchell的机器学习，叫做是否去打网球play-tennis,以下数据仍然是从带逗号分割的文本文件，复制到纪事本，把后缀直接改为.csv就可以拿Excel打开：
*play-tennis data，其中6个变量依次为：编号、天气{Sunny、Overcast、Rain}、温度{热、冷、适中}、湿度{高、正常}、风力{强、弱}以及最后是否去玩的决策{是、否}。一个建议是把这些数据导入Excel后，另复制一份去掉变量的数据到另外一个工作簿，即只保留14个观测值。这样可以方便地使用Excel的排序功能，随时查看每个变量的取值到底有多少。*/
NO. , Outlook , Temperature , Humidity , Wind , Play
1 , Sunny , Hot , High , Weak , No
2 , Sunny , Hot , High , Strong , No
3 , Overcast , Hot , High , Weak , Yes
4 , Rain , Mild , High , Weak , Yes
5 , Rain , Cool , Normal , Weak , Yes
6 , Rain , Cool , Normal , Strong , No
7 , Overcast , Cool , Normal , Strong , Yes
8 , Sunny , Mild , High , Weak , No
9 , Sunny , Cool , Normal , Weak , Yes
10 , Rain , Mild , Normal , Weak , Yes
11 , Sunny , Mild , Normal , Strong , Yes
12 , Overcast , Mild , High , Strong , Yes
13 , Overcast , Hot , Normal , Weak , Yes
14 , Rain , Mild , High , Strong , No
这里我们先不讨论算法（这里用的是ID3/C4.5），把一棵决策树建立起来再说。我们要建立的决策树的形式类似于“如果天气怎么样，去玩；否则，怎么着怎么着”的树形分叉。那么问题是用哪个属性（即变量，如天气、温度、湿度和风力）最适合充当这颗树的根节点，在它上面没有其他节点，其他的属性都是它的后续节点。借用信息论的概念，我们用一个统计量，“信息增益”（Information Gain）来衡量一个属性区分以上数据样本的能力。信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁，比如说一棵树可以这么读成，如果风力弱，就去玩；风力强，再按天气、温度等分情况讨论，此时用风力作为这棵树的根节点就很有价值。如果说，风力弱，再又天气晴朗，就去玩；如果风力强，再又怎么怎么分情况讨论，这棵树相比就不够简洁了。计算信息增益的公式需要用到“熵”（Entropy）。名词越来越多，让我们通过手工计算记住它们的计算方法，把Excel打开：
我们检查的属性是是否出去玩。用Excel对上面数据的play变量的各个取值排个序（这个工作簿里把“play”这个词去掉），一共是14条记录，你能数出取值为yes的记录有9个，取值为no的有5个，我们说这个样本里有9个正例，5 个负例，记为S(9+,5-)，S是样本的意思(Sample)。这里熵记为Entropy(S),计算公式为：
Entropy(S)= -(9/14)*log(9/14)-(5/14)*log(5/14)
解释一下，9/14是正例的个数与总记录之比，同样5/14是负例占总记录的比例。log(.)是以2为底的对数（我们知道以e为底的对数称为自然对数，记为ln(.),lg(.)表示以10为底的对数 ）。在Excel里我们可以随便找一个空白的单元格，键入以下公式即得0.940：
=-(9/14)*LOG(9/14,2)-(5/14)*LOG(5/14,2)
这里LOG(9/14,2)中的“2”表示以2为底。类似地，如果你习惯用Matlab做数学运算本，公式为
-(9/14)*log2(9/14)-(5/14)*log2(5/14)
其中“2”的含义与上同。
总结：在这个例子中，我们的输出属性（我们要检查的属性）“play”只有两个取值，同样地，如果输出属性的取值大于2，公式是对成的，一样的形式，连加就是，找到各个取值的个数，求出各自的比例。如果样本具有二元输出属性，其熵的公式为
Entropy(S) =-(p+)*log(p+)-(p-)*log(p-)
其中，p+、p-分别为正例和负例占总记录的比例。输出属性取值大于2的情况，公式是对称的。
2 分别以Wind、Humidity、Outlook和Temperature作为根节点，计算其信息增益
可以数得，属性Wind中取值为Weak的记录有Normal的记录有8条，其中正例6个，负例2个；同样，取值为Strong的记录6个，正例负例个3个。我们可以计算相应的熵为：
Entropy(Weak)=-(6/8)*log(6/8)-(2/8)*log(2/8)=0.811
Entropy(Strong)=-(3/6)*log(3/6)-(3/6)*log(3/6)=1.0
现在就可以计算出相应的信息增益了：
Gain(Wind)=Entropy(S)-(8/14)*Entropy(Weak)-(6/14)*Entropy(Strong)=0.940-(8/14)*0.811-(6/14)*1.0=0.048
这个公式的奥秘在于，8/14是属性Wind取值为Weak的个数占总记录的比例，同样6/14是其取值为Strong的记录个数与总记录数之比。
同理，如果以Humidity作为根节点：
Entropy(High)=0.985 ; Entropy(Normal)=0.592
Gain(Humidity)=0.940-(7/14)*Entropy(High)-(7/14)*Entropy(Normal)=0.151
以Outlook作为根节点：
Entropy(Sunny)=0.971 ; Entropy(Overcast)=0.0 ; Entropy(Rain)=0.971
Gain(Outlook)=0.940-(5/14)*Entropy(Sunny)-(4/14)*Entropy(Overcast)-(5/14)*Entropy(Rain)=0.247
以Temperature作为根节点：
Entropy(Cool)=0.811 ; Entropy(Hot)=1.0 ; Entropy(Mild)=0.918
Gain(Temperature)=0.940-(4/14)*Entropy(Cool)-(4/14)*Entropy(Hot)-(6/14)*Entropy(Mild)=0.029
这样我们就得到了以上四个属性相应的信息增益值：
Gain(Wind)=0.048 ；Gain(Humidity)=0.151 ； Gain(Outlook)=0.247 ；Gain(Temperature)=0.029
最后按照信息增益最大的原则选Outlook为根节点。子节点重复上面的步骤。这颗树可以是这样的，它读起来就跟你认为的那样：
参考资料：
1.王厚峰，“机器学习‘课程讲义，2007年春季学期，北京大学软件与微电子学院
2.Mitchell,《机器学习》，曾华军等译，北京：机械工业出版社，2003 转载：
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1034025次
积分：14394
积分：14394
排名：第256名
原创：365篇
转载：251篇
评论：250条
(1)(1)(2)(1)(7)(4)(3)(14)(3)(8)(2)(2)(11)(25)(29)(1)(10)(26)(153)(85)(15)(15)(13)(1)(1)(11)(9)(8)(4)(59)(48)(8)(14)(24)(3)(2)(2)扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
基于决策树的汉语未登录词识别
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
增量决策树中样例选择的影响与评价.pdf50页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：220 &&
你可能关注的文档：
··········
··········
硕士学位论文
增量决策树中样例选择的影响与评价
姓名：王硕
申请学位级别：硕士
专业：计算机软件与理论
指导教师：王熙照
随着数据库和网络技术的不断发展，使得人们可以越来越容易地获得海量的数据，
但由于数据信息自身的复杂性，使如何有效地处理和理解这些数据成为需要解决的难
题，而机器学习方法可以帮助我们认识和理解这些数据里隐含的知识，同时还可以帮助
和指导生产实践。此时，首先要面临的问题就是数据的动态增长，其次是数据的数量巨
大，二者都可以通过机器学习中的增量学习和主动学习来解决。前者可以适应数据不断
增长的学习环境，在保持原有学习结果的基础之上接收新的数据，通过调整更新分类器
来获取新的知识，而后者可以主动选择样例，从而降低数据的数量和复杂度，节约学习
的成本，降低构造分类器的代价。
本文研究了基于增量决策树的主动学习方法，其实就是将增量学习和主动学习两种
方法进行有效地结合，从而同时发挥二者的优势。增量决策树是一种有效的增量学习方
法，它可以在尽量最小破坏原有决策树的结构稳定性前提下，通过动态调整算法来更新
决策树。在此基础上，进一步研究了决策树结构的变化规律，提出了基于最大不一致判
断准则的未标注样例选择算法，从而完成主动学习中重要的一环。同时还介绍了基于最
大熵和基于最大可能预测错误的样例选择算法
正在加载中，请稍后...假设可将叶结点覆盖的实例看作统计样本，叶结点对实例的分类错误率遵循二项式分布..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
决策树算法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口基于决策树的属性约简方法研究应用数学（APPLIED MATHEMATICS）是应用目..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
基于决策树的属性约简方法研究
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口}