决策树程序实验

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

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

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

4、入龙1也你4O-5OK453O-4OKJi如4042'30-40K是是4350-60K起3X2O-3OK打553O-4OK是是35207)K273CI-MJKk4313O-4OK是否414O-5OK是曲20-?0K是女29和一咏女3940-5QKft为552O-3OK是疋女19模型求解构造决策树的方法是采用自上而下的递归构造，其思路是: 以代表训练样本的单个结点开始建树（步骤 1 ）。 如果样本都在同一类，则该结点成为树叶，并用该类标记（步骤 2和3 ）。 否则，算法使用称为信息增益的机遇熵的度量为启发信息，选择能最好地将样本分类的属性（步骤6）。该属性成为该结点的“测试”或“判定”属

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

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

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

8、(S)=(-915)log2(915)-(615)log2(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

9、(30-40K) +(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.971In sura nce(保险)=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

10、) =0.8Gain(S,保险)=0.971-0.8=0.171E(S)=(-915)log2(915)-(615)log2(615)=0.971sex(性另廿)=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

11、(615)=0.971age(年龄)=1540,41 60E(S(1540)= (-67)log2 (67)- (17)log2(17)=0.5917E(S(41 60)= (-38)log2 (38)- (58)log2(58)=0.9544E(S,年龄)=(7/15) E(S(1540) +(8/15) E(S(41 60) =0.7851Gain(S,年龄)=0.971-0.7851=0.1859代码package Decisi on Tree;/*决策树结点类*/ public class TreeNode private Stri ng name; / 节点名(分裂属性的名称)pri

12、vate ArrayList<Stri ng> rule; /结点的分裂规则ArrayList<TreeNode> child; /子结点集合private ArrayList<ArrayList<Stri ng>> datas; /划分到该结点的训练元组private ArrayList<Stri ng> can dAttr; /划分到该结点的候选属性public TreeNode() this. name =""this.rule = new ArrayList<Stri ng>();this.ch

13、ild = new ArrayList<TreeNode>(); this.datas = n ull;this.ca ndAttr = nu II;public ArrayList<TreeNode> getChild() return child;public void setChild(ArrayList<TreeNode> child) this.child = child;public ArrayList<Stri ng> getRule() return rule;public void setRule(ArrayList<St

14、ri ng> rule) this.rule = rule;public String getName() return n ame;public void setName(Stri ng n ame) this. name = n ame;public ArrayList<ArrayList<Stri ng>> getDatas() return datas;public void setDatas(ArrayList<ArrayList<Stri ng>> datas) this.datas = datas;public ArrayLi

15、st<Stri ng> getCa ndAttr() retur n can dAttr;public void setCa ndAttr(ArrayList<Stri ng> can dAttr) this.ca ndAttr = can dAttr; package Decisi on Tree;import java.i o.l OExcepti on;import java.i o.ln putStreamReader;*决策树算法测试类*/ public class TestDecisi on Tree /*读取候选属性* return候选属性集合* thro

16、ws IOExceptio n*/public ArrayList<Stri ng> readCa ndAttr() throws IOExcepti onArrayList<Stri ng> can dAttr = new ArrayList<Stri ng>();BufferedReader reader = new BufferedReader( newIn putStreamReader(System.i n);Stri ng str =""while (!(str = reader.readL in e().equals(&qu

17、ot;") Strin gToke ni zer toke ni zer = new Stri ngToke nizer(str);while (toke nizer.hasMoreToke ns() can dAttr.add(toke nizer. nextToke n();retur n can dAttr;*读取训练元组* return训练元组集合* throws lOExceptio n*/public ArrayList<ArrayList<Stri ng>> readData() throws IOExcepti on ArrayList<

18、ArrayList<Stri ng>> datas = new ArrayList<ArrayList<Stri ng>>();BufferedReader reader = new BufferedReader( newIn putStreamReader(System.i n);Stri ng str =""while (!(str = reader.readL in e().equals("") Strin gToke ni zer toke ni zer = new Strin gToke ni zer(

19、str);ArrayList<Stri ng> s = new ArrayList<Stri ng>();while (toke nizer.hasMoreToke ns() s.add(toke nizer. nextToke n();datas.add(s);retur n datas;*递归打印树结构* param root 当前待输出信息的结点*/public void prin tTree(TreeNode root)(” name:" + root.getName();ArrayList<Stri ng> rules = root.ge

20、tRule();(” node rules: ");for (i nt i = 0; i < rules.size(); i+) + "");ArrayList<TreeNode> childre n = root.getChild(); int size =childre n. size();if (size = 0) else + childre n. size();for (int i = 0; i < childre n. size(); i+) + (i + 1) + " of node " + root.ge

21、tName() +":");prin tTree(childre n.get(i);/*主函数，程序入口* param args*/public static void main( Stri ng args) TestDecisi on Tree tdt = new TestDecisi on Tree();ArrayList<Stri ng> can dAttr = n ull; ArrayList<ArrayList<Stri ng>> datas = n ull;try (”请输入候选属性");can dAttr = td

22、t.readCa ndAttr();(”请输入训练数据");datas = tdt.readData(); catch (IOExcepti on e) e.pri ntStackTrace();Decisio nTree tree = new Decisi on Tree();TreeNode root = tree.buildTree(datas, can dAttr); tdt.pri ntTree(root); package Decisi on Tree;*选择最佳分裂属性*/ public class Gai n 训练元组候选属性集private ArrayList<

23、;ArrayList<Stri ng>> D = n ull; /private ArrayList<Stri ng> attrList = n ull; /public Gain( ArrayList<ArrayList<Stri ng>> datas, ArrayList<Stri ng> attrList) this.D = datas;this.attrList = attrList;*获取最佳侯选属性列上的值域（假定所有属性列上的值都是有限的名词或分类类型 的）* param attrl ndex指定的属性列的索引*

24、return值域集合*/public ArrayList<Stri ng> getValues(ArrayList<ArrayList<Stri ng>> datas, int attrl ndex)ArrayList<Stri ng> values = new ArrayList<Stri ng>();Stri ng r =""for (i nt i = 0; i < datas.size(); i+) r = datas.get(i).get(attrI ndex);if (!values.c ontai

25、n s(r) values.add(r);retur n values;*获取指定数据集中指定属性列索引的域值及其计数* param d 指定的数据集* param attrl ndex 指定的属性列索引* return 类别及其计数的 map*/public Map<Stri ng. In teger> valueCo un ts(ArrayList<ArrayList<Stri ng>> datas, int attrI ndex)Map<Stri ng. In teger> valueCo unt = new HashMap<Stri

26、 ng. In teger>();Stri ng c =""ArrayList<Stri ng> tuple = n ull;for (i nt i = 0; i < datas.size(); i+) tuple = datas.get(i);c = tuple.get(attrI ndex);if (valueCo un t.c ontain sKey(c) valueCo un t.put(c, valueCo un t.get(c) + 1); else valueCo un t.put(c, 1);retur n valueCo unt;*

27、求对datas中元组分类所需的期望信息，即datas的熵* param datas训练元组* return datas 的熵值*/public double in foD(ArrayList<ArrayList<Stri ng>> datas)double info = 0.000;int total = datas.size();Map<Stri ng. In teger> classes = valueCo un ts(datas, attrList.size();Iterator iter = classes.e ntrySet().iterator(

28、);In teger counts = new In tegerclasses.size();for(i nt i = 0; iter.hasNext(); i+)Map.E ntry en try = (Map.E ntry) iter. next();In teger val = (In teger) en try.getValue();coun tsi = val;for (int i = 0; i < counts.len gth; i+) double base = DecimalCalculate.div(co un tsi, total, 3);info += (-1) *

29、 base * Math.log(base);return info;/*获取指定属性列上指定值域的所有元组* param attrl ndex指定属性列索引* param value 指定属性列的值域* return 指定属性列上指定值域的所有元组*/public ArrayList<ArrayList<Stri ng>> datasOfValue(i nt attrl ndex. String value)ArrayList<ArrayList<Stri ng>> Di = new ArrayList<ArrayList<Stri

30、 ng>>(); ArrayList<Stri ng> t = n ull;for (i nt i = 0; i < D.size(); i+) t = D.get(i);if(t.get(attrI ndex).equals(value)Di.add(t);return Di;/*基于按指定属性划分对D的元组分类所需要的期望信息* param attrl ndex指定属性的索引* return按指定属性划分的期望信息值*/public double in foAttr(i nt attrl ndex)double info = 0.000;ArrayList&l

31、t;Stri ng> values = getValues(D, attrI ndex);for (i nt i = 0; i < values.size(); i+) ArrayList<ArrayList<Stri ng>> dv = datasOfValue(attrl ndex, values.get(i);info += DecimalCalculate.mul(DecimalCalculate.div(dv.size(), D.size(),3), i nfoD(dv);return info;*获取最佳分裂属性的索引* return最佳分裂属性

32、的索引*/public int bestGai nAttrl ndex()int in dex = -1;double gain = 0.000;double tempGai n = 0.000;for (i nt i = 0; i < attrList.size(); i+) tempGa in = in foD(D) - in foAttr(i); if (tempGa in > gain) gai n = tempGa in;in dex = i;retur n in dex; package Decisi on Tree;/*决策树构造类*/public class Dec

33、isi on Tree private Integer attrSelMode;/最佳分裂属性选择模式，1表示以信息增益度量，2表示以信息增益率度量。暂未实现2public Decisi on Tree()this.attrSelMode = 1;public Decisio nTree( int attrSelMode) this.attrSelMode = attrSelMode;public void setAttrSelMode(l nteger attrSelMode) this.attrSelMode = attrSelMode;*获取指定数据集中的类别及其计数* param da

34、tas 指定的数据集* return类别及其计数的 map*/public Map<Stri ng. In teger> classOfDatas(ArrayList<ArrayList<Stri ng>> datas)Map<Stri ng. In teger> classes = new HashMap<Stri ng. In teger>();Stri ng c =""ArrayList<Stri ng> tuple = n ull;for (i nt i = 0; i < datas.si

35、ze(); i+) tuple = datas.get(i);c = tuple.get(tuple.size() - 1);if (classes.c ontain sKey(c) classes.put(c, classes.get(c) + 1); else classes.put(c, 1);retur n classes;*获取具有最大计数的类名，即求多数类* param classes类的键值集合* return多数类的类名*/public String maxClass(Map<Stri ng, In teger> classes)Stri ng maxC =&quo

36、t;"int max = -1;Iterator iter = classes.e ntrySet().iterator();for(i nt i = 0; iter.hasNext(); i+)Map.E ntry entry = (Map.E ntry) iter. next();Stri ng key = (Stri ng)e ntry.getKey();In teger val = (In teger) en try.getValue(); if(val > max)max = val;maxC = key;return maxC;*构造决策树* param datas

37、训练元组集合* param attrList候选属性集合* return决策树根结点*/public TreeNode buildTree(ArrayList<ArrayList<Stri ng>> datas,ArrayList<Stri ng> attrList)候选属性列表：”)；/for (i nt i = 0; i < attrList.size(); i+) + attrList.get(i) + "");/ TreeNode node = new TreeNode();no de.setDatas(datas);n o

38、de.setCa ndAttr(attrList);Map<Stri ng. In teger> classes = classOfDatas(datas);String maxC = maxClass(classes);if (classes.size() = 1 | attrList.size() = 0) no de.setName(maxC);retur n no de;Gain gain = new Gain( datas, attrList);int bestAttrI ndex = gai n.bestGai nAttrl ndex();ArrayList<St

39、ri ng> rules = gain. getValues(datas, bestAttrI ndex);no de.setRule(rules);no de.setName(attrList.get(bestAttrI ndex);if(rules.size() > 2) /?此处有待商榷attrList.remove(bestAttrI ndex);for (i nt i = 0; i < rules.size(); i+) String rule = rules.get(i);ArrayList<ArrayList<Stri ng>> di =

40、 gain. datasOfValue(bestAttrl ndex, rule);for (int j = 0; j < di.size(); j+) di.get(j).remove(bestAttrI ndex);if (di.size() = 0) TreeNode leafNode = new TreeNode();leafNode.setName(maxC);leafNode.setDatas(di);leafNode.setCa ndAttr(attrList);n ode.getChild().add(leafNode); else TreeNode n ewNode =

41、 buildTree(di, attrList);n ode.getChild().add( newNode);retur n node;package Decisi on Tree;public class DecimalCalculate /*由于Java的简单类型不能够精确的对浮点数进行运算，这个工具类提供精*确的浮点数运算，包括加减乘除和四舍五入。*/默认除法运算精度private static final int DEF_DIV_SCALE = 10;/这个类不能实例化private DecimalCalculate()/*提供精确的加法运算。* param v1被加数* param

42、 v2加数* return两个参数的和*/public static double add(double v1,double v2)/*BigDecimal b2 = new BigDecimal(Double.toStri ng(v2); return b1.add(b2).doubleValue();提供精确的减法运算。* param v1被减数* param v2减数* retur n两个参数的差*/public static double sub(double v1,double v2)BigDecimal b1 = new BigDecimal(Double.toStri ng(v1

43、);/*BigDecimal b2 = new BigDecimal(Double.toStri ng(v2); return b1.subtract(b2).doubleValue();提供精确的乘法运算。* param v1被乘数* param v2乘数* retur n两个参数的积*/public static double mul(double v1,double v2)BigDecimal b2 = new BigDecimal(Double.toStri ng(v2);return b1.multiply(b2).doubleValue();*提供(相对)精确的除法运算，当发生除不

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

45、e v1,double v2,i nt scale) if(scale<0)throw new lllegalArgume ntExceptio n("The scale must be a positive in teger or zero"); BigDecimal b1 = new BigDecimal(Double.toStri ng(v1);BigDecimal b2 = new BigDecimal(Double.toStri ng(v2); returnb1.divide(b2,scale,BigDecimal.ROUND_HALF_UP).double

46、Value();*提供精确的小数位四舍五入处理。* param v需要四舍五入的数字* param scale小数点后保留几位* retur n四舍五入后的结果*/public static double roun d(double v,i nt scale)if(scale<0)throw new IllegalArgume ntExceptio n("The scale must be a positive in teger or zero"); BigDecimal b = new BigDecimal(Double.toStri ng(v);returnb.d

47、ivide(o ne,scale,BigDecimal.ROUND_HALF_UP).doubleValue();*提供精确的类型转换(Float)* param v需要被转换的数字* retur n 返回转换结果*/public static float con vertsToFloat(double v)BigDecimal b = new BigDecimal(v);retur n b.floatValue();*提供精确的类型转换(Int)不进行四舍五入* param v需要被转换的数字* retur n返回转换结果*/public static int con vertsTo In

48、t(double v)BigDecimal b = new BigDecimal(v);return b.i ntValue();/*提供精确的类型转换(Long)* param v需要被转换的数字* retur n返回转换结果*/ public static long con vertsToL on g(double v)BigDecimal b = new BigDecimal(v);retur n b.lon gValue();/*返回两个数中大的一个值* param v1需要被对比的第一个数* param v2需要被对比的第二个数* retur n返回两个数中大的一个值*/public

49、 static double retur nM ax(double v1,double v2)BigDecimal b1 = new BigDecimal(v1);BigDecimal b2 = new BigDecimal(v2);return b1.max(b2).doubleValue();*返回两个数中小的一个值* param v1需要被对比的第一个数* param v2需要被对比的第二个数* retur n 返回两个数中小的一个值*/ public static double retur nMin( double v1,double v2)BigDecimal b1 = new BigDecimal(v1);BigDecimal b2 = new BigDecimal(v2);return b1.mi n(b2).doubleValue();/*精确对比两个数字