隨機(jī)森林和GBDT的學(xué)習(xí)

1、隨機(jī)森林和GBDT的學(xué)習(xí)2015-03-31      0 個(gè)評論    來源：走在前往架構(gòu)師的路上  收藏    我要投稿前言提到森林，就不得不聯(lián)想到樹，因?yàn)檎且豢每玫臉錁?gòu)成了龐大的森林，而在本篇文章中的”樹“，指的就是Decision Tree-決策樹。隨機(jī)森林就是一棵棵決策樹的組合，也就是說隨機(jī)森林=boosting+決策樹，這樣就好理解多了吧，再來說說GBDT，GBDT全稱是Gradient Boosting Decision Tree

2、，就是梯度提升決策樹，與隨機(jī)森林的思想很像，但是比隨機(jī)森林稍稍的難一點(diǎn)，當(dāng)然效果相對于前者而言，也會(huì)好許多。由于本人才疏學(xué)淺，本文只會(huì)詳細(xì)講述Random Forest算法的部分，至于GBDT我會(huì)給出一小段篇幅做介紹引導(dǎo)，讀者能夠如果有興趣的話，可以自行學(xué)習(xí)。隨機(jī)森林算法決策樹要想理解隨機(jī)森林算法，就不得不提決策樹，什么是決策樹，如何構(gòu)造決策樹，簡單的回答就是數(shù)據(jù)的分類以樹形結(jié)構(gòu)的方式所展現(xiàn)，每個(gè)子分支都代表著不同的分類情況，比如下面的這個(gè)圖所示：當(dāng)然決策樹的每個(gè)節(jié)點(diǎn)分支不一定是三元的，可以有2個(gè)或者更多。分類的終止條件為，沒有可以再拿來分類的屬性條件或者說分到的數(shù)據(jù)的分類已經(jīng)完全一致的情況。

3、決策樹分類的標(biāo)準(zhǔn)和依據(jù)是什么呢，下面介紹主要的2種劃分標(biāo)準(zhǔn)。1、信息增益。這是ID3算法系列所用的方法，C4.5算法在這上面做了少許的改進(jìn)，用信息增益率來作為劃分的標(biāo)準(zhǔn)，可以稍稍減小數(shù)據(jù)過于擬合的缺點(diǎn)。2、基尼指數(shù)。這是CART分類回歸樹所用的方法。也是類似于信息增益的一個(gè)定義，最終都是根據(jù)數(shù)據(jù)劃分后的純度來做比較，這個(gè)純度，你也可以理解為熵的變化，當(dāng)然我們所希望的情況就是分類后數(shù)據(jù)的純度更純，也就是說，前后劃分分類之后的熵的差越大越好。不過CART算法比較好的一點(diǎn)是樹構(gòu)造好后，還有剪枝的操作，剪枝操作的種類就比較多了，我之前在實(shí)現(xiàn)CART算法時(shí)用的是代價(jià)復(fù)雜度的剪枝方法。這2種決策算法在我之

4、前的博文中已經(jīng)有所提及，不理解的可以點(diǎn)擊我的ID3系列算法介紹和我的CART分類回歸樹算法。Boosting原本不打算將Boosting單獨(dú)拉出來講的，后來想想還是有很多內(nèi)容可談的。Boosting本身不是一種算法，他更應(yīng)該說是一種思想，首先對數(shù)據(jù)構(gòu)造n個(gè)弱分類器，最后通過組合n個(gè)弱分類器對于某個(gè)數(shù)據(jù)的判斷結(jié)果作為最終的分類結(jié)果，就變成了一個(gè)強(qiáng)分類器，效果自然要好過單一分類器的分類效果。他可以理解為是一種提升算法，舉一個(gè)比較常見的Boosting思想的算法AdaBoost，他在訓(xùn)練每個(gè)弱分類器的時(shí)候，提高了對于之前分錯(cuò)數(shù)據(jù)的權(quán)重值，最終能夠組成一批相互互補(bǔ)的分類器集合。詳細(xì)可以查看我的AdaB

