今天是機器學習專題的第21篇文章，我們一起來看一個新的模型——決策樹。

決策樹的定義

決策樹是我本人非常喜歡的機器學習模型，非常直觀容易理解，並且和數據結構的結合很緊密。我們學習的門檻也很低，相比於那些動輒一堆公式的模型來說，實在是簡單得多。

其實我們生活當中經常在用決策樹，只是我們自己沒有發現。決策樹的本質就是一堆if-else的組合，舉個經典的例子，比如我們去小攤子上買西瓜。水果攤的小販都是怎麼做的？拿起西瓜翻滾一圈，看一眼，然後伸手一拍，就知道西瓜甜不甜。我們把這些動作相關的因素去除，把核心本質提取出來，基本上是這麼三條：

1. 西瓜表面的顏色，顏色鮮艷的往往比較甜
2. 西瓜拍打的聲音，聲音清脆的往往比較甜
3. 西瓜是否有瓜藤，有藤的往往比較甜

這三條顯然不是平等的，因為拍打的聲音是最重要的，可能其次表面顏色，最後是瓜藤。所以我們挑選的時候，肯定也是先聽聲音，然後看瓜藤，最後看顏色。我們把其中的邏輯抽象出來然後整理一下，變成一棵樹結構，於是這就成了決策樹。

這個決策樹本質上做的還是分類的工作，將西瓜分成了甜的和不甜的。也就是說決策樹是一個樹形的分類器，這個也是決策樹的基本定義。另外從圖中我們還有一個啟示，在這個問題當中，決策樹的特徵都是離散值，而不是連續值。也就是說決策樹可以接受像是類別、標識這樣非數值型的特徵，而邏輯回歸這些模型則不太行。

如果你對這些細節還理解不深刻也沒有關係，我們可以先放一放，至少我們明白了決策樹的大概結構以及工作原理。

對於每一條數據來說，它分類的過程其實就是在決策樹上遍歷的過程。每到一個中間節點都會面臨一次判斷，根據判斷的結果選擇下一個子樹。而樹上的葉子節點代表一種分類，當數據到了葉子節點，這個葉子節點的值就代表它的分類結果。

決策樹的訓練

明白了決策樹的結構和工作原理之後，下面就是訓練的過程了。

在理清楚原理之前，我們先來看下數據。我們根據上面決策樹的結構，很容易發現，訓練數據應該是這樣的表格：

那麼最後我們想要實現什麼效果呢？當然是得到的準確率越高越好，而根據決策樹的原理，樹上的每一個葉子節點代表一個分類。那麼我們顯然希望最後到達葉子節點的數據儘可能純粹，舉個例子，如果一個葉子節點代表甜，那麼我們肯定希望根據樹結構被劃歸到這裡的數據儘可能都是甜的，不甜的比例儘可能低。

那麼我們怎麼實現這一點呢？這就需要我們在越頂層提取規則的時候，越選擇一些區分度大的特徵作為切分的依據。所謂區分度大的特徵，也就是能夠將數據很好分開的特徵。這是明顯的貪心做法，使用這樣的方法，我們只可以保證在儘可能高層取得儘可能好的分類結果，但是並不能保證這樣得到的模型是最優的。生成最優的決策樹本質上也是一個NP問題，我們當前的做法可以保證在盡量短的時間內獲得一個足夠優秀的解，但是沒辦法保證是最優解。

回到問題本身，我們想要用區分度大的特徵來進行數據劃分。要做到這一點的前提就是首先定義區分度這個概念，將它量化，這樣我們才好進行選擇。否則總不能憑感覺去衡量區分度，好在這個區分度還是很好解決的，我們只需要再一次引入信息熵的概念就可以了。

信息熵與信息增益

信息熵這個詞很令人費解，它英文原文是information entropy，其實一樣難以理解。因為entropy本身是物理學和熱力學當中的概念，用來衡量物體分散的不均勻程度。也就是說熵越大，說明物體分散得程度越大，可以簡單理解成越散亂。比如我們把房間里一盒整理好的乒乓球打翻，那麼裏面的乒乓球顯然會散亂到房間的各個地方，這個散亂的過程可以理解成熵增大的過程。

信息熵也是一樣的含義，用來衡量一份信息的散亂程度。熵越大，說明信息越雜亂無章，否則說明信息越有調理。信息熵出自大名鼎鼎的信息學巨著《信息論》，它的作者就是赫赫有名的香農。但是這個詞並不是香農原創，據說是計算機之父馮諾依曼取的，他去這個名字的含義也很簡單，因為大家都不明白這個詞究竟是什麼意思。

之前我們曾經在介紹交叉熵的時候詳細解釋過這個概念，我們來簡單回顧一下。對於一個事件X來說，假設它發生的概率是P(X)，那麼這個事件本身的信息量就是：

