Change Dir

決策樹和Random Forests——優秀的群體智慧

What is Decision Tree:

說起決策樹，就好像是一個ML算法的標配一樣，在每本ML的教程里，每個ML的代碼庫里，每個ML的軟件包里，都有決策樹的存在。個人認為決策樹是一種人類本能的規則判別的算法表達，當我們遇到一個分類問題時，本能的會以一些IF-THEN規則去劃分，這是本質的關聯和分類的思維在起作用。比如我們在做決策時總會找一些閾值x，大于x該怎么做，小于x又該怎么做。或者我們換句話說，決策樹是一種歸納推理的典型，而我們數學推理的模式無非是歸納和演繹。

決策樹分類是希望通過數據集中各個屬性的特點，歸納得到一組規則作為分類條件，而這些規則是通過一棵樹來展現的，每個節點都是一個規則，得到規則后在遇到新的數據實例時，只要從樹根按照順序遍歷樹，評估每個節點的規則條件，最后到達葉子時就得到了決策。我們就拿Quinlan論文中的例子來講什么是決策樹。下面的表是一個訓練數據集，其中表示了每天的一個天氣狀況（有4個特征維度：forecast, temperature, humidity, windy），而需要給出的決策結論(class)是當天是否要play tennis。而下面的圖就是決策樹。

其實稍加推斷，不難發現，根據訓練集去構建決策樹，樹的數目是不唯一的，甚至是無限多的（當然前提是數據集足夠充分），比如上面就有兩棵決策樹，它們都是正確的，但是從復雜程度上來看有了區分。但是我們構建分類器的目的是要盡可能的具備優秀的泛化能力，即除了對訓練數據集有好的效果，對于未知數據的分類要準確這才是我們想要的結果?；诖?，我們構建決策樹不是隨便的，我們傾向于更簡單的樹，更簡單的規則來分類數據，因為這樣明顯具有更好的泛化能力（顯而易見）。具體如何構建呢？決策樹算法有成千上萬種，paper也遍地都是，但是ID3算法是構建決策樹的最經典的算法之一，也是Quinlan的經典作。

ID3是一個迭代的算法，自頂向下構建決策樹，步驟可以分作3步：

1. 在所有沒有選定的屬性中，計算每個屬性的信息增益

1. 選擇信息增益最大的特征作為節點

1. 對于選定的節點特征，選擇其所有的可能取值作為子節點，重復步驟a，直到葉子節點的熵為0或者屬性節點全部被計算過

直白的解釋是，構建樹嘛，就要不斷的選好節點和子節點咯，選的規則嘛，很簡單——信息增益，為啥是信息增益？信息增益怎么算？這要引出一段故事了：

熵是信息論中廣泛使用的度量標準，表述的是數據集的純度，在信息論中的解釋是對信息編碼的最少二進制位數。

以上面的數據集為例，14個數據實例的樣本集S，有9個P，5個N，所以它p(class:P)=9/14，p(class:N)=5/14，在class上的熵為-(9/14)log2(9/14)-(5/14)log2(5/14)=0.94。熵值在0~1之間分布，熵越小說明數據集越純。因為分類樹的目的是找到規則屬性來盡量的劃分不同類別，那么也就是說如果能找到一個屬性來劃分數據集從而使期望的熵最小，則這個節點的屬性就是好的，表示這個屬性的這種程度被定義為信息增益（information gain）

Values(Windy)=True, False

S = [9 P, 5 N]

=[3 P, 3 N]

=[6 P, 2 N]

同樣的道理我們計算所有的屬性的信息增益得到

Gain(S,Outlook)=0.246, Gain(S,Humidity)=0.151, Gain(S,Temprature)=0.029

屬性Outlook具有最大信息增益，所以第一個節點就選Outlook，而剩下的過程照此迭代，于是得到了最后的決策樹就如上面圖片中較簡單的樹形。當然作為衡量屬性優劣的度量標準除了信息增益外還有增益比率（gain ratio）和基尼指數（gini index）等。

決策樹的分支條件除了上述的方法，還有通過做轉移函數來進行斜分的和基于最近鄰的圖的方式，具體幾種劃分的幾何表示見下圖。我們一般的劃分數據方法也是采用第一種。

