摘要：也就是說(shuō)，決策樹(shù)有兩種分類(lèi)樹(shù)和回歸樹(shù)。我們可以把決策樹(shù)看作是一個(gè)規(guī)則的集合。這樣可以提高決策樹(shù)學(xué)習(xí)的效率。解決這個(gè)問(wèn)題的辦法是考慮決策樹(shù)的復(fù)雜度，對(duì)已生成的決策樹(shù)進(jìn)行簡(jiǎn)化，也就是常說(shuō)的剪枝處理。最后得到一個(gè)決策樹(shù)。

一天，小迪與小西想養(yǎng)一只寵物。

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

小迪：好呀，養(yǎng)只寵物會(huì)給我們的生活帶來(lái)很多樂(lè)趣呢。不過(guò)養(yǎng)什么寵物可要考慮好，這可不能馬虎。我們需要考慮一些比較重要的問(wèn)題。

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

小迪：其實(shí)我們可以繪制一個(gè)決策樹(shù)，決策樹(shù)是機(jī)器學(xué)習(xí)中做判斷的常用模型。原理也非常簡(jiǎn)單。

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

小迪：別著急，聽(tīng)我，慢慢道來(lái)~

決策樹(shù)（Decision Tree）是有監(jiān)督學(xué)習(xí)中的一種算法，并且是一種基本的分類(lèi)與回歸的方法。也就是說(shuō)，決策樹(shù)有兩種：分類(lèi)樹(shù)和回歸樹(shù)。這里我們主要討論分類(lèi)樹(shù)。

決策樹(shù)算法的本質(zhì)就是樹(shù)形結(jié)構(gòu)，只需要有一些設(shè)計(jì)好的問(wèn)題，就可以對(duì)數(shù)據(jù)進(jìn)行分類(lèi)了。在這里，我們需要了解三個(gè)概念：

? 我們可以把決策樹(shù)看作是一個(gè)if-then規(guī)則的集合。將決策樹(shù)轉(zhuǎn)換成if-then規(guī)則的過(guò)程是這樣的：

由決策樹(shù)的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑構(gòu)建一條規(guī)則

路徑上中間節(jié)點(diǎn)的特征對(duì)應(yīng)著規(guī)則的條件，也葉節(jié)點(diǎn)的類(lèi)標(biāo)簽對(duì)應(yīng)著規(guī)則的結(jié)論

決策樹(shù)的路徑或者其對(duì)應(yīng)的if-then規(guī)則集合有一個(gè)重要的性質(zhì)：互斥并且完備。也就是說(shuō)，每一個(gè)實(shí)例都被 有且僅有一條路徑或者規(guī)則所覆蓋。這里的覆蓋是指實(shí)例的特征與路徑上的特征一致，或?qū)嵗凉M足規(guī)則的條件。

? 使用決策樹(shù)做分類(lèi)的每一個(gè)步驟都很重要，首先要收集足夠多的數(shù)據(jù)，如果數(shù)據(jù)收集不到位，將會(huì)導(dǎo)致沒(méi)有足夠的特征去構(gòu)建錯(cuò)誤率低的決策樹(shù)。數(shù)據(jù)特征充足，但是不知道用哪些特征好，也會(huì)導(dǎo)致最終無(wú)法構(gòu)建出分類(lèi)效果好的決策樹(shù)。

? 決策樹(shù)構(gòu)建過(guò)程可以概括為3個(gè)步驟：特征選擇、決策樹(shù)的生成和決策樹(shù)的剪枝。

? 特征選擇就是決定用哪個(gè)特征來(lái)劃分特征空間，其目的在于選取對(duì)訓(xùn)練數(shù)據(jù)具有分類(lèi)能力的特征。這樣可以提高決策樹(shù)學(xué)習(xí)的效率。如果利用一個(gè)特征進(jìn)行分類(lèi)的結(jié)果與隨機(jī)分類(lèi)的結(jié)果沒(méi)有很大的差別，則稱(chēng)這個(gè)特征是沒(méi)有分類(lèi)能力的，經(jīng)驗(yàn)上扔掉這些特征對(duì)決策樹(shù)學(xué)習(xí)的精度影響不會(huì)很大。

? 那如何來(lái)選擇最優(yōu)的特征來(lái)劃分呢？一般而言，隨著劃分過(guò)程不斷進(jìn)行，我們希望決策樹(shù)的分支節(jié)點(diǎn)所包含的樣本盡可能屬于同一類(lèi)別，也就是節(jié)點(diǎn)的純度（purity）越來(lái)越高。

