摘要：也就是說，決策樹有兩種分類樹和回歸樹。我們可以把決策樹看作是一個規則的集合。這樣可以提高決策樹學習的效率。解決這個問題的辦法是考慮決策樹的復雜度，對已生成的決策樹進行簡化，也就是常說的剪枝處理。最后得到一個決策樹。

一天，小迪與小西想養一只寵物。

小西：小迪小迪，好想養一只寵物呀，但是不知道養那種寵物比較合適。

小迪：好呀，養只寵物會給我們的生活帶來很多樂趣呢。不過養什么寵物可要考慮好，這可不能馬虎。我們需要考慮一些比較重要的問題。

小西：我也考慮了好多呀，可是還是很難去選擇。我想養可愛的小兔兔，可是兔兔吃得很挑剔，又想養狗狗，可是狗狗每天都需要遛它，怕自己沒有時間呀。

小迪：其實我們可以繪制一個決策樹，決策樹是機器學習中做判斷的常用模型。原理也非常簡單。

小西：決策樹是什么，怎么能幫助我們作出決策呢？

小迪：別著急，聽我，慢慢道來~

決策樹（Decision Tree）是有監督學習中的一種算法，并且是一種基本的分類與回歸的方法。也就是說，決策樹有兩種：分類樹和回歸樹。這里我們主要討論分類樹。

決策樹算法的本質就是樹形結構，只需要有一些設計好的問題，就可以對數據進行分類了。在這里，我們需要了解三個概念：

? 我們可以把決策樹看作是一個if-then規則的集合。將決策樹轉換成if-then規則的過程是這樣的：

由決策樹的根節點到葉節點的每一條路徑構建一條規則

路徑上中間節點的特征對應著規則的條件，也葉節點的類標簽對應著規則的結論

決策樹的路徑或者其對應的if-then規則集合有一個重要的性質：互斥并且完備。也就是說，每一個實例都被 有且僅有一條路徑或者規則所覆蓋。這里的覆蓋是指實例的特征與路徑上的特征一致，或實例滿足規則的條件。

? 使用決策樹做分類的每一個步驟都很重要，首先要收集足夠多的數據，如果數據收集不到位，將會導致沒有足夠的特征去構建錯誤率低的決策樹。數據特征充足，但是不知道用哪些特征好，也會導致最終無法構建出分類效果好的決策樹。

? 決策樹構建過程可以概括為3個步驟：特征選擇、決策樹的生成和決策樹的剪枝。

? 特征選擇就是決定用哪個特征來劃分特征空間，其目的在于選取對訓練數據具有分類能力的特征。這樣可以提高決策樹學習的效率。如果利用一個特征進行分類的結果與隨機分類的結果沒有很大的差別，則稱這個特征是沒有分類能力的，經驗上扔掉這些特征對決策樹學習的精度影響不會很大。

? 那如何來選擇最優的特征來劃分呢？一般而言，隨著劃分過程不斷進行，我們希望決策樹的分支節點所包含的樣本盡可能屬于同一類別，也就是節點的純度（purity）越來越高。

? 下面三個圖表示的是純度越來越低的過程，最后一個表示的是三幅圖中純度最低的狀態。

? 在實際使用中，我們衡量的常常是不純度。度量不純度的指標有很多種，比如：熵、增益率、基尼值數。

? 這里我們使用的是熵，也叫作香農熵，這個名字來源于信息論之父 克勞德·香農。

1.1 香農熵及計算函數

熵定義為信息的期望值。在信息論與概率統計中，熵是表示隨機變量不確定性的度量。

假定當前樣本集合D中一共有n類樣本，第i類樣本為$x_i$，那么$x_i$的信息定義為：

$$ l(x_i)=-log_2p(x_i) $$

其中$p(x_i)$是選擇該分類的概率。

通過上式，我們可以得到所有類別的信息。為了計算熵，我們需要計算所有類別所有可能值包含的信息期望值(數學期望)，通過下面的公式得到：

$$ Ent(D)=-sum^n_{i=1}p(x_i)log_2p(x_i) $$

$Ent(D)$的值越小，則D的不純度就越低。

香農熵的python代碼如下：

"""
函數功能：計算香農熵
參數說明：
    dataSet：原始數據集
返回：
    ent:香農熵的值
"""
def calEnt(dataSet):
    n = dataSet.shape[0]                             #數據集總行數
    iset = dataSet.iloc[:,-1].value_counts()         #標簽的所有類別
    p = iset/n                                       #每一類標簽所占比
    ent = (-p*np.log2(p)).sum()                      #計算信息熵
    return ent

我們以海洋生物數據為例，構建數據集，并計算其香農熵

表1 海洋生物數據

#創建數據集
import numpy as np
import pandas as pd

