決策樹(shù)的判斷標(biāo)準(zhǔn)及算法

什么是決策樹(shù)

決策樹(shù)是預(yù)測(cè)模型。先舉一個(gè)簡(jiǎn)單的決策樹(shù)的例子。

在這個(gè)例子中，我們考慮是否出去吃飯，需要經(jīng)過(guò)以下考慮。

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

如果天氣刮風(fēng)，就看目的地遠(yuǎn)近。如果距離遠(yuǎn)，就不出去吃。如果距離近，就出去吃。

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

這個(gè)過(guò)程就是決策樹(shù)。

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

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

決策樹(shù)的判斷標(biāo)準(zhǔn)

在決策樹(shù)中，可能有多個(gè)特征，但是一些特征是無(wú)關(guān)重要的，一些則是對(duì)分類（target）起到?jīng)Q定作用的。

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

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

信息熵模型

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

信息量和什么相關(guān)呢？分別是該信息對(duì)別人有沒(méi)有用，和信息表達(dá)的事情會(huì)不會(huì)發(fā)生。

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

比如，我們告訴別人，你老板年終獎(jiǎng)會(huì)給你發(fā)100萬(wàn)，這件事雖然是聽(tīng)者關(guān)心的，但是如果不會(huì)發(fā)生，那信息量也為0。

但如果我們和別人說(shuō)了一件未來(lái)一定會(huì)發(fā)生的事情，那如果這件事對(duì)別人來(lái)說(shuō)一點(diǎn)用也沒(méi)有，信息量也為0。

比如，我們告訴別人，你明年一定會(huì)長(zhǎng)一歲。這件事雖然一定會(huì)發(fā)生，但是對(duì)聽(tīng)者沒(méi)有意義，因此信息量為0。

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

信息熵

我們?cè)賮?lái)看h（x）和p（x）有什么關(guān)系。也就是一件事的信息量和發(fā)生概率的關(guān)系。

通常來(lái)說(shuō)，一件事情發(fā)生概率越低，那么信息量越大。

比如，如果有人告訴你明天彩票的中獎(jiǎng)號(hào)碼，那這件事十分重要，但發(fā)生的概率也非常低。

如果一件事是必然發(fā)生的，那這件事的信息量也十分有限。比如有人告訴你第二天太陽(yáng)會(huì)升起，這件事其實(shí)沒(méi)什么用。

因此，我們可以得到以下結(jié)論：

1.h（x）和p（x）是負(fù)相關(guān)的；

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

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

此外，

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

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

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

那么x1，x2……xn的重要性是h（x1）+h（x2）……h(huán)（xn）

綜上所述，h（x）和p（x）滿足log（x）的函數(shù)形式，考慮到p（x）=0時(shí)，h（x）無(wú)限大，因此還需要加一個(gè)負(fù)號(hào)。因此我們?cè)O(shè)定h（X）=-log（p（x））

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

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

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

假設(shè)一個(gè)事件的信息量是n個(gè)相互獨(dú)立隨機(jī)變量發(fā)生的結(jié)果，其中每一個(gè)選擇都在“是”或“否“之間做出，則所有可能結(jié)果數(shù)為N=2^n，n= log2（N）

返回最開(kāi)始的信息熵。

將h（x）和p（x）的關(guān)系代入，我們就有：

決策樹(shù)的算法

有了上面信息熵，我們就能根據(jù)信息熵選擇特征，也就是選擇哪些因素作為決策樹(shù)的分類的判斷標(biāo)準(zhǔn)。

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

ID3算法

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

也就是說(shuō)，我們按照某一個(gè)特征進(jìn)行分類，來(lái)觀察信息熵的變化。若信息熵的變化足夠大，那這個(gè)特征就會(huì)被選中。信息熵的變化稱為信息增益。

信息增益

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

ID4.5算法

但是根據(jù)信息增益來(lái)判斷特征會(huì)有一個(gè)缺點(diǎn)。信息增益會(huì)受到特征數(shù)量的影響。特征數(shù)量越多，信息熵越大，那剔除某些特征后的信息增益越大。當(dāng)特征的取值較多時(shí)，根據(jù)此特征劃分之后的熵更低，由于劃分前的熵是一定的，因此信息增益更大，因此信息增益比較 偏向取值較多的特征。極端一點(diǎn)，有多少個(gè)樣本，這個(gè)特征就有多少個(gè)類別，那么就會(huì)導(dǎo)致決策樹(shù)非常淺。

那如何處理這個(gè)問(wèn)題呢？我們選擇增加一個(gè)懲罰項(xiàng)。

這個(gè)懲罰項(xiàng)就是H（D）。

信息增益率：

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

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

CART算法

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

因此，產(chǎn)生了新的算法，CART算法。

CART是采用基尼系數(shù)（基尼不純度），選取最優(yōu)劃分特征。

責(zé)任編輯人：CC