【機器學習·基本功】-1決策樹 | 演算法原理介紹

05-10

引言

王妮梅今年 26 歲，單身，一天她媽媽要給她介紹男朋友，於是媽媽和女兒的一場對話如下：

媽媽：給你介紹一男的

女兒：帥嗎？

媽媽：一般。

女兒：性格怎樣？

媽媽：不好。

女兒：不見！

媽媽：妮梅！尼妹！

第二天，媽媽又找到一位男士

媽媽：給你介紹一男的

女兒：帥嗎？

媽媽：還好。

女兒：收入高不？

媽媽：不高。

女兒：不見！

媽媽：妮梅！尼瑪！

妮梅的兩次決策過程就是通過性格 (好/壞)、長相 (美/丑) 和收入(高/低) 對和男人是否見面的結果分為兩個類別：見/不見。如果把妮梅的決策過程用樹來表示，見下圖：

通過上圖可知妮梅對男朋友的不見的要求是：長相一般性格一般；長相難看收入低。注意：上圖底層兩個紅色葉子框里「不見」字眼，除此之外，上圖還有三個綠色像葉子框里的「問號」。問號的意思就是目前還不知道妮梅的決策。假設她媽媽又和她進行三個對話：

媽媽：給你介紹一男的

女兒：帥嗎？

媽媽：帥。

女兒：見！

媽媽：噢耶！

媽媽：給你介紹一男的

女兒：帥嗎？

媽媽：還好。

女兒：性格好嗎？

媽媽：好。

女兒：見！！

媽媽：噢耶！！

媽媽：給你介紹一男的

女兒：帥嗎？

媽媽：不帥。

女兒：收入高不？

媽媽：高。

女兒：見！！！

媽媽：噢耶！！！

加上這三段對話，我們可以完整地把妮梅的決策過程用樹來表示，見下圖：

注意，上圖的「問號」全部變成了「見」的字眼，而且樹的每一個分支都得到了一個明確答案，見或不見！媽媽以後拿著這顆樹直接可以比較男方的信息然後介紹給妮梅了，根本無需再問她任何問題，除非妮梅有新的想法。例如，妮梅在得知男方長相難看收入高的情況後，還想再知道對方性格怎樣，壞的話不約，好的話才約。在這種情況下，這棵樹還要繼續生長 (在第二章會考慮此情況)。

現在，我來問你：

你會加減乘除嗎？
你會提問題嗎？
你會提一些重要的問題嗎？
你會問完之後刪除繁冗的問題嗎？

如果你的回答都是「會」，那麼決策樹這種找答案 (分類) 的機器學習演算法對你實在是太簡單了！終於有一篇不用做前戲的帖子了。

本帖目錄如下

第一章 - 前戲王

第二章 - 理論皇

2.1 樹的定義

2.2 樹的數據

2.3 樹的指標

2.4 樹的生成

第三章 - 實踐狼

3.1 多分類樹

3.2 閾值選取

3.3 欠過擬合

3.4 樹的修剪

3.5 數據缺失

3.6 其它指標

總結和下帖預告

第一章 - 前戲王

無！無！無！無！無！無！無！

第二章 - 理論皇

2.1 樹的定義

決策樹

決策樹 (decision tree) 是一種描述對實例進行分類的樹形結構，由結點 (node) 和有向邊 (directed edge) 組成。結點有三種類型：

根結點 (root node)：表示樹根
內結點 (internal node)：表示特徵
葉結點 (leaf node)：表示類

決策樹是從根結點一層一層往葉結點走的，根結點在的位置叫做第 0 層，依次往下推。上一層的結點稱為下一層結點的父結點 (parent node)，而下一層的結點稱為上一層結點的子結點 (child node)。

用決策樹分類，從根結點開始，對樣例的某一個特徵進行測試，根據測試結果，將樣例分配到其子結點。此時，每一個子結點對應著該特徵的一個取值。如此遞推下去對樣例測試再分配，直到達到葉結點而分到其類中。

所有關於決策樹的定義和分類流程用下圖展示：

上圖黑色的多邊形是根結點，粉色的菱形是內結點，而綠色紅色的葉形是葉結點。注意天藍色的矩形不是任何結點，他們只是每個內結點中特徵的可能值。對照著上面定義和王妮梅那個具體例子來看：