比如說世界盃中國隊奪冠的概率是1/128，那麼我們需要用8個比特才能表示，說明它信息量很大。假如巴西隊奪冠的概率是1/4，那麼只要2個比特就足夠了，說明它的信息量就很小。同樣一件事情，根據發生的概率不同，它的信息量也是不同的。

那麼信息熵的含義其實就是信息量的期望，也就是用信息量乘上它的概率：

同樣，假設我們有一份數據集合，其中一共有K類樣本，每一類樣本所佔的比例是，那麼我們把這個比例看成是概率的話，就可以寫出這整個集合的信息熵：

理解了信息熵的概念之後，再來看信息增益就很簡單了。信息增益說白了就是我們劃分前後信息熵的變化量，假設我們選擇了某一個特徵進行切分，將數據集D切分成了D1和D2。那麼就叫做信息增益，也就是切分之後信息熵與之前的變化量。

我們根據熵的定義可以知道，如果數據變得純粹了，那麼信息熵應該會減少。減少得越多，說明切分的效果越好。所以我們就找到了衡量切分效果的方法，就是信息增益。我們根據信息增益的定義，可以很簡單地理出整個決策樹建立的過程。就是我們每次在選擇切分特徵的時候，都會遍歷所有的特徵，特徵的每一個取值對應一棵子樹，我們通過計算信息增益找到切分之後增益最大的特徵。上層的結構創建好了之後， 通過遞歸的形式往下繼續建樹，直到切分之後的數據集變得純粹，或者是所有特徵都使用結束了為止。

這個算法稱為ID3算法，它也是決策樹最基礎的構建算法。這裡有一個小細節， 根據ID3算法的定義，每一次切分選擇的是特徵，而不是特徵的取值。並且被選中作為切分特徵的特徵的每一個取值都會建立一棵子樹，也就是說每一個特徵在決策樹當中都只會最多出現一次。因為使用一次之後，這個特徵的所有取值就都被使用完了。

舉個例子，比如拍打聲音是否清脆這個特徵，我們在一開始就選擇了它。根據它的兩個取值，是和否都建立了一棵子樹。那麼如果我們在子樹當中再根據這個特徵拆分顯然沒有意義，因為子樹中的所有數據的這個特徵都是一樣的。另外，ID3算法用到的所有特徵必須是離散值，因為連續值無法完全切分。如果西瓜的重量是一個特徵，那麼理論上來說所有有理數都可能是西瓜的質量，我們顯然不可能窮盡所有的取值。

這一點非常重要，不僅關係到我們實現的決策樹是否正確，也直接關係到我們之後理解其他的建樹算法。

代碼實現

理解了算法原理和流程之後，就到了我們緊張刺激的編碼環節。老實講決策樹的算法實現並不難，比之前的FP-growth還要簡單，大家不要有壓力。

首先，我們來創造實驗數據：

import numpy as np
import math
def create_data():
    X1 = np.random.rand(50, 1)*100
    X2 = np.random.rand(50, 1)*100
    X3 = np.random.rand(50, 1)*100
    
    def f(x):
        return 2 if x > 70 else 1 if x > 40 else 0
    
    y = X1 + X2 + X3
    Y = y > 150
    Y = Y + 0
    r = map(f, X1)
    X1 = list(r)
    
    r = map(f, X2)
    X2 = list(r)
    
    r = map(f, X3)
    X3 = list(r)
    x = np.c_[X1, X2, X3, Y]
    return x, ['courseA', 'courseB', 'courseC']

這份數據模擬的是學生考試，一共考三門，一共要考到150分以上才算是通過。由於ID3算法只能接受離散值的特徵，所以我們要先將連續值轉成離散值，我們根據每一門的考試分數，生成三個檔次。大於70分的是2檔，40到70分的是1檔，小於40分的是0檔。

為了方便編碼，我們把預測值Y放在特徵的最後，並且返回這三個特徵的名稱，方便以後用來建樹。

我們運行一下數據查看一下結果：

下面，我們實現計算集合信息熵的函數。這個函數也很簡單，我們只需要計算出每個類別的佔比，然後套用一下信息熵的公式即可。

from collections import Counter

def calculate_info_entropy(dataset):
    n = len(dataset)
    # 我們用Counter統計一下Y的數量
    labels = Counter(dataset[:, -1])
    entropy = 0.0
    # 套用信息熵公式
    for k, v in labels.items():
        prob = v / n
        entropy -= prob * math.log(prob, 2)
    return entropy

有了信息熵的計算函數之後，我們接下來實現拆分函數，也就是根據特徵的取值將數據集進行拆分的函數。

