image.png

本文基于李航博士的【統(tǒng)計(jì)學(xué)習(xí)方法】第五章 決策樹，包含ID3代碼。

決策樹(decisionTree)是一種基本的分類和回歸方法。此文僅討論用于分類方法的決策樹。

決策樹的學(xué)習(xí)通常分為3步：

• 特征選擇
• 決策樹生成
• 決策樹修剪

決策樹的學(xué)習(xí)的思想主要源于

• 1986年，Quinlan提出的ID3算法
• 1993年，Quinlan提出的C4.5算法
• 1984年，Beriman等人提出的CART算法

1.0 決策樹的模型與學(xué)習(xí)

1.1 決策樹模型

定義決策樹：

結(jié)點(diǎn)和有向邊.png

分類決策樹模型是一種描述對(duì)實(shí)例進(jìn)行分類的樹形結(jié)構(gòu)。決策樹由結(jié)點(diǎn)(node)和有向邊(directed edge)組成。結(jié)點(diǎn)又分為內(nèi)部結(jié)點(diǎn)(internal node)和葉結(jié)點(diǎn)(leaf node)。內(nèi)部結(jié)點(diǎn)表示一個(gè)特征或?qū)傩?，葉結(jié)點(diǎn)表示一個(gè)類。
形如：

image.png

其中，圓表示內(nèi)部結(jié)點(diǎn)，方框表示葉結(jié)點(diǎn)。

1.2 決策樹與if-then規(guī)則

if-then規(guī)則，簡(jiǎn)單來(lái)說(shuō)就是 ：

舉例：對(duì)于一個(gè)蘋果，外表是紅色的是紅蘋果，外表是綠色的是青蘋果。可以表示為：

if-then規(guī)則集合具有一個(gè)重要的性質(zhì)：

這就是說(shuō)每一個(gè)實(shí)例都被一條路徑或規(guī)則覆蓋，并且只被一條路徑或規(guī)則覆蓋。這里所謂的覆蓋是指實(shí)例的特征與路徑上的特征一致，或?qū)嵗凉M足規(guī)則的條件。

1.3 決策樹學(xué)習(xí)

給定數(shù)據(jù)集：

其中，為輸入實(shí)例（特征向量），含有個(gè)特征，為類標(biāo)記，, 為樣本容量。

目標(biāo)：
根據(jù)給定的訓(xùn)練數(shù)據(jù)集構(gòu)建一個(gè)決策樹模型，使它能夠?qū)?shí)例進(jìn)行正確分類。

2.0 特征選擇

2.1 特征選擇問題

特征選擇在于選取對(duì)訓(xùn)練數(shù)據(jù)具有分類能力的特征，這樣可以提高決策樹學(xué)習(xí)的效率。

如果我們利用某一個(gè)特征進(jìn)行分類的結(jié)果與隨機(jī)分類的結(jié)果沒什么很大的差別的話，則稱這個(gè)特征沒有分類能力。

那么問題來(lái)了，怎么選擇特征呢？

通常特征選擇的準(zhǔn)則是

下面通過例子來(lái)說(shuō)明一下。

目標(biāo)：
希望通過所給的訓(xùn)練集數(shù)據(jù)，學(xué)習(xí)一個(gè)貸款申請(qǐng)的決策樹。當(dāng)新的客戶提出貸款申請(qǐng)的時(shí)候，根據(jù)申請(qǐng)人的特征利用決策樹決定是否批準(zhǔn)貸款申請(qǐng)。

可見這里共有4個(gè)特征可供選擇。用特征選擇的準(zhǔn)則是。接下來(lái)介紹。

2.2 信息增益

：
熵是表示隨機(jī)變量不確定性的度量。

這里我想說(shuō)一個(gè)熵的比較形象的比喻。
我第一次學(xué)習(xí)到熵這個(gè)概念，是在高中的化學(xué)課熵。老師講完熵的概念之后，全班進(jìn)入無(wú)言的狀態(tài)，大家都不理解。當(dāng)時(shí)的化學(xué)老師也是我們班的班主任，他雖然平時(shí)不太靠譜，講課還是挺有意思的。他說(shuō)，不用把熵想的那么復(fù)雜，熵就是你房間的雜亂程度，那么可以想見，熵只會(huì)越來(lái)越大，即使你剛剛收拾房間，你的房間還是會(huì)越來(lái)越亂...
我 ...深以為然。

設(shè)是一個(gè)取有限個(gè)值的隨機(jī)變量，其概率分布為

則隨機(jī)變量的熵定義為

