99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀CART分類回歸樹(shù)算法
CART分類回歸樹(shù)算法
2015-12-03
收藏

CART分類回歸樹(shù)算法


    CART分類回歸樹(shù)算法

與上次文章中提到的ID3算法和C4.5算法類似，CART算法也是一種決策樹(shù)分類算法。CART分類回歸樹(shù)算法的本質(zhì)也是對(duì)數(shù)據(jù)進(jìn)行分類的，最終數(shù)據(jù)的表現(xiàn)形式也是以樹(shù)形的模式展現(xiàn)的，與ID3，C4.5算法不同的是，他的分類標(biāo)準(zhǔn)所采用的算法不同了。下面列出了其中的一些不同之處：

1、CART最后形成的樹(shù)是一個(gè)二叉樹(shù)，每個(gè)節(jié)點(diǎn)會(huì)分成2個(gè)節(jié)點(diǎn)，左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)，而在ID3和C4.5中是按照分類屬性的值類型進(jìn)行劃分，于是這就要求CART算法在所選定的屬性中又要?jiǎng)澐殖鲎罴训膶傩詣澐种?，?jié)點(diǎn)如果選定了劃分屬性名稱還要確定里面按照那個(gè)值做一個(gè)二元的劃分。

2、CART算法對(duì)于屬性的值采用的是基于Gini系數(shù)值的方式做比較，gini某個(gè)屬性的某次值的劃分的gini指數(shù)的值為：

，pk就是分別為正負(fù)實(shí)例的概率，gini系數(shù)越小說(shuō)明分類純度越高，可以想象成與熵的定義一樣。因此在最后計(jì)算的時(shí)候我們只取其中值最小的做出劃分。最后做比較的時(shí)候用的是gini的增益做比較，要對(duì)分類號(hào)的數(shù)據(jù)做出一個(gè)帶權(quán)重的gini指數(shù)的計(jì)算。舉一個(gè)網(wǎng)上的一個(gè)例子：

比如體溫為恒溫時(shí)包含哺乳類5個(gè)、鳥(niǎo)類2個(gè)，則：

體溫為非恒溫時(shí)包含爬行類3個(gè)、魚(yú)類3個(gè)、兩棲類2個(gè),則

所以如果按照“體溫為恒溫和非恒溫”進(jìn)行劃分的話，我們得到GINI的增益（類比信息增益）：

最好的劃分就是使得GINI_Gain最小的劃分。

通過(guò)比較每個(gè)屬性的最小的gini指數(shù)值，作為最后的結(jié)果。

3、CART算法在把數(shù)據(jù)進(jìn)行分類之后，會(huì)對(duì)樹(shù)進(jìn)行一個(gè)剪枝，常用的用前剪枝和后剪枝法，而常見(jiàn)的后剪枝發(fā)包括代價(jià)復(fù)雜度剪枝，悲觀誤差剪枝等等，我寫(xiě)的此次算法采用的是代價(jià)復(fù)雜度剪枝法。代價(jià)復(fù)雜度剪枝的算法公式為：

α表示的是每個(gè)非葉子節(jié)點(diǎn)的誤差增益率，可以理解為誤差代價(jià)，最后選出誤差代價(jià)最小的一個(gè)節(jié)點(diǎn)進(jìn)行剪枝。

里面變量的意思為：

是子樹(shù)中包含的葉子節(jié)點(diǎn)個(gè)數(shù);

是節(jié)點(diǎn)t的誤差代價(jià)，如果該節(jié)點(diǎn)被剪枝;

r(t)是節(jié)點(diǎn)t的誤差率;

p(t)是節(jié)點(diǎn)t上的數(shù)據(jù)占所有數(shù)據(jù)的比例。

是子樹(shù)Tt的誤差代價(jià)，如果該節(jié)點(diǎn)不被剪枝。它等于子樹(shù)Tt上所有葉子節(jié)點(diǎn)的誤差代價(jià)之和。下面說(shuō)說(shuō)我對(duì)于這個(gè)公式的理解：其實(shí)這個(gè)公式的本質(zhì)是對(duì)于剪枝前和剪枝后的樣本偏差率做一個(gè)差值比較，一個(gè)好的分類當(dāng)然是分類后的樣本偏差率相較于沒(méi)分類（就是剪枝掉的時(shí)候）的偏差率小，所以這時(shí)的值就會(huì)大，如果分類前后基本變化不大，則意味著分類不起什么效果，α值的分子位置就小，所以誤差代價(jià)就小，可以被剪枝。但是一般分類后的偏差率會(huì)小于分類前的，因?yàn)?a href='/map/piancha/' style='color:#000;font-size:inherit;'>偏差數(shù)在高層節(jié)點(diǎn)的時(shí)候肯定比子節(jié)點(diǎn)的多，子節(jié)點(diǎn)偏差數(shù)最多與父親節(jié)點(diǎn)一樣。

