用實(shí)例說(shuō)明決策樹算法

2019.01.24

決策樹是最重要的機(jī)器學(xué)習(xí)算法之一。它用于機(jī)器學(xué)習(xí)分類和機(jī)器學(xué)習(xí)回歸問(wèn)題。在本文中，我們將討論相對(duì)于機(jī)器學(xué)習(xí)中的分類部分。

什么是決策樹？

機(jī)器學(xué)習(xí)種的決策樹是一種具有樹狀結(jié)構(gòu)的分類和預(yù)測(cè)工具，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示對(duì)一個(gè)屬性的測(cè)試，每個(gè)分支表示測(cè)試的結(jié)果，每個(gè)葉節(jié)點(diǎn)(終端節(jié)點(diǎn))持有一個(gè)類標(biāo)簽。

上面我們有一個(gè)小決策樹。決策樹的一個(gè)重要優(yōu)點(diǎn)是它具有很強(qiáng)的可解釋性。這里如果身高> 180厘米（或身高<180厘米并且體重> 80公斤）的人是男性。其他女性。你有沒(méi)有想過(guò)我們是怎么得出這個(gè)決策樹的。我將嘗試使用天氣數(shù)據(jù)集來(lái)解釋它。

在進(jìn)一步討論之前，我將解釋一些與決策樹相關(guān)的重要術(shù)語(yǔ)。

熵

在機(jī)器學(xué)習(xí)中，熵是對(duì)正在處理的信息中的隨機(jī)性的度量。熵越高，從該信息中得出任何結(jié)論就越困難。

信息增益

信息增益可以定義為從觀察另一個(gè)隨機(jī)變量獲得的隨機(jī)變量或信號(hào)的信息量?？梢哉J(rèn)為是父節(jié)點(diǎn)的熵與子節(jié)點(diǎn)的加權(quán)平均熵之間的差異。

基尼雜質(zhì)

Gini雜質(zhì)是一種度量，如果根據(jù)子集中標(biāo)簽的分布對(duì)隨機(jī)選擇的元素進(jìn)行隨機(jī)標(biāo)記，那么該元素被錯(cuò)誤標(biāo)記的頻率。

基尼雜質(zhì)的下限為0，如果數(shù)據(jù)集僅包含一個(gè)類，則出現(xiàn)0。

有很多算法可以構(gòu)建決策樹。

CART（分類和回歸樹） - 這使用基尼雜質(zhì)作為度量。
ID3（Iterative Dichotomiser 3） - 它使用熵和信息增益作為度量。

在本文中，我將介紹ID3。

使用ID3算法進(jìn)行分類

考慮一下我們將決定是否踢足球的天氣數(shù)據(jù)集。

這里有自變量來(lái)確定因變量。自變量是Outlook，Temperature,Humidity 和Wind。自變量是play football（yes/no）。

作為第一步，我們必須為決策樹找到父節(jié)點(diǎn)。為此，請(qǐng)按照以下步驟操作：

找到類變量的熵。

E(S) = -[(9/14)log(9/14) + (5/14)log(5/14)] = 0.94

注意:這里的log以2為底。這里總共有14個(gè)yes/ni。其中9個(gè)yes，5個(gè)no。在此基礎(chǔ)上，我們計(jì)算了上述概率。

從上面的數(shù)據(jù)我們可以很容易地得到下表

現(xiàn)在我們必須計(jì)算平均加權(quán)熵。也就是說(shuō)，我們發(fā)現(xiàn)每個(gè)特征的權(quán)重總和乘以概率。

E(S, outlook) = (5/14)*E(3,2) + (4/14)*E(4,0) + (5/14)*E(2,3) = (5/14)(-(3/5)log(3/5)-(2/5)log(2/5))+ (4/14)(0) + (5/14)((2/5)log(2/5)-(3/5)log(3/5)) = 0.693

下一步是尋找信息增益。它是我們?cè)谏厦姘l(fā)現(xiàn)的父熵和平均加權(quán)熵之間的差。

IG(S, outlook) = 0.94 - 0.693 = 0.247

同樣地找到Temperature，Humidity和Windy的信息增益。

IG(S, Temperature) = 0.940 - 0.911 = 0.029
IG(S, Humidity) = 0.940 - 0.788 = 0.152
IG(S, Windy) = 0.940 - 0.8932 = 0.048

現(xiàn)在選擇具有最大熵增益的特征。這是Outlook.So，它形成決策樹的第一個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)）。

現(xiàn)在我們的數(shù)據(jù)如下所示

由于overcast 僅包含“yes”類的示例，我們可以將其設(shè)置為yes?，F(xiàn)在我們的決策樹看起來(lái)如下。

下一步是在我們的決策樹中找到下一個(gè)節(jié)點(diǎn)?，F(xiàn)在我們將在sunny下找到一個(gè)。我們必須確定以下哪個(gè)Temperature ,Humidity 或Wind有更高的信息增益。

計(jì)算父熵E（sunny）

E(sunny) = (-(3/5)log(3/5)-(2/5)log(2/5)) = 0.971.

現(xiàn)在計(jì)算溫度的信息增益。 IG(sunny, Temperature)

E(sunny, Temperature) = (2/5)*E(0,2) + (2/5)*E(1,1) + (1/5)*E(1,0)=2/5=0.4

現(xiàn)在計(jì)算信息增益。

IG(sunny, Temperature) = 0.971–0.4 =0.571

同樣我們得到

IG(sunny, Humidity) = 0.971
IG(sunny, Windy) = 0.020

這里IG(sunny, Humidity)是最大的值。所以Humidity 是sunny下的節(jié)點(diǎn)。

對(duì)于上表中的Humidity ，我們可以說(shuō)，如果humidity是normal時(shí), play將發(fā)生，如果high則不會(huì)play。同樣地，找到rainy下面的節(jié)點(diǎn)。

注意：熵大于0的分支需要進(jìn)一步拆分。

最后，我們的決策樹將如下所示：

使用CART算法進(jìn)行分類

使用CART的分類與它類似。但是我們使用基尼雜質(zhì)代替熵。

因此，作為第一步，我們將找到?jīng)Q策樹的根節(jié)點(diǎn)。為此計(jì)算類變量的gini索引

Gini(S) = 1 - [(9/14)2 + (5/14)2] = 0.4591

下一步我們將計(jì)算基尼增益。首先，我們將找到Outlook，Temperature, Humidity 和Windy的平均加權(quán)基尼雜質(zhì)。

首先考慮Outlook的情況

Gini(S, outlook) = (5/14)gini(3,2) + (4/14)*gini(4,0)+ (5/14)*gini(2,3) = (5/14)(1 - (3/5)2 - (2/5)2) + (4/14)*0 + (5/14)(1 - (2/5)2 - (3/5)2)= 0.171+0+0.171 = 0.342
gain (S, outlook) = 0.459 - 0.342 = 0.117
gain(S, Temperature) = 0.459 - 0.4405 = 0.0185
gain(S, Humidity) = 0.459 - 0.3674 = 0.0916
gain(S, windy) = 0.459 - 0.4286 = 0.0304

選擇一種具有較高gini增益的。由于outlook的Gini增益更高，所以我們可以選擇它作為根節(jié)點(diǎn)。

現(xiàn)在您已經(jīng)知道如何進(jìn)一步進(jìn)行。重復(fù)我們?cè)贗D3算法中使用的相同步驟。