你應該能分清楚各個圖形要表達的東西了吧：

黑色多邊形根結點
粉色菱形內結點：表示特徵長相、性格、類
綠色紅色葉結點：表示類，綠色正類「見」，紅色反類「不見」
天藍色矩形：表示特徵值

長相：好看、一般、難看
性格：好、壞
收入：高、低

決策樹樁

決策樹樁 (decision stump) 就是只有一層的決策樹。

由上圖可知妮梅這棵決策樹包含三個樹樁。

2.2 樹的數據

上面的決策樹只有一個基本的樹形，再從妮梅媽媽和妮梅的五段對話提煉出來五種分類結果 (你們可以從根數到葉子看是不是只有五條路徑)。現在假如有 40 個像妮梅這樣的女孩，她們各自的媽媽都有一個男士要介紹，問各自的女兒對長相、性格和收入之類的要求，得到女兒的回答，把數據交給情感大師斯蒂文來統計並生成相對應的決策樹 (具體生成方法見下一章)。這 40 個女孩的數據和決策樹如下：

數據

從上表裡看出數據總共有 40 行，每一個數據有四列，前三列長相、性格和收入是特徵，而最後一列「見嗎？」是類別。為了便於看出，正類 22 個「是」用綠色高亮標示，反類 18 個「否」用紅色高亮標示。

決策樹

單從數據的類上看有 22 個是 18 個否，如果不做任何決策，正分類比為 22:18，因此在根結點附近記錄 [22 18]。

斯蒂文一開始用的是長相特徵按照好看、一般和難看對樹進行分裂，當長相為

好看 (只看第一列是好看的行)，正分類比為 9:0，因此在內結點「好看」附近記錄 [9 0]
一般 (只看第一列是一般的行)，正分類比為 9:4，因此在內結點「一般」附近記錄 [9 4]
難看 (只看第一列是難看的行)，正分類比為 4:14，因此在內結點「難看」附近記錄 [4 14]

當長相為一般時，斯蒂文用的性格特徵按照好和壞對樹進行分類，當性格為

好 (在第一列是一般時，只看第二列是好的行)，正分類比為 9:0，因此在內結點「好」附近記錄 [9 0]
壞 (在第一列是一般時，只看第二列是壞的行)，正分類比為 0:4，因此在內結點「壞」附近記錄 [0 4]

當長相為難看時，斯蒂文用的收入特徵按照高和低對樹進行分類，當收入為

高 (在第一列是難看時，只看第二列是高的行)，正分類比為 4:5，因此在內結點「高」附近記錄 [4 5]
低 (在第一列是難看時，只看第二列是低的行)，正分類比為 0:9，因此在內結點「低」附近記錄 [0 9]

接下來當收入為高時，按照上述同樣的方法類推

決策樹中每個結點對正類反類計數的過程，類似於計算條件概率，因為隨著樹越來越深，你知道的條件就越來越多，比如在知道對方長相一般和性格好的條件下見不見對方男士？但是在現在我們沒有計算條件概率，姑且把這個過程叫做條件計數吧。

2.3 樹的指標

後面將介紹樹的分裂會遵循一些度量指標來選取最合適的特徵來分裂，最常見的指標有分類誤差率、信息增益、信息增益比和基尼指數等。本章先講最簡單的分類誤差率，下章再講其他指標。在介紹分類誤差率之前需要了解多數規則。

多數規則

多數規則 (majority rules)，也稱為多數投票規則 (majority voting rules)，是指一項決策須經半數以上人贊成，才能獲得通過的一種投票規則。多數規則的實質，是少數服從多數。由於一致同意規則的決策成本很高，使得多數規則成為在實踐中最為普遍運用的投票規則。對於 2.2 小節的圖

如果在根結點樹根就開始進行多數規則，正反類比為 22:18，很明顯決策為正類，意思就是情感專家斯蒂文根據數據為所有 40 個女孩的建議是「見」男方！

往下細分，如果在內結點對長相進行多數規則，當長相

好看，正反類比為 9:0，決策為正類，見男方
一般，正反類比為 9:4，決策為正類，見男方
難看，正反類比為 4:14，決策為反類，不見男方