決策樹學習算法包含了3個部分：特征選擇、樹構建和剪枝，特征選擇可以幫助我們構建更簡單有效的樹，這個過程其實在很多的機器學習算法中都必不可少，正如Quinlan在論文中提到的噪音問題和丟失值問題，這些都會影響樹的構建。而樹構建由上面介紹的ID3算法可知是一個啟發式搜索過程，如果采用暴力的做法，那么構建決策樹是一個需要搜索出所有可能的樹然后選擇最優的問題，這是NP的，所以全局最優的結論是無法做到的，只能通過像ID3這樣找到合適的啟發準則（信息增益）來做局部最優搜索（貪心搜索）。順序搜索帶來的問題就是過擬合和局部最優性，我們對于一個訓練集進行ID3算法，很難找到一個泛化能力強的樹形model，所以這也順其自然的引出了剪枝的過程。剪枝就是把一些不重要的分支砍掉從而達到簡化model的目的，同時這也滿足決策樹在歸納偏置上的傾向——簡單勝于復雜。剪枝可以看做是構建的一個逆過程，自底向上的剔除不“合格”的分支，而“合格”的定義取決于代價函數，代價函數定義為

如果把代價函數的第一項表示為

那么最后的代價函數形式為

這里C(T)表示預測誤差，|T|表示模型的復雜度。剪枝的算法描述如下：

1. 計算節點的經驗熵
2. 
3. 重復步驟b直到得到最小子樹。

經過剪枝的決策樹將原有的可能過擬合和有點復雜的樹縮減到一棵簡單樹，完成了模型的泛化。

在應用ID3決策樹時需要考慮的問題還有很多，比如缺失值、噪聲數據、數據屬性要求是nominal或者是enum等等，而Quinlan后面的C4.5算法作為ID3的升級版優化解決了部分問題，比如對于特征屬性已經可以兼容連續數值型屬性，使用信息增益比率來代替信息增益作為度量標準等等。因為決策樹是隨機森林的基礎，所以特地結合教科書和Quinlan的paper做一個簡單介紹，由于發展歷史較為悠久，所以變種的決策樹多如牛毛，決策樹算法的各個階段都有非常多的paper改進，包括各種剪枝方法理論、樹的大數據挑戰和可視化等等，感興趣的話自行查閱搜索，后面可能會單獨介紹CART和C4.5這兩種樹的算法并對比ID3,C4.5和CART。

What is Random Forests:

隨機森林是一個組合分類的方法，和bagging和boosting一樣都非常常用，組合分類的思想就是將k個學習模型組合在一起，從而創建一個復合分類模型，最后通過投票來決定分類決策。隨機森林的一個通俗解釋就是：由一組決策樹構建的復合分類器，它的特點是每個決策樹在樣本域里使用隨機的特征屬性進行分類劃分。最后分類時投票每棵分類樹的結論取最高票為最終分類結論。

如上所述，如果我們理解隨機森林是一組決策樹構成的，那么我們需要首先找到構建決策樹的方法，同時我們也需要一個判別函數去將各個決策樹的分類結果匯總起來并且能保證他們的準確度。首先，如何構建這些決策樹呢，顯然不能用同樣的數據集和同樣的特征向量，否則構建n個決策樹和構建一個是等價的。那么隨機化如何呢？隨機化是ML的一個很重要的方法，也是一個很有用的工具，例如交叉驗證、隨機抽樣等等。一種方法來構建決策樹就是隨機的選擇n個特征子集來訓練n個決策樹，那如上所說，樹構建好后需要判別函數來把結果整合，定義判別函數之前我們先看一個后驗概率

隨機森林是集體智慧的象征，通過隨機分配一些特征向量來各自學習最后選舉結果，準確率據說可以媲美AdaBoost，且對錯誤和利群點更魯棒，通過調整森林中樹的個數可以使泛化誤差收斂，解決過擬合問題。同時調整個體樹的屬性選擇可以提高準確率，通常的選擇方法是log2d+1個屬性。

posted on 2014-08-27 10:12 changedi 閱讀(5024) 評論(2)  編輯  收藏 所屬分類: 機器學習