若，則定義。通常對(duì)數(shù)取以2為底，或是以為底，熵的單位分布為比特（bit）或是納特（nat）。
由上式可知，熵只依賴的分布，而已的值無(wú)關(guān)，則的熵還可記作，即

則從定義可知

當(dāng)隨機(jī)變量只取2個(gè)值的時(shí)候，例如時(shí)，的分布為

熵為

熵隨概率變化的曲線為

image.png

當(dāng)或時(shí)，隨機(jī)變量完全沒有不確定性，當(dāng)時(shí)，熵取值最大，隨機(jī)變量不確定性最大。

設(shè)隨機(jī)變量，其聯(lián)合概率分布

條件熵表示在已知隨機(jī)變量的條件下隨機(jī)變量的不確定性。隨機(jī)變量給定條件下隨機(jī)變量的條件熵(conditional entropy)，定義為給定條件下的條件概率分布的熵對(duì)的數(shù)學(xué)期望

信息增益
特征對(duì)訓(xùn)練集的信息增益

根據(jù)信息增益準(zhǔn)則的特征選擇方法：對(duì)訓(xùn)練集，計(jì)算其每個(gè)特征的信息增益，并比較大小，選擇信息增益最大的特征。

前期定義各個(gè)量：

訓(xùn)練集 特征,有個(gè)可能值，	類有個(gè)可能值，
根據(jù)的取值，劃分為個(gè)子集，, 為的樣本數(shù)	為屬于類的樣本數(shù)
	為特征的取值為，又屬于類的樣本數(shù)

信息增益的算法
輸入：訓(xùn)練集和特征；
輸出：特征對(duì)訓(xùn)練集的信息增益

1. 計(jì)算訓(xùn)練集的熵
   
2. 計(jì)算特征對(duì)數(shù)據(jù)集的條件熵
   
3. 計(jì)算信息增益
   

回看剛才的例子，

解：

1. 計(jì)算訓(xùn)練集的熵
   
2. 計(jì)算特征各個(gè)對(duì)數(shù)據(jù)集的信息增益，年齡，有工作，有自己的房子，信貸情況這4個(gè)特征分別以表示。
   
   

3. 比較各個(gè)特征的信息增益，（有自己的房子）的信息增益最大，選擇作為最優(yōu)特征。

代碼講解

這一次我很無(wú)聊的想用一下.csv文件類型。

CSV是一種通用的、相對(duì)簡(jiǎn)單的文件格式，被用戶、商業(yè)和科學(xué)廣泛應(yīng)用。包括kaggle的一個(gè)基礎(chǔ)算法比賽【泰坦尼克之災(zāi)】給的數(shù)據(jù)庫(kù)也是寫在.csv文件里的。
簡(jiǎn)單來(lái)說(shuō).csv文件就是能用excel打開的文件。

所以訓(xùn)練數(shù)據(jù)集部分如下，我存在一個(gè)loan.csv文件里了。對(duì).csv文件的各種處理一般由python的pandas模塊完成。

image.png

第一步，導(dǎo)入相關(guān)模塊

import numpy as np
import pandas as pd

第二步，讀入數(shù)據(jù)

data = pd.read_csv('loan.csv')

若是使用jupyter，可以即刻查看一下數(shù)據(jù)，和數(shù)據(jù)標(biāo)簽。

image.png

image.png

可以看出，除了'ID'之外前4個(gè)標(biāo)簽 'age', 'work', 'own house', 'Credit conditions'為我們一直在說(shuō)的特征，而最后一個(gè)標(biāo)簽'label'是我們所說(shuō)的類，所以要處理一下這些標(biāo)簽，

label = data.columns
features = list(label[1: -1]) #如上圖，label并不是是列表，為了方便下面引用，將它變?yōu)榱斜硇问?classes = label[-1]

第三步，計(jì)算訓(xùn)練集的熵：

這里會(huì)用到pandas的一個(gè)統(tǒng)計(jì)數(shù)據(jù)的功能，groupby(by = [列]).groups，將數(shù)據(jù)統(tǒng)計(jì)成字典的形式，這么說(shuō)比較抽象，看下圖，將我們用pandas讀入的data，分為2類，，Index表示索引，即第0，1，4，5，6，14（python計(jì)數(shù)從0開始）個(gè)數(shù)據(jù)的，第2，3，7，8，9，10，11，12，13個(gè)數(shù)據(jù)的.

image.png

那么計(jì)算訓(xùn)練集的熵

def empricalEntropy(data, classes):
    
    #計(jì)算每個(gè)類的樣本數(shù)
    C = {}#記錄每個(gè)類樣本數(shù)的字典
    C_temp = data.groupby(by = [classes]).groups#記錄每個(gè)類索引的字典
    for key in C_temp.keys():
        C[key] = len(C_temp[key])
    
    H_D = 0#初始化熵
    for key in C.keys():#key取0，1
        H_D -= C[key]/len(data) * np.log2(C[key]/len(data))
        
    return H_D

