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