python實作分類決策樹ID3和C4.5算法

ID3算法介紹

• ID3算法全稱為疊代二叉樹3代算法（Iterative Dichotomiser 3）
• 該算法要先進行特征選擇，再生成決策樹，其中特征選擇是基于“資訊增益”最大的原則進行的。
• 但由于決策樹完全基于訓練集生成的，有可能對訓練集過于“依賴”，即産生過拟合現象。是以在生成決策樹後，需要對決策樹進行剪枝。剪枝有兩種形式，分别為前剪枝（Pre-Pruning）和後剪枝（Post-Pruning），一般采用後剪枝。

資訊熵、條件熵和資訊增益

• 資訊熵：來自于香農定理，表示資訊集合所含資訊的平均不确定性。資訊熵越大，表示不确定性越大，所含的資訊量也就越大。

  設 x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n} x1​,x2​,x3​,...xn​為資訊集合X的n個取值，則 x i x_i xi​的機率： P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n P(X=i)=pi​,i=1,2,3,...,n

  資訊集合X的資訊熵為： H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i} H(X)=−i=1∑n​pi​logpi​

• 條件熵：指已知某個随機變量的情況下，資訊集合的資訊熵。

  設資訊集合X中有 y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m} y1​,y2​,y3​,...ym​組成的随機變量集合Y，則随機變量（X，Y）的聯合機率分布為 P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij} P(x=i,y=j)=pij​條件熵： H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)} H(X∣Y)=j=1∑m​p(yj​)H(X∣yj​)由 H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)} H(X∣yj​)=−j=1∑m​p(yj​)i=1∑n​p(xi​∣yj​)logp(xi​∣yj​)和貝葉斯公式： p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j) p(xi​yj​)=p(xi​∣yj​)p(yj​)可以化簡條件熵的計算公式為: H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}} H(X∣Y)=j=1∑m​i=1∑n​p(xi​,yj​)logp(xi​,yj​)p(xi​)​

• 資訊增益：資訊熵-條件熵，用于衡量在知道已知随機變量後，資訊不确定性減小越大。

  d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y) d(X,Y)=H(X)−H(X∣Y)

python代碼實作

import numpy as np
import math

def calShannonEnt(dataSet):
    """ 計算資訊熵 """
    labelCountDict = {}
    for d in dataSet:
        label = d[-1]
        if label not in labelCountDict.keys():
            labelCountDict[label] = 1
        else:
            labelCountDict[label] += 1
    entropy = 0.0
    for l, c in labelCountDict.items():
        p = 1.0 * c / len(dataSet)
        entropy -= p * math.log(p, 2)        
    return entropy
    
def filterSubDataSet(dataSet, colIndex, value):
    """傳回colIndex特征列label等于value，并且過濾掉改特征列的資料集"""
    subDataSetList = []
    for r in dataSet:
        if r[colIndex] == value:
            newR = r[:colIndex]
            newR = np.append(newR, (r[colIndex + 1:]))
            subDataSetList.append(newR)
    return np.array(subDataSetList)

def chooseFeature(dataSet):
    """ 通過計算資訊增益選擇最合适的特征"""
    featureNum = dataSet.shape[1] - 1
    entropy = calShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeatureIndex = -1
    for i in range(featureNum):
        uniqueValues = np.unique(dataSet[:, i])
        condition_entropy = 0.0
        
        for v in uniqueValues:  #計算條件熵
            subDataSet = filterSubDataSet(dataSet, i, v)
            p = 1.0 * len(subDataSet) / len(dataSet)
            condition_entropy += p * calShannonEnt(subDataSet)
        infoGain = entropy - condition_entropy    #計算資訊增益
        
        if infoGain >= bestInfoGain:    #選擇最大資訊增益
            bestInfoGain = infoGain
            bestFeatureIndex = i
    return bestFeatureIndex   

def creatDecisionTree(dataSet, featNames):
    """ 通過訓練集生成決策樹 """
    featureName = featNames[:]    # 拷貝featNames，此處不能直接用指派操作，否則新變量會指向舊變量的位址
    classList = list(dataSet[:, -1])
    if len(set(classList)) == 1:    # 隻有一個類别
        return classList[0]
    if dataSet.shape[1] == 1:    #當所有特征屬性都利用完仍然無法判斷樣本屬于哪一類，此時歸為該資料集中數量最多的那一類
        return max(set(classList), key=classList.count)
    
    
    bestFeatureIndex = chooseFeature(dataSet)    #選擇特征
    bestFeatureName = featNames[bestFeatureIndex]
    del featureName[bestFeatureIndex]        #移除已選特征列
    decisionTree = {bestFeatureName: {}}
    
    featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex]))    #已選特征列所包含的類别， 通過遞歸生成決策樹
    for v in featureValueUnique:
        copyFeatureName = featureName[:]
        subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
        decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, copyFeatureName)
    return decisionTree
    
