機器學習中決策樹的原理與演算法 | 科普

雷鋒網按：本文作者栗向濱，中科院自動化所複雜系統國家重點實驗室研究生畢業，機器學習與計算機視覺方向演算法工程師。雷鋒網首發文章。

我們知道，在機器學習中有兩類十分重要的問題，一類是分類問題，一類是回歸問題。我們今天所要探討的就是在分類和回歸問題中所用到的一種非常基本的方法，叫決策樹。決策樹也是重要的標籤學習方法。這篇文章裡面的部分內容來自於AI 慕課學院的《機器學習理論與實戰高級特訓班》課程筆記。

從名字來看，決策的的意思就是在眾多類別中我們需要決策出我們分類的東西是屬於哪一個類別，決策離散型的值的叫決策樹，決策連續型值的叫回歸樹。用學術一點的語言就是決策樹的輸出是離散型隨機變數，回歸樹的輸出是連續型隨機變數，這篇文章的重點是講解輸出是離散型隨機變數的決策樹，當你明白決策樹的運行機理後，回歸樹也就觸類旁通了。

名字中的樹，顧名思義，就是模型的結構是樹形結構，樹形結構的主要優點就是可讀性較強，分類速度較快。樹是由軀幹和葉子組成，決策樹中的有向邊和結點與之對應，其中結點也有兩種類型，一種是內部結點，一種是葉結點。

上面的介紹的都是從字面上可以理解出的一些概念，性質上來講，決策樹是一個預測模型，它代表的是對象屬性與對象值之間的一種映射關係。樹中每個結點表示某個對象，內部結點表示一個特徵或屬性，葉結點表示一個類，而每個分叉路徑則代表某個可能的屬性值，而每個葉結點則對應從根節點到該葉節點所經歷的路徑所表示的對象的值。

我們可以認為決策樹就是一種 if-then 規則的集合，也可以理解為它是定義在特徵空間與類空間上的條件概率分布。既然是if-then規則，那麼決策樹具有一個重要的性質就是：互斥並且完備，也就是說每一個實例都被一條路徑或一條規則所覆蓋，而且只被一條路徑或一條規則所覆蓋。

說了這麼多抽象的概念，那決策樹到底可以用來處理什麼樣的問題，那我們通過一個實際的例子來展開決策樹的講解，並且為了讓大家更好入門，我也選擇了一個十分簡單的情景。

假如小明上班可以選擇兩種交通工具，一種是網約車打車上班，一種是騎共享單車上班。採取這兩種途徑中的哪一種取決於三個因素，一個是天氣情況，天氣假設可分為惡劣天氣和非惡劣天氣，另一個因素是小明的心情，心情分為好心情和壞心情，最後一個因素是小明是否快要遲到。假設三個因素對應的小明上班方式的情況如下表：

上面這個表格就是我們所說的樣本集，細心的讀者可能會發現，上面的樣本集少了一種情況，即天氣惡劣、小明心情不好但是上班時間又比較充裕的這種情況，沒錯，我故意省去這一組就是想讓這一組成為測試集，讓大家通過構建一個決策樹來預測在這種情況下，小明會採取哪一種方式上班。

現在我們已經有了數據，那麼我們該如何構建一顆決策樹呢？

在構建一顆決策樹的時候我們需要解決的問題有三個：

• 根結點放置哪個條件屬性；

• 下面的結點放置哪個屬性；

• 什麼時候停止樹的生長。

為了解決上面三個問題，我們需要引入一些概念。

第一個引入的概念叫信息熵，英文名為 Entropy。在 Tom Mitchell 的書中是這樣解釋信息熵的：

它確定了要編碼集合 S 中任意成員（即以均勻的概率隨機抽出的一個成員）的分類所需要的最少二進位位數。

說實話，當時的我理解這句話是費了不少勁，其實把它轉化成通俗點的語言就是說，信息熵就是「預測隨機變數Y的取值」的難度，或者說度量「隨機變數Y」的不確定性。

通過兩個例子來解釋。假如你在地球上，手裡握著一個鐵塊，當你不對鐵塊施力而直接鬆手的情況下，請你判斷它是會向下墜落，還是向上飛去，根據我們的常識我們能很容易判斷出石塊會下落，那麼判斷這個事情的結果就非常容易，那麼此時的信息熵就可以認為是0。

