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

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀決策分類樹(shù)算法之ID3，C4.5算法系列
決策分類樹(shù)算法之ID3，C4.5算法系列
2015-12-03
收藏

決策分類樹(shù)算法之ID3，C4.5算法系列


一、引言

在最開(kāi)始的時(shí)候，我本來(lái)準(zhǔn)備學(xué)習(xí)的是C4.5算法，后來(lái)發(fā)現(xiàn)C4.5算法的核心還是ID3算法，所以又輾轉(zhuǎn)回到學(xué)習(xí)ID3算法了，因?yàn)镃4.5是他的一個(gè)改進(jìn)。至于是什么改進(jìn)，在后面的描述中我會(huì)提到。

二、ID3算法

ID3算法是一種分類決策樹(shù)算法。他通過(guò)一系列的規(guī)則，將數(shù)據(jù)最后分類成決策樹(shù)的形式。分類的根據(jù)是用到了熵這個(gè)概念。熵在物理這門學(xué)科中就已經(jīng)出現(xiàn)過(guò)，表示是一個(gè)物質(zhì)的穩(wěn)定度，在這里就是分類的純度的一個(gè)概念。公式為：

在ID3算法中，是采用Gain信息增益來(lái)作為一個(gè)分類的判定標(biāo)準(zhǔn)的。他的定義為：

每次選擇屬性中信息增益最大作為劃分屬性，在這里本人實(shí)現(xiàn)了一個(gè)java版本的ID3算法，為了模擬數(shù)據(jù)的可操作性，就把數(shù)據(jù)寫到一個(gè)input.txt文件中，作為數(shù)據(jù)源，格式如下：

[java] view plaincopyprint?
  1. Day OutLook Temperature Humidity Wind PlayTennis  
  2. 1 Sunny Hot High Weak No  
  3. 2 Sunny Hot High Strong No  
  4. 3 Overcast Hot High Weak Yes  
  5. 4 Rainy Mild High Weak Yes  
  6. 5 Rainy Cool Normal Weak Yes  
  7. 6 Rainy Cool Normal Strong No  
  8. 7 Overcast Cool Normal Strong Yes  
  9. 8 Sunny Mild High Weak No  
  10. 9 Sunny Cool Normal Weak Yes  
  11. 10 Rainy Mild Normal Weak Yes  
  12. 11 Sunny Mild Normal Strong Yes  
  13. 12 Overcast Mild High Strong Yes  
  14. 13 Overcast Hot Normal Weak Yes  
  15. 14 Rainy Mild High Strong No  

PalyTennis屬性為結(jié)構(gòu)屬性，是作為類標(biāo)識(shí)用的，中間的OutLool,Temperature,Humidity,Wind才是劃分屬性，通過(guò)將源數(shù)據(jù)與執(zhí)行程序分類，這樣可以模擬巨大的數(shù)據(jù)量了。下面是ID3的主程序類，本人將ID3的算法進(jìn)行了包裝，對(duì)外只開(kāi)放了一個(gè)構(gòu)建決策樹(shù)的方法，在構(gòu)造函數(shù)時(shí)候，只需傳入一個(gè)數(shù)據(jù)路徑文件即可：