再往下細分，按照上述多數規則可得到所有結點上的決策

按照多數規則得到的決策樹圖如下：

分類誤差率

分類誤差率 (misclassification error, 簡稱ME) 就是分類器錯誤分類的樣本數與總樣本數之比。在決策樹應用中，在一個結點，通常會計算分裂前和分裂後的分類誤差率，如果前者比後者高，那麼應該分裂，反之不應該分裂。

下圖計算了樹樁 1 在分裂前和分裂後的分類誤差率：

在第零層樹，根據多數規則，根結點的預測的是 40 正類，因為真實樣例總共有 22 正類 18 反類，那麼有 18 個預測錯誤，因此分類誤差為 18/40 等於 0.45。

對著數據表，在第一層樹，根據多數規則，當長相

好看，預測正類，真實樣例總共有 9 正類 0 反類，有 0 個預測錯誤
一般，預測正類，真實樣例總共有 9 正類 4 反類，有 4 個預測錯誤
難看，預測反類，真實樣例總共有 4 正類 14 反類，有 4 個預測錯誤

在三個特徵值下加起來一共有 8 個預測錯誤，因此分類誤差為 8/40 等於 0.2。

2.3 樹的生成

構造決策樹的關鍵步驟是分裂屬性。所謂分裂屬性就是在某個結點處按照某一特徵屬性的不同值構造不同的分支，其目標是讓各個分裂子集儘可能地「純」。儘可能「純」就是盡量讓一個分裂子集中待分類項屬於同一類別。

第一步：從樹根開始，決定一個特徵開始分裂樹，用的度量標準是分類誤差率。

具體過程如上圖，在本例中只有三個特徵：長相、性格和收入。以此用它們來分裂樹，根據上面數據表裡的數據，記下每個特徵的特徵值 (比如性格特徵對應著好和壞，收入特徵對應著高和低) 對應的正類 (見) 和反類 (不見) 的個數，再利用多數規則計算出分類誤差率。由上述結果可知，按長相分時的分類誤差率為 0.2，最低，因此一開始從樹根應該用「長相」這個特徵來分裂。

第二步：分裂之後檢查每個特徵值對應的分支，如果某個分支里所有樣例都屬於一類，那麼停止分裂；如果不屬於則繼續分裂。

按照上圖發現當長相「好看」時，所有決策都是「見」 (9比0)，因此對於這個分支無需再繼續分裂；但是當長相「一般」或「難看」時，決策結果還有分歧，還可以繼續分裂。用什麼特徵來分裂，還是按著第一步的過程，選一個分類誤差最小的但沒有用過的特徵 (這點很重要，防止一直用重複特徵會使得樹太過於複雜) 來分裂。省去具體計算 (有興趣的同學可以自己計算)，分裂完後的決策樹如下圖展示的這個樣子。

第三步：遞推生成完整的決策樹，遵循以下兩條停止條件 (stopping condition)：

條件 1 – 某個分支里所有樣例都屬於一類，停止分裂
條件 2 – 特徵已經用完了，停止分裂

由上圖知只有當長相「難看」和收入「高」時，決策結果還有分歧，因此還可以繼續分裂，但是只能用這條分支之前沒有用過的特徵 – 性格 – 來分裂。(註：沒有用過的特徵不是指著在整棵樹里沒有用過，而是特指在某條分支上沒有用過)

當樹不能再繼續分裂了，意味著每條分支都有葉結點。在每片葉子上用多數規則給出決策，也就是見或不見。最終決策樹如下圖展示的這個樣子。

根據 40 個訓練數據生成決策樹之後，我們可以用它來做預測。例如，出現了一個新男士，他的個人條件是長相難看，收入高，性格好，那麼從根往葉將上面決策樹穿越一遍 (橙色高亮)，得出的結論是見！！！如下圖所示

第三章 - 實踐狼

3.1 多分類樹

上一章的例子是個二分類決策樹，女孩只有兩種決策，見男士，不見男士。假如一位男士長得丑收入低性格暴力，那麼女孩絕逼不見！那麼這是可能有三種決策：見、不見、絕逼不見去死吧！這個例子可能不是很適當，再看一個例子，銀行根據借貸人信息決定這筆貸款是否應該借出去。這時銀行可能會對借貸人劃分三種類別：安全、危險、垃圾！這個時候怎麼玩轉決策樹呢？處理方式一模一樣，除了兩類變多類，下面還是用女孩見男士的例子來解釋，數據如下：