def createDataSet():
    row_data = {"no surfacing":[1,1,1,0,0],
                "flippers":[1,1,0,1,1],
                "fish":["yes","yes","no","no","no"]}
    dataSet = pd.DataFrame(row_data)
    return dataSet

dataSet = createDataSet()
dataSet

calEnt(dataSet)

熵越高，信息的不純度就越高。也就是混合的數據就越多。

1.2 信息增益

? 信息增益（Information Gain）的計算公式其實就是父節點的信息熵與其下所有子節點總信息熵之差。但這里要注意的是，此時計算子節點的總信息熵不能簡單求和，而要求在求和匯總之前進行修正。

假設離散屬性a有V個可能的取值${a^1,a^2,……,a^V}$,若使用a對樣本數據集D進行劃分，則會產生V個分支節點，其中第v個分支節點包含了D中所有在屬性a上取值為$a^v$的樣本，記為$D^v$.我們可根據信息熵的計算公式計算出$D^v$的信息熵，再考慮到不同的分支節點所包含的樣本數不同，給分支節點賦予權重$|D^v|/|D|$,這就是所謂的的修正。

所以信息增益的計算公式為

$$ Gain(D,a)=Ent(D)-sum^V_{v=1}frac{|D^v|}{|D|}Ent(D^v) $$

那我們手動計算一下，海洋生物數據集中第0列的信息增益：

$$ egin{align*} Gain("no surfacing") &= Ent(D)- [frac{3}{5}Ent(D_1)+frac{2}{5}Ent(D_2)] &= calEnt(dataSet)-[frac{3}{5}(-frac{2}{3}log_2frac{2}{3}-frac{1}{3}log_2frac{1}{3})+frac{2}{5}(-frac{2}{2}log_2frac{2}{2})] &= 0.97-0.55 &= 0.42 end{align*} $$

a=(3/5)*(-(2/3)*np.log2(2/3)-(1/3)*np.log2(1/3))
calEnt(dataSet)-a

用同樣的方法，把第1列的信息增益也算出來，結果為0.17

? 劃分數據集的最大準則是選擇最大信息增益，也就是信息下降最快的方向。

"""
函數功能：根據信息增益選擇出最佳數據集切分的列
參數說明：
    dataSet：原始數據集
返回：
    axis:數據集最佳切分列的索引
"""

#選擇最優的列進行切分
def bestSplit(dataSet):
    baseEnt = calEnt(dataSet)                                #計算原始熵
    bestGain = 0                                             #初始化信息增益
    axis = -1                                                #初始化最佳切分列，標簽列
    for i in range(dataSet.shape[1]-1):                      #對特征的每一列進行循環
        levels= dataSet.iloc[:,i].value_counts().index       #提取出當前列的所有取值
        ents = 0                                               #初始化子節點的信息熵       
        for j in levels:                                     #對當前列的每一個取值進行循環
            childSet = dataSet[dataSet.iloc[:,i]==j]         #某一個子節點的dataframe
            ent = calEnt(childSet)                             #計算某一個子節點的信息熵
            ents += (childSet.shape[0]/dataSet.shape[0])*ent #計算當前列的信息熵
        #print(f"第{i}列的信息熵為{ents}")
        infoGain = baseEnt-ents                                 #計算當前列的信息增益
        #print(f"第{i}列的信息增益為{infoGain}")
        if (infoGain > bestGain):
            bestGain = infoGain                              #選擇最大信息增益
            axis = i                                         #最大信息增益所在列的索引
    return axis

通過上面手動計算，可以得出：

第0列的信息增益為0.42，第1列的信息增益為0.17，0.42>0.17，所以應該選擇第0列進行切分數據集。

接下來，我們來驗證我們構造的數據集最佳切分函數返回的結果與手動計算的結果是否一致。

bestSplit(dataSet)        #返回的結果為0，即選擇第0列來切分數據集

通過最佳切分函數返回最佳切分列的索引，可以根據這個索引，構建一個按照給定列切分數據集的函數

"""
函數功能：按照給定的列劃分數據集
參數說明：
    dataSet：原始數據集
    axis：指定的列索引
    value：指定的屬性值
返回：
    redataSet：按照指定列索引和屬性值切分后的數據集
"""

def mySplit(dataSet,axis,value):
    col = dataSet.columns[axis]
    redataSet = dataSet.loc[dataSet[col]==value,:].drop(col,axis=1)
    return redataSet  

驗證函數，以axis=0，value=1為例

mySplit(dataSet,0,1)

? 目前我們已經學習了從數據集構造決策樹算法所需要的子功能模塊，其工作原理如下：得到原始數據集，然后基于最好的屬性值劃分數據集，由于特征值可能多于兩個，因此可能存在大于兩個分支的數據集劃分。第一次劃分之后，數據集被向下傳遞到樹的分支的下一個結點。在這個結點上，我們可以再次劃分數據。因此我們可以采用遞歸的原則處理數據集。

