前言

在上一篇文章中我們已經詳細介紹了決策樹模型，并且提到了ID3演算法及其局限性，那么在本篇文章中，我們將會介紹基于ID3演算法進行改良的C4.5演算法以及決策樹擬合度的優化問題，

1 C4.5 演算法

C4.5 演算法與 ID3 演算法相似，C4.5 演算法對 ID3 演算法進行了改進，C4.5 在生成的程序中，用資訊增益比準則來選擇特征，

1.1 修改區域最優化條件

• 以資訊增益作為劃分訓練資料集的特征，存在偏向于選擇取值較多的特征的問題，
• 使用資訊增益比（information gain ratio）可以對這一問題進行校正，

資訊增益比定義為其資訊增益與訓練資料集關于某一特征的值的熵之比： G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)?其中 I V ( a ) = ? ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ IV(a)=-\sum_{v=1}^{V}{\frac{|D^v|}{|D|}log_2 \frac{|D^v|}{|D|}} IV(a)=?v=1∑V?∣D∣∣Dv∣?log2?∣D∣∣Dv∣?稱為屬性 a 的 "固有值“（intrinsic value），

屬性 a 的可能取值越多（即 V 越大），則 IV(a) 的值通常會越大，

IV 值會隨著葉節點上樣本量的變小而逐漸變大，也就是說一個特征屬性中如果標簽分類太多，每個葉子上的 IV 值就會非常大，

值得注意的是，增益率準則對可取值數目較少的屬性有所偏好，因此，C4.5 演算法并不是直接選擇增益率最大的候選劃分屬性，而是使用了一種啟發式：先從候選劃分屬性中找出資訊增益高于平均水平的屬性， 再從中選擇增益率最高的，

我們可利用 Gain_ratio 代替 Gain 重新計算資料集中第 0 列的 Gain_ratio ，由于根據 accompany 欄位切分后，2 個分支分別有 3 個和 2 個的樣例資料，因此其 IV 指標計算程序如下： I V ( ′ a c c o m p a n y ′ ) = ? 3 5 l o g 2 3 5 ? 2 5 l o g 2 2 5 = 0.971 G a i n _ r a t i o ( ′ a c c o m p a n y ′ ) = G a i n ( ′ a c c o m p a n y ′ ) I V ( ′ a c c o m p a n y ′ ) = 0.42 0.971 = 0.432 IV('accompany')=-\frac{3}{5}log_2 \frac{3}{5}-\frac{2}{5}log_2 \frac{2}{5}=0.971\\Gain\_ratio('accompany')=\frac{Gain('accompany')}{IV('accompany')}=\frac{0.42}{0.971}=0.432 IV(′accompany′)=?53?log2?53??52?log2?52?=0.971Gain_ratio(′accompany′)=IV(′accompany′)Gain(′accompany′)?=0.9710.42?=0.432然后可進一步計算其他各欄位的 Gain_ratio ，并選取 Gain_ratio 最大的欄位進行切分，

1.2 連續變數處理手段

在 C4.5 中，同樣還增加了針對連續變數的處理手段，如果輸入特征欄位是連續型變數，則演算法首先會對這一列數進行從小到大的排序，然后選取相鄰的兩個數的中間數作為切分資料集的備選點，若一個連續變數有 N 個值，則在 C4.5 的處理程序中將產生 N-1 個備選切分點，并且每個切分點都代表著一種二叉樹的切分方案，例如：

這里需要注意的是，此時針對連續變數的處理并非是將其轉化為一個擁有 N-1 個分類水平的分類變數，而是將其轉化成了 N-1 個二分方案，而在進行下一次的切分程序中，這 N-1 個方案都要單獨帶入考慮，其中每一個切分方案和一個離散變數的地位均相同（一個離散變數就是一個單獨的多路切分方案）， 例如有如下資料集，資料集中只有兩個欄位，第一行代表年齡，是特征變數，第二行代表性別，是目標欄位，則對年齡這一連續變數的切分方案如圖所示：

