決策樹的優化這一刀該不該剪？

02-12

本文默認大家都對決策樹演算法有比較清楚的了解，如果不太明白決策樹的基本原理可以先Skip，在以後也會提供一些關於決策樹基礎知識的一些入門專題。本文主要討論的是決策樹的模型優化問題。

決策樹也是機器學習的主要模型之一，通過測試集，訓練出一個樹形的模型來，樹的每一個路徑（從根節點到葉節點），都是一個決策規則。如下圖：

費用變化率=F2->繳費方式=T1->在網時長=H1 èYes 就是一個規則

按理說，這個模型已經okay了，每個路徑是一條規則的話，就形成了10條規則（有多少條規則數有多少個葉節點就是了，葉節點通常表現為決策屬性）。但是，這個模型或許需要簡化，因為模型複雜了會有過度擬合的問題。什麼是過度擬合呢？因為這個模型是來自於訓練數據集的，但是適合訓練數據集的數據不一定適合未知的測試數據。所以，如果太Match訓練數據所構造的模型，對於測試的數據可能就不那麼match了。注意，其實我們的根本目的其實是要構造一個足夠match測試數據集的模型！太強調match訓練集而導致模型在測試集性能反而下降，就是所謂的過度擬合的現象，英文稱為：Overfitting。

過度擬合的問題其實挺複雜的，可以專門開一個專題說了，總而言之，模型的構造需要盡量滿足訓練集數據，也要考慮模型的複雜性，二者之間需要一個折中。

這個折中也可以描述為：優先選擇擬合數據的最簡單的假設。（Occam』s Razor）

學習馬克思理論的一看這英文就知道，這其實就是常說的奧坎姆剃刀，「追求簡潔」。如果兩個模型都玩兒的轉，那麼優先選擇簡單一點兒的模型。Okay，其實誰不喜歡簡單一點兒呢？生活就是簡簡單單，玩兒技術也一樣。越炫的未必是越好的，我們不提倡裝B。

接下來就說說，怎麼追求簡單的模型。一般的思路是，先把模型搞出來，複雜點兒沒關係，然後，再從下向上砍掉這顆決策樹的枝，把它化簡。機器學習，將這個過程稱作剪枝（pruning）。剪枝的過程，就是把一個屬性節點直接變成一個決策節點的過程。如圖：

扣下來一小塊兒，比如職業這個屬性是一個分類屬性，有三個取值：職業=Z1èNo 職業=Z2èYes 職業=Z3èNo

然後開始剪，把這個屬性剪掉，我不管職業這個屬性取什麼，我都讓它是Yes。於是這個屬性節點，包括後面的決策結果，都剪了，就直接用一個Yes節點代替好了。為什麼選用Yes擺在兒？別認真，舉個例子，我假設到達這個職業節點的訓練數據裡面，決策屬性是Yes的多，就貼個標籤是Yes（選多數的類別）。

剪枝還可以更牛逼一點，比如：

繳費方式這個屬性，在下面還有屬性分類的過程，沒關係，可以直接剪（一次剪掉兩層），到達繳費方式這個屬性的數據不再按照繳費方式這個屬性取值分類了，直接貼個標籤（Yes or No）。但是我們不提倡一次剪兩層，這樣講只是說明剪枝是沒有限制的，畢竟一次步子邁大了，容易扯到x。但是無論如何，我要說明的是，剪枝的方法，一定是從葉子開始，自下而上的，不斷地把決策所需要考慮的屬性從決策樹裡面剝離出去。（也有一些方法不是自下而上的化簡掉決策屬性，那就不是剪枝方法了，這兒暫不談）

剪枝怎麼剪說清楚了，很簡單，說剪就剪，嘎嘣利落？不然，文明人還是要問為什麼的，我們說的剪枝要考慮條件，只有剪了比不剪好，才剪，指甲可以剪，手指頭行么？我們一般來講有可供生成模型的數據，為了考慮剪枝的問題，我們不把所有的數據都拿來做訓練數據集，而是一分為二，一份兒訓練模型（A集合），一份兒做測試集（B集合）。A集合先把決策樹work出來，然後拿B集合來測試，對於決策樹從下向上一點兒一點兒地剪，每剪一刀，用B集合測一次，看看效果優化了沒有，優化了就繼續剪，變差了，就到此為止，再剪就剪手指頭了。那麼你又問了，即便從下向上剪枝，每次可以很多地方下刀，怎麼選？這個問題不難，選擇對B集合測試結果優化最顯著的地方就可以了。隨著剪枝，一般來講模型性能（在測試集）先優化後下降，我們一點一點地剪枝找到那個最優的點就好。

這裡來一條分割線，以上是1.0版本的剪枝，後面是2.0版本的，考慮一個稍微複雜點兒的情況。假如我們不想把數據分成訓練集合和測試集合怎麼辦？我們手頭上的數據本來就夠少的了，你還叫我分家，太殘忍了，事實上，數據的成本也是很高的。很多人想，湊合一下，訓練集合和測試集合用一個可以不可以？

你的直覺是：「當然不可以了，你用訓練集work出模型，再用它測，肯定性能越剪越差，如果性能越剪越好的話，壓根就不可能work出這模樣兒的模型，這顆樹早就停止生長了。」這話沒錯，但是，剪枝是帶來效益的，這個效益如果能夠量化到決策樹的準確率裡面去，就可以衡量剪枝前和剪枝後的模型的好壞了。即便剪枝了，正確率下降了，但是剪枝又帶來了效益，把這個效益換算成一定的正確率加上去，沒準剪了就比沒剪好。

我們考慮這樣的問題：假設到達一個屬性節點的數據總數是N。現在沒剪枝，被這個屬性一分割，分成了m份兒（假設這個屬性的取值有m個離散值），每一份兒是一個葉子節點，每個葉子節點裡面兒都有 $n_{1},n_{2},...n_{m}$ 個數據。然後，每個葉子節點裡面錯誤分類的個數是 $k_{1},k{2},....k_{m}$ 。假設每個節點的錯誤數為：