决策树java代码.doc

import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.LinkedHashSet;class TreeNode String element; / 该值为数据的属性名称 String value; / 上一个分裂属性在此结点的值 LinkedHashSet childs; / 结点的子结点，以有顺序的链式哈希集存储 public TreeNode() this.element=null; this.value=null; this.childs=null; public TreeNode(String value) this.element=null; this.value=value; this.childs=null; public String getElement() return this.element; public void setElement(String e) this.element=e; public String getValue() return this.value; public void setValue(String v) this.value=v; public LinkedHashSet getChilds() return this.childs; public void setChilds(LinkedHashSet childs) this.childs=childs; / 决策树类class DecisionTree TreeNode root; / 决策树的树根结点 public DecisionTree() root=new TreeNode(); public DecisionTree(TreeNode root) this.root=root; public TreeNode getRoot() return root; public void setRoot(TreeNode root) this.root=root; public String selectAtrribute(TreeNode node, String deData, boolean flags, LinkedHashSet atrributes, HashMap attrIndexMap) / Gain数组存放当前结点未分类属性的Gain值 double Gain=new doubleatrributes.size(); / 每条数据中归类的下标，为每条数据的最后一个值 int class_index=deData0.length - 1; / 属性名，该结点在该属性上进行分类 String return_atrribute=null; / 计算每个未分类属性的 Gain值 int count=0; / 计算到第几个属性 for(String atrribute : atrributes) / 该属性有多少个值，该属性有多少个分类 int values_count, class_count; / 属性值对应的下标 int index=attrIndexMap.get(atrribute); / 存放属性的各个值和分类值 LinkedHashSet values=new LinkedHashSet(); LinkedHashSet classes=new LinkedHashSet(); for(int i=0; i deData.length; i+) if(flagsi = true) values.add(deDataiindex); classes.add(deDataiclass_index); values_count=values.size(); class_count=classes.size(); int values_vector=new intvalues_count * class_count; int class_vector=new intclass_count; for(int i=0; i deData.length; i+) if(flagsi = true) int j=0; for(String v : values) if(deDataiindex.equals(v) break; else j+; int k=0; for(String c : classes) if(deDataiclass_index.equals(c) break; else k+; values_vectorj * class_count + k+; class_vectork+; double InfoD=0.0; double class_total=0.0; for(int i=0; i class_vector.length; i+) class_total+=class_vectori; for(int i=0; i class_vector.length; i+) if(class_vectori = 0) continue; else double d=Math.log(class_vectori / class_total) / Math.log(2.0) * class_vectori / class_total; InfoD=InfoD - d; / 计算InfoA double InfoA=0.0; for(int i=0; i values_count; i+) double middle=0.0; double attr_count=0.0; for(int j=0; j class_count; j+) attr_count+=values_vectori * class_count + j; for(int j=0; j max) max=Gaini; return_atrribute=atrribute; i+; return return_atrribute; public void buildDecisionTree(TreeNode node, String deData, boolean flags, LinkedHashSet attributes, HashMap attrIndexMap) / 如果待分类属性已空 if(attributes.isEmpty() = true) / 从数据集中选择多数类，遍历符合条件的所有数据 HashMap classMap=new HashMap(); int classIndex=deData0.length - 1; for(int i=0; i deData.length; i+) if(flagsi = true) if(classMap.containsKey(deDataiclassIndex) int count=classMap.get(deDataiclassIndex); classMap.put(deDataiclassIndex, count + 1); else classMap.put(deDataiclassIndex, 1); / 选择多数类 String mostClass=null; int mostCount=0; Iterator it=classMap.keySet().iterator(); while(it.hasNext() String strClass=(String) it.next(); if(classMap.get(strClass) mostCount) mostClass=strClass; mostCount=classMap.get(strClass); / 对结点进行赋值，该结点为叶结点 node.setElement(mostClass); node.setChilds(null); System.out.println(yezhi: + node.getElement() + : + node.getValue(); return; / 如果待分类数据全都属于一个类 int class_index=deData0.length - 1; String class_name=null; HashSet classSet=new HashSet(); for(int i=0; i deData.length; i+) if(flagsi = true) class_name=deDataiclass_index; classSet.add(class_name); / 则该结点为叶结点，设置有关值，然后返回 if(classSet.size() = 1) node.setElement(class_name); node.setChilds(null); System.out.println(leaf: + node.getElement() + : + node.getValue(); return; / 给定的分枝没有元组，是不是有这种情况？ / 选择一个分类属性 String attribute=selectAtrribute(node, deData, flags, attributes, attrIndexMap); / 设置分裂结点的值 node.setElement(attribute); / System.out.println(attribute); if(node = root) System.out.println(root: + node.getElement() + : + node.getValue(); else System.out.println(branch: + node.getElement() + : + node.getValue(); / 生成和设置各个子结点 int attrIndex=attrIndexMap.get(attribute); LinkedHashSet attrValues=new LinkedHashSet(); for(int i=0; i deData.length; i+) if(flagsi = true) attrValues.add(deDataiattrIndex); LinkedHashSet childs=new LinkedHashSet(); for(String attrValue : attrValues) TreeNode tn=new TreeNode(attrValue); childs.add(tn); node.setChilds(childs); / 在候选分类属性中删除当前属性 attributes.remove(attribute); / 在各个子结点上递归调用本函数 if(childs.isEmpty() != true) for(TreeNode child : childs) / 设置子结点待分类的数据集 boolean newFlags=new booleandeData.length; for(int i=0; i deData.length; i+) newFlagsi=flagsi; if(deDataiattrIndex != child.getValue() newFlagsi=false; / 设置子结点待分类的属性集 LinkedHashSet newAttributes=new LinkedHashSet(); for(String attr : attributes) newAttributes.add(attr); / 在子结点上递归生成决策树 buildDecisionTree(child, deData, newFlags, newAttributes, attrIndexMap); / 输出决策树 public void printDecisionTree() public class Data2 public static void main(String args) /* * /输入数据集1 String deData = new String12; deData0 = new * StringYes,No,No,Yes,Some,high,No,Yes,French,010,Yes; deData1 = * new StringYes,No,No,Yes,Full,low,No,No,Thai,3060,No; deData2 = * new StringNo,Yes,No,No,Some,low,No,No,Burger,010,Yes; deData3 * = new StringYes,No,Yes,Yes,Full,low,Yes,No,Thai,1030,Yes; * deData4 = new * StringYes,No,Yes,No,Full,high,No,Yes,French,60,No; deData5 = * new StringNo,Yes,No,Yes,Some,middle,Yes,Yes,Italian,010,Yes; * deData6 = new * StringNo,Yes,No,No,None,low,Yes,No,Burger,010,No; deData7 = * new StringNo,No,No,Yes,Some,middle,Yes,Yes,Thai,010,Yes; * deData8 = new * StringNo,Yes,Yes,No,Full,low,Yes,No,Burger,60,No; deData9 = * new StringYes,Yes,Yes,Yes,Full,high,No,Yes,Italian,1030,No; * deData10= new StringNo,No,No,No,None,low,No,No,Thai,010,No; * deData11= new * StringYes,Yes,Yes,Yes,Full,low,No,No,Burger,3060,Yes; /待分类的属性集1 * String attr = new Stringalt, bar, fri, hun, pat, price, rain, res, * type, est; */ 输入数据集2 String deData=new String14; deData0=new String youth, high, no, fair, no ; deData1=new String youth, high, no, excellent, no ; deData2=new String middle_aged, high, no, fair, yes ; deData3=new String senior, medium, no, fair, yes ; deData4=new String senior, low, yes, fair, yes ; deData5=new String senior, low, yes, excellent, no ; deData6=new String middle_aged, low, yes, excellent, yes ; deData7=new String youth, medium, no, fair, no ; deData8=new String youth, low, yes, fair, yes ; deData9=new String senior, medium, yes, fair, yes ; deData10=new String youth, medium, yes, excellent