image.png

第四步，計(jì)算特征對(duì)數(shù)據(jù)集的條件熵

def empricalConditionalEntropy(data, feature, classes):
    D_temp = data.groupby(by = [feature]).groups #返回統(tǒng)計(jì)特征A的數(shù)據(jù)字典，它的key是特征A的各個(gè)取值，value是索引
    C_temp = data.groupby(by = [classes]).groups#返回統(tǒng)計(jì)分類的字典，它的key是分類的各個(gè)取值，value是索引
    
    H_DA = 0#初始化條件熵
    for key, i_index in D_temp.items():# D_temp的key是特征的各個(gè)取值
        D_i = len(i_index)#索引的長(zhǎng)度，即為某個(gè)特征值的樣本個(gè)數(shù)
        
        classConditionalEntropy = 0#H初始化H(Y|X=x_i)
        for label, k_index in C_temp.items():#key為0或者1
            D_ik = len(list(set(i_index).intersection(set(k_index))))#set(A).intersection(B)取集合A和B的交集
            if D_ik == 0:#計(jì)算機(jī)會(huì)在計(jì)算log0時(shí)返回nan，所以要把0的情況單獨(dú)處理
                classConditionalEntropy += 0
            else:
                classConditionalEntropy += (D_ik/D_i) * (np.log2(D_ik/D_i))
        
        D = len(data)
        H_DA -= D_i/D * classConditionalEntropy
        
    return H_DA

image.png

第五步 ，計(jì)算信息增益

def infoGain(data, features, classes):
    
    H_D = empricalEntropy(data, classes)
    
    #初始化
    maxEntropy = 0
    maxFeature = ''
    
    for feature in features:
        H_DA = empricalConditionalEntropy(data, feature, classes)
        
        G = H_D - H_DA

        print(feature, G)#輸出各個(gè)特征和G，方便查看

        #選出最優(yōu)特征
        if G > maxEntropy:
            maxEntropy = G
            maxFeature = feature  
    
    return maxEntropy, maxFeature

image.png

3.0 決策樹的生成

3.1 ID3算法

輸入：訓(xùn)練集和特征和閾值；
輸出：決策樹
(1) 中所有實(shí)例都屬于同一類，則為單結(jié)點(diǎn)樹，并將類作為該結(jié)點(diǎn)的類標(biāo)記，返回；
(2) 若，則為單結(jié)點(diǎn)樹，并將中實(shí)例數(shù)最大的類作為該結(jié)點(diǎn)的類標(biāo)記，返回；
(3)否則，按照上述信息增益的算法，計(jì)算中各個(gè)特征對(duì)的信息增益，選擇信息增益最大的特征；
(4)如果特征的信息增益小于閾值，將置為單結(jié)點(diǎn)樹，并將中實(shí)例數(shù)最大的類作為該結(jié)點(diǎn)的類標(biāo)記，返回；
(5)否則，對(duì)的每一個(gè)可能值，依 將分割為若干非空子集 ，將 中實(shí)例數(shù)最大的類作為該結(jié)點(diǎn)的類標(biāo)記，構(gòu)建子結(jié)點(diǎn)，由結(jié)點(diǎn)及其子結(jié)點(diǎn)構(gòu)成樹 ，返回 ；
(6)對(duì)第個(gè)子結(jié)點(diǎn)，以為訓(xùn)練集，以為特征集，遞歸的調(diào)用步驟(1)~步驟(5)，得到子樹 ，返回 。

還是那個(gè)例子

對(duì)上述表的訓(xùn)練集數(shù)據(jù)，利用ID3算法建立決策樹。

解：

第一次迭代：

1. 計(jì)算訓(xùn)練集的熵
   
2. 計(jì)算特征各個(gè)對(duì)數(shù)據(jù)集的信息增益，年齡，有工作，有自己的房子，信貸情況這4個(gè)特征分別以表示。
   
   

3. 比較各個(gè)特征的信息增益，（有自己的房子）的信息增益最大，選擇作為最優(yōu)特征。

【特征：有自己的房子】將數(shù)據(jù)集劃分為2個(gè)子集（有自己的房子）和（沒有自己的房子），觀察一下和：

：

由于所有實(shí)例都屬于同一類，所以它是一個(gè)葉結(jié)點(diǎn)，結(jié)點(diǎn)的類標(biāo)記為“是”。

：

對(duì)于則需從特征中選擇新的特征。

第二次迭代：

