决策树程序实验

决策树程序实验决策树程序实验决策树程序实验决策树程序实验编制仅供参考审核批准生效日期地址：电话：传真:邮编:决策树程序实验

众所周知，数据库技术从20世纪80年代开始，已经得到广泛的普及和应用。随着数据库容量的膨胀，特别是数据仓库以及web等新型数据源的日益普及，人们面临的主要问题不再是缺乏足够的信息可以使用，而是面对浩瀚的数据海洋如何有效地利用这些数据。从数据中生成分类器的一个特别有效的方法是生成一个决策树（DecisionTree）。决策树表示方法是应用最广泛的逻辑方法之一，它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3、CN2、SLIQ、SPRINT等。一、问题描述相关信息决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输入，而每个树叶结点代表类或类分布。数的最顶层结点是根结点。一棵典型的决策树如图1所示。它表示概念buys_computer，它预测顾客是否可能购买计算机。内部结点用矩形表示，而树叶结点用椭圆表示。为了对未知的样本分类，样本的属性值在决策树上测试。决策树从根到叶结点的一条路径就对应着一条合取规则，因此决策树容易转化成分类规则。图1ID3算法：■ 决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。■ 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。■ 采用信息增益来选择能够最好地将样本分类的属性。信息增益基于信息论中熵的概念。ID3总是选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。问题重述1、目标概念为“寿险促销”2、计算每个属性的信息增益3、确定根节点的测试属性模型求解构造决策树的方法是采用自上而下的递归构造，其思路是：■ 以代表训练样本的单个结点开始建树（步骤1）。■ 如果样本都在同一类，则该结点成为树叶，并用该类标记（步骤2和3）。■ 否则，算法使用称为信息增益的机遇熵的度量为启发信息，选择能最好地将样本分类的属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。值得注意的是，在这类算法中，所有的属性都是分类的，即取离散值的。连续值的属性必须离散化。■ 对测试属性的每个已知的值，创建一个分支，并据此划分样本（步骤8~10）。■ 算法使用同样的过程，递归地形成每个划分上的样本决策树。一旦一个属性出现在一个结点上，就不必考虑该结点的任何后代（步骤13）。■ 递归划分步骤，当下列条件之一成立时停止：（a）给定结点的所有样本属于同一类（步骤2和3）。（b）没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，采用多数表决（步骤5）。这涉及将给定的结点转换成树叶，并用samples中的多数所在类别标记它。换一种方式，可以存放结点样本的类分布。（c）分支test_attribute=ai没有样本。在这种情况下，以samples中的多数类创建一个树叶（步骤12）。算法 Decision_Tree(samples,attribute_list)输入 由离散值属性描述的训练样本集samples;候选属性集合attribute_list。输出 一棵决策树。（1）创建节点N；（2）Ifsamples都在同一类C中then（3）返回N作为叶节点，以类C标记；（4）Ifattribute_list为空then（5）返回N作为叶节点，以samples中最普遍的类标记；quals("")){ StringTokenizertokenizer=newStringTokenizer(str); while()){ ()); } } returncandAttr; } /** *读取训练元组 *@return训练元组集合 *@throwsIOException */ publicArrayList<ArrayList<String>>readData()throwsIOException{ ArrayList<ArrayList<String>>datas=newArrayList<ArrayList<String>>(); BufferedReaderreader=newBufferedReader(newInputStreamReader); Stringstr=""; while(!(str=()).equals("")){ StringTokenizertokenizer=newStringTokenizer(str); ArrayList<String>s=newArrayList<String>(); while()){ ()); } (s); } returndatas; } /** *递归打印树结构 *@paramroot当前待输出信息的结点 */ publicvoidprintTree(TreeNoderoot){ "name:"+()); ArrayList<String>rules=(); "noderules:{"); for(inti=0;i<();i++){ +""); } "}"); ""); ArrayList<TreeNode>children=(); intsize=(); if(size==0){ "-->leafnode!<--"); }else{ "sizeofchildren:"+()); for(inti=0;i<();i++){ "child"+(i+1)+"ofnode"+()+":"); printTree(i)); } } } /** *主函数，程序入口 *@paramargs */ publicstaticvoidmain(String[]args){ TestDecisionTreetdt=newTestDecisionTree(); ArrayList<String>candAttr=null; ArrayList<ArrayList<String>>datas=null; try{ "请输入候选属性"); candAttr=(); "请输入训练数据"); datas=(); }catch(IOExceptione){ (); } DecisionTreetree=newDecisionTree(); TreeNoderoot=(datas,candAttr); (root); }}packageDecisionTree;import*选择最佳分裂属性*/publicclassGain{ privateArrayList<ArrayList<String>>D=null;et(attrIndex); if(!(r)){ (r); } } returnvalues; } /** *获取指定数据集中指定属性列索引的域值及其计数 *@paramd指定的数据集 *@paramattrIndex指定的属性列索引 *@return类别及其计数的map */ publicMap<String,Integer>valueCounts(ArrayList<ArrayList<String>>datas,intattrIndex){ Map<String,Integer>valueCount=newHashMap<String,Integer>(); Stringc=""; ArrayList<String>tuple=null; for(inti=0;i<();i++){ tuple=(i); c=(attrIndex); if(c)){ (c,(c)+1); }else{ (c,1); } } returnvalueCount; } /** *求对datas中元组分类所需的期望信息，即datas的熵 *@paramdatas训练元组 *@returndatas的熵值 */ publicdoubleinfoD(ArrayList<ArrayList<String>>datas){ doubleinfo=; inttotal=(); Map<String,Integer>classes=valueCounts(datas,()); Iteratoriter=().iterator(); Integer[]counts=newInteger[()]; for(inti=0;();i++) { entry=(); Integerval=(Integer)(); counts[i]=val; } for(inti=0;i<;i++){ doublebase=(counts[i],total,3); info+=(-1)*base*(base); } returninfo; } /** *获取指定属性列上指定值域的所有元组 *@paramattrIndex指定属性列索引 *@paramvalue指定属性列的值域 *@return指定属性列上指定值域的所有元组 */ publicArrayList<ArrayList<String>>datasOfValue(intattrIndex,Stringvalue){ ArrayList<ArrayList<String>>Di=newArrayList<ArrayList<String>>(); ArrayList<String>t=null; for(inti=0;i<();i++){ t=(i); if(attrIndex).equals(value)){ (t); } } returnDi; } /** *基于按指定属性划分对D的元组分类所需要的期望信息 *@paramattrIndex指定属性的索引 *@return按指定属性划分的期望信息值 */ publicdoubleinfoAttr(intattrIndex){ doubleinfo=; ArrayList<String>values=getValues(D,attrIndex); for(inti=0;i<();i++){ ArrayList<ArrayList<String>>dv=datasOfValue(attrIndex,(i)); info+=(),(),3),infoD(dv)); } returninfo; } /** *获取最佳分裂属性的索引 *@return最佳分裂属性的索引 */ publicintbestGainAttrIndex(){ intindex=-1; doublegain=; doubletempGain=; for(inti=0;i<();i++){ tempGain=infoD(D)-infoAttr(i); if(tempGain>gain){ gain=tempGain; index=i; } } returnindex; }}packageDecisionTree;import.*;/***决策树构造类*/publicclassDecisionTree{ privateIntegerattrSelMode;terator(); for(inti=0;();i++) { entry=(); Stringkey=(String)(); Integerval=(Integer)(); if(val>max){ max=val; maxC=key; } } returnmaxC; } /** *构造决策树 *@paramdatas训练元组集合 *@paramattrList候选属性集合 *@return决策树根结点 */ publicTreeNodebuildTree(ArrayList<ArrayList<String>>datas,ArrayList<String>attrList){emove(bestAttrIndex); } if()==0){ TreeNodeleafNode=newTreeNode(); (maxC); (di); (attrList); ().add(leafNode); }else{ TreeNodenewNode=buildTree(di,attrList); ().add(newNode); } } returnnode; }}packageDecisionTree;importpublicclassDecimalCalculate{/***由于Java的简单类型不能够精确的对浮点数进行运算，这个工具类提供精*确的浮点数运算，包括加减乘除和四舍五入。*/oubleValue(); } /** *提供精确的减法运算。 *@paramv1被减数 *@paramv2减数 *@return两个参数的差 */ publicstaticdoublesub(doublev1,doublev2){ BigDecimalb1=newBigDecimal(v1)); BigDecimalb2=newBigDecimal(v2)); return(b2).doubleValue(); } /** *提供精确的乘法运算。 *@paramv1被乘数 *@paramv2乘数 *@return两个参数的积 */ publicstaticdoublemul(doublev1,doublev2){ BigDecimalb1=newBigDecimal(v1)); BigDecimalb2=newBigDecimal(v2)); return(b2).doubleValue(); } /** *提供（相对）精确的除法运算，当发生除不尽的情况时，精确到 *小数点以后10位，以后的数字四舍五入。 *@paramv1被除数 *@paramv2除数 *@return两个参数的商 */ publicstaticdoublediv(doublev1,doublev2){ returndiv(v1,v2,DEF_DIV_SCALE); } /** *提供（相对）精确的除法运算。当发生除不尽的情况时，由scale参数指 *定精度，以后的数字四舍五入。 *@paramv1被除数 *@paramv2除数 *@paramscale表示表示需要精确到小数点以后几位。 *@return两个参数的商 */ publicstaticdoublediv(doublev1,doublev2,intscale){ if(scale<0){ thrownewIllegalArgumentException( "Thescalemustbeapositiveintegerorzero"); } BigDecimalb1=newBigDecimal(v1)); BigDecimalb2=newBigDecimal(v2)); return(b2,scale,.doubleValue(); } /** *提供精确的小数位四舍五入处理。 *@paramv需要四舍五入的数字 *@paramscale小数点后保留几位 *@return四舍五入后的结果 */ publicstaticdoubleround(doublev,intscale){ if(scale<0){ thrownewIllegalArgumentException( "Thescalemustbeapositiveintegerorzero"); } BigDecimalb=newBigDecimal(v)); BigDecimalone=newBigDecimal("1"); return(one,scale,.doubleValue(); } /** *提供精确的类型转换(Float) *@paramv需要被转换的数字 *@return返回转换结果 */ publicstaticfloatconvertsToFloat(doublev){ BigDecimalb=newBigDecimal(v); return(); } /** *提供精确的类型转换(Int)不进行四舍五入 *@paramv需要被转换的数字 *@return返回转换结果 */ publicstaticintconvertsToInt(doublev){ BigDecimalb=newBigDecimal(v); return(); } /** *提供精确的类型转换(Long) *@paramv需要被转换的数字 *@return返回转换结果 */ publicstaticlongconvertsToLong(doublev){ BigDecimalb=newBigDecimal(v); return(); } /** *返回两个数中大的一个值 *@paramv1需要被对比的第一个数 *@paramv2需要被对比的第二个数 *@return返回两个数中大的一个值 */ pub