决策树程序试验

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

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

3、点对应着一个非类别属性，树枝代表这个属性的 值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性 值。 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。 采用信息增益来选择能够最好地将样本分类的属性。信息增益基于信息论中嫡的概念.ID3总是选择具有最高信息增益（或最大嫡 压缩）的属性作为当前结点的测试属性.该属性使得对结果划分中的样本分类所 需的信息量最小，并反映划分的最小随机性或“不纯性”。1.2 问题重述1、目标概念为“寿险促销”2、计算每个属性的信息增益3、确定根节点的测试属性数据收入范IH险促倘任川片保险1性别W如一50K看古45-3O-4OK是古*404。T

4、OKt i宵方4230-40K是/外代5O-6OK14 蛆有382O-3OK否怨女553O-4OK足兄152O-3UK有势21I3O-4OK否否女5O-4OK是杏k41'4O-5OKH 心有43122T0K是哲女2950 - 60K是杏女4(1-50K杏古力55 2O-3OK是是女J9模型求解构造决策树的方法是采用自上而下的递归构造，其思路是： 以代表训练样本的单个结点开始建树（步骤 1）。 如果样本都在同一类，则该结点成为树叶，并用该类标记（步骤 2和3）。 否则，算法使用称为信息增益的机遇嫡的度量为启发信息，选择能最好地将 样本分类的属性（步骤6）.该属性成为该结点的“测试”或“判

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

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

