上傳人：鼠***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：沃**（實名認(rèn)證）

IP屬地：上海

IP屬地：上海 上傳時間：2022-02-25 格式：DOCX 頁數(shù)：19 大小：119.86KB 積分：20 舉報 版權(quán)申訴

1、決策樹程序?qū)嶒灡娝苤瑪?shù)據(jù)庫技術(shù)從20世紀(jì)80年代開始，已經(jīng)得到廣泛的普及和應(yīng)用。隨著數(shù)據(jù)庫容量的膨脹，特別是數(shù)據(jù)倉庫以及web等新型數(shù)據(jù)源的日益普及，人們面臨的主要問題不再是缺乏足夠的信息可以使用，而是面對浩瀚的數(shù)據(jù)海洋如何有效地利用這些數(shù)據(jù)。從數(shù)據(jù)中生成分類器的一個特別有效的方法是生成一個決策樹（Decision Tree）。決策樹表示方法是應(yīng)用最廣泛的邏輯方法之一，它從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則。決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進行屬性值的比較并根據(jù)不同的屬性值判斷從該結(jié)點向下的分支，在決策樹的葉結(jié)點得到結(jié)論。所以從決策樹的根到葉結(jié)

2、點的一條路徑就對應(yīng)著一條合取規(guī)則，整棵決策樹就對應(yīng)著一組析取表達式規(guī)則。決策樹是應(yīng)用非常廣泛的分類方法，目前有多種決策樹方法，如ID3、CN2、SLIQ、SPRINT等。一、問題描述1.1相關(guān)信息決策樹是一個類似于流程圖的樹結(jié)構(gòu)，其中每個內(nèi)部結(jié)點表示在一個屬性上的測試，每個分支代表一個測試輸入，而每個樹葉結(jié)點代表類或類分布。數(shù)的最頂層結(jié)點是根結(jié)點。一棵典型的決策樹如圖1所示。它表示概念buys_computer，它預(yù)測顧客是否可能購買計算機。內(nèi)部結(jié)點用矩形表示，而樹葉結(jié)點用橢圓表示。為了對未知的樣本分類，樣本的屬性值在決策樹上測試。決策樹從根到葉結(jié)點的一條路徑就對應(yīng)著一條合取規(guī)則，因此決策樹容

3、易轉(zhuǎn)化成分類規(guī)則。圖1ID3算法：決策樹中每一個非葉結(jié)點對應(yīng)著一個非類別屬性，樹枝代表這個屬性的值。一個葉結(jié)點代表從樹根到葉結(jié)點之間的路徑對應(yīng)的記錄所屬的類別屬性值。每一個非葉結(jié)點都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。采用信息增益來選擇能夠最好地將樣本分類的屬性。信息增益基于信息論中熵的概念。ID3總是選擇具有最高信息增益（或最大熵壓縮）的屬性作為當(dāng)前結(jié)點的測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機性或“不純性”。1.2問題重述1、目標(biāo)概念為“壽險促銷”2、計算每個屬性的信息增益3、確定根節(jié)點的測試屬性模型求解構(gòu)造決策樹的方法是采用自上而下的遞歸構(gòu)

4、造，其思路是：以代表訓(xùn)練樣本的單個結(jié)點開始建樹（步驟1）。如果樣本都在同一類，則該結(jié)點成為樹葉，并用該類標(biāo)記（步驟2和3）。否則，算法使用稱為信息增益的機遇熵的度量為啟發(fā)信息，選擇能最好地將樣本分類的屬性（步驟6）。該屬性成為該結(jié)點的“測試”或“判定”屬性（步驟7）。值得注意的是，在這類算法中，所有的屬性都是分類的，即取離散值的。連續(xù)值的屬性必須離散化。對測試屬性的每個已知的值，創(chuàng)建一個分支，并據(jù)此劃分樣本（步驟810）。算法使用同樣的過程，遞歸地形成每個劃分上的樣本決策樹。一旦一個屬性出現(xiàn)在一個結(jié)點上，就不必考慮該結(jié)點的任何后代（步驟13）。遞歸劃分步驟，當(dāng)下列條件之一成立時停止：（a）給定

5、結(jié)點的所有樣本屬于同一類（步驟2和3）。（b）沒有剩余屬性可以用來進一步劃分樣本（步驟4）。在此情況下，采用多數(shù)表決（步驟5）。這涉及將給定的結(jié)點轉(zhuǎn)換成樹葉，并用samples中的多數(shù)所在類別標(biāo)記它。換一種方式，可以存放結(jié)點樣本的類分布。（c）分支test_attribute=ai 沒有樣本。在這種情況下，以samples中的多數(shù)類創(chuàng)建一個樹葉（步驟12）。算法Decision_Tree(samples,attribute_list)輸入由離散值屬性描述的訓(xùn)練樣本集samples;候選屬性集合attribute_list。輸出一棵決策樹。（1） 創(chuàng)建節(jié)點N；（2） If samples 都在同