從上述論述能夠看出，在對于包含連續變數的資料集進行樹模型構建的程序中要消耗更多的運算資源，但與此同時，我們也會發現，當連續變數的某中間點參與到決策樹的二分程序中，往往代表該點對于最終分類結果有較大影響，這也為我們連續變數的分箱壓縮提供了指導性意見， 例如上述案例，若要對Age 列進行壓縮，則可考慮使用 36.5 對其進行分箱，則分箱結果對于性別這一目標欄位仍然具有較好的分類效果，這也是決策樹的最常見用途之一，也是最重要的模型指導分箱的方法，

下面附上使用C4.5演算法建立決策樹的Python代碼：

import numpy as np
import pandas as pd

# 定義資訊熵
def calEnt(dataSet):
    n = dataSet.shape[0]                                     # 資料集總行數
    iset = dataSet.iloc[:,-1].value_counts()                 # 統計標簽的所有類別
    p = iset/n                                               # 統計每一類標簽所占比  
    ent = (-p*np.log2(p)).sum()                              # 計算資訊熵
    return ent

# 選擇最優的列進行切分
def bestSplit2(dataSet):
    baseEnt = calEnt(dataSet)                                # 計算原始熵
    bestGainRatio = 0                                       # 初始化資訊增益
    axis = -1                                                # 初始化最佳切分列，標簽列
    
    for i in range(dataSet.shape[1]-1):                      # 對特征的每一列進行回圈
        levels= dataSet.iloc[:,i].value_counts().index       # 提取出當前列的所有取值
        ents = 0                                             # 初始化子節點的資訊熵
        IV = 0                                               # 初始化子節點的屬性分裂資訊度量
        
        for j in levels:                                     # 對當前列的每一個取值進行回圈
            childSet = dataSet[dataSet.iloc[:,i]==j]         # 某一個子節點的dataframe
            ent = calEnt(childSet)                           # 計算某一個子節點的資訊熵
            p = childSet.shape[0]/dataSet.shape[0]           # 計算當前取值的概率
            ents += p*ent                                    # 計算當前列的資訊熵
            IV += -(p*np.log(p))                             # 計算當前列的分裂資訊度量
        print('第{}列的資訊熵為{}'.format(i,ents))
            
        infoGain = baseEnt-ents                              # 計算當前列的資訊增益
        print('第{}列的資訊增益為{}'.format(i,infoGain))
        
        gainRatio = infoGain / IV                           # 計算當前列的資訊增益率
        print('第{}列的資訊增益率為{}\n'.format(i,gainRatio))
        
        if (gainRatio > bestGainRatio):
            bestGainRatio = gainRatio                      # 選擇最大資訊增益率
            axis = i                                         # 最大資訊增益率所在列的索引
    print("第{}列為最優切分列\n".format(axis))
    return axis

#為決策樹進一步劃分去做準備
def mySplit(dataSet,axis,value):
    col = dataSet.columns[axis]
    redataSet = dataSet.loc[dataSet[col]==value,:].drop(col,axis=1)
    return redataSet

"""
函式功能：基于最大資訊增益率切分資料集，遞回構建決策樹
引數說明：
dataSet：原始資料集(最右一列是標簽)
return：myTree：字典形式的樹
"""
def createTree2(dataSet):
    featlist = list(dataSet.columns)                        # 提取出資料集所有的列
    classlist = dataSet.iloc[:,-1].value_counts()           # 獲取最后一列類標簽
    
    # 判斷最多標簽數目是否等于資料集行數，或者資料集是否只有一列
    if classlist[0]==dataSet.shape[0] or dataSet.shape[1] == 1:
        return classlist.index[0]                           # 如果是，回傳類標簽
   
    axis = bestSplit2(dataSet)                              # 確定出當前最佳切分列的索引
    bestfeat = featlist[axis]                               # 獲取該索引對應的特征
    myTree = {bestfeat:{}}                                  # 采用字典嵌套的方式存盤樹資訊
    del featlist[axis]                                      # 洗掉當前特征
    valuelist = set(dataSet.iloc[:,axis])                   # 提取最佳切分列所有屬性值
    
    for value in valuelist:                                 # 對每一個屬性值遞回建樹
        myTree[bestfeat][value] = createTree(mySplit(dataSet,axis,value))
    
    return myTree