def classify(decisionTree, featnames, featList):
    """ 使用訓練所得的決策樹進行分類 """
    classLabel = None
    root = decisionTree.keys()[0]
    firstGenDict = decisionTree[root] 
    featIndex = featnames.index(root)
    for k in firstGenDict.keys():
        if featList[featIndex] == k:
            if isinstance(firstGenDict[k], dict):  #若子節點仍是樹，則遞歸查找
                classLabel = classify(firstGenDict[k], featnames, featList)
            else:
                classLabel = firstGenDict[k]
    return classLabel
           

下面用鸢尾花資料集對該算法進行測試。由于ID3算法隻能用于标稱型資料，是以用在對連續型的數值資料上時，還需要對資料進行離散化，離散化的方法稍後說明，此處為了簡化，先使用每一種特征所有連續性數值的中值作為分界點，小于中值的标記為1，大于中值的标記為0。訓練1000次，統計準确率均值。

from sklearn import datasets
from sklearn.model_selection import train_test_split

iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]

scoreL = []
for i in range(1000):  #對該過程進行10000次
    trainData, testData = train_test_split(data)  #區分測試集和訓練集
    
    featNames = iris.feature_names[:]
    for i in range(trainData.shape[1] - 1):  #對訓練集每個特征，以中值為分界點進行離散化
        splitPoint = np.mean(trainData[:, i])
        featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
        trainData[:, i] = [1 if x <= splitPoint else 0  for x in trainData[:, i]] 
        testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]
    
    decisionTree = creatDecisionTree(trainData, featNames)
    classifyLable = [classify(decisionTree, featNames, td) for td in testData]
    scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
           

輸出結果為：score: 0.7335，即準确率有73%。每次訓練和預測的準确率分布如下：

資料離散化

然而，在上例中對特征值離散化的劃分點實際上過于“野蠻”，此處介紹一種通過資訊增益最大的标準來對資料進行離散化。原理很簡單，當資訊增益最大時，說明用該點劃分能最大程度降低資料集的不确定性。

具體步驟如下：

• 對每個特征所包含的數值型特征值排序
• 對相鄰兩個特征值取均值，這些均值就是待選的劃分點
• 用每一個待選點把該特征的特征值劃分成兩類，小于該特征點置為1， 大于該特征點置為0，計算此時的條件熵，并計算出資訊增益
• 選擇資訊使資訊增益最大的劃分點進行特征離散化

實作代碼如下：

def filterRawData(dataSet, colIndex, value, tag):
    """ 用于把每個特征的連續值按照區分點分成兩類，加入tag參數，可用于标記篩選的是哪一部分資料"""
    filterDataList = []
    for r in dataSet:
        if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
            newR = r[:colIndex]
            newR = np.append(newR, (r[colIndex + 1:]))
            filterDataList.append(newR)
    return np.array(filterDataList)
            
def dataDiscretization(dataSet, featName):
    """ 對資料每個特征的數值型特征值進行離散化 """
    featureNum = dataSet.shape[1] - 1
    entropy = calShannonEnt(dataSet)

    for featIndex in range(featureNum):  #對于每一個特征
        uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
        meanPoint = []

        for i in range(len(uniqueValues) - 1):  # 求出相鄰兩個值的平均值
            meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
        bestInfoGain = 0.0
        bestMeanPoint = -1
        for mp in meanPoint:     #對于每個劃分點
            subEntropy = 0.0     #計算該劃分點的資訊熵
            for tag in range(2):  #分别劃分為兩類
                subDataSet = filterRawData(dataSet, featIndex, mp, tag)
                p = 1.0 * len(subDataSet) / len(dataSet)
                subEntropy += p * calShannonEnt(subDataSet)
     
            ## 計算資訊增益
            infoGain = entropy - subEntropy
            ## 選擇最大資訊增益
            if infoGain >= bestInfoGain:
                bestInfoGain = infoGain
                bestMeanPoint = mp
        featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
        dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
    return dataSet, featName    
           

重新對資料進行離散化，并重複該步驟1000次，同時用sklearn中的DecisionTreeClassifier對相同資料進行分類，分别統計平均準确率。運作代碼如下:

