I3算法实验报告.doc

1D3算法全析现 学专学姓既 学 专 学 姓 号 XXXXXXXXXXX 名 XXXX 指导教师. XXXX 2015 年 x 刀 xx Q :决策树是对数据进行分类，以此达到预测的目的。该决策树方法先根据训练 集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加 入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树 形结构。 先上问题吧，我们统计了 14天的气象数据(指标包括outlook ,temperature ,humidity , windy),并已知这些天气是否打球(play)。如果给出新一天的气象指标数 据:sunny,cool,high,TRUE ,判断一下会不会去打球。 outlook temperature humidity windy play sunny hot high false no sunny hot high true no overcast hot high false yes rainy mild high false yes rainy cool normal false yes rainy cool normal true no overcast cool normal true yes sunny mild high false no sunny cool normal false yes rainy mild normal false yes sunny mild normal true yes overcast mild high true yes overcast hot normal false yes rainy mild high true no 这个问题当然可以用朴素贝叶斯法求解，分别计算在给定天气条件下打球和不打 球的概率，选概率大者作为推测结果。 预备知识：信息鴆 熵是无序性（或不确定性龙勺度量指标。假如事件A的全概率划分是（A1，A2An）, 每部分发生的概率是（p1，p2pn）,那信息熵定义为： entropy{p”p2，.：pn）=-p} logj?, -p2 logj?2 pnlog^^ 通常以2为底数，所以信息熇的单位是bito logzlB logzlB = =logcA - logcB logJ5 logcA ID3算法 构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越 快越好，这样我们有望得到一棵高度最矮的决策树。 在没有给定任何天气信息时，根据历史数据，我们只知道新的一天打球的概率是 14914log214=0.940 14 9 14 log2 14 =0.940 属性有4个：outlook , temperature , humidity , windy。我们首先要决定哪个属性作 树的根节点。 对每项指标分别统计：在不同的取值下打球和不打球的次数。 下面我们计算当已知变量outlook的值时，信息熵为多少。 outlook:sunny时，2/5的概率打球，3/5的概率不打球。entropy= 0.971 outlook= overcast 日寸，entropy= 0 outlook= rainy 时，entropy: 0.971 而根据历史统计数据，outlook取值为sunny、overcast、rainy的概率分别是5/14、 4/14、5/14,所以当已知变量outlook的值时，信息熵为：5/14 x 0.971 + 4/14 x 0 + 5/14 x 0.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在第一步使系统的信息熵下降得最快)，所以决策树 (outlook N1 N2 N3 接下来要确定N1取temperature, humidity还是windy?在已知outlook= sunny的情 况，根据历史数据，我们作出类似table 2的一张表，分别计算gain(temperature)、 gain(humidity)和 gain(windy),选最大者为 N1。 依此类推，构造决策树。当系统的信息熵降为0时，就没有必要再往下构造决策 树了，此时叶子节点都是纯的--这是理想情况。最坏的情况下，决策树的高度为属性 (决策变量)的个数，叶子节点不纯(这意味着我们要以一定的概率来作出决策X Java实现 最终的决策树保存在了 X ML中，使用了 Dom4j，