row_data = {'是否陪伴' :[0,0,0,1,1],
            '是否玩游戲':[1,1,0,1,1],
            '渣男' :['是','是','不是','不是','不是']}
dataSet = pd.DataFrame(row_data) 

createTree2(dataSet)

運行結果如下：

第0列的資訊熵為0.5509775004326937
第0列的資訊增益為0.4199730940219749
第0列的資訊增益率為0.6240205253621535

第1列的資訊熵為0.8
第1列的資訊增益為0.17095059445466854
第1列的資訊增益率為0.3416262320352702

第0列為最優切分列

第0列的資訊熵為0.0
第0列的資訊增益為0.9182958340544896
第0列的資訊增益率為1.4426950408889636

第0列為最優切分列

{‘是否陪伴’: {0: {‘是否玩游戲’: {0: ‘不是’, 1: ‘是’}}, 1: ‘不是’}}

2 決策樹的擬合度優化

在實際操作程序中，我們判斷模型是否過擬合往往是從模型訓練誤差和泛化誤差的比較中得出，而采用我們之前介紹的交叉驗證可得到較為準確的訓練誤差和泛化誤差，二者結合使用就能判斷模型是否存在過擬合現象，雖然我們之前舉例時并沒有對資料集進行切分，但任何有監督學習演算法建模程序中都需要進行訓練集和測驗集的劃分，決策樹也不例外，進而我們可用交叉驗證計算訓練誤差和泛化誤差，進而判斷決策樹是否存在過擬合，這是一套通用地判斷有監督學習演算法是否過擬合的方法，同時通用的方法中還有更高級的方法，我們將在后續進行逐步介紹，但對于決策樹而言，有一套決策樹獨有的防止過擬合的解決方案——剪枝，

2.1 決策樹剪枝

所謂剪枝是指在決策樹中去除部分葉節點，

剪枝（Pruning）主要是用來防止過擬合，對于一般的資料集如果總是追求 ”純的“ 葉節點，或者觀測數較小的葉節點，很容易使得樹過于龐雜，尤其是存在可以反復使用的連續變數的時候，此時就需要主動去掉一些分支來降低過擬合的風險，

常見的剪枝策略有 ”預剪枝“（Pre-Pruning）和 ”后剪枝“（Post-Pruning），

• 預剪枝：在決策樹生成的程序中，對每個節點在劃分前先進行估計，如果當前的節點劃分不能帶來決策樹泛化性能（預測性能）的提升，則停止劃分并且將當前節點標記為葉節點，
• 后剪枝：先訓練生成一顆完整的樹，自底向上對非葉節點進行考察，如果將該節點對應的子樹替換為葉節點能帶來決策樹泛化能力的提升，則將該子樹替換為葉節點，

2.2 CART 演算法

CART：分類回歸樹（Classification and Regression Tree）

• 分裂程序是一個二叉遞回劃分程序
• CART 預測變數 x 的型別既可以是連續型變數也可以是分型別變數
• 資料應以其原始形式處理，不需要離散化
• 用于數值型預測時，并沒有使用回歸，而是基于到達葉節點的案例的平均值做出預測

2.2.1 分裂準則

二叉遞回劃分：條件成立向左，反之向右

• 對于連續變數：條件是屬性小于等于最優分裂點
• 對于分類變數：條件是屬性屬于若干類

2.2.2 二叉分裂的優點

