ID3算法实验报告

题目：ID3算法分析与实现学院xxxxxxxxxxxxxxxxxxxx专业xxxxxxxxxxxxxxxx学号xxxxxxxxxxx姓名xxxx指导教师xxxx2015年x月xx日装订线ID3算法分析与实现摘要:决策树是对数据进行分类，以此达到预测的目的。该决策树方法先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。先上问题吧，我们统计了14天的气象数据(指标包括outlook，temperature，humidity，windy)，并已知这些天气是否打球(play)。如果给出新一天的气象指标数据:sunny,cool,high,TRUE，判断一下会不会去打球。这个问题当然可以用朴素贝叶斯法求解，分别计算在给定天气条件下打球和不打球的概率，选概率大者作为推测结果。现在我们使用ID3归纳决策树的方法来求解该问题。预备知识：信息熵熵是无序性（或不确定性）的度量指标。假如事件A的全概率划分是（A1,A2,...,An），每部分发生的概率是(p1,p2,...,pn)，那信息熵定义为：通常以2为底数，所以信息熵的单位是bit。补充两个对数去处公式：ID3算法构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越快越好，这样我们有望得到一棵高度最矮的决策树。在没有给定任何天气信息时，根据历史数据，我们只知道新的一天打球的概率是9/14，不打的概率是5/14。此时的熵为：属性有4个：outlook，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/14、4/14、5/14，所以当已知变量outlook的值时，信息熵为：5/14×0.971+4/14×0+5/14×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取temperature、humidity还是windy?在已知outlook=sunny的情况，根据历史数据，我们作出类似table2的一张表，分别计算gain(temperature)、gain(humidity)和gain(windy)，选最大者为N1。依此类推，构造决策树。当系统的信息熵降为0时，就没有必要再往下构造决策树了，此时叶子节点都是纯的--这是理想情况。最坏的情况下，决策树的高度为属性（决策变量）的个数，叶子节点不纯（这意味着我们要以一定的概率来作出决策）。Java实现最终的决策树保存在了XML中，使用了Dom4J，注意如果要让Dom4J支持按XPath选择节点，还得引入包jaxen.jar。程序代码要求输入文件满足ARFF格式，并且属性都是标称变量。实验用的数据文件：@relationweather.symbolic@attributeoutlook{sunny,overcast,rainy}@attributetemperature{hot,mild,cool}@attributehumidity{high,normal}@attributewindy{TRUE,FALSE}@attributeplay{yes,no}@datasunny,hot,high,FALSE,nosunny,hot,high,TRUE,noovercast,hot,high,FALSE,yesrainy,mild,high,FALSE,yesrainy,cool,normal,FALSE,yesrainy,cool,normal,TRUE,noovercast,cool,normal,TRUE,yessunny,mild,high,FALSE,nosunny,cool,normal,FALSE,yesrainy,mild,normal,FALSE,yessunny,mild,normal,TRUE,yesovercast,mild,high,TRUE,yesovercast,hot,normal,FALSE,yesrainy,mild,high,TRUE,no程序代码：packagecom.dfsj;importjava.io.BufferedReader;importjava.io.File;importjava.io.FileReader;importjava.io.FileWriter;importjava.io.IOException;importjava.util.ArrayList;importjava.util.Iterator;importjava.util.LinkedList;importjava.util.List;importjava.util.regex.Matcher;importjava.util.regex.Pattern;importorg.dom4j.Document;importorg.dom4j.DocumentHelper;importorg.dom4j.Element;importorg.dom4j.io.OutputFormat;importorg.dom4j.io.XMLWriter;publicclassID3{privateArrayListStringattribute=newArrayListString();//存储属性的名称privateArrayListArrayListStringattributevalue=newArrayListArrayListString();//存储每个属性的取值privateArrayListString[]data=newArrayListString[]();;//原始数据intdecatt;//决策变量在属性集中的索引publicstaticfinalStringpatternString=@attribute(.*)[{](.*?)[}];Documentxmldoc;Elementroot;publicID3(){xmldoc=DocumentHelper.createDocument();root=xmldoc.addElement(root);root.addElement(DecisionTree).addAttribute(value,null);}publicstaticvoidmain(String[]args){ID3inst=newID3();inst.readARFF(newFile(/home/orisun/test/weather.nominal.arff));inst.setDec(play);LinkedListIntegerll=newLinkedListInteger();for(inti=0;iinst.attribute.size();i++){if(i!=inst.decatt)ll.add(i);}ArrayListIntegeral=newArrayListInteger();for(inti=0;iinst.data.size();i++){al.add(i);}inst.buildDT(DecisionTree,null,al,ll);inst.writeXML(/home/orisun/test/dt.xml);return;}//读取arff文件，给attribute、attributevalue、data赋值publicvoidreadARFF(Filefile){try{FileReaderfr=newFileReader(file);BufferedReaderbr=newBufferedReader(fr);Stringline;Patternpattern=Pattern.compile(patternString);while((line=br.readLine())!=null){Matchermatcher=pattern.matcher(line);if(matcher.find()){attribute.add(matcher.group(1).trim());String[]values=matcher.group(2).split(,);ArrayListStringal=newArrayListString(values.length);for(Stringvalue:values){al.add(value.trim());}attributevalue.add(al);}elseif(line.startsWith(@data)){while((line=br.readLine())!=null){if(line==)continue;String[]row=line.split(,);data.add(row);}}else{continue;}}br.close();}catch(IOExceptione1){e1.printStackTrace();}}//设置决策变量publicvoidsetDec(intn){if(n0||n=attribute.size()){System.err.println(决策变量指定错误。);System.exit(2);}decatt=n;}publicvoidsetDec(Stringname){intn=attribute.indexOf(name);setDec(n);}//给一个样本（数组中是各种情况的计数），计算它的熵publicdoublegetEntropy(int[]arr){doubleentropy=0.0;intsum=0;for(inti=0;iarr.length;i++){entropy-=arr[i]*Math.log(arr[i]+Double.MIN_VALUE)/Math.log(2);sum+=arr[i];}entropy+=sum*Math.log(sum+Double.MIN_VALUE)/Math.log(2);entropy/=sum;returnentropy;}//给一个样本数组及样本的算术和，计算它的熵publicdoublegetEntropy(int[]arr,intsum){doubleentropy=0.0;for(inti=0;iarr.length;i++){entropy-=arr[i]*Math.log(arr[i]+Double.MIN_VALUE)/Math.log(2);}entropy+=sum*Math.log(sum+Double.MIN_VALUE)/Math.log(2);entropy/=sum;returnentropy;}publicbooleaninfoPure(ArrayListIntegersubset){Stringvalue=data.get(subset.get(0))[decatt];for(inti=1;isubset.size();i++){Stringnext=data.get(