決的定解幾個：根節點、父節點、子節點和葉子節點。父節點和子節點是相對的，說白了子節點由父節點根據某一規則而來，然后子節點作為新的父親節點繼續，直至不能為止。而根節點是沒有父節點的節點，即初始節點，葉子節點是沒有子節點的節點，如下圖所示：1.1決如何做決2.1是否是是是否是否否否否上邊中有4個客戶的屬性，如何綜合利用這些屬性去判斷用戶的意向？決圖2.1銀行意向分析決示意通過圖2.1的訓練數據，我們可以建議圖2.1所示的決，其輸入是用戶的信息，輸出是用戶的意向。如果要判斷某一客戶是否有的意向，直接根據用戶的職業、收入、以及學歷就可以分析得出用戶的類型。如某客戶的信息為：{職業、，收入，學歷}={工人、39，1800，小學}，將信息輸入上述決，可以得到下列的分析決的構那么問題就來了，如何構建如圖2.1所示一棵決呢？決的構建是數據逐步步驟3：生成若干孩子節點，對每一個孩子節點進行判斷，如果滿足停止的條件，進42；3.1表 分類信息否否否否是是1“職業”是離散型變量，有三個取值，分別為白領、工人和學生，根據三個取值3.21不1102113.32不1202(40,—10表3.3可以表示成如下的決結構3.2屬性的選 決采用貪婪思想進行，即選擇可以得到最優結果的屬性進行。那么怎樣才算是最優的結果？最理想的情況當然是能找到一個屬性剛好能夠將不同類別分開，但是大多數情況下很難一步到位，我們希望每一次之后孩子節點的數據盡量”有提高；按照屬性2后每個節點各類的數量相差比較大，可以很大概率認為第一個孩122。選擇屬性是要找出能夠使所有孩子節點數據最純的屬性，決使用信息增益用信息增益表示前后跟的數據復雜度和節點數據復雜度的變化值，計算公前的數據復雜度減去孩子節點的數據復雜度的和，信息增益越大，后的復雜度減熵熵描述了數據的程度，熵越大，程度越高，也就是純度越低；反之，熵越小，程度越低，純度越高。熵的計算 Pii的數量占比。以二分類問題為例，如果兩類的數量相同，此時分類節點的其中Pii的數量占比。其同樣以上述熵的二分類例子為例，當兩類數量相等0.50。基尼值越大，數據越不屬性1進行的結果，圖3.2表示節點選擇屬性2進行的結果，通過計算兩個屬性后的信息增益，選擇最優的屬性。由 作為的屬性屬性進行。為了解決這個問題，引入了信息增益率這個概念。信息增益率是在信息增益的基礎上除以節點數據量的信息增益（聽起來很拗口），其計算如下：其中表示信息增益， 其中m表示子節點的數量，表示第i個子節點的數據量，N表示父節點數據量，說白了，其實是 時選擇子節點多的屬性的傾向性。信息增益率越高，說明的效果越好。 3.3停止的條決不可能不限制地生長，總有停止的時候，最的情況是當節點到只剩下一個數據點時自動結束，但這種情況下樹過于復雜，而且預測的經度不高。一般情況下為了降低決復雜度和提高預測的經度，會適當提前終止節點的。以下是決節點停止的一般性條件3.4決的構建方決的構建算法主要有ID3、C4.5、CART三種，其中ID3和C4.5是分類樹CART是分類回歸樹，將在本系列的ID3、C4.5和CART中分別講述其中ID3是決最基本的構建算法，而C4.5和CART是在ID3的基礎上進行優決的優 決是充分考慮了所有的數據點而生成的復雜樹，有可能出現過擬合的情況，決剪枝修剪前后分類誤差相差不大的，能夠降低決的復雜度，降低過擬先剪枝說白了就是提前結束決的增長，跟上述決停止生長的方法一樣。后剪枝是指在決生長完成之后再進行剪枝的過程。這里介紹三種后剪枝方案：REP剪枝需要用新的數據集，原因是如果用舊的數據集，不可能出現后的錯誤率比前錯誤率要高的情況。由于使用新的數據集沒有參與決的構建，能夠降低訓悲觀剪枝認為如果決的精度在剪枝前后沒有影響的話，則進行剪枝。怎樣才算 誤差的經度滿足二項分布，根據二項分布的性質，，其 誤 上述中，0.5表示修正因子。由于子節點是父節點進行的結果，從理論上0.5，在計算誤差的時候，子節點由于加上了誤差修由 令 表示葉子節點的誤差代價，， 表示的誤差代價， 為子節點i的錯誤 表示節點i的數據節點占比；表示節點個數。下圖是決A的其中一顆，決的總數據量為40求出該的表面錯誤覆蓋率為1/40，只要求出其他的表面誤差率增益值就可以對決進行剪枝.決系列（三）——數據是怎么1晴晴陰陰陰雨晴晴雨陰晴晴陰晴雨陰雨晴陰雨晴陰雨4雨對于離散型數據，直接按照離散數據的取值進行，每一個取值對應一個子節點，以“當前天氣”1所示。對于連續型數據，ID3原本是沒有處理能力的，只有通過離散化將連續性數據轉化的話方法。該方法先對數據進行排序，然后將連續型數據劃分為多個區間，并使每一2所示。選擇最優屬ID3采用信息增益作為選擇最優的屬性的方法，選擇熵作為衡量節點純度的標 表示父節點的熵；表示節點i的熵，熵越大，節點的 表示子節點i的數據量與父節點數據量之比。 最大的屬性作為屬性。 停止的條時，再做容易強化噪聲數據的作用；二是降低樹生長的復雜性。提前結束一定程數據的純度比較大，如果熵或者基尼值小于一定程度時，節點停止。是所有葉子節點的最大深度，當深度到達指定的上限大小時，停止。鏈表數組進行，數組的第一個元素表示屬性1的離散值。staticList<String>[]21112122263313兩個類：節點類和信a）節點類ViewViewb）信息類ViewView節點方法findBestSplit(Nodenode,List<int>nums,int[]isUsed)，該方法對節點進行，返回值NodeisUsed表示到該節點位置所有屬性的使用情況（1：表示該屬性不能再次使用，0：表尋找最優的屬尋找最優的屬性需要計算每一個屬性后的信息增益，計算上文已給出.其實就是遞歸的過程，對每一個子節點執行findBestSplit方法進行（注：上述代碼只是ID3的代碼，數據預處理的代碼并沒有給出，只要將預處理后的數據輸入到主方法findBestSplit中，就可以得到最終的結果）總ID3是基本的決構建算法，作為決經典的構建算法，其具有結構簡單、清晰易懂的特點。雖然ID3比較靈活方便，但是有以下幾個缺點：如上一篇文章所述，ID3方法主要有幾個缺點：一是采用信息增益進行數據，C4.5采用剪枝的策略，對完全生長的決進行剪枝處理，一定程度上降低過采用信息增益率作為的依信息增益率的計算為 其中m表示節點的數量，Ni表示第i個節點的數據量，N表示父親節點的數據量， 晴否晴是晴晴否晴是晴是晴是陰8是陰否陰是陰否雨否雨是雨否雨4否 對連續型屬性進行C4.5處理離散型屬性的方式與ID3一致，新增對連續型屬性的處理。處理方式是先從上圖可以看出，理論上來講，N條數據就有N-1個切割點，為了選取最優的切割23條記錄，兩者的類（逛街）都是“是”，如果從這里切割的話，就將兩個本來相同的類分開了，肯定不會比將他們歸為一類的切分方法好，因此，可以通過去除前后兩個類相同116個，降低了計算信息增益進行內部擇優的，因為如果使用信息增益率進行會出現傾向于選擇分割前后剪決只已經提到，剪枝是在完全生長的決的基礎上，對生長后分類效果不佳的進行修剪，減小決的復雜度，降低過擬合的影響。C4.5采用悲觀剪枝方法（PEP）。悲觀剪枝認為如果決的精度在剪枝前后沒有表示的誤差；， ，其中，N為子上述中，0.5表示修正因子。由于對父節點進行總會得到比父節點分類結果0.5的修正因此，在計算誤差的時候，子節點由于加由 程序設計及源代碼（C#版前n-1列表示屬性，最后一列表示分類的。1112122263313staticdouble[][] staticList<String featureValues是鏈表數組，數組的長度為屬性的個數，數組的每個元素為該屬性的離散注意，與ID3中相比，新增了兩個屬性：leafWrongleafNode_Count分別表示葉子findBestSplit(Nodenode,List<intnums,intisUsed)isUsed表示到該節點位置所有屬性的使用情況；findBestSplit的這個方法主要有以下幾個組成部分：其實就是遞歸的工程，對每一個子節點執行findBestSplit方法進行總結要記住，C4.5是分類樹最終要的算法，算法的思想其實很簡單，但是分類的準確性高。可以說C4.5ID3ID3未能解決的問題。要重點記住以CART，又名分類回歸樹，是在ID3的基礎上進行優化的決，學習CART記住以下幾4CART既能是分類樹，又能是決，如上表所示，如果我們想預測一個人是否已分類樹和回歸樹是怎么做決策的？假設我們構建了兩棵決分別預測用戶是否已婚和實際的，如圖1和圖2所示：圖1預測情況決 圖2預測的決圖2是一棵回歸樹，預測用戶的實際，是一個具體的輸出值。怎樣得到這個輸CART如何選擇的屬性是如何評價節點的純度呢？如果是分類樹，CARTGINI值衡量節點純度；如果是回GINI值的計算節點越不純，GINI值越大。以二分類為例，如果節點的所有數據只有一個類別，則，如果兩類數量相同，則。回歸方差計算0，此時可以很肯定得認為該節點的輸出值；如果節點的數據相差很因此，無論是分類樹還是回歸樹，CARTGINI值或者回歸方差CART如何成一棵二叉樹CART對連續型屬性的處理與C4.5差不多，通過最小化后的GINI值或者樣本C4.5。X，Y，Z，則該屬性的方法有{X}、{Y，Z}，{Y}、{X，Z}，{Z}、{X，Y}，分別計算每種劃族”}，{“上班族”}、{“學生”、“老師”}GINI值或者樣預測（回歸預測（回歸預測（回歸預測，則選擇{“老師”}、{“學生”、“上班族”}的劃分方法。如何剪枝CART采用（代價復雜度）剪枝方法。代價復雜度選擇節點表面誤差率增益值令 表示葉子節點的誤差代價，， 表示節點i的數據節點占比；表示節點個數求出該的表面錯誤覆蓋率為，只要求出其他的表面誤差率增益值就可以對決程序實際以及源代前n-1列表示屬性，最后一列表示分類的。3434254其中，對于“情況”屬性，數字{1，2}分別表示{未婚，已婚}；對于“職業”屬性{1，2，3，}分別表示{學生、老師、上班族}；staticdouble[][] staticList<String featureValues是鏈表數組，數組的長度為屬性的個數，數組的每個元素為該屬性的離散該類表一個節，屬性括節點擇的屬性、節的輸出、孩子點、深D3lWong和lNo_ount分別表 findBestSplit(Nodenode,List<intnums,intisUsed)isUsed表示到