5、oost算法學(xué)習(xí)。OK，2個(gè)重要的概念都已經(jīng)介紹完畢，終于可以介紹主角Random Forest的出現(xiàn)了，正如前言中所說Random Forest=Decision Trees + Boosting，這里的每個(gè)弱分類器就是一個(gè)決策樹了，不過這里的決策樹都是二叉樹，就是只有2個(gè)孩子分支，自然我立刻想到的做法就是用CART算法來構(gòu)建，因?yàn)槿思宜惴ň褪嵌种У?。隨機(jī)算法，隨機(jī)算法，當(dāng)然重在隨機(jī)2個(gè)字上面，下面是2個(gè)方面體現(xiàn)了隨機(jī)性。對于數(shù)據(jù)樣本的采集量，比如我數(shù)據(jù)由100條，我可以每次隨機(jī)取出其中的20條，作為我構(gòu)造決策樹的源數(shù)據(jù)，采取又放回的方式，并不是第一次抽到的數(shù)據(jù)，第二次不能重復(fù)，第二隨機(jī)

6、性體現(xiàn)在對于數(shù)據(jù)屬性的隨機(jī)采集，比如一行數(shù)據(jù)總共有10個(gè)特征屬性，我每次隨機(jī)采用其中的4個(gè)。正是由于對于數(shù)據(jù)的行壓縮和列壓縮，使得數(shù)據(jù)的隨機(jī)性得以保證，就很難出現(xiàn)之前的數(shù)據(jù)過擬合的問題了，也就不需要在決策樹最后進(jìn)行剪枝操作了，這個(gè)是與一般的CART算法所不同的，尤其需要注意。下面是隨機(jī)森林算法的構(gòu)造過程：1、通過給定的原始數(shù)據(jù)，選出其中部分?jǐn)?shù)據(jù)進(jìn)行決策樹的構(gòu)造，數(shù)據(jù)選取是”有放回“的過程，我在這里用的是CART分類回歸樹。2、隨機(jī)森林構(gòu)造完成之后，給定一組測試數(shù)據(jù)，使得每個(gè)分類器對其結(jié)果分類進(jìn)行評估，最后取評估結(jié)果的眾數(shù)最為最終結(jié)果。算法非常的好理解，在Boosting算法和決策樹之上做了一個(gè)

7、集成，下面給出算法的實(shí)現(xiàn)，很多資料上只有大篇幅的理論，我還是希望能帶給大家一點(diǎn)實(shí)在的東西。隨機(jī)算法的實(shí)現(xiàn)輸入數(shù)據(jù)(之前決策樹算法時(shí)用過的)input.txt: ?123456789101112131415Rid Age Income Student CreditRating BuysComputer1 Youth High No Fair No2 Youth High No Excellent No3 MiddleAged High No Fair Yes4 Senior Medium No Fair Yes5 Senior Low Yes Fair Yes6 Senior Low

8、Yes Excellent No7 MiddleAged Low Yes Excellent Yes8 Youth Medium No Fair No9 Youth Low Yes Fair Yes10 Senior Medium Yes Fair Yes11 Youth Medium Yes Excellent Yes12 MiddleAged Medium No Excellent Yes13 MiddleAged High Yes Fair Yes14 Senior Medium No Excellent No 樹節(jié)點(diǎn)類TreeNode.java: ?12345678

9、910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485package DataMining_RandomForest; import java.util.ArrayList; /* * 回歸分類樹節(jié)點(diǎn) *  * author lyq *  */public class Tree

10、Node     / 節(jié)點(diǎn)屬性名字    private String attrName;    / 節(jié)點(diǎn)索引標(biāo)號(hào)    private int nodeIndex;    /包含的葉子節(jié)點(diǎn)數(shù)    private int leafNum;    / 節(jié)點(diǎn)誤差率    priva

11、te double alpha;    / 父親分類屬性值    private String parentAttrValue;    / 孩子節(jié)點(diǎn)    private TreeNode childAttrNode;    / 數(shù)據(jù)記錄索引    private ArrayList<String> dataIndex;  &

12、#160;  public String getAttrName()         return attrName;         public void setAttrName(String attrName)         this.attrName = attrName;    

