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