决策树程序试验

1、决策树程序实验众所周知，数据库技术从20世纪80年代开始，已经得到广泛的普及和应用。随着数据库容量的膨胀，特别是数据仓库以及web等新型数据源的日益普及，人们面临的主要问题不再是缺乏足够的信息可以使用，而是面对浩瀚的数据海洋如何有效地利用这些数据。从数据中生成分类器的一个特别有效的方法是生成一个决策树(DecisionTree)。决策树表示方法是应用最广泛的逻辑方法之一，它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从决策树的根到叶结点

2、的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3、CN2SLIQ、SPRINT。一、问题描述1.1 相关信息决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输入，而每个树叶结点代表类或类分布。数的最顶层结点是根结点。一棵典型的决策树如图1所示。它表示概念buys_computer,它预测顾客是否可能购买计算机。内部结点用矩形表示，而树叶结点用玉圆表示。为了对未知的样本分类，样本的属性值在决策树上测试。决策树从根到叶结点的一条路径就对应着一条合取规则，因此决策树容易转

3、化成分类规则。图1ID3算法: 决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。 采用信息增益来选择能够最好地将样本分类的属性。信息增益基于信息论中嫡的概念。ID3总是选择具有最高信息增益（或最大嫡压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。1.2 问题重述1、目标概念为“寿险促销”2、计算每个属性的信息增益3、确定根节点的测试属性数据收入就国估用”保险件利隼龄4O-5OK

4、有春力453O-4OK1-1蛆古女404O-5OK有否力423O-4OK是是43心何3X2030K杏后k5530-40KK是力352O-3OKfl杏%273O-MJK有女4330-40K忠否女41140-5OK是古为432O-3OK是不1女295。二60K是杏玉3940-5QK看否力5520-W1-11PM&女J9模型求解构造决策树的方法是采用自上而下的递归构造，其思路是： 以代表训练样本的单个结点开始建树（步骤1）。 如果样本都在同一类，则该结点成为树叶，并用该类标记（步骤2和3）c 否则，算法使用称为信息增益的机遇嫡的度量为启发信息，选择能最好地将样本分类的属性（步骤6）。该属性成

5、为该结点的“测试”或“判定”属性（步骤7）。值得注意的是，在这类算法中，所有的属性都是分类的，即取离散值的连续值的属性必须离散化。 对测试属性的每个已知的值，创建一个分支，并据此划分样本（步骤810） 算法使用同样的过程，递归地形成每个划分上的样本决策树。一旦一个属性出现在一个结点上，就不必考虑该结点的任何后代(步骤13)。 递归划分步骤，当下列条件之一成立时停止：(a)给定结点的所有样本属于同一类(步骤2和3)。(b)没有剩余属性可以用来进一步划分样本(步骤4)o在此情况下，采用多数表决(步骤5)o这涉及将给定的结点转换成树叶，并用samples中的多数所在类别标记它。换一种方式，可以存放结

6、点样本的类分布。(c)分支test_attribute=a没有样本。在这种情况下，以samples中的多数类创建一个树叶(步骤12)。算法Decision_Tree(samples,attribute_list)输入由离散值属性描述的训练样本集samples;候选属性集合attribute_list。输出一棵决策树。(1)创建节点N;(2) Ifsamples都在同一类C中then(3) 返回N作为叶节点，以类C标记；(4) Ifattribute_list为空then(5) 返0N作为叶节点，以samples中最普遍的类标记；多数表决(6) 选择attribute_list中具有最高信息增益

7、的属性test_attribute;(7) 以test_attribute标记节点N；(8) Foreachtest_attribute的已知值v/戈U分samples(9) 由节点N分出一个对应test_attribute=v的分支；(10) 令Sv为samples中test_attribute=v的样本集合；一个划分块(11) IfSv为空then(12) 加上一个叶节点，以samples中最普遍的类标记；(13) Else加入一个由Decision_Tree(Sv,attribute_list-test_attribute)返回节点值E(S)=(-915)log2(915)-(615)l

