亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

統計學習方法(五)——決策樹

系統 1915 0

/*先把標題給寫了,這樣就能經常提醒自己*/

  決策樹是一種容易理解的分類算法,它可以認為是if-then規則的一個集合。主要的優點是模型具有可讀性,且分類速度較快,不用進行過多的迭代訓練之類。決策樹學習通常包括3個步驟:特征選擇、決策樹的生成和決策樹的修剪。比較常用到的算法有ID3、C4.5和CART。

1. 決策樹模型

  決策樹是一種樹形結構的分類模型,它由結點和有向邊組成,結點分為內部結點和葉結點,內部結點表示一個特征或屬性,葉結點表示一個類。

決策樹的分類即是從樹的根節點開始對實例的某一個特征進行判斷,通過內部結點逐步下潛到葉結點的過程。

2. 特征選擇

  特征選擇在于選取對訓練數據具有分類能力的特征,通常的選擇準則是信息增益或信息增益率。為了便于說明,書中給出了一個例子

統計學習方法(五)——決策樹_第1張圖片

希望通過所給的訓練數據學習一個貸款申請的決策樹,當新客戶提出貸款申請時,根據申請人的特征決定是否可貸。

????? 從認知上個人覺得特征的選擇就是找出一些具有代表性,對于分類辨識度高的特征,如此能夠快速準確的為實例分類,從數學的角度上來講,就要涉及到信息論與概率統計中的熵了。在此不贅述太多,直接給出特征選擇的算法(信息增益)。

????? 輸入:訓練數據集D和特征A;

????? 輸出:特征A對訓練數據集D的信息增益 和增益率

?

(1)?? 計算數據集D的經驗熵

    ?

(2)?? 計算特征A的經驗條件熵

    ?

(3)?? 計算信息增益

?    

(4)?? 信息增益率

    ?

????? 對于書中的例子,首先計算經驗熵

?

然后計算各特征的信息增益,分別以 表示年齡、有工作、有房子和信貸情況4個特征,則

    ? ?

分別計算 的信息增益,由于 的信息增益值最大,則選擇其為最優特征,當然也可以計算出信息增益率的結果作為選擇的依據。

3. 決策樹的生成

ID3和C4.5算法基本上一樣,只是在特征選擇的依據上C4.5采用了改進后的信息增益率。因為本文只介紹其中的ID3算法即可。?

ID3算法步驟

輸入:訓練數據集D,特征集A,閾值e

輸出:決策樹T

(1)?? 若D中所有實例屬于同一類Ck,則T為單結點樹,并將類Ck作為該結點的類標記,返回T;

(2)?? 若A=空,則T為單結點樹,將D中實例數最多的類Ck作為結點類標記,返回T;

(3)?? 否則,計算A中各特征對D的信息增益,選擇信息增益值最大的特征Ag;

(4)?? 如果Ag的信息增益小于閾值e,則T為單結點樹,將D中最多的類Ck作為結點類標記,返回T;

(5)?? 否則,對Ag的每一可能值ai,依Ag=ai將D分割為若干子集Di,將Di中實例數最大多的類作為類標記,構建子結點,由結點及其子結點構成樹T,返回T;

(6)?? 對于第i個子結點,以Di為訓練集,以A-Ag為特征集,遞歸調用步驟(1)~(5),得到子樹Ti,返回Ti。

?

從描述上感覺決策樹的生成還是挺簡單明了的,但是具體的實現上樹的生成是最最難的,要注意的細節很多,花了倆個晚上才搞好的,遇到了好多坑

代碼塊1:信息增益類

      
        package
      
      
         org.juefan.decisiontree;
        