[java] view plaincopyprint?
  1. package DataMing_ID3;  
  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.Iterator;  
  10. import java.util.Map;  
  11. import java.util.Map.Entry;  
  12. import java.util.Set;  
  13.   
  14. /** 
  15.  * ID3算法實(shí)現(xiàn)類 
  16.  *  
  17.  * @author lyq 
  18.  *  
  19.  */  
  20. public class ID3Tool {  
  21.     // 類標(biāo)號(hào)的值類型  
  22.     private final String YES = "Yes";  
  23.     private final String NO = "No";  
  24.   
  25.     // 所有屬性的類型總數(shù),在這里就是data源數(shù)據(jù)的列數(shù)  
  26.     private int attrNum;  
  27.     private String filePath;  
  28.     // 初始源數(shù)據(jù)，用一個(gè)二維字符數(shù)組存放模仿表格數(shù)據(jù)  
  29.     private String[][] data;  
  30.     // 數(shù)據(jù)的屬性行的名字  
  31.     private String[] attrNames;  
  32.     // 每個(gè)屬性的值所有類型  
  33.     private HashMap<String, ArrayList<String>> attrValue;  
  34.   
  35.     public ID3Tool(String filePath) {  
  36.         this.filePath = filePath;  
  37.         attrValue = new HashMap<>();  
  38.     }  
  39.   
  40.     /** 
  41.      * 從文件中讀取數(shù)據(jù) 
  42.      */  
  43.     private void readDataFile() {  
  44.         File file = new File(filePath);  
  45.         ArrayList<String[]> dataArray = new ArrayList<String[]>();  
  46.   
  47.         try {  
  48.             BufferedReader in = new BufferedReader(new FileReader(file));  
  49.             String str;  
  50.             String[] tempArray;  
  51.             while ((str = in.readLine()) != null) {  
  52.                 tempArray = str.split(" ");  
  53.                 dataArray.add(tempArray);  
  54.             }  
  55.             in.close();  
  56.         } catch (IOException e) {  
  57.             e.getStackTrace();  
  58.         }  
  59.   
  60.         data = new String[dataArray.size()][];  
  61.         dataArray.toArray(data);  
  62.         attrNum = data[0].length;  
  63.         attrNames = data[0];  
  64.   
  65.         /* 
  66.          * for(int i=0; i<data.length;i++){ for(int j=0; j<data[0].length; j++){ 
  67.          * System.out.print(" " + data[i][j]); } 
  68.          *  
  69.          * System.out.print("\n"); } 
  70.          */  
  71.     }  
  72.   
  73.     /** 
  74.      * 首先初始化每種屬性的值的所有類型，用于后面的子類熵的計(jì)算時(shí)用 
  75.      */  
  76.     private void initAttrValue() {  
  77.         ArrayList<String> tempValues;  
  78.   
  79.         // 按照列的方式，從左往右找  
  80.         for (int j = 1; j < attrNum; j++) {  
  81.             // 從一列中的上往下開(kāi)始尋找值  
  82.             tempValues = new ArrayList<>();  
  83.             for (int i = 1; i < data.length; i++) {  
  84.                 if (!tempValues.contains(data[i][j])) {  
  85.                     // 如果這個(gè)屬性的值沒(méi)有添加過(guò)，則添加  
  86.                     tempValues.add(data[i][j]);  
  87.                 }  
  88.             }  
  89.   
  90.             // 一列屬性的值已經(jīng)遍歷完畢，復(fù)制到map屬性表中  
  91.             attrValue.put(data[0][j], tempValues);  
  92.         }  
  93.   
  94.         /* 
  95.          * for(Map.Entry entry : attrValue.entrySet()){ 
  96.          * System.out.println("key:value " + entry.getKey() + ":" + 
  97.          * entry.getValue()); } 
  98.          */  
  99.     }  
  100.   
  101.     /** 
  102.      * 計(jì)算數(shù)據(jù)按照不同方式劃分的熵 
  103.      *  
  104.      * @param remainData 
  105.      *            剩余的數(shù)據(jù) 
  106.      * @param attrName 
  107.      *            待劃分的屬性，在算信息增益的時(shí)候會(huì)使用到 
  108.      * @param attrValue 
  109.      *            劃分的子屬性值 
  110.      * @param isParent 
  111.      *            是否分子屬性劃分還是原來(lái)不變的劃分 
  112.      */  
  113.     private double computeEntropy(String[][] remainData, String attrName,  
  114.             String value, boolean isParent) {  
  115.         // 實(shí)例總數(shù)  
  116.         int total = 0;  
  117.         // 正實(shí)例數(shù)  
  118.         int posNum = 0;  
  119.         // 負(fù)實(shí)例數(shù)  
  120.         int negNum = 0;  
  121.   
  122.         // 還是按列從左往右遍歷屬性  
  123.         for (int j = 1; j < attrNames.length; j++) {  
  124.             // 找到了指定的屬性  
  125.             if (attrName.equals(attrNames[j])) {  
  126.                 for (int i = 1; i < remainData.length; i++) {  
  127.                     // 如果是父結(jié)點(diǎn)直接計(jì)算熵或者是通過(guò)子屬性劃分計(jì)算熵，這時(shí)要進(jìn)行屬性值的過(guò)濾  
  128.                     if (isParent  
  129.                             || (!isParent && remainData[i][j].equals(value))) {  
  130.                         if (remainData[i][attrNames.length - 1].equals(YES)) {  
  131.                             // 判斷此行數(shù)據(jù)是否為正實(shí)例  
  132.                             posNum++;  
  133.                         } else {  
  134.                             negNum++;  
  135.                         }  
  136.                     }  
  137.                 }  
  138.             }  
  139.         }  
  140.   
  141.         total = posNum + negNum;  
  142.         double posProbobly = (double) posNum / total;  
  143.         double negProbobly = (double) negNum / total;  
  144.   
  145.         if (posProbobly == 1 || posProbobly == 0) {  
  146.             // 如果數(shù)據(jù)全為同種類型，則熵為0，否則帶入下面的公式會(huì)報(bào)錯(cuò)  
  147.             return 0;  
  148.         }  
  149.   
  150.         double entropyValue = -posProbobly * Math.log(posProbobly)  
  151.                 / Math.log(2.0) - negProbobly * Math.log(negProbobly)  
  152.                 / Math.log(2.0);  
  153.   
  154.         // 返回計(jì)算所得熵  
  155.         return entropyValue;  
  156.     }  
  157.   
  158.     /** 
  159.      * 為某個(gè)屬性計(jì)算信息增益 
  160.      *  
  161.      * @param remainData 
  162.      *            剩余的數(shù)據(jù) 
  163.      * @param value 
  164.      *            待劃分的屬性名稱 
  165.      * @return 
  166.      */  
  167.     private double computeGain(String[][] remainData, String value) {  
  168.         double gainValue = 0;  
  169.         // 源熵的大小將會(huì)與屬性劃分后進(jìn)行比較  
  170.         double entropyOri = 0;  
  171.         // 子劃分熵和  
  172.         double childEntropySum = 0;  
  173.         // 屬性子類型的個(gè)數(shù)  
  174.         int childValueNum = 0;  
  175.         // 屬性值的種數(shù)  
  176.         ArrayList<String> attrTypes = attrValue.get(value);  
  177.         // 子屬性對(duì)應(yīng)的權(quán)重比  
  178.         HashMap<String, Integer> ratioValues = new HashMap<>();  
  179.   
  180.         for (int i = 0; i < attrTypes.size(); i++) {  
  181.             // 首先都統(tǒng)一計(jì)數(shù)為0  
  182.             ratioValues.put(attrTypes.get(i), 0);  
  183.         }  
  184.   
  185.         // 還是按照一列，從左往右遍歷  
  186.         for (int j = 1; j < attrNames.length; j++) {  
  187.             // 判斷是否到了劃分的屬性列  
  188.             if (value.equals(attrNames[j])) {  
  189.                 for (int i = 1; i <= remainData.length - 1; i++) {  
  190.                     childValueNum = ratioValues.get(remainData[i][j]);  
  191.                     // 增加個(gè)數(shù)并且重新存入  
  192.                     childValueNum++;  
  193.                     ratioValues.put(remainData[i][j], childValueNum);  
  194.                 }  
  195.             }  
  196.         }  
  197.   
  198.         // 計(jì)算原熵的大小  
  199.         entropyOri = computeEntropy(remainData, value, null, true);  
  200.         for (int i = 0; i < attrTypes.size(); i++) {  
  201.             double ratio = (double) ratioValues.get(attrTypes.get(i))  
  202.                     / (remainData.length - 1);  
  203.             childEntropySum += ratio  
  204.                     * computeEntropy(remainData, value, attrTypes.get(i), false);  
  205.   
  206.             // System.out.println("ratio:value: " + ratio + " " +  
  207.             // computeEntropy(remainData, value,  
  208.             // attrTypes.get(i), false));  
  209.         }  
  210.   
  211.         // 二者熵相減就是信息增益  
  212.         gainValue = entropyOri - childEntropySum;  
  213.         return gainValue;  
  214.     }  
  215.   
  216.     /** 
  217.      * 計(jì)算信息增益比 
  218.      *  
  219.      * @param remainData 
  220.      *            剩余數(shù)據(jù) 
  221.      * @param value 
  222.      *            待劃分屬性 
  223.      * @return 
  224.      */  
  225.     private double computeGainRatio(String[][] remainData, String value) {  
  226.         double gain = 0;  
  227.         double spiltInfo = 0;  
  228.         int childValueNum = 0;  
  229.         // 屬性值的種數(shù)  
  230.         ArrayList<String> attrTypes = attrValue.get(value);  
  231.         // 子屬性對(duì)應(yīng)的權(quán)重比  
  232.         HashMap<String, Integer> ratioValues = new HashMap<>();  
  233.   
  234.         for (int i = 0; i < attrTypes.size(); i++) {  
  235.             // 首先都統(tǒng)一計(jì)數(shù)為0  
  236.             ratioValues.put(attrTypes.get(i), 0);  
  237.         }  
  238.   
  239.         // 還是按照一列，從左往右遍歷  
  240.         for (int j = 1; j < attrNames.length; j++) {  
  241.             // 判斷是否到了劃分的屬性列  
  242.             if (value.equals(attrNames[j])) {  
  243.                 for (int i = 1; i <= remainData.length - 1; i++) {  
  244.                     childValueNum = ratioValues.get(remainData[i][j]);  
  245.                     // 增加個(gè)數(shù)并且重新存入  
  246.                     childValueNum++;  
  247.                     ratioValues.put(remainData[i][j], childValueNum);  
  248.                 }  
  249.             }  
  250.         }  
  251.   
  252.         // 計(jì)算信息增益  
  253.         gain = computeGain(remainData, value);  
  254.         // 計(jì)算分裂信息，分裂信息度量被定義為(分裂信息用來(lái)衡量屬性分裂數(shù)據(jù)的廣度和均勻)：  
  255.         for (int i = 0; i < attrTypes.size(); i++) {  
  256.             double ratio = (double) ratioValues.get(attrTypes.get(i))  
  257.                     / (remainData.length - 1);  
  258.             spiltInfo += -ratio * Math.log(ratio) / Math.log(2.0);  
  259.         }  
  260.   
  261.         // 計(jì)算機(jī)信息增益率  
  262.         return gain / spiltInfo;  
  263.     }  
  264.   
  265.     /** 
  266.      * 利用源數(shù)據(jù)構(gòu)造決策樹(shù) 
  267.      */  
  268.     private void buildDecisionTree(AttrNode node, String parentAttrValue,  
  269.             String[][] remainData, ArrayList<String> remainAttr, boolean isID3) {  
  270.         node.setParentAttrValue(parentAttrValue);  
  271.   
  272.         String attrName = "";  
  273.         double gainValue = 0;  
  274.         double tempValue = 0;  
  275.   
  276.         // 如果只有1個(gè)屬性則直接返回  
  277.         if (remainAttr.size() == 1) {  
  278.             System.out.println("attr null");  
  279.             return;  
  280.         }  
  281.   
  282.         // 選擇剩余屬性中信息增益最大的作為下一個(gè)分類的屬性  
  283.         for (int i = 0; i < remainAttr.size(); i++) {  
  284.             // 判斷是否用ID3算法還是C4.5算法  
  285.             if (isID3) {  
  286.                 // ID3算法采用的是按照信息增益的值來(lái)比  
  287.                 tempValue = computeGain(remainData, remainAttr.get(i));  
  288.             } else {  
  289.                 // C4.5算法進(jìn)行了改進(jìn)，用的是信息增益率來(lái)比,克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足  
  290.                 tempValue = computeGainRatio(remainData, remainAttr.get(i));  
  291.             }  
  292.   
  293.             if (tempValue > gainValue) {  
  294.                 gainValue = tempValue;  
  295.                 attrName = remainAttr.get(i);  
  296.             }  
  297.         }  
  298.   
  299.         node.setAttrName(attrName);  
  300.         ArrayList<String> valueTypes = attrValue.get(attrName);  
  301.         remainAttr.remove(attrName);  
  302.   
  303.         AttrNode[] childNode = new AttrNode[valueTypes.size()];  
  304.         String[][] rData;  
  305.         for (int i = 0; i < valueTypes.size(); i++) {  
  306.             // 移除非此值類型的數(shù)據(jù)  
  307.             rData = removeData(remainData, attrName, valueTypes.get(i));  
  308.   
  309.             childNode[i] = new AttrNode();  
  310.             boolean sameClass = true;  
  311.             ArrayList<String> indexArray = new ArrayList<>();  
  312.             for (int k = 1; k < rData.length; k++) {  
  313.                 indexArray.add(rData[k][0]);  
  314.                 // 判斷是否為同一類的  
  315.                 if (!rData[k][attrNames.length - 1]  
  316.                         .equals(rData[1][attrNames.length - 1])) {  
  317.                     // 只要有1個(gè)不相等，就不是同類型的  
  318.                     sameClass = false;  
  319.                     break;  
  320.                 }  
  321.             }  
  322.   
  323.             if (!sameClass) {  
  324.                 // 創(chuàng)建新的對(duì)象屬性，對(duì)象的同個(gè)引用會(huì)出錯(cuò)  
  325.                 ArrayList<String> rAttr = new ArrayList<>();  
  326.                 for (String str : remainAttr) {  
  327.                     rAttr.add(str);  
  328.                 }  
  329.   
  330.                 buildDecisionTree(childNode[i], valueTypes.get(i), rData,  
  331.                         rAttr, isID3);  
  332.             } else {  
  333.                 // 如果是同種類型，則直接為數(shù)據(jù)節(jié)點(diǎn)  
  334.                 childNode[i].setParentAttrValue(valueTypes.get(i));  
  335.                 childNode[i].setChildDataIndex(indexArray);  
  336.             }  
  337.   
  338.         }  
  339.         node.setChildAttrNode(childNode);  
  340.     }  
  341.   
  342.     /** 
  343.      * 屬性劃分完畢，進(jìn)行數(shù)據(jù)的移除 
  344.      *  
  345.      * @param srcData 
  346.      *            源數(shù)據(jù) 
  347.      * @param attrName 
  348.      *            劃分的屬性名稱 
  349.      * @param valueType 
  350.      *            屬性的值類型 
  351.      */  
  352.     private String[][] removeData(String[][] srcData, String attrName,  
  353.             String valueType) {  
  354.         String[][] desDataArray;  
  355.         ArrayList<String[]> desData = new ArrayList<>();  
  356.         // 待刪除數(shù)據(jù)  
  357.         ArrayList<String[]> selectData = new ArrayList<>();  
  358.         selectData.add(attrNames);  
  359.   
  360.         // 數(shù)組數(shù)據(jù)轉(zhuǎn)化到列表中，方便移除  
  361.         for (int i = 0; i < srcData.length; i++) {  
  362.             desData.add(srcData[i]);  
  363.         }  
  364.   
  365.         // 還是從左往右一列列的查找  
  366.         for (int j = 1; j < attrNames.length; j++) {  
  367.             if (attrNames[j].equals(attrName)) {  
  368.                 for (int i = 1; i < desData.size(); i++) {  
  369.                     if (desData.get(i)[j].equals(valueType)) {  
  370.                         // 如果匹配這個(gè)數(shù)據(jù)，則移除其他的數(shù)據(jù)  
  371.                         selectData.add(desData.get(i));  
  372.                     }  
  373.                 }  
  374.             }  
  375.         }  
  376.   

數(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); }