相比多路分裂導致資料碎片化的速度慢，允許在一個屬性上重復分裂，即可以在一個屬性上產生足夠多的分裂，兩路分裂帶來的樹預測性能提升足以彌補其相應的樹易讀性損失，

對于屬性不同的被預測變數 y 分裂準則不同：

• 分類樹：Gini 準則，與之前的資訊增益很類似，Gini 系數度量一個節點的不純度，
• 回歸樹：一種常見的分割標準是標準偏差減少（Standard Deviation Reduction, SDR），類似于最小均方誤差 LS（least squares，預測錯誤的平方和）準則，

2.2.3 利用測驗集進行剪枝

簡單討論 CART 演算法剪枝程序，該程序也是測驗集用于修正模型的最佳體現，例如，有如下在訓練集中訓練得到的樹模型，黑色數字表示訓練集上的分類情況，紅色數字表示模型作用于驗證集上的分類情況，

則 CART 演算法利用驗證集剪枝的程序如下：

• 判斷每個葉節點在驗證集上的錯誤率：
• 節點 4 的錯誤率 e ( 4 ) = 1 3 e(4)=\frac{1}{3} e(4)=31?
• 節點 5 的錯誤率 e ( 5 ) = 1 e(5)=1 e(5)=1
• 節點 6 的錯誤率 e ( 6 ) = 1 e(6)=1 e(6)=1
• 節點 7 的錯誤率為 e ( 7 ) = 4 9 e(7)=\frac{4}{9} e(7)=94?

計算子節點總加權平均錯誤率并和父節點進行比較，加權方法就是乘以該節點樣本量占父節點樣本總量的百分比（測驗集）：

如節點 2 的錯誤率為 e ( 2 ) = 1 4 e(2)=\frac{1}{4} e(2)=41?，而節點 4 和節點 5 的加權平均錯誤率為 e ( 4 ) ? 3 4 + e ( 5 ) ? 1 4 = 2 4 e(4)*\frac{3}{4}+e(5)*\frac{1}{4}=\frac{2}{4} e(4)?43?+e(5)?41?=42?，因此子節點錯誤率更高，考慮剪枝；

節點 3 的錯誤率 e ( 3 ) = 4 10 e(3)=\frac{4}{10} e(3)=104?，而 e ( 6 ) ? 1 10 + e ( 7 ) ? 9 10 = 5 10 e(6)*\frac{1}{10}+e(7)*\frac{9}{10}=\frac{5}{10} e(6)?101?+e(7)?109?=105?，因此考慮剪枝；

節點 2 和節點 3 的加權平均錯誤率為 e ( 2 ) ? 4 14 + e ( 3 ) ? 10 14 = 5 14 e(2)*\frac{4}{14}+e(3)*\frac{10}{14}=\frac{5}{14} e(2)?144?+e(3)?1410?=145?，比父節點（節點 1）的錯
誤率 e ( 1 ) = 7 14 e(1)=\frac{7}{14} e(1)=147?要小，因此保留該節點，停止剪枝，

如果讀到這里的朋友對上述操作仍有疑問，請詳細查看下面內容，