13、;     public int getNodeIndex()         return nodeIndex;         public void setNodeIndex(int nodeIndex)         this.nodeIndex = nodeIndex; 

14、60;       public double getAlpha()         return alpha;         public void setAlpha(double alpha)         this.alpha = alpha;  &

15、#160;      public String getParentAttrValue()         return parentAttrValue;         public void setParentAttrValue(String parentAttrValue)        &#

16、160;this.parentAttrValue = parentAttrValue;         public TreeNode getChildAttrNode()         return childAttrNode;         public void setChildAttrNode(TreeNode childAt

17、trNode)         this.childAttrNode = childAttrNode;         public ArrayList<String> getDataIndex()         return dataIndex;       &#

18、160; public void setDataIndex(ArrayList<String> dataIndex)         this.dataIndex = dataIndex;         public int getLeafNum()         return leafNum;  &#

19、160;      public void setLeafNum(int leafNum)         this.leafNum = leafNum;                   決策樹類DecisionTree.java:  ?1234

20、567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371

21、38139140141142143144145146147148149150151152153154155156157158159160161162163164165package DataMining_RandomForest; import java.util.ArrayList;import java.util.HashMap;import java.util.Map; /* * 決策樹 *  * author lyq *  */public class DecisionTree    &

22、#160;/ 樹的根節(jié)點(diǎn)    TreeNode rootNode;    / 數(shù)據(jù)的屬性列名稱    String featureNames;    / 這棵樹所包含的數(shù)據(jù)    ArrayList<String> datas;    / 決策樹構(gòu)造的的工具類    CARTTool tool; 

23、;    public DecisionTree(ArrayList<String> datas)         this.datas = datas;        this.featureNames = datas.get(0);         tool = new CARTTool(da

24、tas);        / 通過CART工具類進(jìn)行決策樹的構(gòu)建，并返回樹的根節(jié)點(diǎn)        rootNode = tool.startBuildingTree();         /*     * 根據(jù)給定的數(shù)據(jù)特征描述進(jìn)行類別的判斷     

25、;*      * param features     * return     */    public String decideClassType(String features)         String classType = ""     &

26、#160;  / 查詢屬性組        String queryFeatures;        / 在本決策樹中對應(yīng)的查詢的屬性值描述        ArrayList<String> featureStrs;         fe

27、atureStrs = new ArrayList<>();        queryFeatures = features.split(",");         String array;        for (String name : featureNames)    

28、0;        for (String featureValue : queryFeatures)                 array = featureValue.split("=");           

