什么是決策樹

決策樹是預測模型。先舉一個簡單的決策樹的例子。

在這個例子中，我們考慮是否出去吃飯，需要經過以下考慮。

如果天氣下雨，就考慮打車是否方便。如果打車方便，就要看是否和別人有約。如果有約，就出去吃，如果無約，就不出去吃。

如果天氣刮風，就看目的地遠近。如果距離遠，就不出去吃。如果距離近，就出去吃。

如果天氣多云，就看目的地遠近。如果距離遠，就不出去吃。如果距離近，就出去吃。

這個過程就是決策樹。

天氣、打車是否方便、距離遠近、是否有約等要素稱為特征（features）。

出去吃和不出去吃，就是特質值下的分類（target）。

決策樹的判斷標準

在決策樹中，可能有多個特征，但是一些特征是無關重要的，一些則是對分類（target）起到決定作用的。

比如，在上例中，下雨、刮風和多云影響我們是否出去吃飯，但還有其他不影響我們是否出去吃的因素。

那我們選擇哪個因素作為分類標準呢？我們有兩種方法，一種叫做信息熵（音同“商”），一種叫做基尼不純度。

信息熵模型

信息熵（entropy）是指信息包括的信息量，也就是信息量的大小。

信息量和什么相關呢？分別是該信息對別人有沒有用，和信息表達的事情會不會發生。

試想，如果我們和別人說了一件根本不會發生的事，那是不是一句廢話，也就是說，信息量為0。

比如，我們告訴別人，你老板年終獎會給你發100萬，這件事雖然是聽者關心的，但是如果不會發生，那信息量也為0。

但如果我們和別人說了一件未來一定會發生的事情，那如果這件事對別人來說一點用也沒有，信息量也為0。

比如，我們告訴別人，你明年一定會長一歲。這件事雖然一定會發生，但是對聽者沒有意義，因此信息量為0。

因此，我們定義信息熵，用h（x）——信息有沒有用和p（x）——信息可能發生的概率表示。

信息熵

我們再來看h（x）和p（x）有什么關系。也就是一件事的信息量和發生概率的關系。

通常來說，一件事情發生概率越低，那么信息量越大。

比如，如果有人告訴你明天彩票的中獎號碼，那這件事十分重要，但發生的概率也非常低。

如果一件事是必然發生的，那這件事的信息量也十分有限。比如有人告訴你第二天太陽會升起，這件事其實沒什么用。

因此，我們可以得到以下結論：

1.h（x）和p（x）是負相關的；

2.p（x）=1，h（x）=0；

3.p（x）=0， h（x）是無限大的。

此外，

如果一件事x1發生的概率是p（x1），第二件事x2發生概率是p（x2）……第n件事xn發生概率事p（xn），

那么x1，x2……xn共同發生的概率是p（x1）p（x2）……P（xn）

如果一件事x1的重要性是h（x1），第二件事x2的重要性是h（x2）……第n件事xn的重要性是h（xn），

那么x1，x2……xn的重要性是h（x1）+h（x2）……h（xn）

綜上所述，h（x）和p（x）滿足log（x）的函數形式，考慮到p（x）=0時，h（x）無限大，因此還需要加一個負號。因此我們設定h（X）=-log（p（x））

一般情況下，我們假定log的底數為2。就有

h（x）=-log2（p（x））

為什么要選擇以2為底呢？

假設一個事件的信息量是n個相互獨立隨機變量發生的結果，其中每一個選擇都在“是”或“否“之間做出，則所有可能結果數為N=2^n，n= log2（N）

返回最開始的信息熵。

將h（x）和p（x）的關系代入，我們就有：

決策樹的算法

有了上面信息熵，我們就能根據信息熵選擇特征，也就是選擇哪些因素作為決策樹的分類的判斷標準。

選擇方法有兩種，一種是根據信息增益，一種是根據信息增益率。

ID3算法

信息增益的概念很簡單，整體的信息熵減掉以按某一特征分裂后的條件熵。

也就是說，我們按照某一個特征進行分類，來觀察信息熵的變化。若信息熵的變化足夠大，那這個特征就會被選中。信息熵的變化稱為信息增益。

信息增益

這種根據信息增益選定特征的算法叫做ID3。

ID4.5算法

但是根據信息增益來判斷特征會有一個缺點。信息增益會受到特征數量的影響。特征數量越多，信息熵越大，那剔除某些特征后的信息增益越大。當特征的取值較多時，根據此特征劃分之后的熵更低，由于劃分前的熵是一定的，因此信息增益更大，因此信息增益比較 偏向取值較多的特征。極端一點，有多少個樣本，這個特征就有多少個類別，那么就會導致決策樹非常淺。

那如何處理這個問題呢？我們選擇增加一個懲罰項。

這個懲罰項就是H（D）。

信息增益率：

Gainratio（D，A） = Gain（D，A）/H（D）

這種根據信息增益率選定特征的算法叫做ID4.5。

CART算法

不管是ID3還是ID4.5，他們都有一個問題，就是不能處理回歸問題。

因此，產生了新的算法，CART算法。

CART是采用基尼系數（基尼不純度），選取最優劃分特征。

責任編輯人：CC