和二分類決策樹分裂規則一樣，在一開始選一個有最小分類誤差率的特徵來分裂，這個特徵還是「長相」，如下圖所示：

3.4 閾值選取

本例中特徵「收入」的值是離散值，高或低，這概念有點模糊，多高算高多低算低啊？現實中，特別是在問卷調查中，收入這欄填的都是10萬、20萬、50萬這種連續值。如下圖所示：

假設我們對收入出現的每個連續值來分裂，得到的樹會長成下面這樣子。

這樣劃分有兩個很嚴重的問題：

絕大多數結點只包含一個數據，要麼正類要麼反類，這是典型的過擬合現象
注意中間兩個結點顯示著矛盾的決策，見 24 萬收入的男士，卻不見 24.5 萬收入的男士

當連續值劃分的太細，我們對決策樹的預測真的沒什麼信心。一個改進方法是找一個閾值 (threshold) 來進行分裂，比如對上例，25 萬是個不錯的分界點，小於 25 萬歸結成收入低，大於等於 25 萬歸結成收入高。如下圖所示：

現在你可能會問，為什麼選擇 25 萬當做閾值？問得好，下面就來給出閾值的演算法。如下圖，將所有收入連續值按升序標註在軸上，同時也記下每個收入值對應的類別，見或不見。顯然，閾值選在圖中 A 點和 B 點中間任一點，得到的分類誤差率都一樣！

因此我們的做法是

對每兩個相鄰的點，算出它們的中間值 (N 個點就有 N-1 個中間值)
把每個中間值當成閾值，計算出相對應的分類誤差率
找到最小的分類誤差率，並將其對應的中間值當成閾值

如下圖所示：

3.4 欠擬合

和所有機器學習方法一樣，決策樹也可能發生欠擬合或過擬合的現象。如下例，黑色加號代表正類，桃紅色減號代表反類。

其中 x[1] 和 x[2] 是兩個連續值特徵。下圖展示了一層樹和兩層樹的全貌。

和離散特徵不同，連續特徵可以在一條分支上多次選擇不同的閾值來進行分裂。你可以想像不停地細分連續值，那麼決策樹可以完美分類任何訓練集，但是也嚴重地過擬合了訓練數據而降低了其泛化能力。

下圖類比了決策樹和對率分類模型，其中

一層決策樹和一次多項式對率分類欠擬合了數據，訓練集上的誤差都比較大
十層決策樹和六次多項式對率分類過擬合了數據，訓練集上的誤差為零，但模型泛化能力弱
三層決策樹和二次多項式對率分類好擬合了數據，模型棒棒噠

對於欠擬合模型，我們增加模型複雜度 (增加決策樹的層數，增加對率模型多項式次數)；對於過擬合模型，我們降低模型複雜度 (修剪決策樹，正規化對率模型)。下小節就細談如何修剪樹來防止它過擬合。

3.4 樹的修剪

修剪 (pruning) 是決策樹防止「過擬合」的主要手段。在決策樹生成過程中，為了儘可能正確地分類訓練集，結點劃分將不斷重複而可能造成分支過多。這樣的後果就是這棵樹把訓練集學的太好了，從而把訓練集所有特點當作所有數據具有的一般性質，這樣模型的泛化 (generalization) 能力就會下降。因此可通過主動去掉一些分支來降低過擬合的風險，可以用兩種思路：

未雨綢繆的思路：從根到葉的方向，在樹生成中，預修剪 (pre-pruning) 分支以防樹變得複雜
亡羊補牢的思路：從葉到根的方法，在樹生成後，後修剪 (post-pruning) 分支致使樹變得簡單

預修剪

預修剪是指在決策樹生成過程中，對每個結點在劃分前先進行估計，一旦遇到以下三個提前停止條件 (early stopping condition)，就應該將當前結點標記為葉結點。

提前停止條件 1：當樹的深度超過一個特定值 (最大樹深)