from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000):  #對該過程進行1000次
    featNames = iris.feature_names[:]
    trainData, testData = train_test_split(data)  #區分測試集和訓練集
    trainData_tmp = copy.copy(trainData)
    testData_tmp = copy.copy(testData)
    discritizationData,  discritizationFeatName= dataDiscretization(trainData, featNames) #根據資訊增益離散化
    for i in range(testData.shape[1]-1):  #根據測試集的區分點離散化訓練集
        splitPoint = float(discritizationFeatName[i].split('<=')[-1])
        testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
    decisionTree = creatDecisionTree(trainData, featNames)
    classifyLable = [classify(decisionTree, featNames, td) for td in testData]
    scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
    
    clf = DecisionTreeClassifier('entropy')
    clf.fit(trainData[:, :-1], trainData[:, -1])
    clf.predict(testData[:, :-1])
    scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))
    
print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
plt.show()
           

兩者準确率分别為：

score: 0.7037894736842105

score-sk: 0.7044736842105263

準确率分布如下：

兩者的結果非常一樣。

（但是。。為什麼根據資訊熵離散化得到的準确率比直接用均值離散化的準确率還要低啊？？哇的哭出聲。。）

最後一次決策樹圖形如下：

決策樹剪枝

由于決策樹是完全依照訓練集生成的，有可能會有過拟合現象，是以一般會對生成的決策樹進行剪枝。常用的是通過決策樹損失函數剪枝，決策樹損失函數表示為: C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T| Ca​(T)=t=1∑T​Nt​Ht​(T)+α∣T∣

其中， H t ( T ) H_t(T) Ht​(T)表示葉子節點t的熵值，T表示決策樹的深度。前項 ∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T) ∑t=1T​Nt​Ht​(T)是決策樹的經驗損失函數當随着T的增加，該節點被不停的劃分的時候，熵值可以達到最小，然而T的增加會使後項的值增大。決策樹損失函數要做的就是在兩者之間進行平衡，使得該值最小。

對于決策樹損失函數的了解，如何了解決策樹的損失函數? - 陶輕松的回答 - 知乎這個回答寫得挺好，可以按照答主的思路了解一下

C4.5算法

ID3算法通過資訊增益來進行特征選擇會有一個比較明顯的缺點：即在選擇的過程中該算法會優先選擇類别較多的屬性（這些屬性的不确定性小，條件熵小，是以資訊增益會大），另外，ID3算法無法解決當每個特征屬性中每個分類都隻有一個樣本的情況（此時每個屬性的條件熵都為0）。

C4.5算法ID3算法的改進，它不是依據資訊增益進行特征選擇，而是依據資訊增益率，它添加了特征分裂資訊作為懲罰項。定義分裂資訊： S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|} SplitInfo(X,Y)=−i∑n​∣X∣∣Xi​∣​log∣X∣∣Xi​∣​則資訊增益率為： G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)} GainRatio(X,Y)=SplitInfo(X,Y)d(X,Y)​

關于ID3和C4.5算法

在學習分類回歸決策樹算法時，看了不少的資料和部落格。關于這兩個算法，ID3算法是最早的分類算法，這個算法剛出生的時候其實帶有很多缺陷：

• 無法處理連續性特征資料
• 特征選取會傾向于分類較多的特征
• 沒有解決過拟合的問題
• 沒有解決缺失值的問題

即該算法出生時是沒有帶有連續特征離散化、剪枝等步驟的。C4.5作為ID3的改進版本彌補列ID3算法不少的缺陷：

• 通過資訊最大增益的标準離散化連續的特征資料
• 在選擇特征是标準從“最大資訊增益”改為“最大資訊增益率”
• 通過加入正則項系數對決策樹進行剪枝
• 對缺失值的處理展現在兩個方面：特征選擇和生成決策樹。初始條件下對每個樣本的權重置為1。
  • 特征選擇：在選取最優特征時，計算出每個特征的資訊增益後，需要乘以一個**“非缺失值樣本權重占總樣本權重的比例”**作為系數來對比每個特征資訊增益的大小
  • 生成決策樹：在生成決策樹時，對于缺失的樣本我們按照一定比例把它歸屬到每個特征值中，比例為該特征每一個特征值占非缺失資料的比重

關于C4.5和CART回歸樹

作為ID3的改進版本，C4.5克服了許多缺陷，但是它自身還是存在不少問題：

• C4.5的熵運算中涉及了對數運算，在資料量大的時候效率非常低。
• C4.5的剪枝過于簡單
• C4.5隻能用于分類運算不能用于回歸
• 當特征有多個特征值是C4.5生成多叉樹會使樹的深度加深