6、一類C中then （3） 返回N作為葉節(jié)點，以類C標(biāo)記；（4） If attribute_list為空then （5） 返回N作為葉節(jié)點，以samples 中最普遍的類標(biāo)記；/多數(shù)表決（6） 選擇attribute_list 中具有最高信息增益的屬性test_attribute;（7） 以test_attribute 標(biāo)記節(jié)點N；（8） For each test_attribute 的已知值v /劃分 samples（9） 由節(jié)點N分出一個對應(yīng)test_attribute=v的分支；（10） 令Sv為 samples中 test_attribute=v 的樣本集合；/一個劃分塊（11） If

7、 Sv為空 then （12） 加上一個葉節(jié)點，以samples中最普遍的類標(biāo)記；（13） Else 加入一個由Decision_Tree(Sv,attribute_list-test_attribute)返回節(jié)點值E(S)=(-915)log2(915)-(615)log2(615)=0.971Values(收入范圍)=20-30K,30-40k,40-50K,50-60K E(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)log

8、2(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(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.971Insurance(保險)=yes, noE(S(yes)= (-33

9、)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) =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

10、, 性別)=(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(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.9

11、71-0.7851=0.1859代碼package DecisionTree;import java.util.ArrayList;/* * 決策樹結(jié)點類 */public class TreeNode private String name; /節(jié)點名（分裂屬性的名稱）private ArrayList rule; /結(jié)點的分裂規(guī)則ArrayList child; /子結(jié)點集合private ArrayListArrayList datas; /劃分到該結(jié)點的訓(xùn)練元組private ArrayList candAttr; /劃分到該結(jié)點的候選屬性public TreeNode() this.

12、name = ;this.rule = new ArrayList();this.child = new ArrayList();this.datas = null;this.candAttr = null;public ArrayList getChild() return child;public void setChild(ArrayList child) this.child = child;public ArrayList getRule() return rule;public void setRule(ArrayList rule) this.rule = rule;public

13、 String getName() return name;public void setName(String name) = name;public ArrayListArrayList getDatas() return datas;public void setDatas(ArrayListArrayList datas) this.datas = datas;public ArrayList getCandAttr() return candAttr;public void setCandAttr(ArrayList candAttr) this.candAttr

14、 = candAttr;package DecisionTree;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;/* * 決策樹算法測試類 */public class TestDecisionTree /* * 讀取候選屬性 * return 候選屬性集合 * throws IOException */public ArrayList rea

15、dCandAttr() throws IOExceptionArrayList candAttr = new ArrayList();BufferedReader reader = new BufferedReader(new InputStreamReader(System.in);String str = ;while (!(str = reader.readLine().equals() StringTokenizer tokenizer = new StringTokenizer(str);while (tokenizer.hasMoreTokens() candAttr.add(to

16、kenizer.nextToken();return candAttr;/* * 讀取訓(xùn)練元組 * return 訓(xùn)練元組集合 * throws IOException */public ArrayListArrayList readData() throws IOException ArrayListArrayList datas = new ArrayListArrayList();BufferedReader reader = new BufferedReader(new InputStreamReader(System.in);String str = ;while (!(str =

17、reader.readLine().equals() StringTokenizer tokenizer = new StringTokenizer(str);ArrayList s = new ArrayList();while (tokenizer.hasMoreTokens() s.add(tokenizer.nextToken();datas.add(s);return datas;/* * 遞歸打印樹結(jié)構(gòu) * param root 當(dāng)前待輸出信息的結(jié)點 */public void printTree(TreeNode root)System.out.println(name: + r

18、oot.getName();ArrayList rules = root.getRule();System.out.print(node rules: );for (int i = 0; i rules.size(); i+) System.out.print(rules.get(i) + );System.out.print();System.out.println();ArrayList children = root.getChild();int size =children.size();if (size = 0) System.out.println(-leaf node!-); e

19、lse System.out.println(size of children: + children.size();for (int i = 0; i children.size(); i+) System.out.print(child + (i + 1) + of node + root.getName() + : );printTree(children.get(i);/* * 主函數(shù)，程序入口 * param args */public static void main(String args) TestDecisionTree tdt = new TestDecisionTree(

20、);ArrayList candAttr = null;ArrayListArrayList datas = null;try System.out.println(請輸入候選屬性);candAttr = tdt.readCandAttr();System.out.println(請輸入訓(xùn)練數(shù)據(jù));datas = tdt.readData(); catch (IOException e) e.printStackTrace();DecisionTree tree = new DecisionTree();TreeNode root = tree.buildTree(datas, candAtt

21、r);tdt.printTree(root);package DecisionTree;import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.Map;/* * 選擇最佳分裂屬性 */public class Gain private ArrayListArrayList D = null; /訓(xùn)練元組private ArrayList attrList = null; /候選屬性集public Gain(ArrayListArrayList datas, Ar

22、rayList attrList) this.D = datas;this.attrList = attrList;/* * 獲取最佳侯選屬性列上的值域（假定所有屬性列上的值都是有限的名詞或分類類型的） * param attrIndex 指定的屬性列的索引 * return 值域集合 */public ArrayList getValues(ArrayListArrayList datas, int attrIndex)ArrayList values = new ArrayList();String r = ;for (int i = 0; i datas.size(); i+) r =

23、datas.get(i).get(attrIndex);if (!values.contains(r) values.add(r);return values;/* * 獲取指定數(shù)據(jù)集中指定屬性列索引的域值及其計數(shù) * param d 指定的數(shù)據(jù)集 * param attrIndex 指定的屬性列索引 * return 類別及其計數(shù)的map */public Map valueCounts(ArrayListArrayList datas, int attrIndex)Map valueCount = new HashMap();String c = ;ArrayList tuple = nu

24、ll;for (int i = 0; i datas.size(); i+) tuple = datas.get(i);c = tuple.get(attrIndex);if (valueCount.containsKey(c) valueCount.put(c, valueCount.get(c) + 1); else valueCount.put(c, 1);return valueCount;/* * 求對datas中元組分類所需的期望信息，即datas的熵 * param datas 訓(xùn)練元組 * return datas的熵值 */public double infoD(ArrayL

25、istArrayList datas)double info = 0.000;int total = datas.size();Map classes = valueCounts(datas, attrList.size();Iterator iter = classes.entrySet().iterator();Integer counts = new Integerclasses.size();for(int i = 0; iter.hasNext(); i+)Map.Entry entry = (Map.Entry) iter.next(); Integer val = (Intege

26、r) entry.getValue(); countsi = val;for (int i = 0; i counts.length; i+) double base = DecimalCalculate.div(countsi, total, 3);info += (-1) * base * Math.log(base);return info;/* * 獲取指定屬性列上指定值域的所有元組 * param attrIndex 指定屬性列索引 * param value 指定屬性列的值域 * return 指定屬性列上指定值域的所有元組 */public ArrayListArrayList

27、datasOfValue(int attrIndex, String value)ArrayListArrayList Di = new ArrayListArrayList();ArrayList t = null;for (int i = 0; i D.size(); i+) t = D.get(i);if(t.get(attrIndex).equals(value)Di.add(t);return Di;/* * 基于按指定屬性劃分對D的元組分類所需要的期望信息 * param attrIndex 指定屬性的索引 * return 按指定屬性劃分的期望信息值 */public doubl

28、e infoAttr(int attrIndex)double info = 0.000;ArrayList values = getValues(D, attrIndex);for (int i = 0; i values.size(); i+) ArrayListArrayList dv = datasOfValue(attrIndex, values.get(i);info += DecimalCalculate.mul(DecimalCalculate.div(dv.size(), D.size(), 3), infoD(dv); return info;/* * 獲取最佳分裂屬性的索

29、引 * return 最佳分裂屬性的索引 */public int bestGainAttrIndex()int index = -1;double gain = 0.000;double tempGain = 0.000;for (int i = 0; i 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;impor

30、t javax.smartcardio.*;/* * 決策樹構(gòu)造類 */public class DecisionTree private Integer attrSelMode; /最佳分裂屬性選擇模式，1表示以信息增益度量，2表示以信息增益率度量。暫未實現(xiàn)2public DecisionTree()this.attrSelMode = 1;public DecisionTree(int attrSelMode) this.attrSelMode = attrSelMode;public void setAttrSelMode(Integer attrSelMode) this.attrSe

31、lMode = attrSelMode;/* * 獲取指定數(shù)據(jù)集中的類別及其計數(shù) * param datas 指定的數(shù)據(jù)集 * return 類別及其計數(shù)的map */public Map classOfDatas(ArrayListArrayList datas)Map classes = new HashMap();String c = ;ArrayList tuple = null;for (int i = 0; i datas.size(); i+) tuple = datas.get(i);c = tuple.get(tuple.size() - 1);if (classes.con

32、tainsKey(c) classes.put(c, classes.get(c) + 1); else classes.put(c, 1);return classes;/* * 獲取具有最大計數(shù)的類名，即求多數(shù)類 * param classes 類的鍵值集合 * return 多數(shù)類的類名 */public String maxClass(Map classes)String maxC = ;int max = -1;Iterator iter = classes.entrySet().iterator();for(int i = 0; iter.hasNext(); i+)Map.Ent

33、ry entry = (Map.Entry) iter.next(); String key = (String)entry.getKey();Integer val = (Integer) entry.getValue(); if(val max)max = val;maxC = key;return maxC;/* * 構(gòu)造決策樹 * param datas 訓(xùn)練元組集合 * param attrList 候選屬性集合 * return 決策樹根結(jié)點 */public TreeNode buildTree(ArrayListArrayList datas, ArrayList attrLi

34、st)/System.out.print(候選屬性列表： );/for (int i = 0; i attrList.size(); i+) /System.out.print( + attrList.get(i) + );/System.out.println();TreeNode node = new TreeNode();node.setDatas(datas);node.setCandAttr(attrList);Map classes = classOfDatas(datas);String maxC = maxClass(classes);if (classes.size() =

35、1 | attrList.size() = 0) node.setName(maxC);return node;Gain gain = new Gain(datas, attrList);int bestAttrIndex = gain.bestGainAttrIndex();ArrayList rules = gain.getValues(datas, bestAttrIndex);node.setRule(rules);node.setName(attrList.get(bestAttrIndex);if(rules.size() 2) /?此處有待商榷attrList.remove(be

36、stAttrIndex);for (int i = 0; i rules.size(); i+) String rule = rules.get(i);ArrayListArrayList 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(d

37、i);leafNode.setCandAttr(attrList);node.getChild().add(leafNode); else TreeNode newNode = buildTree(di, attrList);node.getChild().add(newNode);return node;package DecisionTree;import java.math.BigDecimal; public class DecimalCalculate /* * 由于Java的簡單類型不能夠精確的對浮點數(shù)進行運算，這個工具類提供精 * 確的浮點數(shù)運算，包括加減乘除和四舍五入。 */

38、/默認(rèn)除法運算精度 private static final int DEF_DIV_SCALE = 10; /這個類不能實例化 private DecimalCalculate() /* * 提供精確的加法運算。 * param v1 被加數(shù) * param v2 加數(shù) * return 兩個參數(shù)的和 */ public static double add(double v1,double v2) BigDecimal b1 = new BigDecimal(Double.toString(v1); BigDecimal b2 = new BigDecimal(Double.toString

39、(v2); return b1.add(b2).doubleValue(); /* * 提供精確的減法運算。 * param v1 被減數(shù) * param v2 減數(shù) * return 兩個參數(shù)的差 */ 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(); /* * 提供精確

40、的乘法運算。 * param v1 被乘數(shù) * param v2 乘數(shù) * return 兩個參數(shù)的積 */ 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(); /* * 提供（相對）精確的除法運算，當(dāng)發(fā)生除不盡的情況時，精確到 * 小數(shù)點以后10位，以后的數(shù)字四舍五入。 *

41、 param v1 被除數(shù) * param v2 除數(shù) * return 兩個參數(shù)的商 */ public static double div(double v1,double v2) return div(v1,v2,DEF_DIV_SCALE); /* * 提供（相對）精確的除法運算。當(dāng)發(fā)生除不盡的情況時，由scale參數(shù)指 * 定精度，以后的數(shù)字四舍五入。 * param v1 被除數(shù) * param v2 除數(shù) * param scale 表示表示需要精確到小數(shù)點以后幾位。 * return 兩個參數(shù)的商 */ public static double div(double v1,do

42、uble v2,int scale) if(scale0) throw new IllegalArgumentException( 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(); /* * 提供精確的小數(shù)位四舍五

43、入處理。 * param v 需要四舍五入的數(shù)字 * param scale 小數(shù)點后保留幾位 * return 四舍五入后的結(jié)果 */ public static double round(double v,int scale) if(scale0) throw new IllegalArgumentException( The scale must be a positive integer or zero); BigDecimal b = new BigDecimal(Double.toString(v); BigDecimal one = new BigDecimal(1); return b.divide(one,scale,BigDecimal.ROUND_HALF_UP).doubleValue(); /* * 提供精確的類型轉(zhuǎn)換(Float) * param v 需