29、0;    / 將對應(yīng)的屬性值加入到列表中                if (array0.equals(name)                     featureStrs.add(arr

30、ay);                                             / 開始從根據(jù)節(jié)點(diǎn)往下遞歸搜索  

31、;      classType = recusiveSearchClassType(rootNode, featureStrs);         return classType;         /*     * 遞歸搜索樹，查詢屬性的分類類別     

32、*      * param node     *            當(dāng)前搜索到的節(jié)點(diǎn)     * param remainFeatures     *           

33、剩余未判斷的屬性     * return     */    private String recusiveSearchClassType(TreeNode node,            ArrayList<String> remainFeatures)      

34、60;  String classType = null;         / 如果節(jié)點(diǎn)包含了數(shù)據(jù)的id索引，說明已經(jīng)分類到底了        if (node.getDataIndex() != null && node.getDataIndex().size() > 0)          &

35、#160;  classType = judgeClassType(node.getDataIndex();             return classType;                 / 取出剩余屬性中的一個(gè)匹配屬性作為當(dāng)前的判斷屬性名稱  

36、      String currentFeature = null;        for (String featureValue : remainFeatures)             if (node.getAttrName().equals(featureValue0)     

37、60;           currentFeature = featureValue;                break;                

38、60;            for (TreeNode childNode : node.getChildAttrNode()             / 尋找子節(jié)點(diǎn)中屬于此屬性值的分支            if (childNode.

39、getParentAttrValue().equals(currentFeature1)                 remainFeatures.remove(currentFeature);                classType = recusiveSearc

40、hClassType(childNode, remainFeatures);                 / 如果找到了分類結(jié)果，則直接挑出循環(huán)                break;      

41、60;     else                /進(jìn)行第二種情況的判斷加上!符號(hào)的情況                String value = childNode.getParentAttrValue(); 

42、                                if(value.charAt(0) = '!')            

43、60;       /去掉第一個(gè)！字符                    value = value.substring(1, value.length();              

44、                           if(!value.equals(currentFeature1)                 

45、60;      remainFeatures.remove(currentFeature);                        classType = recusiveSearchClassType(childNode, remainFeatures);  

46、0;                      break;                          

47、0;                                      return classType;         

48、;/*     * 根據(jù)得到的數(shù)據(jù)行分類進(jìn)行類別的決策     *      * param dataIndex     *            根據(jù)分類的數(shù)據(jù)索引號(hào)     * return    

49、; */    public String judgeClassType(ArrayList<String> dataIndex)         / 結(jié)果類型值        String resultClassType = ""        String classTyp

50、e = ""        int count = 0;        int temp = 0;        Map<String, Integer> type2Num = new HashMap<String, Integer>();      &#

51、160;  for (String index : dataIndex)             temp = Integer.parseInt(index);            / 取最后一列的決策類別數(shù)據(jù)          

52、0; classType = datas.get(temp)featureNames.length - 1;             if (type2Num.containsKey(classType)                 / 如果類別已經(jīng)存在，則使其計(jì)數(shù)加1  &

53、#160;             count = type2Num.get(classType);                count+;             else 

54、0;               count = 1;                         type2Num.put(classType, count);   

55、;              / 選出其中類別支持計(jì)數(shù)最多的一個(gè)類別值        count = -1;        for (Map.Entry entry : type2Num.entrySet()        

56、60;    if (int) entry.getValue() > count)                 count = (int) entry.getValue();                resultClassT

57、ype = (String) entry.getKey();                             return resultClassType;    隨機(jī)森林算法工具類RandomForestTool.java:  ?12345

58、678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713

59、8139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223package DataMining_RandomForest; import

60、 java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.io.IOException;import java.util.ArrayList;import java.util.HashMap;import java.util.Map;import java.util.Random; /* * 隨機(jī)森林算法工具類 *  * author lyq *  */public class RandomForestTool  

61、60;  / 測試數(shù)據(jù)文件地址    private String filePath;    / 決策樹的樣本占總數(shù)的占比率    private double sampleNumRatio;    / 樣本數(shù)據(jù)的采集特征數(shù)量占總特征的比例    private double featureNumRatio;    / 決策樹的采樣樣本數(shù)

62、    private int sampleNum;    / 樣本數(shù)據(jù)的采集采樣特征數(shù)    private int featureNum;    / 隨機(jī)森林中的決策樹的數(shù)目,等于總的數(shù)據(jù)數(shù)/用于構(gòu)造每棵樹的數(shù)據(jù)的數(shù)量    private int treeNum;    / 隨機(jī)數(shù)產(chǎn)生器    private R

63、andom random;    / 樣本數(shù)據(jù)列屬性名稱行    private String featureNames;    / 原始的總的數(shù)據(jù)    private ArrayList<String> totalDatas;    / 決策樹森林    private ArrayList<DecisionTree> decisi

64、onForest;     public RandomForestTool(String filePath, double sampleNumRatio,            double featureNumRatio)         this.filePath = filePath;     

65、;   this.sampleNumRatio = sampleNumRatio;        this.featureNumRatio = featureNumRatio;         readDataFile();         /*     *

66、從文件中讀取數(shù)據(jù)     */    private void readDataFile()         File file = new File(filePath);        ArrayList<String> dataArray = new ArrayList<String>();  

67、60;      try             BufferedReader in = new BufferedReader(new FileReader(file);            String str;       

68、     String tempArray;            while (str = in.readLine() != null)                 tempArray = str.split(" ");  

69、              dataArray.add(tempArray);                        in.close();      

70、   catch (IOException e)             e.getStackTrace();                 totalDatas = dataArray;        fe

71、atureNames = totalDatas.get(0);        sampleNum = (int) (totalDatas.size() - 1) * sampleNumRatio);        /算屬性數(shù)量的時(shí)候需要去掉id屬性和決策屬性，用條件屬性計(jì)算        featureNum = (int) (featureNames.le

72、ngth -2) * featureNumRatio);        / 算數(shù)量的時(shí)候需要去掉首行屬性名稱行        treeNum = (totalDatas.size() - 1) / sampleNum;         /*     * 產(chǎn)生決策樹   

73、  */    private DecisionTree produceDecisionTree()         int temp = 0;        DecisionTree tree;        String tempData;    

74、0;   /采樣數(shù)據(jù)的隨機(jī)行號(hào)組        ArrayList<Integer> sampleRandomNum;        /采樣屬性特征的隨機(jī)列號(hào)組        ArrayList<Integer> featureRandomNum;     

75、;   ArrayList<String> datas;                 sampleRandomNum = new ArrayList<>();        featureRandomNum = new ArrayList<>();  

76、0;     datas = new ArrayList<>();                 for(int i=0; i<sampleNum;)            temp = random.nextInt(totalDatas.

77、size();                         /如果是行首屬性名稱行，則跳過            if(temp = 0)       &#

78、160;        continue;                                     if(!sampleRandomN

79、um.contains(temp)                sampleRandomNum.add(temp);                i+;          &#

80、160;                          for(int i=0; i<featureNum;)            temp = random.nextInt(featureNames.len

81、gth);                         /如果是第一列的數(shù)據(jù)id號(hào)或者是決策屬性列，則跳過            if(temp = 0 | temp = featureNames.length-1) 

82、;               continue;                                 &#

83、160;   if(!featureRandomNum.contains(temp)                featureRandomNum.add(temp);                i+;   

84、60;                         String singleRecord;        String headCulumn = null;        / 獲取隨機(jī)

85、數(shù)據(jù)行        for(int dataIndex: sampleRandomNum)            singleRecord = totalDatas.get(dataIndex);                 

86、;        /每行的列數(shù)=所選的特征數(shù)+id號(hào)            tempData = new StringfeatureNum+2;            headCulumn = new StringfeatureNum+2;   &#

87、160;                     for(int i=0,k=1; i<featureRandomNum.size(); i+,k+)                temp = featureRandomN

88、um.get(i);                                 headCulumnk = featureNamestemp;          &

89、#160;     tempDatak = singleRecordtemp;                                     /加上id列的信息 

90、;           headCulumn0 = featureNames0;            /加上決策分類列的信息            headCulumnfeatureNum+1 = featureNamesfeatureNames.

91、length-1;            tempDatafeatureNum+1 = singleRecordfeatureNames.length-1;                         /加入此行數(shù)據(jù) 

92、;           datas.add(tempData);                         /加入行首列出現(xiàn)名稱        datas

93、.add(0, headCulumn);        /對篩選出的數(shù)據(jù)重新做id分配        temp = 0;        for(String array: datas)            /從第2行開始賦值 &

94、#160;          if(temp > 0)                array0 = temp + ""                

95、                     temp+;                         tree = new Decisio

96、nTree(datas);                 return tree;         /*     * 構(gòu)造隨機(jī)森林     */    public void constructRa

97、ndomTree()         DecisionTree tree;        random = new Random();        decisionForest = new ArrayList<>();         System.out

98、.println("下面是隨機(jī)森林中的決策樹：");        / 構(gòu)造決策樹加入森林中        for (int i = 0; i < treeNum; i+)             System.out.println("n決策樹" + (i+1);

99、0;           tree = produceDecisionTree();            decisionForest.add(tree);                 /*&#

100、160;    * 根據(jù)給定的屬性條件進(jìn)行類別的決策     *      * param features     *            給定的已知的屬性描述     * return     

101、*/    public String judgeClassType(String features)         / 結(jié)果類型值        String resultClassType = ""        String classType = "" 

102、60;      int count = 0;        Map<String, Integer> type2Num = new HashMap<String, Integer>();         for (DecisionTree tree : decisionForest)             classType = tree.decideClassType(features);            if (type2Num.containsKey(classType)