import java.util.ArrayList; import java.util.HashMap; import java.util.Map; import org.juefan.basic.FileIO; import org.juefan.bayes.Data; public class InfoGain { // 數據實例存儲類 class Data { public ArrayList<Object> x; public Object y; /** 讀取一行數據轉化為標準格式 */ public Data(String content){ String[] strings = content.split("\t| |:" ); ArrayList <Object> xList = new ArrayList<Object> (); for ( int i = 1; i < strings.length; i++ ){ xList.add(strings[i]); } this .x = new ArrayList<> (); this .x = xList; this .y = strings[0 ]; } public Data(){ x = new ArrayList<> (); y = 0 ; } public String toString(){ StringBuilder builder = new StringBuilder(); builder.append( "[ " ); for ( int i = 0; i < x.size() - 1; i++ ) builder.append(x.get(i).toString()).append( "," ); builder.append(x.get(x.size() - 1 ).toString()); builder.append( " ]" ); return builder.toString(); } } // 返回底數為2的對數值 public static double log2( double d){ return Math.log(d)/Math.log(2 ); } /** * 計算經驗熵 * @param datas 當前數據集,可以為訓練數據集中的子集 * @return 返回當前數據集的經驗熵 */ public double getEntropy(ArrayList<Data> datas){ int counts = datas.size(); double entropy = 0 ; Map <Object, Double> map = new HashMap<Object, Double> (); for (Data data: datas){ if (map.containsKey(data.y)){ map.put(data.y, map.get(data.y) + 1 ); } else { map.put(data.y, 1D); } } for ( double v: map.values()) entropy -= (v/counts * log2(v/ counts)); return entropy; } /** * 計算條件熵 * @param datas 當前數據集,可以為訓練數據集中的子集 * @param feature 待計算的特征位置 * @return 第feature個特征的條件熵 */ public double getCondiEntropy(ArrayList<Data> datas, int feature){ int counts = datas.size(); double condiEntropy = 0 ; Map <Object, ArrayList<Data>> tmMap = new HashMap<> (); for (Data data: datas){ if (tmMap.containsKey(data.x.get(feature))){ tmMap.get(data.x.get(feature)).add(data); } else { ArrayList <Data> tmDatas = new ArrayList<> (); tmDatas.add(data); tmMap.put(data.x.get(feature), tmDatas); } } for (ArrayList<Data> datas2: tmMap.values()){ condiEntropy += ( double )datas2.size()/counts * getEntropy(datas2); } return condiEntropy; } /** * 計算信息增益(ID3算法) * @param datas 當前數據集,可以為訓練數據集中的子集 * @param feature 待計算的特征位置 * @return 第feature個特征的信息增益 */ public double getInfoGain(ArrayList<Data> datas, int feature){ return getEntropy(datas) - getCondiEntropy(datas, feature); } /** * 計算信息增益率(C4.5算法) * @param datas 當前數據集,可以為訓練數據集中的子集 * @param feature 待計算的特征位置 * @return 第feature個特征的信息增益率 */ public double getInfoGainRatio(ArrayList<Data> datas, int feature){ return getInfoGain(datas, feature)/ getEntropy(datas); } }

代碼塊2:決策樹類

      
        package
      
      
         org.juefan.decisiontree;
        
import java.util.ArrayList; import java.util.List; public class TreeNode { private String feature;  //候選特征 private List<TreeNode> childTreeNode; private String targetFunValue;  //特征對應的值 private String nodeName;  //分類的類別 public TreeNode(String nodeName){ this .nodeName = nodeName; this .childTreeNode = new ArrayList<TreeNode> (); } public TreeNode(){ this .childTreeNode = new ArrayList<TreeNode> (); } public void printTree(){ if (targetFunValue != null ) System.out.print( "特征值: " + targetFunValue + "\t" ); if (nodeName != null ) System.out.print( "類型: " + nodeName + "\t" ); System.out.println(); for (TreeNode treeNode: childTreeNode){ System.out.println( "當前特征為:" + feature); treeNode.printTree(); } }
public String getAttributeValue() { return feature; } public void setAttributeValue(String attributeValue) { this .feature = attributeValue; } public List<TreeNode> getChildTreeNode() { return childTreeNode; } public void setChildTreeNode(List<TreeNode> childTreeNode) { this .childTreeNode = childTreeNode; } public String getTargetFunValue() { return targetFunValue; } public void setTargetFunValue(String targetFunValue) { this .targetFunValue = targetFunValue; } public String getNodeName() { return nodeName; } public void setNodeName(String nodeName) { this .nodeName = nodeName; } }

代碼塊3:決策樹的生成

      
        package
      
      
         org.juefan.decisiontree;


      
      
        import
      
      
         java.util.ArrayList;

      
      
        import
      
      
         java.util.HashMap;

      
      
        import
      
      
         java.util.HashSet;

      
      
        import
      
      
         java.util.List;

      
      
        import
      
      
         java.util.Map;

      
      
        import
      
      
         java.util.Set;

      
      
        import
      
      
         org.juefan.basic.FileIO;

      
      
        import
      
      
         org.juefan.bayes.Data;


      
      
        public
      
      
        class
      
      
         DecisionTree {
    
      
      
        public
      
      
        static
      
      
        final
      
      
        double
      
       e = 0.1
      
        ;
    
      
      
        public
      
       InfoGain infoGain = 
      
        new
      
      
         InfoGain();
    
    
      
      
        public
      
       TreeNode buildTree(ArrayList<Data> datas, ArrayList<String>
      
         featureName){
        TreeNode treeNode 
      
      = 
      
        new
      
      
         TreeNode();
        ArrayList
      
      <String> feaName = 
      
        new
      
       ArrayList<>
      
        ();
        feaName 
      
      =
      
         featureName;
        
      
      
        if
      
      (isSingle(datas) || getMaxInfoGain(datas) <
      
         e){
            treeNode.setNodeName(getLabel(datas).toString());
            
      
      
        return
      
      
         treeNode;
        }
      
      
        else
      
      
          {
            
      
      
        int
      
       feature =
      
         getMaxInfoGainFeature(datas);
            treeNode.setAttributeValue(feaName.get(feature 
      
      + 1
      
        ));
            ArrayList
      
      <String> tList = 
      
        new
      
       ArrayList<>
      
        ();
            tList 
      
      =
      
         feaName;
            Map
      
      <Object, ArrayList<Data>> tMap = 
      
        new
      
       HashMap<>
      
        ();
            
      
      
        for
      
      
        (Data data: datas){
                
      
      
        if
      
      
        (tMap.containsKey(data.x.get(feature))){
                    Data tData 
      
      = 
      
        new
      
      
         Data();
                    
      
      
        for
      
      (
      
        int
      
       i = 0; i < data.x.size(); i++
      
        )
                        
      
      
        if
      
      (i !=
      
         feature)
                            tData.x.add(data.x.get(i));
                    tData.y 
      
      =
      
         data.y;
                    tMap.get(data.x.get(feature)).add(tData);
                }
      
      
        else
      
      
         {
                    Data tData 
      
      = 
      
        new
      
      
         Data();
                    
      
      
        for
      
      (
      
        int
      
       i = 0; i < data.x.size(); i++
      
        )
                        
      
      
        if
      
      (i !=
      
         feature)
                            tData.x.add(data.x.get(i));
                    tData.y 
      
      =
      
         data.y;
                    ArrayList
      
      <Data> tDatas = 
      
        new
      
       ArrayList<>
      
        ();
                    tDatas.add(tData);
                    tMap.put(data.x.get(feature),tDatas);
                }
            }
            List
      
      <TreeNode> treeNodes = 
      
        new
      
       ArrayList<>
      
        ();
            
      
      
        int
      
       child = 0
      
        ;
            
      
      
        for
      
      
        (Object key: tMap.keySet()){
                
      
      
        //
      
      
        這一步太坑爹了,java的拷背坑真多啊,害我浪費了半天的時間
      
      
                ArrayList<String> tList2 = 
      
        new
      
       ArrayList<>
      
        (tList);
                tList2.remove(feature 
      
      + 1
      
        );
                treeNodes.add(buildTree(tMap.get(key), tList2));
                treeNodes.get(child 
      
      ++
      
        ).setTargetFunValue(key.toString());
            }
            treeNode.setChildTreeNode(treeNodes);
            feaName.remove(feature 
      
      + 1
      
        );
        }    
        
      
      
        return
      
      
         treeNode;
    }
    
    
      
      
        /**
      
      
        
     * 獲取實例中的最大類
     * 
      
      
        @param
      
      
         datas 實例集
     * 
      
      
        @return
      
      
         出現次數最多的類
     
      
      
        */
      
      
        public
      
       Object getLabel(ArrayList<Data>
      
         datas){
        Map
      
      <Object, Integer> map = 
      
        new
      
       HashMap<Object, Integer>
      
        ();
        Object label 
      
      = 
      
        null
      
      
        ;
        
      
      
        int
      
       max = 0
      
        ;
        
      
      
        for
      
      
        (Data data: datas){
            
      
      
        if
      
      
        (map.containsKey(data.y)){
                map.put(data.y, map.get(data.y) 
      
      + 1
      
        );
                
      
      
        if
      
      (map.get(data.y) >
      
         max){
                    max 
      
      =
      
         map.get(data.y);
                    label 
      
      =
      
         data.y;
                }
            }
      
      
        else
      
      
         {
                map.put(data.y, 
      
      1
      
        );
            }
        }
        
      
      
        return
      
      
         label;
    }
    
    
      
      
        /**
      
      
        
     * 計算信息增益(率)的最大值
     * 
      
      
        @param
      
      
         datas
     * 
      
      
        @return
      
      
         最大的信息增益值
     
      
      
        */
      
      
        public
      
      
        double
      
       getMaxInfoGain(ArrayList<Data>
      
         datas){
        
      
      
        double
      
       max = 0
      
        ;
        
      
      
        for
      
      (
      
        int
      
       i = 0; i < datas.get(0).x.size(); i++
      
        ){
            
      
      
        double
      
       temp =
      
         infoGain.getInfoGain(datas, i);
            
      
      
        if
      
      (temp >
      
         max)
                max 
      
      =
      
         temp;
        }
        
      
      
        return
      
      
         max;
    }
    
    
      
      
        /**
      
      
        信息增益最大的特征
      
      
        */
      
      
        public
      
      
        int
      
       getMaxInfoGainFeature(ArrayList<Data>
      
         datas){
        
      
      
        double
      
       max = 0
      
        ;
        
      
      
        int
      
       feature = 0
      
        ;
        
      
      
        for
      
      (
      
        int
      
       i = 0; i < datas.get(0).x.size(); i++
      
        ){
            
      
      
        double
      
       temp =
      
         infoGain.getInfoGain(datas, i);
            
      
      
        if
      
      (temp >
      
         max){
                max 
      
      =
      
         temp;
                feature 
      
      =
      
         i;
            }
        }
        
      
      
        return
      
      
         feature;
    }
    
    
      
      
        /**
      
      
        判斷是否只有一類
      
      
        */
      
      
        public
      
      
        boolean
      
       isSingle(ArrayList<Data>
      
         datas){
        Set
      
      <Object> set = 
      
        new
      
       HashSet<>
      
        ();
        
      
      
        for
      
      
        (Data data: datas)
            set.add(data.y);
        
      
      
        return
      
       set.size() == 1? 
      
        true
      
      :
      
        false
      
      
        ;
    }
    
    
      
      
        public
      
      
        static
      
      
        void
      
      
         main(String[] args) {
        ArrayList
      
      <Data> datas = 
      
        new
      
       ArrayList<>
      
        ();
        FileIO fileIO 
      
      = 
      
        new
      
      
         FileIO();
        DecisionTree decisionTree 
      
      = 
      
        new
      
      
         DecisionTree();
        fileIO.setFileName(
      
      ".//file//decision.tree.txt"
      
        );
        fileIO.FileRead(
      
      "utf-8"
      
        );
        ArrayList
      
      <String> featureName = 
      
        new
      
       ArrayList<>
      
        ();
        
      
      
        //
      
      
        獲取文件的標頭
      
      
        for
      
      (String string: fileIO.fileList.get(0).split("\t"
      
        ))
            featureName.add(string);
        
      
      
        for
      
      (
      
        int
      
       i = 1; i < fileIO.fileList.size(); i++
      
        ){
            datas.add(
      
      
        new
      
      
         Data(fileIO.fileList.get(i)));
        }
        TreeNode treeNode 
      
      = 
      
        new
      
      
         TreeNode();
        treeNode 
      
      =
      
         decisionTree.buildTree(datas, featureName);
        treeNode.printTree();
    }
}
      
    

?運行情況:

輸入文件?".//file//decision.tree.txt" 內容為:

類型 年齡 有工作 有自己的房子 信貸情況
否 青年 否 否 一般
否 青年 否 否 好
是 青年 是 否 好
是 青年 是 是 一般
否 青年 否 否 一般
否 中年 否 否 一般
否 中年 否 否 好
是 中年 是 是 好
是 中年 否 是 非常好
是 中年 否 是 非常好
是 老年 否 是 非常好
是 老年 否 是 好
是 老年 是 否 好
是 老年 是 否 非常好
否 老年 否 否 一般

運行結果為:

當前特征為:有自己的房子
特征值: 是 類型: 是
當前特征為:有自己的房子
特征值: 否
當前特征為:有工作
特征值: 是 類型: 是
當前特征為:有工作
特征值: 否 類型: 否

對代碼有興趣的可以上本人的GitHub查看: https://github.com/JueFan/StatisticsLearningMethod/

里面也有具體的實例數據

統計學習方法(五)——決策樹


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 91精品国产高清久久久久久io | 99干99 | 四虎影视在线播放 | 一级毛片一级毛片一级毛片aa | 国产乱码精品一区二区三区卡 | 久热精品男人的天堂在线视频 | 精品欧美一区二区三区在线 | 免费观看欧美成人禁片 | 妖精视频免费在线观看 | 免费看国产精品麻豆 | 久久国产成人亚洲精品影院老金 | 国产免费一级在线观看 | 亚洲国产成人久久一区二区三区 | 欧美一级片免费 | 99国产福利视频在线观看 | 欧美久久xxxxxx影院 | freexxxx性特大另类ww | 亚洲在线视频观看 | 性色网站| 国产精品亚洲欧美大片在线看 | 欧美成人h精品网站 | 午夜免费福利在线观看 | 一区二区三区在线观看免费 | 亚洲永久精品ww47 | 亚洲激情视频网 | 四虎网站1515hh四虎 | 精品香蕉99久久久久网站 | 日日噜噜夜夜躁躁狠狠 | 羞羞免费观看视频 | 国产成人啪午夜精品网站男同 | 久久尹人 | 伊在人亚洲香蕉精品播放 | 久久99久久精品久久久久久 | 久久福利小视频 | 奇米影视大全 | 国产亚洲精品麻豆一区二区 | 欧美一级视频在线 | 色一色综合 | 日本吻胸抓胸激烈视频网站 | 国产精品久久久久影院色老大 | 久久99国产一区二区三区 |