回顧上一節的「十層決策樹」，當你無限次用不同的閾值分裂節點，得到的決策樹可以完美分類所訓練集，但是對新的測試集分類性能一定很差因為過擬合了。為了防止過擬合，我們會限制樹的深度。做法是用驗證集 (當數據很多時) 和交叉驗證集 (當數據不多時)。

用驗證集選擇最大樹的深度流程如下：

按 80% 和 20% 劃分訓練集和驗證集
用訓練集構建不同深度的樹，並在驗證集上計算分類誤差率
選一個分類誤差率最小的樹對應的深度作為最大樹深

用交叉驗證集選擇最大樹的深度流程如下：

將整個數據集大概平均分成 5 份
對於每一個模型 (不同深度的樹)，從第一份到最後一份，將選中那份數據集當作驗證集，剩餘的四份一起當作訓練集

用訓練集構建不同深度的樹
在驗證集上計算分類誤差率

求出 5 個分類誤差率的均值作為交叉分類誤差率。
選一個交叉分類誤差率最小的樹對應的深度作為最大樹深

提前停止條件 2：當繼續分裂不能減小分類誤差率

假設從樹根用特徵長相分裂後的樹樁如下，當長相難看時，有 5 個正類和 16 反類，很顯然還可以繼續分裂下去。接下來我們計算不劃分、用性格劃分和用收入劃分後的分類誤差率，發現都是 0.24 (見下圖)。既然不分裂和繼續分裂的分類誤差率都一樣，那麼我們選擇簡單的 (簡單點，簡單點，修剪的方式簡單點)，應該提早停止分裂而直接作決策。

有的時候，當你簡化樹的決心更大時，你可能會選擇一個 r 值，比如 5%，進而規定"只要繼續分裂生成的分類誤差率沒有減少 r ，那麼停止分裂」。

提前停止條件 3：當內結點包含的數據個數小於一個特定值

當結點裡數據太少，我們就會提早停止分裂，如下圖所示，當長相一般只對應這 3 個數據，這時候應該直接作決策而不是再往下分裂。

具體這個特定值要根據數據總數決定，通常實踐中選 10 到 100 之間任何一個數。

後修剪

預修剪使得決策樹的很多分支都沒有展開，不僅降低了過擬合的風險，還減少了決策樹的訓練時間。但另一方面，有些分支過早停止但其實後續分裂區有可能導致性能顯著提高。這樣看來，預修剪有可能給決策樹帶來欠擬合的風險，這個時候後修剪的作用就來了。

後修剪的核心理念是先訓練好決策樹，即便複雜，再從葉往根開始簡化，如果一個樹樁可以用一個葉結點替代，那就替代而簡化樹！在後修剪過程中，我們需要平衡模型的分類能力和樹的複雜度，前者可用誤差分類率來量化，而後者可用樹葉的個數來量化。其代價函數為

C(T)= ME(T) + λ?L(T)

其中

T = 當前的樹

C(T) = 代價函數

ME(T) = 分類誤差率

L(T) = 葉結點的個數

λ = 參數

當 λ 等於 0 時，後修剪就只比較分類誤差率而不考慮葉結點的個數；當 λ 等於無窮時，後修剪最終生成單單一個樹根，因為多一個葉結點的代價太大了。下圖描述了後修剪的過程。

假設參數 λ 是 0.3，從最低層樹樁開始 (上圖紅色橢圓框)，如果不修剪，整棵樹有 6 片葉子，C(T) 為 0+ 6 ? 0.3 等於 1.8；如果修剪 (用一片葉子替代這個樹樁)，那麼修後的樹 (見下圖) 有 5 片葉子，C(T) 為 0.1+ 5 ? 0.3 等於 1.6。修剪後的 C(T) 小於修剪前的 C(T)，那麼這個樹樁應該要被修剪掉！注意，雖然修剪後的分類誤差率大了一些，但是葉結點也少了，權衡這兩點還是應該修剪。

接下來，對剩下三個內結點「性格」，「收入」和「長相」重複以上修剪過程。

後修剪決策樹通常比預修剪決策樹保留了更多的分支，因此前者的欠擬合風險很小，而泛化性能往往優於後者。但後修剪過程是在生成完整決策樹之後進行的，並且要從葉往根對樹中所有內結點逐一檢測，因此其時間開銷比預修剪決策樹要大得多。