def split_dataset(dataset, idx):
   # idx是要拆分的特徵下標
    splitData = defaultdict(list)
    for data in dataset:
       # 這裡刪除了idx這個特徵的取值，因為用不到了
        splitData[data[idx]].append(np.delete(data, idx))
    return list(splitData.values())

本質上就是根據特徵取值歸類的過程，我們可以隨便調用測試一下：

和我們預期一樣，根據特徵的取值將數據分成了若干份。接下來我們就要實現核心的特徵的選擇函數了，也就是要選擇信息增益最大的特徵對數據進行切分。

def choose_feature_to_split(dataset):
    n = len(dataset[0])-1
    m = len(dataset)
    # 切分之前的信息熵
    entropy = calculate_info_entropy(dataset)
    bestGain = 0.0
    feature = -1
    for i in range(n):
       # 根據特徵i切分
        split_data = split_dataset(dataset, i)
        new_entropy = 0.0
        # 計算切分後的信息熵
        for data in split_data:
            prob = len(data) / m
            new_entropy += prob * calculate_info_entropy(data)
        # 獲取信息增益
        gain = entropy - new_entropy
        if gain > bestGain:
            bestGain = gain
            feature = i
    return feature

到這裡，我們所有工具方法都已經開發完了，下面就到了我們緊張刺激的建樹部分了。建樹其實並沒有什麼大不了的，無非是通過遞歸來重複調用上面的方法來創造每一個分支節點而已。如果你熟悉樹形數據結構，會發現它和其他樹形數據結構的構建過程並沒有什麼兩樣。

我們來看下代碼，整個過程也只有十幾行而已。

def create_decision_tree(dataset, feature_names):
    dataset = np.array(dataset)
    counter = Counter(dataset[:, -1])
    # 如果數據集值剩下了一類，直接返回
    if len(counter) == 1:
        return dataset[0, -1]
    
    # 如果所有特徵都已經切分完了，也直接返回
    if len(dataset[0]) == 1:
        return counter.most_common(1)[0][0]
    
    # 尋找最佳切分的特徵
    fidx = choose_feature_to_split(dataset)
    fname = feature_names[fidx]
    
    node = {fname: {}}
    feature_names.remove(fname)
    
    # 遞歸調用，對每一個切分出來的取值遞歸建樹
    split_data, vals = split_dataset(dataset, fidx)
    for data, val in zip(split_data, vals):
        node[fname][val] = create_decision_tree(data, feature_names[:])
    return node

我們運行一下這段代碼，會得到一份dict，這個dict當中的層次結構其實就是決策樹的結構：

我們這樣看可能不太清楚，但是我們把這個dict展開就得到了下圖的這棵樹結構：

我們觀察一下上圖當中紅圈的部分，這個節點只有兩個分叉，而其他的節點都有三個分叉。這並不是代碼有bug，而是說明數據當中缺失了這種情況，所以少了一個分叉。這其實非常正常，當我們訓練數據的樣本量不夠的時候，很有可能無法覆蓋所有的情況，就會出現這種沒有分叉的情況。

到這裡雖然決策樹是實現完了，但是還沒有結束，還有一個關鍵的部分我們沒有做，就是預測。我們訓練完了，總得把模型用起來，顯然需要一個預測的函數。這個預測的函數也簡單，它介紹一條數據以及我們訓練完的樹結構，返回分類的結果。其實也是一個遞歸調用的過程：

def classify(node, feature_names, data):
   # 獲取當前節點判斷的特徵
    key = list(node.keys())[0]
    node = node[key]
    idx = feature_names.index(key)
    
    # 根據特徵進行遞歸
    pred = None
    for key in node:
       # 找到了對應的分叉
        if data[idx] == key:
           # 如果再往下依然還有子樹，那麼則遞歸，否則返回結果
            if isinstance(node[key], dict):
                pred = classify(node[key], feature_names, data)
            else:
                pred = node[key]
                
    # 如果沒有對應的分叉，則找到一個分叉返回
    if pred is None:
        for key in node:
            if not isinstance(node[key], dict):
                pred = node[key]
                break
    return pred

我們來創造一些簡單的數據測試一下：

基本上和我們的預期一致，說明我們決策樹就實現完了。

總結

我們的決策樹雖然構建完了，但是仍然有很多不完美的地方。比如說，目前我們的模型只能接受離散值的特徵，如果是連續值則無法進行拆分。而且我們每個特徵只能用一次，有時候我們希望能夠多次使用同一個特徵。在這種情況下ID3就無法實現了。所以我們還需要引入其他的優化。

在後序的文章當中我們將會討論這些相關的優化，以及決策樹這個模型本身的一些特性。如果對此感興趣，一定不要錯過。

喜歡的話，順手點個關注吧。