资源描述：
《id3算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1D3算法全析现学专学姓既XXXXXXXXXXXXXXXXXXXXjkXXXXXXXXXXXXXXXX号XXXXXXXXXXX名XXXX指导教师.XXXX2015年x刀xxQ摘要:决策树是对数据进行分类，以此达到预测的目的。该决策树方法先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。先上问题吧，我们统计了14天的气象数据(指标包括outlook,temperature,humidity,wi
2、ndy),并已知这些天气是否打球(play)。如果给出新一天的气象指标数据:sunny,cool,high,TRUE,判断一下会不会去打球。outlooktemperaturehumiditywindyplaysunnyhothighfalsenosunnyhothightruenoovercasthothighfalseyesrainymildhighfalseyesrainycoolnormalfalseyesrainycoolnormaltruenoovercastcoolnormaltrueyess
3、unnymildhighfalsenosunnycoolnormalfalseyesrainymildnormalfalseyessunnymildnormaltrueyesovercastmildhightrueyesovercasthotnormalfalseyesrainymildhightrueno这个问题当然可以用朴素贝叶斯法求解，分别计算在给定天气条件下打球和不打球的概率，选概率大者作为推测结果。预备知识：信息鴆熵是无序性（或不确定性龙勺度量指标。假如事件A的全概率划分是（A1，A2An）,每部
4、分发生的概率是（p1，p2pn）,那信息熵定义为：entropy{p”p2，.：pn）=-p}logj?,-p2logj?2pnlog^^通常以2为底数，所以信息熇的单位是bitologzlB=补充两个对数去处公式：=logcA-logcBlogJ5logcAID3算法构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越快越好，这样我们有望得到一棵高度最矮的决策树。在没有给定任何天气信息时，根据历史数据，我们只知道新的一天打球的概率是14914log214=0.940属性有4个：outlo
5、ok,temperature,humidity,windy。我们首先要决定哪个属性作树的根节点。对每项指标分别统计：在不同的取值下打球和不打球的次数。下面我们计算当已知变量outlook的值时，信息熵为多少。outlook:sunny时，2/5的概率打球，3/5的概率不打球。entropy=0.971outlook=overcast日寸，entropy=0outlook=rainy时，entropy:0.971而根据历史统计数据，outlook取值为sunny、overcast、rainy的概率分别是5/1
6、4、4/14、5/14,所以当已知变量outlook的值时，信息熵为：5/14x0.971+4/14x0+5/14x0.971=0.693这样的话系统熵就从0.940下降到了0.693,信息增溢gain(outlook)为0.940-0.693=0.247同样可以计算出gain(temperature)=0.029,gain(humidity)=0.152,gain(windy)=0.048。gain(outlook)最大(即outlook在第一步使系统的信息熵下降得最快)，所以决策树(outlookN1N
7、2N3接下来要确定N1取temperature,humidity还是windy?在已知outlook=sunny的情况，根据历史数据，我们作出类似table2的一张表，分别计算gain(temperature)、gain(humidity)和gain(windy),选最大者为N1。依此类推，构造决策树。当系统的信息熵降为0时，就没有必要再往下构造决策树了，此时叶子节点都是纯的--这是理想情况。最坏的情况下，决策树的高度为属性(决策变量)的个数，叶子节点不纯(这意味着我们要以一定的概率来作出决策XJava实现
8、最终的决策树保存在了XML中，使用了Dom4j，注意如果要让Dom4j支持按XPath选择节点，还得引入包jaxenjar。程序代码要求输入文件满足ARFF格式，并且属性都是标称变量。实验用的数据文件：©relationweather.symbolic©attributeoutlook{sunny,overcast,rainy}©attributetemperature{hot,mild,cool}©attrib
