1
雷鋒網(wǎng)按：本文作者栗向濱，中科院自動化所復(fù)雜系統(tǒng)國家重點實驗室研究生畢業(yè)，機器學(xué)習(xí)與計算機視覺方向算法工程師。雷鋒網(wǎng)首發(fā)文章。
我們知道，在機器學(xué)習(xí)中有兩類十分重要的問題，一類是分類問題，一類是回歸問題。我們今天所要探討的就是在分類和回歸問題中所用到的一種非?；镜姆椒?，叫決策樹。決策樹也是重要的標簽學(xué)習(xí)方法。這篇文章里面的部分內(nèi)容來自于 AI 慕課學(xué)院的《機器學(xué)習(xí)理論與實戰(zhàn)高級特訓(xùn)班》課程筆記。
從名字來看，決策的的意思就是在眾多類別中我們需要決策出我們分類的東西是屬于哪一個類別，決策離散型的值的叫決策樹，決策連續(xù)型值的叫回歸樹。用學(xué)術(shù)一點的語言就是決策樹的輸出是離散型隨機變量，回歸樹的輸出是連續(xù)型隨機變量，這篇文章的重點是講解輸出是離散型隨機變量的決策樹，當你明白決策樹的運行機理后，回歸樹也就觸類旁通了。
名字中的樹，顧名思義，就是模型的結(jié)構(gòu)是樹形結(jié)構(gòu)，樹形結(jié)構(gòu)的主要優(yōu)點就是可讀性較強，分類速度較快。樹是由軀干和葉子組成，決策樹中的有向邊和結(jié)點與之對應(yīng)，其中結(jié)點也有兩種類型，一種是內(nèi)部結(jié)點，一種是葉結(jié)點。
上面的介紹的都是從字面上可以理解出的一些概念，性質(zhì)上來講，決策樹是一個預(yù)測模型，它代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個結(jié)點表示某個對象，內(nèi)部結(jié)點表示一個特征或?qū)傩?，葉結(jié)點表示一個類，而每個分叉路徑則代表某個可能的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。
我們可以認為決策樹就是一種 if-then 規(guī)則的集合，也可以理解為它是定義在特征空間與類空間上的條件概率分布。既然是if-then規(guī)則，那么決策樹具有一個重要的性質(zhì)就是：互斥并且完備，也就是說每一個實例都被一條路徑或一條規(guī)則所覆蓋，而且只被一條路徑或一條規(guī)則所覆蓋。
說了這么多抽象的概念，那決策樹到底可以用來處理什么樣的問題，那我們通過一個實際的例子來展開決策樹的講解，并且為了讓大家更好入門，我也選擇了一個十分簡單的情景。
假如小明上班可以選擇兩種交通工具，一種是網(wǎng)約車打車上班，一種是騎共享單車上班。采取這兩種途徑中的哪一種取決于三個因素，一個是天氣情況，天氣假設(shè)可分為惡劣天氣和非惡劣天氣，另一個因素是小明的心情，心情分為好心情和壞心情，最后一個因素是小明是否快要遲到。假設(shè)三個因素對應(yīng)的小明上班方式的情況如下表：
上面這個表格就是我們所說的樣本集，細心的讀者可能會發(fā)現(xiàn)，上面的樣本集少了一種情況，即天氣惡劣、小明心情不好但是上班時間又比較充裕的這種情況，沒錯，我故意省去這一組就是想讓這一組成為測試集，讓大家通過構(gòu)建一個決策樹來預(yù)測在這種情況下，小明會采取哪一種方式上班。
現(xiàn)在我們已經(jīng)有了數(shù)據(jù)，那么我們該如何構(gòu)建一顆決策樹呢？
在構(gòu)建一顆決策樹的時候我們需要解決的問題有三個：
根結(jié)點放置哪個條件屬性；
下面的結(jié)點放置哪個屬性；
什么時候停止樹的生長。
為了解決上面三個問題，我們需要引入一些概念。
第一個引入的概念叫信息熵，英文名為 Entropy。在 Tom Mitchell 的書中是這樣解釋信息熵的：
它確定了要編碼集合 S 中任意成員（即以均勻的概率隨機抽出的一個成員）的分類所需要的最少二進制位數(shù)。
說實話，當時的我理解這句話是費了不少勁，其實把它轉(zhuǎn)化成通俗點的語言就是說，信息熵就是“預(yù)測隨機變量Y的取值”的難度，或者說度量“隨機變量Y”的不確定性。
通過兩個例子來解釋。假如你在地球上，手里握著一個鐵塊，當你不對鐵塊施力而直接松手的情況下，請你判斷它是會向下墜落，還是向上飛去，根據(jù)我們的常識我們能很容易判斷出石塊會下落，那么判斷這個事情的結(jié)果就非常容易，那么此時的信息熵就可以認為是0。
再舉一個例子，假如讓你判斷一枚勻質(zhì)的硬幣拋出后正面朝上還是反面朝上，這個問題我們就比較難回答了，因為正面朝上和反面朝上的概率均等，我們不能有一個很確定的判斷硬幣到底哪個面朝上，那么這個時候判斷就比較難了，所以此時的信息熵就可以認為是1。
但是上面這段話怎么轉(zhuǎn)化成數(shù)學(xué)的語言進行定義和描述呢，有很多學(xué)者都提出了他們認為的信息熵表達式，我們可以通過下面這個表格看一下目前的一些信息熵的定義。
雖然有這么多的定義，但我們平時很多情況下用的都是香農(nóng)信息熵，所以接下來我也采用香農(nóng)信息熵對下面的其他定義進行表述。
當我們有了信息熵的表達式我們就可以得出一個二分類問題的信息熵圖像，如下圖所示。
我們可以看到，這個圖像所表達出來的信息和我們之前舉的例子完全對應(yīng)，當一個事情非常容易判斷的時候，也就是我們以很大的概率認為它會發(fā)生或者不會發(fā)生，那么它的信息熵就偏向0，當一個事情非常難判斷的時候，我們可以認為最難的時候就是這個事件的所有可能性均相等的時候，那么它的信息熵為1.
現(xiàn)在我們已經(jīng)有了信息熵的概念，那么我們再引入第二個概念，這個概念需要建立在信息熵之上。那就是條件信息熵。有了信息熵的概念之后，我們自然而然就可以得出條件信息熵的概念，條件信息熵就是度量“在隨機變量X的前提下，預(yù)測隨機變量Y”的難度。
信息熵表示判斷難度，有了條件兩個字就是說我們已經(jīng)知道了一個條件之后，再讓你判斷變量結(jié)果，這時候的難度就是就是條件信息熵。就像上面的例子，我們發(fā)現(xiàn)只要小明發(fā)現(xiàn)他要遲到了，那么他就會打車上班，所以當我得知了小明今天快要遲到了，那么我判斷他是否打車這件事就非常容易了，那么此時的條件信息熵就可以認為是0，這就是條件信息熵。如果仍然采用香農(nóng)的定義方法，那么條件信息熵的數(shù)學(xué)表達式就是
已知P(Y|X)，P(X)，
有了信息熵和條件信息熵的概念，那我們就自然而然地就可以引出第三個概念，那就是信息增益，信息增益的數(shù)學(xué)定義是
我們通過看這個數(shù)學(xué)表達式不難看出信息增益所表達的意思。被減數(shù)是信息熵，也就是在沒人給我們通風(fēng)報信的時候判斷結(jié)果的難度；減數(shù)是條件信息熵，也就是當我們知道了一個條件后，判斷結(jié)果的難度。信息增益這個變量表達的意思就是條件x對判斷結(jié)果減少了多少難度，即度量X對預(yù)測Y的能力的影響。
就像有一檔電視節(jié)目叫開心辭典，當答題選手無法判斷答案的時候會選擇三種求助方式，其實求助方式就是一種條件，當選手用過了求助方式后對回答問題的難度的減少量，就是信息增益。如果難度降低很大，那么我們就可以說信息增益很大。
介紹了上面三個概念，我們就可以回答在構(gòu)造決策樹的時候遇到的第一個問題了：根結(jié)點放置哪個條件屬性。
我們的放置方法是：選擇信息增益最大的一個屬性作為根結(jié)點。
因為一個數(shù)據(jù)集的信息熵是固定的，所以這個問題就轉(zhuǎn)化為選擇條件信息熵最小的屬性，所以我們只要求出條件信息熵最小的屬性就知道根結(jié)點了。
通過對例子的計算我們可以分別計算出單個特性的條件信息熵，計算過程如下圖：
通過計算，我們看到小明是否遲到這個屬性的條件信息熵最小，那么我們就將這個屬性作為根結(jié)點。所以決策樹的的雛形如下圖。
知道了根結(jié)點的放置方法，那么第二個問題也就迎刃而解了，下面的結(jié)點放置哪個屬性。我們只需要將已經(jīng)得到的結(jié)點看做一個新的根結(jié)點，利用最小化條件信息熵的方法即可。我們將小明并不會快要遲到作為一個條件，那么表格如下
然后再次計算條件信息熵，計算過程如下圖：
我們看到天氣因素的條件信息熵最小，為0，那么我們下一個節(jié)點就方式天氣因素。這個時候其實我們就可以結(jié)束決策樹的生長了，為什么呢？那么我們怎么判斷什么時候結(jié)束決策樹的生長呢？
因為我們在一直最小化條件信息熵，所以當我們發(fā)現(xiàn)所有特征的信息增益均很小，或者我們沒有特征可以選擇了就可以停止了。至此我們就構(gòu)建出了我們的決策樹。
那么我們最終的決策樹如下圖所示：
通過決策樹我們很容易判斷出天氣惡劣、小明心情不好但是上班時間又比較充裕的情況下，小明的出行方式是選擇打車。
所以，如何構(gòu)建一個決策樹的方法截止現(xiàn)在已經(jīng)基本上全部介紹給了大家，在學(xué)術(shù)上，常用的算法有 ID3算法，C4.5算法和 CART 算法，其實這些算法和我上面介紹的方法和思想基本上完全一樣，只是在選擇目標函數(shù)的時候有一些差別，我說的是最小化條件信息熵，ID3 用的是信息增益，C4.5 算法用的是信息增益比，CART算法用的是基尼指數(shù)，這個指數(shù)在上面介紹信息熵的表格中就有，可以參考。
決策樹的原理和算法部分就基本上介紹完畢，因為防止模型過擬合也是機器學(xué)習(xí)中的一個重要議題，所以，我再簡單介紹一下決策樹的剪枝。
之所以會發(fā)生過擬合，是因為我們在學(xué)習(xí)的過程中過多地考慮如何提高對訓(xùn)練數(shù)據(jù)的正確分類上，所以有的時候就會構(gòu)建出過于復(fù)雜的決策樹。而決策樹一旦復(fù)雜，對測試數(shù)據(jù)的分類就沒那么精確了，也就是過擬合。所以根據(jù)奧卡姆剃刀的精神，要對決策樹進行簡化，這個過程就叫做剪枝。
決策樹剪枝是通過最小化決策樹整體的損失函數(shù)完成的。決策樹的損失函數(shù)定義為：
其中，樹 T 的葉節(jié)點個數(shù)為 |T| ，C(T) 表示模型對訓(xùn)練數(shù)據(jù)的預(yù)測誤差，即模型與訓(xùn)練數(shù)據(jù)的擬合程度， |T| 表示模型復(fù)雜度，參數(shù) α 是一個非負數(shù)，控制兩者之間的影響。
C(T) 的計算方法是
其中，t 是樹 T 的葉結(jié)點，該葉結(jié)點有 Nt 個樣本，其中k類的樣本點有 Ntk 個，k=1,2,…,K。
有個上面的表達式就可以進行最小化損失函數(shù)的計算了，從葉結(jié)點開始遞歸地向上計算損失函數(shù)，如果一組葉結(jié)點回到其父結(jié)點之前與之后的整體樹分別為 TB 與 TA，其對應(yīng)的損失函數(shù)分別為 Cα(TB)與Cα(TA)，如果
則進行剪枝，即將父結(jié)點變?yōu)樾碌娜~結(jié)點。
因為決策樹的生成在開源庫 OpenCV 已經(jīng)有實現(xiàn)，最后我再附上一段利用 OpenCV 來訓(xùn)練我上面例子的代碼，目的也是讓大家自己實現(xiàn)一個類似 Hello World 的程序。OpenCV 的配置方法在這里不再贅述，大家可以利用下面的代碼自己作為練習(xí)。OpenCV 的內(nèi)部實現(xiàn)過程感興趣的同學(xué)也可以對源碼進行學(xué)習(xí)，源碼也可以在 OpenCV 的官網(wǎng)上下載到。 
需要進行解釋的一點就是，我們需要將上面的情景進行了數(shù)據(jù)化，我們將上面的情況都作為0和1來代表進行決策樹的構(gòu)建。所以新的表格如下所示： 
利用這段程序大家可以看一下這顆決策樹對天氣惡劣，心情不好，但是時間還充足的情況下小明會選擇哪種交通工具進行出行進行的預(yù)測。在這先偷偷地告訴你，AI 給出的答案如下圖
是不是和我們推導(dǎo)的結(jié)果一樣呢？
雷鋒網(wǎng)友情提醒：
深度學(xué)習(xí)作為人工智能領(lǐng)域的黑科技，快速入門一直以來是很多學(xué)員的夢想。AI 慕課學(xué)院在 6月17日-18日有一個為期 12 小時的深度學(xué)習(xí)課程，由 fastai 中文社區(qū)最活躍的四位貢獻者為你打開深度學(xué)習(xí)入門的那扇門。
課程采用 “探索+實踐” 的硅谷教學(xué)模式，讓你從一個門外漢迅速進入深度學(xué)習(xí)工程師的角色，去完成一個接著一個的項目挑戰(zhàn)。最流行的深度學(xué)習(xí)技能，在這里你都會一一體驗，學(xué)完整個課程，CNN、RNN、VGG16、ResNet、InceptionCNN 這些最新科技你都會順手捏來，彈指一揮間，快速構(gòu)建你的深度學(xué)習(xí)應(yīng)用不再是一個夢。
只要你有基本的 Python 編程經(jīng)驗，就能學(xué)好這門課！即使零編程基礎(chǔ)，我們也能帶你飛！
雷峰網(wǎng)特約稿件，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