? 下面三個(gè)圖表示的是純度越來(lái)越低的過(guò)程，最后一個(gè)表示的是三幅圖中純度最低的狀態(tài)。

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

? 這里我們使用的是熵，也叫作香農(nóng)熵，這個(gè)名字來(lái)源于信息論之父 克勞德·香農(nóng)。

1.1 香農(nóng)熵及計(jì)算函數(shù)

熵定義為信息的期望值。在信息論與概率統(tǒng)計(jì)中，熵是表示隨機(jī)變量不確定性的度量。

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

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

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

通過(guò)上式，我們可以得到所有類(lèi)別的信息。為了計(jì)算熵，我們需要計(jì)算所有類(lèi)別所有可能值包含的信息期望值(數(shù)學(xué)期望)，通過(guò)下面的公式得到：

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

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

香農(nóng)熵的python代碼如下：

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

我們以海洋生物數(shù)據(jù)為例，構(gòu)建數(shù)據(jù)集，并計(jì)算其香農(nóng)熵

表1 海洋生物數(shù)據(jù)

#創(chuàng)建數(shù)據(jù)集
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)

熵越高，信息的不純度就越高。也就是混合的數(shù)據(jù)就越多。

1.2 信息增益

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

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

所以信息增益的計(jì)算公式為

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

那我們手動(dòng)計(jì)算一下，海洋生物數(shù)據(jù)集中第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列的信息增益也算出來(lái)，結(jié)果為0.17

? 劃分?jǐn)?shù)據(jù)集的最大準(zhǔn)則是選擇最大信息增益，也就是信息下降最快的方向。

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

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

通過(guò)上面手動(dòng)計(jì)算，可以得出：

第0列的信息增益為0.42，第1列的信息增益為0.17，0.42>0.17，所以應(yīng)該選擇第0列進(jìn)行切分?jǐn)?shù)據(jù)集。

接下來(lái)，我們來(lái)驗(yàn)證我們構(gòu)造的數(shù)據(jù)集最佳切分函數(shù)返回的結(jié)果與手動(dòng)計(jì)算的結(jié)果是否一致。

bestSplit(dataSet)        #返回的結(jié)果為0，即選擇第0列來(lái)切分?jǐn)?shù)據(jù)集

通過(guò)最佳切分函數(shù)返回最佳切分列的索引，可以根據(jù)這個(gè)索引，構(gòu)建一個(gè)按照給定列切分?jǐn)?shù)據(jù)集的函數(shù)

"""
函數(shù)功能：按照給定的列劃分?jǐn)?shù)據(jù)集
參數(shù)說(shuō)明：
    dataSet：原始數(shù)據(jù)集
    axis：指定的列索引
    value：指定的屬性值
返回：
    redataSet：按照指定列索引和屬性值切分后的數(shù)據(jù)集
"""

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

驗(yàn)證函數(shù)，以axis=0，value=1為例

mySplit(dataSet,0,1)

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

? 決策樹(shù)生成算法遞歸地產(chǎn)生決策樹(shù)，直到不能繼續(xù)下去未為止。這樣產(chǎn)生的樹(shù)往往對(duì)訓(xùn)練數(shù)據(jù)的分類(lèi)很準(zhǔn)確，但對(duì)未知的測(cè)試數(shù)據(jù)的分類(lèi)卻沒(méi)有那么準(zhǔn)確，即出現(xiàn)過(guò)擬合現(xiàn)象。過(guò)擬合的原因在于學(xué)習(xí)時(shí)過(guò)多地考慮如何提高對(duì)訓(xùn)練數(shù)據(jù)的正確分類(lèi)，從而構(gòu)建出過(guò)于復(fù)雜的決策樹(shù)。解決這個(gè)問(wèn)題的辦法是考慮決策樹(shù)的復(fù)雜度，對(duì)已生成的決策樹(shù)進(jìn)行簡(jiǎn)化，也就是常說(shuō)的剪枝處理。剪枝處理的具體講解我會(huì)放在回歸樹(shù)里面。

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

