機器學習算法複習手冊——決策樹
- 2019 年 10 月 29 日
- 筆記
本手冊整理自機器學習各相關書籍、網絡資料、個人的理解與實踐。總體編寫宗旨： ①一看就懂； ②用20%的文字，涵蓋80%的內容。 至於剩下的20%，一般屬於比較偏、難的部分，建議自行查詢相關書籍資料學習。而只用20%的文字，則代表手冊裏面幾乎沒有廢話，也只有極少數必要的例子。
下面進入正題。
決策樹
決策樹是一種基本的分類回歸模型。它可以認為是if-then規則的一個集合，或者是特徵空間和類空間上的條件概率分佈。
優點：模型可讀性強，訓練速度快。
構建決策樹的步驟：
- 特徵選擇
- 決策樹的生成
- 決策樹的剪枝
主要算法：ID3（1986年），C4.5（1993年），CART（1984年）
一、特徵選擇
決策樹中的每一個分支是怎麼來的呢？比方對貸款違約情況訓練一個分類模型，我們有「年齡段」、「是否有房子」、「是否有工作」三個特徵。那究竟選擇哪個特徵呢？
特徵選擇，就是要選出有「分類效果」的特徵。 如何體現「分類效果」？——信息增益，信息增益比，基尼指數
1.信息增益
信息增益，顧名思義，就是信息增加的情況。 何謂信息呢？在信息論中，我們使用「熵」（entropy）來表示事務不確定性的程度，也就是信息量的大小（往往說信息量大，就是指這個事情背後的不確定因素太多了） 。
假設一個隨機變量的概率分佈為：
則這個隨機變量的熵為：
可以看出，熵的大小，跟變量本身的值無關，只跟變量的概率分佈有關。
對於隨機變量(X,Y),其聯合概率分佈為：
這個時候，可以定義Y在X的條件下的條件熵：
條件熵的意義就是：在給定了X的信息之後，Y這個隨機變量的信息量（不確定性）的大小。
因此，我們可以進一步定義，特徵A對數據集D的信息增益（information gain）為g(D|A)，它等於D本來的熵，與給定A的條件下的D的條件熵的差值，即：
具體：
從上面的公式很容易理解信息增益的意義：引入了特徵A之後，原來數據集D的不確定性減小了多少。
這樣，我們就可以方便地計算出每一個特徵引入後的信息增益，選擇給D帶來的信息增益最大的特徵，即為最優的特徵了。
2.信息增益比
用信息增益作為標準來確定特徵的話，存在偏向於特徵取值較多的特徵，而這樣的話很容易造成過擬合。因此，我們引入了信息增益比（information gain ratio）這個指標，對那些特徵值過多的特徵做一定的「懲罰」：
就是對信息增益除以一個跟A有關的分母，這個分母稱為屬性A的「固有值」，往往A的特徵值越多的話，這個固有值也會越大。
但是，需要注意的是：信息增益比，反過來會對可取值數目較少的特徵有偏好。所以也不是信息增益比就一定優於信息增益。 實際上，C4.5算法也不是直接使用信息增益比來進行特徵選擇，而是先找出信息增益高出平均水平的那些特徵，然後再從中挑選信息增益比最高的。
3. 基尼指數
基尼指數跟信息增益的理念不同，它除了要選擇最優的特徵，還要確定這個特徵的最優二值切分點。也就是說，對於每一個特徵，我們都只確定一個切分點，將數據集分成兩份。而在信息增益（比）的標準中，一個特徵有幾個值，就會把數據集分成幾份。
基尼指數的定義是這樣的，對於隨機變量X，其基尼指數為：
那麼對於一個數據集D，其基尼指數就是：
其中C是類別數。 基尼指數反映了這個數據集的「純度」。基尼指數越小，說明數據集純度越高。
同樣也有條件基尼指數，對於給定特徵A後，A中的某一個特徵值a將D分成了兩部分D1和D2，那麼定義在特徵A=a的情況下，D的基尼指數為：
因此，對於一個特徵A，我們可以對每一個特徵值（劃分點）求一個基尼指數，其中最小的那個基尼指數，就對應着這個特徵的最佳劃分點。
二、決策樹的生成
決策樹的生成方式，一句話就是：用特徵選擇指標，從根節點往下一個個節點選擇最佳特徵，遞歸地生成決策樹。 所以從編程的角度講，就是一個遞歸函數：
tree_generation(D,A): 先處理遞歸終止情況： 1. 如果D所有樣本都屬於同一類，那麼整個D就是一個結點，返回一個葉子節點 2. 如果A是空集，即沒有特徵供我們選擇，則整個D就是一個結點，返回一個葉子節點 再處理其他正常情況： 3. 排除上面兩種情況後，選擇A中對D的最優特徵Ai 4. 如果特徵Ai不滿足某種條件（不夠有區分度，比如信息增益小於某閾值）,則D就成為一個葉子節點並返回 4. 如果特徵Ai滿足某種條件，那麼就用Ai對D進行劃分，得到若干個子結點，對每個節點，調用tree_generation(Dk，A-Ai)
不同的算法的主要區別在於用什麼指標來進行特徵選擇：
- ID3算法使用信息增益作為指標來選擇特徵。
- C4.5算法使用信息增益比來選擇特徵
- CART算法則使用基尼指數
當然，不同的算法還有很多其他細節的不同，例如CART生成的就是二叉樹。但是主要的思想就是上面那個遞歸函數。
三、決策樹的剪枝
前面的決策樹的生成過程，是完全根據訓練集來的，所以會儘可能地去擬合訓練集中中的特點，這樣形成的樹往往會很茂密，分支很多，往往泛化性能就不高。 所以，我們就要使用一個驗證集來對生成的樹進行「剪枝」處理。
剪枝的基本策略有兩種：「預剪枝」和「後剪枝」。
1. 預剪枝
預剪枝，顧名思義，就是不要等到最後再剪，而是在前面有機會剪就剪。 什麼時候有機會呢？——當你發現當前對節點的劃分不能帶來性能的提升時。這個時候就果斷把這個小樹苗「扼殺在搖籃里」。因此這是一種「自頂向下」的剪枝方法。
比方，對於一個結點，根據訓練集的數據，我們發現使用特徵A的信息增益（比）最高，所以可以使用A來對該結點進行劃分。 但是你擔心劃分會過擬合，也就是在驗證集/測試集上的表現不好。
要怎麼判斷呢？
- 假設不劃分（對應剪枝），那麼該結點就是葉子結點了，其類別就是服從大多數的類別。然後，計算一下這個結點在驗證集上的準確率α1；
- 假設劃分（對應不剪枝），那麼該結點就分成了若干個子結點，每個子結點的類別還是按照「服從大多數」的方法來確定。然後，計算一下驗證集在各個子結點上的綜合的準確率α2；
- 比較一下α1和α2，誰大誰就好。
思路還是很簡潔的哈。
預剪枝的方法，使得很多分支，還沒出生，就被扼殺，大大減少了決策樹訓練的時間、計算開銷。 但是，這樣生成的樹，往往很稀疏，存在欠擬合的風險。為啥呢？因為你剪枝的過程「太急」了，可能十分「短視」，有一些節點的劃分，可能當前不能提升泛化性能，但是在這個劃分的基礎上的劃分，卻可能會有顯著的效果提升。這就是短視可能的代價，只追求眼前的利益，可能長遠看來確實虧損的。
2.後剪枝
後剪枝，顧名思義，就是事後諸葛亮，先一口氣把樹使勁生成，然後我再回過頭來，一刀一刀地砍。這個時候就只能「自底向上」地砍樹了。 思路也很簡單：
- 本來整棵樹在驗證集上的準確率為α1
- 對於一個節點的劃分，如果把分支都砍掉，那麼就退化成一個結點。使用「服從大多數」法則，確定其類別，計算整棵樹在驗證集上的準確率α2；
- 比較一下α1和α2，誰大誰就好。
後剪枝明顯會比預剪枝的泛化性能更好，欠擬合風險也更低。但是這個方法，需要等樹完全生成，所以總體時間開銷也比較大。
x、關於決策樹的其他
其他細節包括：
- 如何處理連續值
- 如何處理缺失值
- 決策樹的分類邊界
- ……
這些細節問題建議參考周志華的西瓜書，這裡不再贅述。
當然，Talk is cheap, show me the code. 後面的文章我會展示如何用python實現一個簡單的決策樹模型的思路和代碼。
本文參考資料： 1. 李航，《統計學習方法》 2. 周志華，《機器學習》
