Change Dir

決策樹和Random Forests——優(yōu)秀的群體智慧

What is Decision Tree:

說起決策樹，就好像是一個(gè)ML算法的標(biāo)配一樣，在每本ML的教程里，每個(gè)ML的代碼庫里，每個(gè)ML的軟件包里，都有決策樹的存在。個(gè)人認(rèn)為決策樹是一種人類本能的規(guī)則判別的算法表達(dá)，當(dāng)我們遇到一個(gè)分類問題時(shí)，本能的會(huì)以一些IF-THEN規(guī)則去劃分，這是本質(zhì)的關(guān)聯(lián)和分類的思維在起作用。比如我們?cè)谧鰶Q策時(shí)總會(huì)找一些閾值x，大于x該怎么做，小于x又該怎么做。或者我們換句話說，決策樹是一種歸納推理的典型，而我們數(shù)學(xué)推理的模式無非是歸納和演繹。

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

其實(shí)稍加推斷，不難發(fā)現(xiàn)，根據(jù)訓(xùn)練集去構(gòu)建決策樹，樹的數(shù)目是不唯一的，甚至是無限多的（當(dāng)然前提是數(shù)據(jù)集足夠充分），比如上面就有兩棵決策樹，它們都是正確的，但是從復(fù)雜程度上來看有了區(qū)分。但是我們構(gòu)建分類器的目的是要盡可能的具備優(yōu)秀的泛化能力，即除了對(duì)訓(xùn)練數(shù)據(jù)集有好的效果，對(duì)于未知數(shù)據(jù)的分類要準(zhǔn)確這才是我們想要的結(jié)果。基于此，我們構(gòu)建決策樹不是隨便的，我們傾向于更簡單的樹，更簡單的規(guī)則來分類數(shù)據(jù)，因?yàn)檫@樣明顯具有更好的泛化能力（顯而易見）。具體如何構(gòu)建呢？決策樹算法有成千上萬種，paper也遍地都是，但是ID3算法是構(gòu)建決策樹的最經(jīng)典的算法之一，也是Quinlan的經(jīng)典作。

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

1. 在所有沒有選定的屬性中，計(jì)算每個(gè)屬性的信息增益

1. 選擇信息增益最大的特征作為節(jié)點(diǎn)

1. 對(duì)于選定的節(jié)點(diǎn)特征，選擇其所有的可能取值作為子節(jié)點(diǎn)，重復(fù)步驟a，直到葉子節(jié)點(diǎn)的熵為0或者屬性節(jié)點(diǎn)全部被計(jì)算過

直白的解釋是，構(gòu)建樹嘛，就要不斷的選好節(jié)點(diǎn)和子節(jié)點(diǎn)咯，選的規(guī)則嘛，很簡單——信息增益，為啥是信息增益？信息增益怎么算？這要引出一段故事了：

熵是信息論中廣泛使用的度量標(biāo)準(zhǔn)，表述的是數(shù)據(jù)集的純度，在信息論中的解釋是對(duì)信息編碼的最少二進(jìn)制位數(shù)。

以上面的數(shù)據(jù)集為例，14個(gè)數(shù)據(jù)實(shí)例的樣本集S，有9個(gè)P，5個(gè)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之間分布，熵越小說明數(shù)據(jù)集越純。因?yàn)榉诸悩涞哪康氖钦业揭?guī)則屬性來盡量的劃分不同類別，那么也就是說如果能找到一個(gè)屬性來劃分?jǐn)?shù)據(jù)集從而使期望的熵最小，則這個(gè)節(jié)點(diǎn)的屬性就是好的，表示這個(gè)屬性的這種程度被定義為信息增益（information gain）

Values(Windy)=True, False

S = [9 P, 5 N]

=[3 P, 3 N]

=[6 P, 2 N]

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

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

屬性O(shè)utlook具有最大信息增益，所以第一個(gè)節(jié)點(diǎn)就選Outlook，而剩下的過程照此迭代，于是得到了最后的決策樹就如上面圖片中較簡單的樹形。當(dāng)然作為衡量屬性優(yōu)劣的度量標(biāo)準(zhǔn)除了信息增益外還有增益比率（gain ratio）和基尼指數(shù)（gini index）等。

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

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

如果把代價(jià)函數(shù)的第一項(xiàng)表示為

那么最后的代價(jià)函數(shù)形式為

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

1. 計(jì)算節(jié)點(diǎn)的經(jīng)驗(yàn)熵
2. 
3. 重復(fù)步驟b直到得到最小子樹。

經(jīng)過剪枝的決策樹將原有的可能過擬合和有點(diǎn)復(fù)雜的樹縮減到一棵簡單樹，完成了模型的泛化。

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

What is Random Forests:

隨機(jī)森林是一個(gè)組合分類的方法，和bagging和boosting一樣都非常常用，組合分類的思想就是將k個(gè)學(xué)習(xí)模型組合在一起，從而創(chuàng)建一個(gè)復(fù)合分類模型，最后通過投票來決定分類決策。隨機(jī)森林的一個(gè)通俗解釋就是：由一組決策樹構(gòu)建的復(fù)合分類器，它的特點(diǎn)是每個(gè)決策樹在樣本域里使用隨機(jī)的特征屬性進(jìn)行分類劃分。最后分類時(shí)投票每棵分類樹的結(jié)論取最高票為最終分類結(jié)論。

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

隨機(jī)森林是集體智慧的象征，通過隨機(jī)分配一些特征向量來各自學(xué)習(xí)最后選舉結(jié)果，準(zhǔn)確率據(jù)說可以媲美AdaBoost，且對(duì)錯(cuò)誤和利群點(diǎn)更魯棒，通過調(diào)整森林中樹的個(gè)數(shù)可以使泛化誤差收斂，解決過擬合問題。同時(shí)調(diào)整個(gè)體樹的屬性選擇可以提高準(zhǔn)確率，通常的選擇方法是log2d+1個(gè)屬性。

posted on 2014-08-27 10:12 changedi 閱讀(5024) 評(píng)論(2)  編輯  收藏 所屬分類: 機(jī)器學(xué)習(xí)