CART算法實(shí)現(xiàn)

首先是程序的備用數(shù)據(jù)，我是把他存在了一個(gè)文字中，通過(guò)程序進(jìn)行逐行的讀取：

[java] view plaincopyprint?
  1. Rid Age Income Student CreditRating BuysComputer  
  2. 1 Youth High No Fair No  
  3. 2 Youth High No Excellent No  
  4. 3 MiddleAged High No Fair Yes  
  5. 4 Senior Medium No Fair Yes  
  6. 5 Senior Low Yes Fair Yes  
  7. 6 Senior Low Yes Excellent No  
  8. 7 MiddleAged Low Yes Excellent Yes  
  9. 8 Youth Medium No Fair No  
  10. 9 Youth Low Yes Fair Yes  
  11. 10 Senior Medium Yes Fair Yes  
  12. 11 Youth Medium Yes Excellent Yes  
  13. 12 MiddleAged Medium No Excellent Yes  
  14. 13 MiddleAged High Yes Fair Yes  
  15. 14 Senior Medium No Excellent No  

下面是主程序，里面有具體的注釋：

[java] view plaincopyprint?
  1. package DataMing_CART;  
  2.   
  3. import java.io.BufferedReader;  
  4. import java.io.File;  
  5. import java.io.FileReader;  
  6. import java.io.IOException;  
  7. import java.util.ArrayList;  
  8. import java.util.HashMap;  
  9. import java.util.LinkedList;  
  10. import java.util.Map;  
  11. import java.util.Queue;  
  12.   
  13. import javax.lang.model.element.NestingKind;  
  14. import javax.swing.text.DefaultEditorKit.CutAction;  
  15. import javax.swing.text.html.MinimalHTMLWriter;  
  16.   
  17. /** 
  18.  * CART分類回歸樹(shù)算法工具類 
  19.  *  
  20.  * @author lyq 
  21.  *  
  22.  */  
  23. public class CARTTool {  
  24.     // 類標(biāo)號(hào)的值類型  
  25.     private final String YES = "Yes";  
  26.     private final String NO = "No";  
  27.   
  28.     // 所有屬性的類型總數(shù),在這里就是data源數(shù)據(jù)的列數(shù)  
  29.     private int attrNum;  
  30.     private String filePath;  
  31.     // 初始源數(shù)據(jù)，用一個(gè)二維字符數(shù)組存放模仿表格數(shù)據(jù)  
  32.     private String[][] data;  
  33.     // 數(shù)據(jù)的屬性行的名字  
  34.     private String[] attrNames;  
  35.     // 每個(gè)屬性的值所有類型  
  36.     private HashMap<String, ArrayList<String>> attrValue;  
  37.   
  38.     public CARTTool(String filePath) {  
  39.         this.filePath = filePath;  
  40.         attrValue = new HashMap<>();  
  41.     }  
  42.   
  43.     /** 
  44.      * 從文件中讀取數(shù)據(jù) 
  45.      */  
  46.     public void readDataFile() {  
  47.         File file = new File(filePath);  
  48.         ArrayList<String[]> dataArray = new ArrayList<String[]>();  
  49.   
  50.         try {  
  51.             BufferedReader in = new BufferedReader(new FileReader(file));  
  52.             String str;  
  53.             String[] tempArray;  
  54.             while ((str = in.readLine()) != null) {  
  55.                 tempArray = str.split(" ");  
  56.                 dataArray.add(tempArray);  
  57.             }  
  58.             in.close();  
  59.         } catch (IOException e) {  
  60.             e.getStackTrace();  
  61.         }  
  62.   
  63.         data = new String[dataArray.size()][];  
  64.         dataArray.toArray(data);  
  65.         attrNum = data[0].length;  
  66.         attrNames = data[0];  
  67.   
  68.         /* 
  69.          * for (int i = 0; i < data.length; i++) { for (int j = 0; j < 
  70.          * data[0].length; j++) { System.out.print(" " + data[i][j]); } 
  71.          * System.out.print("\n"); } 
  72.          */  
  73.   
  74.     }  
  75.   
  76.     /** 
  77.      * 首先初始化每種屬性的值的所有類型，用于后面的子類熵的計(jì)算時(shí)用 
  78.      */  
  79.     public void initAttrValue() {  
  80.         ArrayList<String> tempValues;  
  81.   
  82.         // 按照列的方式，從左往右找  
  83.         for (int j = 1; j < attrNum; j++) {  
  84.             // 從一列中的上往下開(kāi)始尋找值  
  85.             tempValues = new ArrayList<>();  
  86.             for (int i = 1; i < data.length; i++) {  
  87.                 if (!tempValues.contains(data[i][j])) {  
  88.                     // 如果這個(gè)屬性的值沒(méi)有添加過(guò)，則添加  
  89.                     tempValues.add(data[i][j]);  
  90.                 }  
  91.             }  
  92.   
  93.             // 一列屬性的值已經(jīng)遍歷完畢，復(fù)制到map屬性表中  
  94.             attrValue.put(data[0][j], tempValues);  
  95.         }  
  96.   
  97.         /* 
  98.          * for (Map.Entry entry : attrValue.entrySet()) { 
  99.          * System.out.println("key:value " + entry.getKey() + ":" + 
  100.          * entry.getValue()); } 
  101.          */  
  102.     }  
  103.   
  104.     /** 
  105.      * 計(jì)算機(jī)基尼指數(shù) 
  106.      *  
  107.      * @param remainData 
  108.      *            剩余數(shù)據(jù) 
  109.      * @param attrName 
  110.      *            屬性名稱 
  111.      * @param value 
  112.      *            屬性值 
  113.      * @param beLongValue 
  114.      *            分類是否屬于此屬性值 
  115.      * @return 
  116.      */  
  117.     public double computeGini(String[][] remainData, String attrName,  
  118.             String value, boolean beLongValue) {  
  119.         // 實(shí)例總數(shù)  
  120.         int total = 0;  
  121.         // 正實(shí)例數(shù)  
  122.         int posNum = 0;  
  123.         // 負(fù)實(shí)例數(shù)  
  124.         int negNum = 0;  
  125.         // 基尼指數(shù)  
  126.         double gini = 0;  
  127.   
  128.         // 還是按列從左往右遍歷屬性  
  129.         for (int j = 1; j < attrNames.length; j++) {  
  130.             // 找到了指定的屬性  
  131.             if (attrName.equals(attrNames[j])) {  
  132.                 for (int i = 1; i < remainData.length; i++) {  
  133.                     // 統(tǒng)計(jì)正負(fù)實(shí)例按照屬于和不屬于值類型進(jìn)行劃分  
  134.                     if ((beLongValue && remainData[i][j].equals(value))  
  135.                             || (!beLongValue && !remainData[i][j].equals(value))) {  
  136.                         if (remainData[i][attrNames.length - 1].equals(YES)) {  
  137.                             // 判斷此行數(shù)據(jù)是否為正實(shí)例  
  138.                             posNum++;  
  139.                         } else {  
  140.                             negNum++;  
  141.                         }  
  142.                     }  
  143.                 }  
  144.             }  
  145.         }  
  146.   
  147.         total = posNum + negNum;  
  148.         double posProbobly = (double) posNum / total;  
  149.         double negProbobly = (double) negNum / total;  
  150.         gini = 1 - posProbobly * posProbobly - negProbobly * negProbobly;  
  151.   
  152.         // 返回計(jì)算基尼指數(shù)  
  153.         return gini;  
  154.     }  
  155.   
  156.     /** 
  157.      * 計(jì)算屬性劃分的最小基尼指數(shù)，返回最小的屬性值劃分和最小的基尼指數(shù)，保存在一個(gè)數(shù)組中 
  158.      *  
  159.      * @param remainData 
  160.      *            剩余誰(shuí) 
  161.      * @param attrName 
  162.      *            屬性名稱 
  163.      * @return 
  164.      */  
  165.     public String[] computeAttrGini(String[][] remainData, String attrName) {  
  166.         String[] str = new String[2];  
  167.         // 最終該屬性的劃分類型值  
  168.         String spiltValue = "";  
  169.         // 臨時(shí)變量  
  170.         int tempNum = 0;  
  171.         // 保存屬性的值劃分時(shí)的最小的基尼指數(shù)  
  172.         double minGini = Integer.MAX_VALUE;  
  173.         ArrayList<String> valueTypes = attrValue.get(attrName);  
  174.         // 屬于此屬性值的實(shí)例數(shù)  
  175.         HashMap<String, Integer> belongNum = new HashMap<>();  
  176.   
  177.         for (String string : valueTypes) {  
  178.             // 重新計(jì)數(shù)的時(shí)候，數(shù)字歸0  
  179.             tempNum = 0;  
  180.             // 按列從左往右遍歷屬性  
  181.             for (int j = 1; j < attrNames.length; j++) {  
  182.                 // 找到了指定的屬性  
  183.                 if (attrName.equals(attrNames[j])) {  
  184.                     for (int i = 1; i < remainData.length; i++) {  
  185.                         // 統(tǒng)計(jì)正負(fù)實(shí)例按照屬于和不屬于值類型進(jìn)行劃分  
  186.                         if (remainData[i][j].equals(string)) {  
  187.                             tempNum++;  
  188.                         }  
  189.                     }  
  190.                 }  
  191.             }  
  192.   
  193.             belongNum.put(string, tempNum);  
  194.         }  
  195.   
  196.         double tempGini = 0;  
  197.         double posProbably = 1.0;  
  198.         double negProbably = 1.0;  
  199.         for (String string : valueTypes) {  
  200.             tempGini = 0;  
  201.   
  202.             posProbably = 1.0 * belongNum.get(string) / (remainData.length - 1);  
  203.             negProbably = 1 - posProbably;  
  204.   
  205.             tempGini += posProbably  
  206.                     * computeGini(remainData, attrName, string, true);  
  207.             tempGini += negProbably  
  208.                     * computeGini(remainData, attrName, string, false);  
  209.   
  210.             if (tempGini < minGini) {  
  211.                 minGini = tempGini;  
  212.                 spiltValue = string;  
  213.             }  
  214.         }  
  215.   
  216.         str[0] = spiltValue;  
  217.         str[1] = minGini + "";  
  218.   
  219.         return str;  
  220.     }  
  221.   
  222.     public void buildDecisionTree(AttrNode node, String parentAttrValue,  
  223.             String[][] remainData, ArrayList<String> remainAttr,  
  224.             boolean beLongParentValue) {  
  225.         // 屬性劃分值  
  226.         String valueType = "";  
  227.         // 劃分屬性名稱  
  228.         String spiltAttrName = "";  
  229.         double minGini = Integer.MAX_VALUE;  
  230.         double tempGini = 0;  
  231.         // 基尼指數(shù)數(shù)組，保存了基尼指數(shù)和此基尼指數(shù)的劃分屬性值  
  232.         String[] giniArray;  
  233.   
  234.         if (beLongParentValue) {  
  235.             node.setParentAttrValue(parentAttrValue);  
  236.         } else {  
  237.             node.setParentAttrValue("!" + parentAttrValue);  
  238.         }  
  239.   
  240.         if (remainAttr.size() == 0) {  
  241.             if (remainData.length > 1) {  
  242.                 ArrayList<String> indexArray = new ArrayList<>();  
  243.                 for (int i = 1; i < remainData.length; i++) {  
  244.                     indexArray.add(remainData[i][0]);  
  245.                 }  
  246.                 node.setDataIndex(indexArray);  
  247.             }  
  248.             System.out.println("attr remain null");  
  249.             return;  
  250.         }  
  251.   
  252.         for (String str : remainAttr) {  
  253.             giniArray = computeAttrGini(remainData, str);  
  254.             tempGini = Double.parseDouble(giniArray[1]);  
  255.   
  256.             if (tempGini < minGini) {  
  257.                 spiltAttrName = str;  
  258.                 minGini = tempGini;  
  259.                 valueType = giniArray[0];  
  260.             }  
  261.         }  
  262.         // 移除劃分屬性  
  263.         remainAttr.remove(spiltAttrName);  
  264.         node.setAttrName(spiltAttrName);  
  265.   
  266.         // 孩子節(jié)點(diǎn),分類回歸樹(shù)中，每次二元?jiǎng)澐郑殖?個(gè)孩子節(jié)點(diǎn)  
  267.         AttrNode[] childNode = new AttrNode[2];  
  268.         String[][] rData;  
  269.   
  270.         boolean[] bArray = new boolean[] { true, false };  
  271.         for (int i = 0; i < bArray.length; i++) {  
  272.             // 二元?jiǎng)澐謱儆趯傩灾档膭澐?nbsp; 
  273.             rData = removeData(remainData, spiltAttrName, valueType, bArray[i]);  
  274.   
  275.             boolean sameClass = true;  
  276.             ArrayList<String> indexArray = new ArrayList<>();  
  277.             for (int k = 1; k < rData.length; k++) {  
  278.                 indexArray.add(rData[k][0]);  
  279.                 // 判斷是否為同一類的  
  280.                 if (!rData[k][attrNames.length - 1]  
  281.                         .equals(rData[1][attrNames.length - 1])) {  
  282.                     // 只要有1個(gè)不相等，就不是同類型的  
  283.                     sameClass = false;  
  284.                     break;  
  285.                 }  
  286.             }  
  287.   
  288.             childNode[i] = new AttrNode();  
  289.             if (!sameClass) {  
  290.                 // 創(chuàng)建新的對(duì)象屬性，對(duì)象的同個(gè)引用會(huì)出錯(cuò)  
  291.                 ArrayList<String> rAttr = new ArrayList<>();  
  292.                 for (String str : remainAttr) {  
  293.                     rAttr.add(str);  
  294.                 }  
  295.                 buildDecisionTree(childNode[i], valueType, rData, rAttr,  
  296.                         bArray[i]);  
  297.             } else {  
  298.                 String pAtr = (bArray[i] ? valueType : "!" + valueType);  
  299.                 childNode[i].setParentAttrValue(pAtr);  
  300.                 childNode[i].setDataIndex(indexArray);  
  301.             }  
  302.         }  
  303.   
  304.         node.setChildAttrNode(childNode);  
  305.     }  
  306.   
  307.     /** 
  308.      * 屬性劃分完畢，進(jìn)行數(shù)據(jù)的移除 
  309.      *  
  310.      * @param srcData 
  311.      *            源數(shù)據(jù) 
  312.      * @param attrName 
  313.      *            劃分的屬性名稱 
  314.      * @param valueType 
  315.      *            屬性的值類型 
  316.      * @parame beLongValue 分類是否屬于此值類型 
  317.      */  
  318.     private String[][] removeData(String[][] srcData, String attrName,  
  319.             String valueType, boolean beLongValue) {  
  320.         String[][] desDataArray;  
  321.         ArrayList<String[]> desData = new ArrayList<>();  
  322.         // 待刪除數(shù)據(jù)  
  323.         ArrayList<String[]> selectData = new ArrayList<>();  
  324.         selectData.add(attrNames);  
  325.   
  326.         // 數(shù)組數(shù)據(jù)轉(zhuǎn)化到列表中，方便移除  
  327.         for (int i = 0; i < srcData.length; i++) {  
  328.             desData.add(srcData[i]);  
  329.         }  
  330.   
  331.         // 還是從左往右一列列的查找  
  332.         for (int j = 1; j < attrNames.length; j++) {  
  333.             if (attrNames[j].equals(attrName)) {  
  334.                 for (int i = 1; i < desData.size(); i++) {  
  335.                     if (desData.get(i)[j].equals(valueType)) {  
  336.                         // 如果匹配這個(gè)數(shù)據(jù)，則移除其他的數(shù)據(jù)  
  337.                         selectData.add(desData.get(i));  
  338.                     }  
  339.                 }  
  340.             }  
  341.         }  
  342.   
  343.         if (beLongValue) {  
  344.             desDataArray = new String[selectData.size()][];  
  345.             selectData.toArray(desDataArray);  
  346.         } else {  
  347.             // 屬性名稱行不移除  
  348.             selectData.remove(attrNames);  
  349.             // 如果是劃分不屬于此類型的數(shù)據(jù)時(shí)，進(jìn)行移除  
  350.             desData.removeAll(selectData);  
  351.             desDataArray = new String[desData.size()][];  
  352.      &

數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼，搜微信號(hào)：CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象，之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說(shuō)明請(qǐng)參見(jiàn)：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }