文档章节

CART分类回归树算法

一贱书生
 一贱书生
发布于 2017/04/16 20:32
字数 3917
阅读 14
收藏 0

CART算法也是一种决策树分类算法。CART分类回归树算法的本质也是对数据进行分类的,最终数据的表现形式也是以树形的模式展现的,与ID3,C4.5算法不同的是,他的分类标准所采用的算法不同了。下面列出了其中的一些不同之处:

1、CART最后形成的树是一个二叉树,每个节点会分成2个节点,左孩子节点和右孩子节点,而在ID3和C4.5中是按照分类属性的值类型进行划分,于是这就要求CART算法在所选定的属性中又要划分出最佳的属性划分值,节点如果选定了划分属性名称还要确定里面按照那个值做一个二元的划分。

2、CART算法对于属性的值采用的是基于Gini系数值的方式做比较,gini某个属性的某次值的划分的gini指数的值为:

,pk就是分别为正负实例的概率,gini系数越小说明分类纯度越高,可以想象成与熵的定义一样。因此在最后计算的时候我们只取其中值最小的做出划分。最后做比较的时候用的是gini的增益做比较,要对分类号的数据做出一个带权重的gini指数的计算。举一个网上的一个例子:

 

比如体温为恒温时包含哺乳类5个、鸟类2个,则:

体温为非恒温时包含爬行类3个、鱼类3个、两栖类2个,则

所以如果按照“体温为恒温和非恒温”进行划分的话,我们得到GINI的增益(类比信息增益):

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

通过比较每个属性的最小的gini指数值,作为最后的结果。

3、CART算法在把数据进行分类之后,会对树进行一个剪枝,常用的用前剪枝和后剪枝法,而常见的后剪枝发包括代价复杂度剪枝,悲观误差剪枝等等,我写的此次算法采用的是代价复杂度剪枝法。代价复杂度剪枝的算法公式为:

α表示的是每个非叶子节点的误差增益率,可以理解为误差代价,最后选出误差代价最小的一个节点进行剪枝。

里面变量的意思为:

 

是子树中包含的叶子节点个数;

是节点t的误差代价,如果该节点被剪枝;

r(t)是节点t的误差率;

p(t)是节点t上的数据占所有数据的比例。

是子树Tt的误差代价,如果该节点不被剪枝。它等于子树Tt上所有叶子节点的误差代价之和。下面说说我对于这个公式的理解:其实这个公式的本质是对于剪枝前和剪枝后的样本偏差率做一个差值比较,一个好的分类当然是分类后的样本偏差率相较于没分类(就是剪枝掉的时候)的偏差率小,所以这时的值就会大,如果分类前后基本变化不大,则意味着分类不起什么效果,α值的分子位置就小,所以误差代价就小,可以被剪枝。但是一般分类后的偏差率会小于分类前的,因为偏差数在高层节点的时候肯定比子节点的多,子节点偏差数最多与父亲节点一样。

CART算法实现

首先是程序的备用数据,我是把他存在了一个文字中,通过程序进行逐行的读取:

 

[java] view plain copy

 print?

  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 plain copy

 print?

  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分类回归树算法工具类 
  19.  *  
  20.  * @author lyq 
  21.  *  
  22.  */  
  23. public class CARTTool {  
  24.     // 类标号的值类型  
  25.     private final String YES = "Yes";  
  26.     private final String NO = "No";  
  27.   
  28.     // 所有属性的类型总数,在这里就是data源数据的列数  
  29.     private int attrNum;  
  30.     private String filePath;  
  31.     // 初始源数据,用一个二维字符数组存放模仿表格数据  
  32.     private String[][] data;  
  33.     // 数据的属性行的名字  
  34.     private String[] attrNames;  
  35.     // 每个属性的值所有类型  
  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.      * 从文件中读取数据 
  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.      * 首先初始化每种属性的值的所有类型,用于后面的子类熵的计算时用 
  78.      */  
  79.     public void initAttrValue() {  
  80.         ArrayList<String> tempValues;  
  81.   
  82.         // 按照列的方式,从左往右找  
  83.         for (int j = 1; j < attrNum; j++) {  
  84.             // 从一列中的上往下开始寻找值  
  85.             tempValues = new ArrayList<>();  
  86.             for (int i = 1; i < data.length; i++) {  
  87.                 if (!tempValues.contains(data[i][j])) {  
  88.                     // 如果这个属性的值没有添加过,则添加  
  89.                     tempValues.add(data[i][j]);  
  90.                 }  
  91.             }  
  92.   
  93.             // 一列属性的值已经遍历完毕,复制到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.      * 计算机基尼指数 
  106.      *  
  107.      * @param remainData 
  108.      *            剩余数据 
  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.         // 实例总数  
  120.         int total = 0;  
  121.         // 正实例数  
  122.         int posNum = 0;  
  123.         // 负实例数  
  124.         int negNum = 0;  
  125.         // 基尼指数  
  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.                     // 统计正负实例按照属于和不属于值类型进行划分  
  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.                             // 判断此行数据是否为正实例  
  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.         // 返回计算基尼指数  
  153.         return gini;  
  154.     }  
  155.   
  156.     /** 
  157.      * 计算属性划分的最小基尼指数,返回最小的属性值划分和最小的基尼指数,保存在一个数组中 
  158.      *  
  159.      * @param remainData 
  160.      *            剩余谁 
  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.         // 临时变量  
  170.         int tempNum = 0;  
  171.         // 保存属性的值划分时的最小的基尼指数  
  172.         double minGini = Integer.MAX_VALUE;  
  173.         ArrayList<String> valueTypes = attrValue.get(attrName);  
  174.         // 属于此属性值的实例数  
  175.         HashMap<String, Integer> belongNum = new HashMap<>();  
  176.   
  177.         for (String string : valueTypes) {  
  178.             // 重新计数的时候,数字归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.                         // 统计正负实例按照属于和不属于值类型进行划分  
  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.         // 基尼指数数组,保存了基尼指数和此基尼指数的划分属性值  
  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.         // 孩子节点,分类回归树中,每次二元划分,分出2个孩子节点  
  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.             // 二元划分属于属性值的划分  
  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个不相等,就不是同类型的  
  283.                     sameClass = false;  
  284.                     break;  
  285.                 }  
  286.             }  
  287.   
  288.             childNode[i] = new AttrNode();  
  289.             if (!sameClass) {  
  290.                 // 创建新的对象属性,对象的同个引用会出错  
  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.      * 属性划分完毕,进行数据的移除 
  309.      *  
  310.      * @param srcData 
  311.      *            源数据 
  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.         // 待删除数据  
  323.         ArrayList<String[]> selectData = new ArrayList<>();  
  324.         selectData.add(attrNames);  
  325.   
  326.         // 数组数据转化到列表中,方便移除  
  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.                         // 如果匹配这个数据,则移除其他的数据  
  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.             // 如果是划分不属于此类型的数据时,进行移除  
  350.             desData.removeAll(selectData);  
  351.             desDataArray = new String[desData.size()][];  
  352.             desData.toArray(desDataArray);  
  353.         }  
  354.   
  355.         return desDataArray;  
  356.     }  
  357.   
  358.     public void startBuildingTree() {  
  359.         readDataFile();  
  360.         initAttrValue();  
  361.   
  362.         ArrayList<String> remainAttr = new ArrayList<>();  
  363.         // 添加属性,除了最后一个类标号属性  
  364.         for (int i = 1; i < attrNames.length - 1; i++) {  
  365.             remainAttr.add(attrNames[i]);  
  366.         }  
  367.   
  368.         AttrNode rootNode = new AttrNode();  
  369.         buildDecisionTree(rootNode, "", data, remainAttr, false);  
  370.         setIndexAndAlpah(rootNode, 0, false);  
  371.         System.out.println("剪枝前:");  
  372.         showDecisionTree(rootNode, 1);  
  373.         setIndexAndAlpah(rootNode, 0, true);  
  374.         System.out.println("\n剪枝后:");  
  375.         showDecisionTree(rootNode, 1);  
  376.     }  
  377.   
  378.     /** 
  379.      * 显示决策树 
  380.      *  
  381.      * @param node 
  382.      *            待显示的节点 
  383.      * @param blankNum 
  384.      *            行空格符,用于显示树型结构 
  385.      */  
  386.     private void showDecisionTree(AttrNode node, int blankNum) {  
  387.         System.out.println();  
  388.         for (int i = 0; i < blankNum; i++) {  
  389.             System.out.print("    ");  
  390.         }  
  391.         System.out.print("--");  
  392.         // 显示分类的属性值  
  393.         if (node.getParentAttrValue() != null  
  394.                 && node.getParentAttrValue().length() > 0) {  
  395.             System.out.print(node.getParentAttrValue());  
  396.         } else {  
  397.             System.out.print("--");  
  398.         }  
  399.         System.out.print("--");  
  400.   
  401.         if (node.getDataIndex() != null && node.getDataIndex().size() > 0) {  
  402.             String i = node.getDataIndex().get(0);  
  403.             System.out.print("【" + node.getNodeIndex() + "】类别:"  
  404.                     + data[Integer.parseInt(i)][attrNames.length - 1]);  
  405.             System.out.print("[");  
  406.             for (String index : node.getDataIndex()) {  
  407.                 System.out.print(index + ", ");  
  408.             }  
  409.             System.out.print("]");  
  410.         } else {  
  411.             // 递归显示子节点  
  412.             System.out.print("【" + node.getNodeIndex() + ":"  
  413.                     + node.getAttrName() + "】");  
  414.             if (node.getChildAttrNode() != null) {  
  415.                 for (AttrNode childNode : node.getChildAttrNode()) {  
  416.                     showDecisionTree(childNode, 2 * blankNum);  
  417.                 }  
  418.             } else {  
  419.                 System.out.print("【  Child Null】");  
  420.             }  
  421.         }  
  422.     }  
  423.   
  424.     /** 
  425.      * 为节点设置序列号,并计算每个节点的误差率,用于后面剪枝 
  426.      *  
  427.      * @param node 
  428.      *            开始的时候传入的是根节点 
  429.      * @param index 
  430.      *            开始的索引号,从1开始 
  431.      * @param ifCutNode 
  432.      *            是否需要剪枝 
  433.      */  
  434.     private void setIndexAndAlpah(AttrNode node, int index, boolean ifCutNode) {  
  435.         AttrNode tempNode;  
  436.         // 最小误差代价节点,即将被剪枝的节点  
  437.         AttrNode minAlphaNode = null;  
  438.         double minAlpah = Integer.MAX_VALUE;  
  439.         Queue<AttrNode> nodeQueue = new LinkedList<AttrNode>();  
  440.   
  441.         nodeQueue.add(node);  
  442.         while (nodeQueue.size() > 0) {  
  443.             index++;  
  444.             // 从队列头部获取首个节点  
  445.             tempNode = nodeQueue.poll();  
  446.             tempNode.setNodeIndex(index);  
  447.             if (tempNode.getChildAttrNode() != null) {  
  448.                 for (AttrNode childNode : tempNode.getChildAttrNode()) {  
  449.                     nodeQueue.add(childNode);  
  450.                 }  
  451.                 computeAlpha(tempNode);  
  452.                 if (tempNode.getAlpha() < minAlpah) {  
  453.                     minAlphaNode = tempNode;  
  454.                     minAlpah = tempNode.getAlpha();  
  455.                 } else if (tempNode.getAlpha() == minAlpah) {  
  456.                     // 如果误差代价值一样,比较包含的叶子节点个数,剪枝有多叶子节点数的节点  
  457.                     if (tempNode.getLeafNum() > minAlphaNode.getLeafNum()) {  
  458.                         minAlphaNode = tempNode;  
  459.                     }  
  460.                 }  
  461.             }  
  462.         }  
  463.   
  464.         if (ifCutNode) {  
  465.             // 进行树的剪枝,让其左右孩子节点为null  
  466.             minAlphaNode.setChildAttrNode(null);  
  467.         }  
  468.     }  
  469.   
  470.     /** 
  471.      * 为非叶子节点计算误差代价,这里的后剪枝法用的是CCP代价复杂度剪枝 
  472.      *  
  473.      * @param node 
  474.      *            待计算的非叶子节点 
  475.      */  
  476.     private void computeAlpha(AttrNode node) {  
  477.         double rt = 0;  
  478.         double Rt = 0;  
  479.         double alpha = 0;  
  480.         // 当前节点的数据总数  
  481.         int sumNum = 0;  
  482.         // 最少的偏差数  
  483.         int minNum = 0;  
  484.   
  485.         ArrayList<String> dataIndex;  
  486.         ArrayList<AttrNode> leafNodes = new ArrayList<>();  
  487.   
  488.         addLeafNode(node, leafNodes);  
  489.         node.setLeafNum(leafNodes.size());  
  490.         for (AttrNode attrNode : leafNodes) {  
  491.             dataIndex = attrNode.getDataIndex();  
  492.   
  493.             int num = 0;  
  494.             sumNum += dataIndex.size();  
  495.             for (String s : dataIndex) {  
  496.                 // 统计分类数据中的正负实例数  
  497.                 if (data[Integer.parseInt(s)][attrNames.length - 1].equals(YES)) {  
  498.                     num++;  
  499.                 }  
  500.             }  
  501.             minNum += num;  
  502.   
  503.             // 取小数量的值部分  
  504.             if (1.0 * num / dataIndex.size() > 0.5) {  
  505.                 num = dataIndex.size() - num;  
  506.             }  
  507.   
  508.             rt += (1.0 * num / (data.length - 1));  
  509.         }  
  510.           
  511.         //同样取出少偏差的那部分  
  512.         if (1.0 * minNum / sumNum > 0.5) {  
  513.             minNum = sumNum - minNum;  
  514.         }  
  515.   
  516.         Rt = 1.0 * minNum / (data.length - 1);  
  517.         alpha = 1.0 * (Rt - rt) / (leafNodes.size() - 1);  
  518.         node.setAlpha(alpha);  
  519.     }  
  520.   
  521.     /** 
  522.      * 筛选出节点所包含的叶子节点数 
  523.      *  
  524.      * @param node 
  525.      *            待筛选节点 
  526.      * @param leafNode 
  527.      *            叶子节点列表容器 
  528.      */  
  529.     private void addLeafNode(AttrNode node, ArrayList<AttrNode> leafNode) {  
  530.         ArrayList<String> dataIndex;  
  531.   
  532.         if (node.getChildAttrNode() != null) {  
  533.             for (AttrNode childNode : node.getChildAttrNode()) {  
  534.                 dataIndex = childNode.getDataIndex();  
  535.                 if (dataIndex != null && dataIndex.size() > 0) {  
  536.                     // 说明此节点为叶子节点  
  537.                     leafNode.add(childNode);  
  538.                 } else {  
  539.                     // 如果还是非叶子节点则继续递归调用  
  540.                     addLeafNode(childNode, leafNode);  
  541.                 }  
  542.             }  
  543.         }  
  544.     }  
  545.   
  546. }  

AttrNode节点的设计和属性:

 

 

[java] view plain copy

 print?

  1. /** 
  2.  * 回归分类树节点 
  3.  *  
  4.  * @author lyq 
  5.  *  
  6.  */  
  7. public class AttrNode {  
  8.     // 节点属性名字  
  9.     private String attrName;  
  10.     // 节点索引标号  
  11.     private int nodeIndex;  
  12.     //包含的叶子节点数  
  13.     private int leafNum;  
  14.     // 节点误差率  
  15.     private double alpha;  
  16.     // 父亲分类属性值  
  17.     private String parentAttrValue;  
  18.     // 孩子节点  
  19.     private AttrNode[] childAttrNode;  
  20.     // 数据记录索引  
  21.     private ArrayList<String> dataIndex;  
  22.     .....  

get,set方法自行补上。客户端的场景调用:

 

 

[java] view plain copy

 print?

  1. package DataMing_CART;  
  2.   
  3. public class Client {  
  4.     public static void main(String[] args){  
  5.         String filePath = "C:\\Users\\lyq\\Desktop\\icon\\input.txt";  
  6.           
  7.         CARTTool tool = new CARTTool(filePath);  
  8.           
  9.         tool.startBuildingTree();  
  10.     }  
  11. }  

数据文件路径自行修改,否则会报错(特殊情况懒得处理了.....)。最后程序的输出结果,请自行从左往右看,从上往下,左边的是父亲节点,上面的是考前的子节点:

 

 

[java] view plain copy

 print?

  1. 剪枝前:  
  2.   
  3.     --!--【1:Age】  
  4.         --MiddleAged--【2】类别:Yes[3, 7, 12, 13, ]  
  5.         --!MiddleAged--【3:Student】  
  6.                 --No--【4:Income】  
  7.                                 --High--【6】类别:No[1, 2, ]  
  8.                                 --!High--【7:CreditRating】  
  9.                                                                 --Fair--【10】类别:Yes[4, 8, ]  
  10.                                                                 --!Fair--【11】类别:No[14, ]  
  11.                 --!No--【5:CreditRating】  
  12.                                 --Fair--【8】类别:Yes[5, 9, 10, ]  
  13.                                 --!Fair--【9:Income】  
  14.                                                                 --Medium--【12】类别:Yes[11, ]  
  15.                                                                 --!Medium--【13】类别:No[6, ]  
  16. 剪枝后:  
  17.   
  18.     --!--【1:Age】  
  19.         --MiddleAged--【2】类别:Yes[3, 7, 12, 13, ]  
  20.         --!MiddleAged--【3:Student】  
  21.                 --No--【4:Income】【  Child Null】  
  22.                 --!No--【5:CreditRating】  
  23.                                 --Fair--【8】类别:Yes[5, 9, 10, ]  
  24.                                 --!Fair--【9:Income】  
  25.                                                                 --Medium--【12】类别:Yes[11, ]  
  26.                                                                 --!Medium--【13】类别:No[6, ]  

 

结果分析:

我在一开始的时候根据的是最后分类的数据是否为同一个类标识的,如果都为YES或者都为NO的,分类终止,一般情况下都说的通,但是如果最后属性划分完毕了,剩余的数据还有存在类标识不一样的情况就会偏差,比如说这里的7号CredaRating节点,下面Fair分支中的[4,8]就不是同类的。所以在后面的剪枝算法就被剪枝了。因为后面的4和7号节点的误差代价率为0,说明分类前后没有类偏差变化,这也见证了后剪枝算法的威力所在了。

在coding遇到的困难和改进的地方:

1、先说说在编码时遇到的困难,在对节点进行赋索引标号值的时候出了问题,因为是之前生成树的时候采用了DFS的思想,如果编号时也采用此方法就不对了,于是就用到了把节点取出放入队列这样的遍历方式,就是BFS的方式为节点标号。

2、程序的一个改进的地方在于算一个非叶子节点的时候需要计算他所包含的叶子节点数,采用了从当前节点开始从上往下递归计算,而且每个非叶子节点都计算一遍,显然这样做的效率是不高,后来想到了一种从叶子节点开始计算,从下往上直到根节点,对父亲节点的非叶子节点列表做更新操作,就只要计算一次,这有点dp的思想在里面了,由于时间关系,没有来得及实现。

3、第二个优化点就是后剪枝算法的多样化,我这里采用的是CCP代价复杂度算法,大家可以试着实现其他的诸如悲观误差算法进行剪枝,看看能不能把程序中4和7号节点识别出来,并且剪枝掉。

本文转载自:http://blog.csdn.net/androidlushangderen/article/details/42558235

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
诞生即有理---CART(Classification And Regression Tree)

我将CART独立于其他经典决策树算法的原因是CART相对来说较为复杂。因为它不仅仅可以作为分类树,还可以作为回归树。 CART分类树算法 对于对于CART分类树,这就和我们之前所说的《经典决策树算...

香橙云子
2018/10/30
0
0
人工智能之机器学习CART算法解析

  人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下CART算法。   我们知道十大机器学习中决策树算法占有两席位置,即C4.5算法和CART算法,可见CART算...

数据星河
2018/11/29
0
0
《机器学习实战》 第九章 树回归

线性回归模型需要拟合所有样本(除局部加权线性回归外),当数据拥有众多特征且特征间关系十分复杂时,构建全局模型就显得太难了。一种可行的方法是将数据集切分成很多份易建模的数据,然后利...

wanty_chen
2018/04/24
0
0
轻松入门机器学习之概念总结(一)

欢迎大家前往腾讯云社区,获取更多腾讯海量技术实践干货哦~ 作者:许敏 前言 1,机器学习算法分类 1)监督学习: 有train set,train set里面y的取值已知。 2)无监督学习:有train set, tr...