7、有最高信息增益的属性 test_attribute ；(7)以 test_attribute 标记节点 N；(8) For each test_attribute 的已知值 v /戈U分 samples(9) 由节点N分出一个对应test_attribute=v的分支；(10) 令Sv为samples中test_attribute=v的样本集合；一个划分块(11) If Sv 为空 then(12) 加上一个叶节点，以samples中最普遍的类标记；(13) Else加入一个由 Decision_Tree(Sv ,attribute_list test_attribute) 返回节点值E (S

8、)= (915) log2 (915)-(615)log2 (615) =0.971Values (收入范围)=2030K, 3040k, 4050K,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(5060K) )= (22)log2 (22) (02) log2(02)=0所以E(S,收入范围)=(4/15) E (S(20-30K)

9、 + (5/15) E (S(3040K) +(4/15)E (S(40- 50K) +(2/15) E (S(50-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

10、, 保险)=(3/15) E (S(yeS )+ (12/15) E(S(no) ) =0.8Gain(S,保险)=0。9710。8=0.171E(S) = (-915)log2 (915) (615)log2 (615) =0。971 sex (性另U )=male, femaleE(S(male) = (37)log2 (37) (47) log2 (47)=0。9852 E(S (female)尸(一68)log2 (68)- (28) 10g2(28)=0。8113E (S, 性别)=(7/15) E (S (male) ) +(8/15) E (S(female) =0。8925 G

11、ain (S,性另U)=0。971-0.8925=0。0785E(S)= (-915)log2 (915)- (615) 10g2(615)=0。971age (年龄)=1540, 41 60E (S (1540) )= (-67) log2 (67) (17)log2(17) =0。5917 E(S(41 60) ) = (-38) log2 (38) (58) 10g2(58)=0。9544 E(S, 年龄)=(7/15) E(S(1540) ) +(8/15) E(S (41 60) ) =0.7851 Gain(S,年龄)=0.9710。7851=0.1859代码package Dec

12、isionTree;import java.util 。 ArrayList ;/* *决策树结点类 /public class TreeNode private String name ; 节点名(分裂属性的名称 )private ArrayList < String > rule; 结点的分裂规则ArrayListTreeNodechild; / 子结点集合private ArrayList ArrayList<String>> datas ; /划分到该结点的训练元组private ArrayList<String> candAttr ; 划分到

13、该结点的候选属性public TreeNode() =""； this.rule = new ArrayList String>(); this。child = new ArrayList<TreeNode > (); this.datas = null;this。candAttr = null ;public ArrayList TreeNode> getChild() return child;public void setChild(ArrayList TreeNode child)this.child = child ;p

14、ublic ArrayList String> getRule( ) return rule;public void setRule (ArrayList<String > rule) thiso rule = rule;public String getName()return name;public void setName(String name) = name;public ArrayList < ArrayList < String > > getDatas ()return datas;public void setDat

15、as (ArrayList ArrayList<String > > datas) thiso datas = datas;public ArrayList < String > getCandAttr () return candAttr;public void setCandAttr(ArrayList String> candAttr) thiso candAttr = candAttr ;package DecisionTree;import java。io。BufferedReader;import java.io.IOException ;imp

16、ort java。io。InputStreamReader;import java。 util.ArrayList ;import java.util 。 StringTokenizer;/* *决策树算法测试类* /public class TestDecisionTree /* * 读取候选属性* return候选属性集合* throws IOException/public ArrayList<String > readCandAttr() throws IOExceptionArrayList<String > candAttr = new ArrayList

17、String > ();BufferedReader reader = new BufferedReader(new InputStreamReader(System。in);String str =while (! (str = reader o readLine()。equals。' ")StringTokenizer tokenizer = new StringTokenizer(str);while (tokenizer。hasMoreTokens () ) candAttr.add (tokenizer。 nextToken();return candAttr

18、;/*读取训练元组return训练元组集合 throws lOException*/public ArrayList<ArrayList<String > >readData()throws lOException ArrayList<ArrayList<String > > datas = new ArrayList ArrayList<String>>(); BufferedReader reader = new BufferedReader (new InputStreamReader(System。in); String

19、 str =""while (! (str = reader.readLine() ) .equals。' ) ) StringTokenizer tokenizer = new StringTokenizer(str);ArrayList String> s = new ArrayList<String > (); while (tokenizer。hasMoreTokens () s。add(tokenizer。nextToken ()； ) datas.add(s);return datas;/* *递归打印树结构* param root当前

20、待输出信息的结点*/public void printTree ( TreeNode root) Systemo out.println( " name:" + root.ge(l)a me ArrayList <String > rules = root。getRule();Systemo out。print ("node rules: ");for (int i = 0; i < rules.size( ) ; i+) Systemo out.print (rules。get(i)+ "");Systemo ou

21、t。print ("");Systemo out.println ("");ArrayList<TreeNode> children = root 。getChild ();int size =children。size();if (size = 0)Systemo out。println( ” 今-leaf node!<-"); else Systemo out.println("size of children: s-izehQdre)nfor (int i = 0 ; i < children。 size

22、(); i+ )Systemo out.print (" child " + (i + 1) + " of node 。 getNam+(i)oot+ ");printTree (children o get(i);/*主函数，程序入口* param args*/public static void main (String口 args)TestDecisionTree tdt = new TestDecisionTree );ArrayList<String> candAttr = null ;ArrayList ArrayList<

23、String>> datas = null;try System.out.println("请输入候选属性”)；candAttr = tdt。 readCandAttr();System.out.println ("请输入训练数据")； datas = tdt.readData (); catch (IOException e) e。printStackTrace();DecisionTree tree = new DecisionTree ();TreeNode root = tree.buildTree(datas , candAttr); tdt

24、o printTree (root); package DecisionTree;import java.util.ArrayList ;import java。 util.HashMap;import java.util 。 Iterator;import java.util.Map;/*选择最佳分裂属性* /public class Gain private ArrayList ArrayList<String > > D = null;训练元组private ArrayList String > attrList = null; / 候选属性集public Gai

25、n(ArrayList ArrayList<String > > datas, ArrayList StringattrList) this.D = datas;this。attrList = attrList ;/*女* 获取最佳侯选属性列上的值域(假定所有属性列上的值都是有限的名词或分类类型 的)* param attrIndex指定的属性列的索引* return值域集合* /public ArrayList<String > getValues (ArrayList < ArrayList < String > > datas, in

26、t attrIndex)ArrayList Stringvalues = new ArrayList<String>( );String r ="for (int i = 0; i < datas.size( ) ;i+) r = datas。get (i) 。 get(attrlndex);if (lvalues。 contains (r) )values。add (r)；)return values;)/* *获取指定数据集中指定属性列索引的域值及其计数* param d指定的数据集* param attrIndex 指定的属性列索引* return类别及其计数

27、的 map* /public Map < String, lnteger> valueCounts(ArrayList ArrayList<String > > datas, int attrIndex)Map <String , lnteger> valueCount = new HashMap <String, Integer > );String c =；ArrayList < String > tuple = null ;for (int i = 0 ; i datas.size() ;i+) tuple = datas

28、.get(i);c = tuple。 get (attrIndex);if (valueCount 。 containsKey(c) )valueCount.put(c, valueCount。 get(c) + 1); else valueCounto put ( c, 1);return valueCount;)/* * 求对datas中元组分类所需的期望信息，即 datas的嫡* param datas训练元组* return datas 的嫡值* /public double infoD (ArrayList <ArrayList Stringdatas) double info

29、 = 0.000;int total = datas。 size();Map <String , Integer> classes = valueCounts (datas, attrList.size();Iterator iter = classes.entrySet ) ).iterator )；Integer counts = new Integer classes size ();for(int i = 0; iter 。 hasNext (); i+ )Map.Entry entry =( Map.Entry) iter.next();Integer val = (In

30、teger) entry.getValue();countsi = val;)for (int i = 0; i countso length ; i+) double base = DecimalCalculate.div (counts i, total, 3);info +=(-1) * base * Math。log(base);return info ;/* 获取指定属性列上指定值域的所有元组* param attrIndex指定属性列索引* param value指定属性列的值域* return指定属性列上指定值域的所有元组*/public ArrayList<ArrayLi

31、st < String > > datasOfValue(int attrIndex , String value) ArrayList<ArrayList<String > > Di = new ArrayList<ArrayList<String > > (); ArrayList < String > t = null;for (int i = 0; i D.size() ; i+) t = D。get ;if (to get(attrIndex)。 equals (value) Di。 add (t);)re

32、turn Di;/* * 基于按指定属性划分对D的元组分类所需要的期望信息* param attrIndex 指定属性的索引* ©return按指定属性划分的期望信息值* /public double infoAttr (int attrIndex) double info = 0.000 ;ArrayList <String > values = getValues (D, attrIndex);for (int i = 0; i < values 。 size () ;i+)ArrayList<ArrayList<String> > dv

33、 = datasOfValue (attrIndex, values.get(i); info += DecimalCalculate.mul(DecimalCalculate 。 div (dv。size ), D。size () 3) , infoD (dv);return info;/* * 获取最佳分裂属性的索引* return最佳分裂属性的索引/public int bestGainAttrIndex () int index = 1;double gain = 0。000;double tempGain = 0.000 ;for (int i = 0; i attrList.siz

34、e (); i+)tempGain = infoD (D) infoAttr(i); if t tempGain > gain) gain = tempGain ;index = i;return index;package DecisionTree;import java.util 。 ArrayList;import java。 util.HashMap;import java。 util.Iterator ;import java.util.Map;import javax 。 smartcardio 。 */*决策树构造类/public class DecisionTree 2表

35、不private Integer attrSelMode;最佳分裂属性选择模式，1表示以信息增益度量,以信息增益率度量。暂未实现2public DecisionTree () this。attrSelMode = 1;public DecisionTree (int attrSelMode) this。attrSelMode = attrSelMode ;public void setAttrSelMode (Integer attrSelMode) this。attrSelMode = attrSelMode;/* *获取指定数据集中的类别及其计数 param datas指定的数据集*/pu

36、blic Map<String , Map<String , String c = "return类别及其计数的 mapInteger> classOfDatas(ArrayList ArrayList<String>> datasInteger> classes = new HashMap<String , Integer>();ArrayList<String > tuple = null;for (int i = 0 ; i < datas.size () ; i+) tuple = datas。get(i

37、);c = tuple.get (tuple。 size () 1);if (classes。 containsKey(c) ) classes, put (c, classes.get(c) + 1); else classes.put (c,1);return classes;/* *获取具有最大计数的类名，即求多数类 param classes 类的键值集合return多数类的类名/public String maxClass(Map<String ) Integer> classes) String maxC =" int max = -1 ;Iterator i

38、ter = classes.entrySet () .iterator ()； for (int i = 0; iter。hasNext () ; i+) Map.Entry entry = (Map.Entry ) iter。next();String key = (String)entry 。 getKey ();Integer val =(Integer) entry.getValue ();if (val > max) max = val;maxC = key;)return maxC;/*构造决策树 param datas训练元组集合 param attrList候选属性集合r

39、eturn决策树根结点*/public TreeNode buildTree(ArrayList<ArrayList<String > > datas, ArrayList<String > attrList) /System.outo print ("候选属性列表： ");/for (int i = 0; i < attrList 。 size (); i+ )/Systemo out.print(" " + tattigst (i) +”");/System.out.println ();TreeN

40、ode node = new TreeNode();node.setDatas (datas);node.setCandAttr (attrList);Map<String , Integer> classes = classOfDatas(datas);String maxC = maxClass(classes);if (classes.size() = 1 | | attrList。 size() = 0) node。setName (maxC);return node;Gain gain = new Gain(datas, attrList);int bestAttrInd

41、ex = gain.bestGainAttrIndex ();ArrayList<String > rules = gain.getValues (datas, bestAttrIndex);node。setRule(rules);node.setName(attrList。 get (bestAttrIndex);if(rules.size ()2) /?此处有待商榷attrList。 remove(bestAttrIndex );for (int i = 0 ; i < rules。 size () ;i+) String rule = rules.get(i );Arr

42、ayList ArrayList<String > > di = gain.datasOfValue ( bestAttrIndex, rule); for (int j = 0; j < di.size () ; j+) di.get(j) .remove(bestAttrIndex );if ( di。size ) = 0) TreeNode leafNode = new TreeNode ();leafNode。setName (maxC);leafNode.setDatas(di);leafNode.setCandAttr ( attrList); node。g

43、etChild ()。add(leafNode); else TreeNode newNode = buildTree (di, attrList); node。getChild () .add (newNode);) return node;)package DecisionTree;import java.math。 BigDecimal;public class DecimalCalculate /*女*由于Java的简单类型不能够精确的对浮点数进行运算，这个工具类提供精*确的浮点数运算，包括加减乘除和四舍五入。*/默认除法运算精度private static final int DEF

44、_DIV_SCALE = 10;这个类不能实例化private DecimalCalculate () )/* * 提供精确的加法运算。* param v1被加数* param v2 加数* return两个参数的和* /public static double add(double v1 , double v2) BigDecimal bl = new BigDecimal( Double。 toString(v1 );BigDecimal b2 = new BigDecimal( Double。 toString(v2);return b1。add(b2) .doubleValue();/

45、* * 提供精确的减法运算。* param v1被减数* param v2 减数* return两个参数的差* /public static double sub(double v1 , double v2) BigDecimal b1 = new BigDecimal ( Double.toString(v1 );BigDecimal b2 = new BigDecimal ( Double.toString(v2);/*return b1。 subtract(b2)。 doubleValue();提供精确的乘法运算。 param v1被乘数* param v2 乘数* return两个参数

46、的积* /public static double mul (double v1 , double v2) BigDecimal b1 = new BigDecimal(Double。toString (v1);BigDecimal b2 = new BigDecimal( Double.toString(v2 );return b1。multiply ( b2).doubleValue ();/* * 提供(相对)精确的除法运算，当发生除不尽的情况时，精确到* 小数点以后10位，以后的数字四舍五入.* param v1被除数* param v2 除数* return两个参数的商* /publ

47、ic static double div (double v1, double v2 ) return div (v1,v2,DEF_DIV_SCALE);/* *提供(相对)精确的除法运算。当发生除不尽的情况时，由scale参数指* 定精度，以后的数字四舍五入。* param v1被除数* param v2 除数* param scale表示表示需要精确到小数点以后几位* return两个参数的商* /public static double div(double v1 , double v2,int scale) if (scale<0) throw new IllegalArgum

48、entException (“The scale must be a positive integer or zero"BigDecimal b1 = new BigDecimal ( Double。 toString(v1);BigDecimal b2 = new BigDecimal(Double 。 toString(v2);return b1。divide(b2,scale,BigDecimal.ROUND_HALF_UP ) .doubleValue();/* * 提供精确的小数位四舍五入处理.* param v需要四舍五入的数字* param scale小数点后保留几位*

49、 return四舍五入后的结果*/public static double round(double v , int scale) if(scale<0) throw new IllegalArgumentException (“The scale must be a positive integer or zero"BigDecimal b = new BigDecimal (Double o toString(v );BigDecimal one = new BigDecimal( ; " 1")return b.divide (one,scale, B

50、igDecimal。ROUND_HALF_UP).doubleValue(); /* * 提供精确的类型转换(Float)* param v需要被转换的数字* return返回转换结果* /public static float convertsToFloat(double v ) BigDecimal b = new BigDecimal(v);return b。floatValue ();/* *提供精确的类型转换(Int)不进行四舍五入* param v需要被转换的数字* return返回转换结果*/public static int convertsToInt(double v ) B

51、igDecimal b = new BigDecimal (v);return Value();/* * 提供精确的类型转换(Long)* param v需要被转换的数字* return返回转换结果*/public static long convertsToLong(double v ) BigDecimal b = new BigDecimal (v);return b.longValue();/* *返回两个数中大的一个值* param v1需要被对比的第一个数* param v2需要被对比的第二个数* return返回两个数中大的一个值* /public static dou

52、ble returnMax(double v1,double v2 ) BigDecimal b1 = new BigDecimal(v1);BigDecimal b2 = new BigDecimal(v2 );return b1.max(b2)。doubleValue ();/* * 返回两个数中小的一个值* param v1需要被对比的第一个数* param v2需要被对比的第二个数* return返回两个数中小的一个值* /public static double returnMin ( double v1 , double v2) BigDecimal b1 = new BigDecimal(v1 );BigDecimal b2 = new