3.5 數據缺失

目前決策是的生成和修剪都是基於完整的數據。但是在實際情況中數據缺失是一種很普遍的現象，可能訓練數據某一個特徵值缺失，也可能測試數據的某一個特徵值缺失。下圖顯示著一個缺失部分數據的訓練集 (兩個性格特徵下和一個收入特徵下的數據缺失)

下圖顯示著一個缺失收入特徵值的測試數據 (當我們要預測是否見下一個男士時，如果該男士沒有提供他的收入，怎麼辦)

一般來說，缺失數據的處理方式有三種：

刪除 (delete)
推算 (impute)
歸類 (categorize)

刪除

刪除數據是最簡單也是最無腦的一種做法，其方式有兩種，刪除行 (數據點)，或者刪除列 (特徵)。如下圖所示：

刪除數據的優缺點有：

優點

操作簡單
可以用在任何模型比如決策樹、線性回歸和對率分類等等

缺點

刪除的數據可能包含著重要信息
不知道刪除行好還是刪除列好
對缺失數據的測試集沒用

推算

根據特徵值是分類型 (categorical) 變數或數值類 (numerical) 變數，推算的方式有兩種：

用眾數來推算分類型缺失數據
用平均數來推算數值型缺失數據

特徵「性格」的特徵值是個分類型變數，因此計數未缺失數據得到 2 個好和 7 個壞，根據眾數原則應該將缺失數據用「壞」來填充。特徵「收入」的特徵值是個數值型變數，根據平均數原則算出未缺失數據的均值 20.4 萬來填充。

推算數據的優缺點有：

優點

操作簡單
可以用在任何模型比如決策樹、線性回歸和對率分類等等
對缺失數據的測試集有用，運用同樣的規則 (眾數分類型變數，平均數數值型變數)

缺點

可能會造成系統性誤差

對於系統性誤差有個真實案例，在華盛頓的銀行里申請貸款，根據當地法律，申請人是不允許填年齡的。如果把整個美國申請人資料合在一起，很明顯發現所有來自華盛頓的數據缺失年齡那一欄。假如按照「平均數數值型變數」這個規則算出均值是 41 歲，那麼把所有華盛頓申請者的年齡填為 41 歲是極其不合理的。

歸類

歸類的核心思想是把「缺失 (unknown)」也當作是一種特徵值，如下圖：

當缺失收入特徵值時，一開始我們無法利用決策樹來做出決策。現在只需把「收入缺失」和「收入低」歸納成同一類，就很容易做出決策 – 不見！

同理，我們可以把「缺失」分類到每個特徵上，一方它們都有可能有缺失的特徵值。現在我們的決策樹長成以下的樣子。

上圖一個有趣的地方是在把「缺失」歸類給特徵性格時，有時把它和「好」放一起，有時把它和「壞」放一起。接下來就來解釋其原因。換一個問題問：是否有一個規則來決定「缺失」放在哪一特徵值？有！和上一章用的規則一樣，選用最小分類誤差率，具體過程見下圖。

歸類數據的優缺點有：

優點

比起刪除/推算數據，預測更准
對缺失數據的訓練集和測試集都有用

缺點

需要修改演算法，雖然對決策樹不難

3.6 其它指標（參考周志華教授《機器學習》）

上一章用的分類誤差率指標來分裂特徵，其它常見的還有信息增益、信息增益比和基尼指數。了解它們之前需要知道熵和條件熵的概念。

熵

在資訊理論 (information theory) 中，熵 (entropy) 是表示隨機變數 Y 不確定性的度量。假設 Y 是一個離散隨機變數，其概率分布為

那麼 Y 的熵定義為

在上式中，pi 表示當前樣本集合中第i類樣本所佔的比例，例如前面介紹男朋友的例子有兩類樣本，即見和不見（n=2）。如果某個 pi 等於0，定義 0log2 0 = 0。由定義可知，熵只跟 Y 的分布有關因為 H 是個概率的函數，而和 Y 的值無關。當隨機變數 Y 只取兩個值時 (概率為 p 和 1-p)，其熵為