上述剪枝的方法其實是叫做錯誤率降低剪枝(REP,Reduced-Error Pruning），它是一種較為簡單的剪枝方法，它將預先準備好用于建模的資料分為訓練集和驗證集，訓練集用來建立決策樹模型，驗證集用來評估這個決策樹模型在未知資料上的精度，也就是用來評估是否修剪決策樹，

其原理是即使學習程序中有可能會因為訓練集中的隨機情況所誤導，但驗證集不大可能表現出同樣的隨機波動，所以驗證集可以用于優化其擬合程度，

該方法以樹的每個節點為物件，洗掉的具體步驟如下：

1. 洗掉以此結點為根的子樹
2. 使其成為葉子結點
3. 賦予該結點關聯的訓練資料的最常見分類
4. 當修剪后的樹對于驗證集合的性能不會比原來的樹差時，才真正洗掉該結點（這就是為什么拿父節點錯誤率和子結點錯誤率權重和比較的原因）

REP是從底向上進行處理，直到進一步修剪有害為止(再剪枝會減低驗證集合的精度)，

REP是最簡單的后剪枝方法之一，不過由于使用獨立的測驗集，原始決策樹相比，修改后的決策樹可能偏向于過度修剪，

如果訓練集較小，通常不考慮采用REP演算法，

2.2.3 測驗集和驗證集

如果你不了解測驗集和驗證集的區別的話，可以詳細查看下面內容，

對于大多數模型而言，測驗集實際上的作用就是用來修正模型，為了提高修正的準確率，我們也可采用交叉驗證的方法，反復判別模型修改條件（如是否要剪枝），并設定模型修改觸發條件（如多數驗證情況需要修改則對其進行修改），從而提高模型優化的可靠性，

而除了訓練集和測驗集之外，我們還常常會劃分一個驗證集，驗證集資料不參與建模也不參與模型修改和優化，只用于測驗最終優化后模型效力，

而訓練集、測驗集和驗證集的劃分通常遵照 6:2:2 的比例進行劃分，當然也可根據實際需求適當調整劃分比例，但無論如何，測驗集和驗證集資料數量都不宜過多也不宜過少，該二者資料集資料均不參與建模， 若占比太多，則會對模型構建程序造成較大影響（欠擬合），而若劃分資料過少，訓練集資料量較大， 則又有可能造成過擬合，資料集的劃分也是影響擬合度的重要因素，

那朋友們，我們怎么區分資料量大還是小呢？

其實這個并沒有明確的規定，通常意義上來講，千位數級別以下的資料為小資料量，這個時候往往沒有設定驗證集的必要（會導致訓練資料太少了），一般可以采用訓練集:測驗集=7:3的方式；而如果是幾萬條資料的話可以采用上述提到的訓練集:驗證集:測驗集=6:2:2的劃分方式，而資料達到了百萬級別的話，就沒必要采用這種劃分方式了，可以采用訓練集:驗證集:測驗集=98:1:1的劃分方式，

當然，這都只是通常情況下，具體需要你自行調整，

結束語

下一篇文章我會接著介紹決策樹模型，主要內容就是利用sklearn實作決策樹模型，之所以要將決策樹這一部分拆成好幾部分是因為我覺得一口吃成大胖子的話還不如細嚼慢咽來得有用，也希望感興趣的朋友能接著看下去，分享知識對其他人有所幫助或許也是一個創作者最大的樂趣吧，

機器學習系列往期回顧

💚 開始學習機器學習時你必須要了解的模型有哪些？機器學習系列之決策樹基礎篇
?? 以??簡單易懂??的語言帶你搞懂有監督學習演算法【附Python代碼詳解】機器學習系列之KNN篇
💜 開始學習機器學習之前你必須要了解的知識有哪些？機器學習系列入門篇

往期內容回顧

🖤 我和關注我的前1000個粉絲“合影”啦！收集前1000個粉絲進行了一系列資料分析，識訓滿滿
?? 分享一個超nice的資料分析實戰案例 ? “手把手”教學，收藏等于學會
💙 資料分析必須掌握的RFM模型是什么？一文搞懂如何利用RFM對用戶進行分類【附實戰講解】
💚 MySQL必須掌握的技能有哪些？超細長文帶你掌握MySQL【建議收藏】
💜 Hive必須了解的技能有哪些？萬字博客帶你掌握Hive??【建議收藏】
🧡 一文帶你了解Hive【詳細介紹】Hive與傳統資料庫有什么區別？

推薦關注的專欄

👨?👩?👦?👦 機器學習：分享機器學習理論基礎和常用模型講解
👨?👩?👦?👦 資料分析：分享資料分析實戰專案和常用技能整理

CSDN@報告，今天也有好好學習