ID3算法的核心是在決策樹(shù)各個(gè)節(jié)點(diǎn)上對(duì)應(yīng)信息增益準(zhǔn)則選擇特征，遞歸地構(gòu)建決策樹(shù)。具體方法是：從根節(jié)點(diǎn)開(kāi)始，對(duì)節(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為節(jié)點(diǎn)的特征，由該特征的不同取值建立子節(jié)點(diǎn)；再對(duì)子節(jié)點(diǎn)遞歸地調(diào)用以上方法，構(gòu)建決策樹(shù)；直到所有特征的信息增益均很小或沒(méi)有特征可以選擇為止。最后得到一個(gè)決策樹(shù)。

? 遞歸結(jié)束的條件是：程序遍歷完所有的特征列，或者每個(gè)分支下的所有實(shí)例都具有相同的分類(lèi)。如果所有實(shí)例具有相同分類(lèi)，則得到一個(gè)葉節(jié)點(diǎn)。任何到達(dá)葉節(jié)點(diǎn)的數(shù)據(jù)必然屬于葉節(jié)點(diǎn)的分類(lèi)，即葉節(jié)點(diǎn)里面必須是標(biāo)簽。

"""
函數(shù)功能：基于最大信息增益切分?jǐn)?shù)據(jù)集，遞歸構(gòu)建決策樹(shù)
參數(shù)說(shuō)明：
    dataSet：原始數(shù)據(jù)集（最后一列是標(biāo)簽）
返回：
    myTree：字典形式的樹(shù)
"""
def createTree(dataSet):
    featlist = list(dataSet.columns)                          #提取出數(shù)據(jù)集所有的列
    classlist = dataSet.iloc[:,-1].value_counts()             #獲取最后一列類(lèi)標(biāo)簽
    #判斷最多標(biāo)簽數(shù)目是否等于數(shù)據(jù)集行數(shù)，或者數(shù)據(jù)集是否只有一列
    if classlist[0]==dataSet.shape[0] or dataSet.shape[1] == 1:
        return classlist.index[0]                             #如果是，返回類(lèi)標(biāo)簽
    axis = bestSplit(dataSet)                                 #確定出當(dāng)前最佳切分列的索引
    bestfeat = featlist[axis]                                 #獲取該索引對(duì)應(yīng)的特征
    myTree = {bestfeat:{}}                                    #采用字典嵌套的方式存儲(chǔ)樹(shù)信息
    del featlist[axis]                                        #刪除當(dāng)前特征
    valuelist = set(dataSet.iloc[:,axis])                     #提取最佳切分列所有屬性值
    for value in valuelist:                                      #對(duì)每一個(gè)屬性值遞歸建樹(shù)
        myTree[bestfeat][value] = createTree(mySplit(dataSet,axis,value))
    return myTree

查看函數(shù)運(yùn)行結(jié)果

myTree = createTree(dataSet)
myTree

? 構(gòu)造決策樹(shù)是很耗時(shí)的任務(wù)，即使處理很小的數(shù)據(jù)集，也要花費(fèi)幾秒的時(shí)間，如果數(shù)據(jù)集很大，將會(huì)耗費(fèi)很多計(jì)算時(shí)間。因此為了節(jié)省時(shí)間，建好樹(shù)之后立馬將其保存，后續(xù)使用直接調(diào)用即可。

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

#樹(shù)的存儲(chǔ)
np.save("myTree.npy",myTree)

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

"""
函數(shù)功能：對(duì)一個(gè)測(cè)試實(shí)例進(jìn)行分類(lèi)
參數(shù)說(shuō)明：
    inputTree：已經(jīng)生成的決策樹(shù)
    labels：存儲(chǔ)選擇的最優(yōu)特征標(biāo)簽
    testVec：測(cè)試數(shù)據(jù)列表，順序?qū)?yīng)原數(shù)據(jù)集
返回：
    classLabel：分類(lèi)結(jié)果
"""
def classify(inputTree,labels, testVec):
    firstStr = next(iter(inputTree))                   #獲取決策樹(shù)第一個(gè)節(jié)點(diǎn)
    secondDict = inputTree[firstStr]                   #下一個(gè)字典
    featIndex = labels.index(firstStr)                    #第一個(gè)節(jié)點(diǎn)所在列的索引
    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

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

測(cè)試函數(shù)

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

使用SKlearn中g(shù)raphviz包實(shí)現(xiàn)決策樹(shù)的繪制

#導(dǎo)入相應(yīng)的包
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
import graphviz

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

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

#給圖形增加標(biāo)簽和顏色
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")

? 這樣最終的樹(shù)模型就畫(huà)出來(lái)啦。