云加社区
2017/12/15
0
0
Python3机器学习实践:集成学习之AdaBoost

一、AdaBoost初识 这个方法主要涉及到2种权重: 样本权重:每个样本都对应一个权重。在构建第一个弱模型之前,所有训练样本的权重是一样的。第一个模型完成后,要加大那些被这个模型错误分类...

AiFan
2018/11/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

泛型就这么简单

前言 从今天开始进入Java基础的复习,可能一个星期会有一篇的<十道简单算法>,我写博文的未必都是正确的~如果有写错的地方请大家多多包涵并指正~ 今天要复习的是泛型,泛型在Java中也是个很...

群星纪元
19分钟前
0
0
大数据提醒你:中国这些古建筑,可能是下一个巴黎圣母院!

大家晚上好,我是今天的提笔人嗅嗅。 巴黎圣母院失火事件让我的心情很沉重,一句无关痛痒的安慰“巴黎不哭”,已经不能表达我对这场文化之殇的惋惜之痛,人类伟大的建筑在一瞬间被毁灭。 世界...

forespider
30分钟前
0
0
mysql函数substring_index的用法

substring_index 按索引字符位进行截取字符串 substring_index(“待截取的字符串”,“截取数据依据的字符”,截取字符的位置N) 第三个参数可正,可负。正数表示索引字符前面的字符串,负数...

echojson
30分钟前
0
0
好程序员web前端分享用CSS和JS打造一个简单的图片编辑器

好程序员web前端分享用CSS和JS打造一个简单的图片编辑器,本文主要是利用CSS的 filter和简单的Jquery代码来实现一个简单的图片编辑器,包括对图片的透明度,黑白,图片亮度等调节。 CSS filt...

好程序员IT
40分钟前
2
0
浅析spring mvc的细节

spring mvc 整体结构 系统监听到请求 -> 通知tomcat -> 根据web.xml 通知相应的拦截器(spring mvc 通常指DispatcherServlet) --> 检查url是否有相匹配的请求实现 --> 拿到请求实现bean的适配...

最爱肉肉
42分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部