8、og2(615)=0.971Values畋入范围尸20-30K,30-40k,40-50K,50-60KE(S(20-30K)=(-24)log2(24)-(24)log2(24)=1E(S(30-40K)=(-45)log2(45)-(15)log2(15)=0.7219E(S(40-50K)=(-14)log2(14)-(34)log2(34)=0.8113E(S(50-60K)=(-22)log2(22)-(02)log2(02)=0所以E(S,收入范围尸(4/15)E(S(20-30K)+(5/15)E(S(30-40K)+(4/15)E(S(40-50K)+(2/15)E(S(50-

9、60K)=0.7236Gain(S,收入范围)=0.971-0.7236=0.2474同理：计算“保险”，“性别”，“年龄”的信息增益为：E(S)=(-915)log2(915)-(615)log2(615)=0.971Insurance(保险)=yes,noE(S(yes)=(-33)log2(33)-(03)log2(03)=0E(S(no)=(-612)log2(612)-(612)log2(612)=1E(S,保险)=(3/15)E(S(yes)+(12/15)E(S(no)=0.8Gain(S,保险)=0.971-0.8=0.171E(S)=(-915)log2(915)-(615)

10、log2(615)=0.971sex(性另U)=male,femaleE(S(male)=(-37)log2(37)-(47)log2(47)=0.9852E(S(female)=(-68)log2(68)-(28)log2(28)=0.8113E(S,性别)=(7/15)E(S(male)+(8/15)E(S(female)=0.8925Gain(S,性别)=0.971-0.8925=0.0785E(S)=(-915)log2(915)-(615)log2(615)=0.971age(年龄)=1540,4160E(S(1540)=(-67)log2(67)-(17)log2(17)=0.59

11、17E(S(4160)=(-38)log2(38)-(58)log2(58)=0.9544E(S,年龄)=(7/15)E(S(1540)+(8/15)E(S(4160)=0.7851Gain(S,年龄)=0.971-0.7851=0.1859代码packageDecisionTree;importjava.util.ArrayList;/*决策树结点类*/publicclassTreeNodeprivateStringname;/节点名(分裂属性的名称)privateArrayList<String>rule;/结点的分裂规则ArrayList<TreeNode>chi

12、ld;/子结点集合privateArrayList<ArrayList<String>>datas;/划分到该结点的训练元组privateArrayList<String>candAttr;/划分到该结点的候选属性publicTreeNode()=""this.rule=newArrayList<String>();this.child=newArrayList<TreeNode>();this.datas=null;this.candAttr=null;publicArrayList<Tr

13、eeNode>getChild()returnchild;publicvoidsetChild(ArrayList<TreeNode>child)this.child=child;publicArrayList<String>getRule()returnrule;)publicvoidsetRule(ArrayList<String>rule)this.rule=rule;)publicStringgetName()returnname;)publicvoidsetName(Stringname)=name;)publicArray

14、List<ArrayList<String>>getDatas()returndatas;)publicvoidsetDatas(ArrayList<ArrayList<String>>datas)this.datas=datas;)publicArrayList<String>getCandAttr()returncandAttr;)publicvoidsetCandAttr(ArrayList<String>candAttr)this.candAttr=candAttr;)packageDecisionTree;imp

15、ortjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.ArrayList;importjava.util.StringTokenizer;/*决策树算法测试类*/publicclassTestDecisionTree/*读取候选属性*return候选属性集合*throwsIOException*/publicArrayList<String>readCandAttr()throwsIOExceptionArrayList<Strin

16、g>candAttr=newArrayList<String>();BufferedReaderreader=newBufferedReader(newInputStreamReader(System.in);Stringstr=""while(!(str=reader.readLine().equals("")StringTokenizertokenizer=newStringTokenizer(str);while(tokenizer.hasMoreTokens()candAttr.add(tokenizer.nextToken()

17、;returncandAttr;/*读取训练元组return训练元组集合throwsIOException*/publicArrayList<ArrayList<String>>readData()throwsIOExceptionArrayList<ArrayList<String>>datas=newArrayList<ArrayList<String>>();BufferedReaderreader=newBufferedReader(newInputStreamReader(System.in);Stringstr

18、=""while(!(str=reader.readLine().equals("")StringTokenizertokenizer=newStringTokenizer(str);ArrayList<String>s=newArrayList<String>();while(tokenizer.hasMoreTokens()s.add(tokenizer.nextToken();datas.add(s);returndatas;/*递归打印树结构paramroot当前待输出信息的结点*/publicvoidprintTree(

19、TreeNoderoot)System.out.println("name:"+root.getName();ArrayList<String>rules=root.getRule();System.out.print("noderules:");for(inti=0;i<rules.size();i+)System.out.print(rules.get(i)+"");System.out.print("");System.out.println("");ArrayList&

20、lt;TreeNode>children=root.getChild();intsize=children.size();if(size=0)System.out.println("->leafnode!<-");elseSystem.out.println("sizeofchildren:"+children.size();for(inti=0;i<children.size();i+)System.out.print("child"+(i+1)+"ofnode"+root.getName

21、()+":");printTree(children.get(i);)/*主函数,程序入口*paramargs*/publicstaticvoidmain(Stringargs)TestDecisionTreetdt=newTestDecisionTree();ArrayList<String>candAttr=null;ArrayList<ArrayList<String>>datas=null;trySystem.out.println("请输入候选属性");candAttr=tdt.readCandAttr();

22、System.out.println("请输入训练数据");datas=tdt.readData();catch(IOExceptione)e.printStackTrace();DecisionTreetree=newDecisionTree();TreeNoderoot=tree.buildTree(datas,candAttr);tdt.printTree(root);packageDecisionTree;importjava.util.ArrayList;importjava.util.HashMap;importjava.util.Iterator;import

23、java.util.Map;/*选择最佳分裂属性*/publicclassGainprivateArrayList<ArrayList<String>>D=null;/训练元组privateArrayList<String>attrList=null;/候选属性集publicGain(ArrayList<ArrayList<String>>datas,ArrayList<String>attrList)this.D=datas;this.attrList=attrList;/* 获取最佳侯选属性列上的值域(假定所有属性列上

24、的值都是有限的名词或分类类型的)* paramattrIndex指定的属性列的索引* return值域集合* /publicArrayList<String>getValues(ArrayList<ArrayList<String>>datas,intattrIndex)ArrayList<String>values=newArrayList<String>();Stringr=""for(inti=0;i<datas.size();i+)r=datas.get(i).get(attrIndex);if(!v

25、alues.contains(r)values.add(r);returnvalues;/* 获取指定数据集中指定属性列索引的域值及其计数* paramd指定的数据集* paramattrIndex指定的属性列索引* return类别及其计数的map* /publicMap<String,IntegervalueCounts(ArrayList<ArrayList<String>>datas,intattrIndex)Map<String,Integer>valueCount=newHashMap<String,Integer>();Str

26、ingc=""ArrayList<String>tuple=null;for(inti=0;i<datas.size();i+)tuple=datas.get(i);c=tuple.get(attrlndex);if(valueCount.containsKey(c)valueCount.put(c,valueCount.get(c)+1);elsevalueCount.put(c,1);/*returnvalueCount;求对datas中元组分类所需的期望信息，即datas的嫡paramdatas训练元组* returndatas的嫡值* /publi

27、cdoubleinfoD(ArrayList<ArrayList<String>>datas)doubleinfo=0.000;inttotal=datas.size();Map<String,Integer>classes=valueCounts(datas,attrList.size();Iteratoriter=classes.entrySet().iterator();Integercounts=newIntegerclasses.size();for(inti=0;iter.hasNext();i+)Map.Entryentry=(Map.Entr

28、y)iter.next();Integerval=(Integer)entry.getValue();countsi=val;)for(inti=0;i<counts.length;i+)doublebase=DecimalCalculate.div(countsi,total,3);info+=(-1)*base*Math.log(base);)returninfo;)/*获取指定属性列上指定值域的所有元组paramattrIndex指定属性列索引paramvalue指定属性列的值域return指定属性列上指定值域的所有元组* /publicArrayList<ArrayList

29、<String>>datasOfValue(intattrIndex,Stringvalue)ArrayList<ArrayList<String>>Di=newArrayList<ArrayList<String>>();ArrayList<String>t=null;for(inti=0;i<D.size();i+)t=D.get(i);if(t.get(attrIndex).equals(value)Di.add(t);)returnDi;/*基于按指定属性划分对D的元组分类所需要的期望信息paramat

30、trIndex指定属性的索引return按指定属性划分的期望信息值*/publicdoubleinfoAttr(intattrIndex)doubleinfo=0.000;ArrayList<String>values=getValues(D,attrIndex);for(inti=0;i<values.size();i+)ArrayList<ArrayList<String>>dv=datasOfValue(attrIndex,values.get(i);info+=DecimalCalculate.mul(DecimalCalculate.div(

31、dv.size(),D.size(),3),infoD(dv);)returninfo;/*获取最佳分裂属性的索引return最佳分裂属性的索引*/publicintbestGainAttrIndex()intindex=-1;doublegain=0.000;doubletempGain=0.000;for(inti=0;i<attrList.size();i+)tempGain=infoD(D)-infoAttr(i);if(tempGain>gain)gain=tempGain;index=i;)returnindex;)packageDecisionTree;importj

32、ava.util.ArrayList;importjava.util.HashMap;importjava.util.Iterator;importjava.util.Map;importjavax.smartcardio.*;/*决策树构造类*/publicclassDecisionTree2表不privateIntegerattrSelMode;/最佳分裂属性选择模式，1表示以信息增益度量,以信息增益率度量。暂未实现2publicDecisionTree()this.attrSelMode=1;)publicDecisionTree(intattrSelMode)this.attrSelM

33、ode=attrSelMode;)publicvoidsetAttrSelMode(IntegerattrSelMode)this.attrSelMode=attrSelMode;)/*获取指定数据集中的类别及其计数paramdatas指定的数据集return类别及其计数的map*/publicMap<String,Integer>classOfDatas(ArrayList<ArrayList<String>>datas)Map<String,Integer>classes=newHashMap<String,Integer>();

34、Stringc=""ArrayList<String>tuple=null;for(inti=0;i<datas.size();i+)tuple=datas.get(i);c=tuple.get(tuple.size()-1);if(classes.containsKey(c)classes.put(c,classes.get(c)+1);elseclasses.put(c,1);returnclasses;/*获取具有最大计数的类名，即求多数类paramclasses类的键值集合return多数类的类名*/publicStringmaxClass(Map

35、<String,Integerclasses)StringmaxC=""intmax=-1;Iteratoriter=classes.entrySet().iterator();for(inti=0;iter.hasNext();i+)(Map.Entryentry=(Map.Entry)iter.next();Stringkey=(String)entry.getKey();Integerval=(Integer)entry.getValue();if(val>max)max=val;maxC=key;returnmaxC;/* 构造决策树* paramdat

36、as训练元组集合* paramattrList候选属性集合* return决策树根结点* /publicTreeNodebuildTree(ArrayList<ArrayList<String>>datas,ArrayList<String>attrList)/System.out.print("候选属性列表：");/for(inti=0;i<attrList.size();i+)/System.out.print(""+attrList.get(i)+"");/System.out.prin

37、tln();TreeNodenode=newTreeNode();node.setDatas(datas);node.setCandAttr(attrList);Map<String,Integerclasses=classOfDatas(datas);StringmaxC=maxClass(classes);if(classes.size()=1|attrList.size()=0)node.setName(maxC);returnnode;Gaingain=newGain(datas,attrList);intbestAttrIndex=gain.bestGainAttrIndex(

38、);ArrayList<String>rules=gain.getValues(datas,bestAttrIndex);node.setRule(rules);node.setName(attrList.get(bestAttrIndex);if(rules.size()>2)/?此处有待商榷attrList.remove(bestAttrIndex);for(inti=0;i<rules.size();i+)Stringrule=rules.get(i);ArrayList<ArrayList<String>>di=gain.datasOfV

39、alue(bestAttrIndex,rule);for(intj=0;j<di.size();j+)di.get(j).remove(bestAttrIndex);if(di.size()=0)TreeNodeleafNode=newTreeNode();leafNode.setName(maxC);leafNode.setDatas(di);leafNode.setCandAttr(attrList);node.getChild().add(leafNode);elseTreeNodenewNode=buildTree(di,attrList);node.getChild().add

40、(newNode);returnnode;packageDecisionTree;importjava.math.BigDecimal;publicclassDecimalCalculate/* 由于Java的简单类型不能够精确的对浮点数进行运算，这个工具类提供精* 确的浮点数运算，包括加减乘除和四舍五入。* /默认除法运算精度privatestaticfinalintDEF_DIV_SCALE=10;这个类不能实例化privateDecimalCalculate()/* 提供精确的加法运算。* paramv1被加数* paramv2加数* return两个参数的和* /publicstati

41、cdoubleadd(doublev1,doublev2)BigDecimalb1=newBigDecimal(Double.toString(v1);BigDecimalb2=newBigDecimal(Double.toString(v2);returnb1.add(b2).doubleValue();/*提供精确的减法运算。paramv1被减数paramv2减数return两个参数的差*/publicstaticdoublesub(doublev1,doublev2)BigDecimalb1=newBigDecimal(Double.toString(v1);BigDecimalb2=n

42、ewBigDecimal(Double.toString(v2);returnb1.subtract(b2).doubleValue();/*提供精确的乘法运算。paramv1被乘数paramv2乘数return两个参数的积*/publicstaticdoublemul(doublev1,doublev2)BigDecimalb1=newBigDecimal(Double.toString(v1);BigDecimalb2=newBigDecimal(Double.toString(v2);returnb1.multiply(b2).doubleValue();/*提供（相对）精确的除法运算，

43、当发生除不尽的情况时，精确到小数点以后10位，以后的数字四舍五入。paramv1被除数paramv2除数return两个参数的商*/publicstaticdoublediv(doublev1,doublev2)returndiv(v1,v2,DEF_DIV_SCALE);/*提供（相对）精确的除法运算。当发生除不尽的情况时，由定精度，以后的数字四舍五入。paramv1被除数paramv2除数paramscale表示表示需要精确到小数点以后几位。return两个参数的商scale参数指*/publicstaticdoublediv(doublev1,doublev2,intscale)if(s

44、cale<0)thrownewIllegalArgumentException("Thescalemustbeapositiveintegerorzero");)BigDecimalb1=newBigDecimal(Double.toString(v1);BigDecimalb2=newBigDecimal(Double.toString(v2);returnb1.divide(b2,scale,BigDecimal.ROUND_HALF_UP).doubleValue();)/*提供精确的小数位四舍五入处理。*paramv需要四舍五入的数字paramscale小数点

45、后保留几位return四舍五入后的结果*/publicstaticdoubleround(doublev,intscale)if(scale<0)thrownewIllegalArgumentException("Thescalemustbeapositiveintegerorzero");)BigDecimalb=newBigDecimal(Double.toString(v);BigDecimalone=newBigDecimal("1");returnb.divide(one,scale,BigDecimal.ROUND_HALF_UP).d

46、oubleValue();/*提供精确的类型转换(Float)paramv需要被转换的数字return返回转换结果*/publicstaticfloatconvertsToFloat(doublev)BigDecimalb=newBigDecimal(v);returnb.floatValue();)/*提供精确的类型转换(Int)不进行四舍五入paramv需要被转换的数字return返回转换结果*/publicstaticintconvertsToInt(doublev)BigDecimalb=newBigDecimal(v);Value();)/*提供精确的类型转换(

47、Long)paramv需要被转换的数字return返回转换结果*/publicstaticlongconvertsToLong(doublev)BigDecimalb=newBigDecimal(v);returnb.longValue();)/*返回两个数中大的一个值paramv1需要被对比的第一个数paramv2需要被对比的第二个数return返回两个数中大的一个值*/publicstaticdoublereturnMax(doublev1,doublev2)BigDecimalb1=newBigDecimal(v1);BigDecimalb2=newBigDecimal(v2);returnb1.max(b2).doubleValue();)/*返回两个数中小的一个值paramv1需要被对比的第一个数paramv2需要被对比的第二个数return返回两个数中小