再舉一個例子，假如讓你判斷一枚勻質的硬幣拋出後正面朝上還是反面朝上，這個問題我們就比較難回答了，因為正面朝上和反面朝上的概率均等，我們不能有一個很確定的判斷硬幣到底哪個面朝上，那麼這個時候判斷就比較難了，所以此時的信息熵就可以認為是1。

但是上面這段話怎麼轉化成數學的語言進行定義和描述呢，有很多學者都提出了他們認為的信息熵表達式，我們可以通過下面這個表格看一下目前的一些信息熵的定義。

雖然有這麼多的定義，但我們平時很多情況下用的都是香農信息熵，所以接下來我也採用香農信息熵對下面的其他定義進行表述。

當我們有了信息熵的表達式我們就可以得出一個二分類問題的信息熵圖像，如下圖所示。

我們可以看到，這個圖像所表達出來的信息和我們之前舉的例子完全對應，當一個事情非常容易判斷的時候，也就是我們以很大的概率認為它會發生或者不會發生，那麼它的信息熵就偏向0，當一個事情非常難判斷的時候，我們可以認為最難的時候就是這個事件的所有可能性均相等的時候，那麼它的信息熵為1.

現在我們已經有了信息熵的概念，那麼我們再引入第二個概念，這個概念需要建立在信息熵之上。那就是條件信息熵。有了信息熵的概念之後，我們自然而然就可以得出條件信息熵的概念，條件信息熵就是度量「在隨機變數X的前提下，預測隨機變數Y」的難度。

信息熵表示判斷難度，有了條件兩個字就是說我們已經知道了一個條件之後，再讓你判斷變數結果，這時候的難度就是就是條件信息熵。就像上面的例子，我們發現只要小明發現他要遲到了，那麼他就會打車上班，所以當我得知了小明今天快要遲到了，那麼我判斷他是否打車這件事就非常容易了，那麼此時的條件信息熵就可以認為是0，這就是條件信息熵。如果仍然採用香農的定義方法，那麼條件信息熵的數學表達式就是

已知P(Y|X)，P(X)，

有了信息熵和條件信息熵的概念，那我們就自然而然地就可以引出第三個概念，那就是信息增益，信息增益的數學定義是

我們通過看這個數學表達式不難看出信息增益所表達的意思。被減數是信息熵，也就是在沒人給我們通風報信的時候判斷結果的難度；減數是條件信息熵，也就是當我們知道了一個條件後，判斷結果的難度。信息增益這個變數表達的意思就是條件x對判斷結果減少了多少難度，即度量X對預測Y的能力的影響。

就像有一檔電視節目叫開心辭典，當答題選手無法判斷答案的時候會選擇三種求助方式，其實求助方式就是一種條件，當選手用過了求助方式後對回答問題的難度的減少量，就是信息增益。如果難度降低很大，那麼我們就可以說信息增益很大。

介紹了上面三個概念，我們就可以回答在構造決策樹的時候遇到的第一個問題了：根結點放置哪個條件屬性。

我們的放置方法是：選擇信息增益最大的一個屬性作為根結點。

因為一個數據集的信息熵是固定的，所以這個問題就轉化為選擇條件信息熵最小的屬性，所以我們只要求出條件信息熵最小的屬性就知道根結點了。

通過對例子的計算我們可以分別計算出單個特性的條件信息熵，計算過程如下圖：

通過計算，我們看到小明是否遲到這個屬性的條件信息熵最小，那麼我們就將這個屬性作為根結點。所以決策樹的的雛形如下圖。

知道了根結點的放置方法，那麼第二個問題也就迎刃而解了，下面的結點放置哪個屬性。我們只需要將已經得到的結點看做一個新的根結點，利用最小化條件信息熵的方法即可。我們將小明並不會快要遲到作為一個條件，那麼表格如下

然後再次計算條件信息熵，計算過程如下圖：

我們看到天氣因素的條件信息熵最小，為0，那麼我們下一個節點就方式天氣因素。這個時候其實我們就可以結束決策樹的生長了，為什麼呢？那麼我們怎麼判斷什麼時候結束決策樹的生長呢？