1. 計(jì)算訓(xùn)練集的熵
   

2. 計(jì)算剩余特征各個(gè)對(duì)數(shù)據(jù)集的信息增益，年齡，有工作，信貸情況這3個(gè)特征分別以表示。
   
   
   

3. 比較各個(gè)特征的信息增益，（有自己的工作）的信息增益最大，選擇作為最優(yōu)特征。

將看作新的數(shù)據(jù)集。【特征：有工作】有2個(gè)可能值，劃分為2個(gè)子集（有工作）和（沒有工作），觀察一下和：

：

由于所有實(shí)例都屬于同一類，所以它是一個(gè)葉結(jié)點(diǎn)，結(jié)點(diǎn)的類標(biāo)記為“是”。

：

由于所有實(shí)例都屬于同一類，所以它也是一個(gè)葉結(jié)點(diǎn)，結(jié)點(diǎn)的類標(biāo)記為“否”。

這樣就生成了下圖所示的決策樹。

image.png

代碼

接上面代碼
第六步，每一次判斷完信息增益之后，我們都需要對(duì)原始數(shù)據(jù)進(jìn)行切割。
比如上述第一次迭代之后，【特征：有自己的房子】將數(shù)據(jù)集劃分為2個(gè)子集（有自己的房子）和（沒有自己的房子），和第二次迭代之后，將看作新的數(shù)據(jù)集。【特征：有工作】有2個(gè)可能值，劃分為2個(gè)子集（有工作）和（沒有工作）。

def splitdataset(data, index):
    data_slice = data.iloc[index, :]#.iloc(pands)對(duì)數(shù)據(jù)切片
    print(data_slice)#方便查看
    return data, data_slice

這里說(shuō)一下為什么要返回原始數(shù)據(jù)data。因?yàn)槿绻麑?duì)切片之后的data_slice再次做統(tǒng)計(jì)分類，它會(huì)返回一個(gè)新的字典，這個(gè)字典中的value表示的雖然還是索引，但是依舊是data的索引而不是data_slice的，所以要保留data才能找到你想要的數(shù)據(jù)。

image.png

第七步，利用上述所有輔助functions實(shí)現(xiàn)ID3算法.

def ID3(data, newData, features, classes, epsilon):
    
    print(features)
    
    C_temp = newData.groupby(by = [classes]).groups
    
    #D中所有實(shí)例都屬于同一類C_k，則T為單結(jié)點(diǎn)樹，并將類C_k作為該結(jié)點(diǎn)的類標(biāo)記，返回T；
    if len(C_temp) == 1:
        for i in C_temp.keys():
            leafNode = i
        return leafNode
  
    #若A 為空，則T為單結(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類C_k作為該結(jié)點(diǎn)的類標(biāo)記，返回T；
    if len(features) == 0:
        count = 0
        for key, index in C_temp.items():
            if count < len(index):
                count = len(index)
                maxClass = key
        leafNode = maxClass
        return leafNode
   
     #否則，按照上述信息增益的算法，計(jì)算A中各個(gè)特征對(duì)D的信息增益，選擇信息增益最大的特征A_g；
    maxEntropy, maxFeature = infoGain(newData, features, classes)
    print(maxFeature)
    
    #如果特征A_g的信息增益小于閾值，將置T為單結(jié)點(diǎn)樹，并將D中實(shí)例數(shù)最大的類C_k作為該結(jié)點(diǎn)的類標(biāo)記，返回T
    if maxEntropy < epsilon:
        count = 0
        for key, index in C_temp.items():
            if count < len(index):
                count = len(index)
                maxClass = key
        leafNode = maxClass
        return leafNode
    
    #否則，對(duì)A_g的每一個(gè)可能值a_i，依 A_g=a_i將D分割為若干非空子集 D_i，將 D_i中實(shí)例數(shù)最大的類C_k作為該結(jié)點(diǎn)的類標(biāo)記，構(gòu)建子結(jié)點(diǎn)，由結(jié)點(diǎn)及其子結(jié)點(diǎn)構(gòu)成樹 T，返回 T
    T = {maxFeature: {}}
    D_temp = newData.groupby(by = [maxFeature]).groups
    print(D_temp)
    
    features.remove(maxFeature)
   
    for i, index in D_temp.items():
        print(i)
        index = list(index)
        data, newData = splitdataset(data, index)
        print("newData",newData)
        T[maxFeature][i] = ID3(data, newData, features, classes, epsilon)
       
    print('\n') 
    return T

image.png

注：ID3算法只有樹的生成，所以該算法生成的樹容易過擬合。關(guān)于樹的修剪，后面會(huì)補(bǔ)齊。