? 決策樹生成算法遞歸地產生決策樹，直到不能繼續下去未為止。這樣產生的樹往往對訓練數據的分類很準確，但對未知的測試數據的分類卻沒有那么準確，即出現過擬合現象。過擬合的原因在于學習時過多地考慮如何提高對訓練數據的正確分類，從而構建出過于復雜的決策樹。解決這個問題的辦法是考慮決策樹的復雜度，對已生成的決策樹進行簡化，也就是常說的剪枝處理。剪枝處理的具體講解我會放在回歸樹里面。

構建決策樹的算法有很多，比如ID3、C4.5和CART，這里我們選擇ID3算法。

ID3算法的核心是在決策樹各個節點上對應信息增益準則選擇特征，遞歸地構建決策樹。具體方法是：從根節點開始，對節點計算所有可能的特征的信息增益，選擇信息增益最大的特征作為節點的特征，由該特征的不同取值建立子節點；再對子節點遞歸地調用以上方法，構建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止。最后得到一個決策樹。

? 遞歸結束的條件是：程序遍歷完所有的特征列，或者每個分支下的所有實例都具有相同的分類。如果所有實例具有相同分類，則得到一個葉節點。任何到達葉節點的數據必然屬于葉節點的分類，即葉節點里面必須是標簽。

"""
函數功能：基于最大信息增益切分數據集，遞歸構建決策樹
參數說明：
    dataSet：原始數據集（最后一列是標簽）
返回：
    myTree：字典形式的樹
"""
def createTree(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 = bestSplit(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

查看函數運行結果

myTree = createTree(dataSet)
myTree

? 構造決策樹是很耗時的任務，即使處理很小的數據集，也要花費幾秒的時間，如果數據集很大，將會耗費很多計算時間。因此為了節省時間，建好樹之后立馬將其保存，后續使用直接調用即可。

? 這里使用的是numpy里面的save()函數，它可以直接把字典形式的數據保存為.npy文件，調用的時候直接使用load()函數即可。

#樹的存儲
np.save("myTree.npy",myTree)

#樹的讀取
read_myTree = np.load("myTree.npy").item()   
read_myTree

"""
函數功能：對一個測試實例進行分類
參數說明：
    inputTree：已經生成的決策樹
    labels：存儲選擇的最優特征標簽
    testVec：測試數據列表，順序對應原數據集
返回：
    classLabel：分類結果
"""
def classify(inputTree,labels, testVec):
    firstStr = next(iter(inputTree))                   #獲取決策樹第一個節點
    secondDict = inputTree[firstStr]                   #下一個字典
    featIndex = labels.index(firstStr)                    #第一個節點所在列的索引
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]) == dict :
                classLabel = classify(secondDict[key], labels, testVec)
            else: 
                classLabel = secondDict[key]
    return classLabel

"""
函數功能：對測試集進行預測，并返回預測后的結果
參數說明：
    train：訓練集
    test：測試集
返回：
    test：預測好分類的測試集
"""
def acc_classify(train,test):
    inputTree = createTree(train)                        #根據測試集生成一棵樹
    labels = list(train.columns)                        #數據集所有的列名稱
    result = []
    for i in range(test.shape[0]):                        #對測試集中每一條數據進行循環
        testVec = test.iloc[i,:-1]                        #測試集中的一個實例
        classLabel = classify(inputTree,labels,testVec)    #預測該實例的分類
        result.append(classLabel)                        #將分類結果追加到result列表中
    test["predict"]=result                                #將預測結果追加到測試集最后一列
    acc = (test.iloc[:,-1]==test.iloc[:,-2]).mean()        #計算準確率
    print(f"模型預測準確率為{acc}")
    return test 

測試函數

train = dataSet
test = dataSet.iloc[:3,:]
acc_classify(train,test)

使用SKlearn中graphviz包實現決策樹的繪制

#導入相應的包
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
import graphviz

#特征
Xtrain = dataSet.iloc[:,:-1]
#標簽
Ytrain = dataSet.iloc[:,-1]
labels = Ytrain.unique().tolist()
Ytrain = Ytrain.apply(lambda x: labels.index(x))  #將本文轉換為數字

#繪制樹模型
clf = DecisionTreeClassifier()
clf = clf.fit(Xtrain, Ytrain)
tree.export_graphviz(clf)
dot_data = tree.export_graphviz(clf, out_file=None)
graphviz.Source(dot_data)

#給圖形增加標簽和顏色
dot_data = tree.export_graphviz(clf, out_file=None,
                                feature_names=["no surfacing", "flippers"],
                                class_names=["fish", "not fish"],
                                filled=True, rounded=True,
                                special_characters=True)
graphviz.Source(dot_data)

#利用render方法生成圖形
graph = graphviz.Source(dot_data)
graph.render("fish")

? 這樣最終的樹模型就畫出來啦。