因為我們在一直最小化條件信息熵，所以當我們發現所有特徵的信息增益均很小，或者我們沒有特徵可以選擇了就可以停止了。至此我們就構建出了我們的決策樹。

那麼我們最終的決策樹如下圖所示：

通過決策樹我們很容易判斷出天氣惡劣、小明心情不好但是上班時間又比較充裕的情況下，小明的出行方式是選擇打車。

所以，如何構建一個決策樹的方法截止現在已經基本上全部介紹給了大家，在學術上，常用的演算法有 ID3演算法，C4.5演算法和 CART 演算法，其實這些演算法和我上面介紹的方法和思想基本上完全一樣，只是在選擇目標函數的時候有一些差別，我說的是最小化條件信息熵，ID3 用的是信息增益，C4.5 演算法用的是信息增益比，CART演算法用的是基尼指數，這個指數在上面介紹信息熵的表格中就有，可以參考。

決策樹的原理和演算法部分就基本上介紹完畢，因為防止模型過擬合也是機器學習中的一個重要議題，所以，我再簡單介紹一下決策樹的剪枝。

之所以會發生過擬合，是因為我們在學習的過程中過多地考慮如何提高對訓練數據的正確分類上，所以有的時候就會構建出過於複雜的決策樹。而決策樹一旦複雜，對測試數據的分類就沒那麼精確了，也就是過擬合。所以根據奧卡姆剃刀的精神，要對決策樹進行簡化，這個過程就叫做剪枝。

決策樹剪枝是通過最小化決策樹整體的損失函數完成的。決策樹的損失函數定義為：

其中，樹 T 的葉節點個數為 |T| ，C(T) 表示模型對訓練數據的預測誤差，即模型與訓練數據的擬合程度， |T| 表示模型複雜度，參數 α 是一個非負數，控制兩者之間的影響。

C(T) 的計算方法是

其中，t 是樹 T 的葉結點，該葉結點有 N_t 個樣本，其中k類的樣本點有 N_tk 個，k=1,2,…,K。

有個上面的表達式就可以進行最小化損失函數的計算了，從葉結點開始遞歸地向上計算損失函數，如果一組葉結點回到其父結點之前與之後的整體樹分別為 TB 與 TA，其對應的損失函數分別為 C_α(T_B)與C_α(T_A)，如果

則進行剪枝，即將父結點變為新的葉結點。

因為決策樹的生成在開源庫 OpenCV 已經有實現，最後我再附上一段利用 OpenCV 來訓練我上面例子的代碼，目的也是讓大家自己實現一個類似 Hello World 的程序。OpenCV 的配置方法在這裡不再贅述，大家可以利用下面的代碼自己作為練習。OpenCV 的內部實現過程感興趣的同學也可以對源碼進行學習，源碼也可以在 OpenCV 的官網上下載到。

需要進行解釋的一點就是，我們需要將上面的情景進行了數據化，我們將上面的情況都作為0和1來代表進行決策樹的構建。所以新的表格如下所示：

利用這段程序大家可以看一下這顆決策樹對天氣惡劣，心情不好，但是時間還充足的情況下小明會選擇哪種交通工具進行出行進行的預測。在這先偷偷地告訴你，AI 給出的答案如下圖

是不是和我們推導的結果一樣呢？

雷鋒網友情提醒：

深度學習作為人工智慧領域的黑科技，快速入門一直以來是很多學員的夢想。AI 慕課學院在 6月17日-18日有一個為期 12 小時的深度學習課程，由 fastai 中文社區最活躍的四位貢獻者為你打開深度學習入門的那扇門。

課程採用 「探索+實踐」 的矽谷教學模式，讓你從一個門外漢迅速進入深度學習工程師的角色，去完成一個接著一個的項目挑戰。最流行的深度學習技能，在這裡你都會一一體驗，學完整個課程，CNN、RNN、VGG16、ResNet、InceptionCNN 這些最新科技你都會順手捏來，彈指一揮間，快速構建你的深度學習應用不再是一個夢。

只要你有基本的 Python 編程經驗，就能學好這門課！即使零編程基礎，我們也能帶你飛！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！