數(shù)據(jù)分析教程決策樹(shù)原理

決策樹(shù)原理

決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類(lèi)的過(guò)程。它提供一種在什么條件下會(huì)得到什么值的類(lèi)似規(guī)則的方法。決策樹(shù)分為分類(lèi)樹(shù)和回歸樹(shù)兩種，分類(lèi)樹(shù)對(duì)離散變量做決策樹(shù)，回歸樹(shù)對(duì)連續(xù)變量做決策樹(shù)。也就是說(shuō)，決策樹(shù)既可以用來(lái)解決分類(lèi)問(wèn)題，也可以解決回歸問(wèn)題。

 

 

決策樹(shù)其實(shí)是一棵倒樹(shù)，它的根在最上面，葉子在下面。

決策樹(shù)由節(jié)點(diǎn)(node)和有向邊(directed edge)組成。節(jié)點(diǎn)有兩種類(lèi)型：內(nèi)部節(jié)點(diǎn)(internal node)和葉節(jié)點(diǎn)(leaf node)。內(nèi)部節(jié)點(diǎn)表示一個(gè)特征或?qū)傩?，葉節(jié)點(diǎn)表示一個(gè)類(lèi)。

下面我們通過(guò)一個(gè)小例子來(lái)看下，這棵樹(shù)到底怎么用

 

 

決定我們是否打籃球的因素有三個(gè)，是否下雨，溫度是否適合，是否是室內(nèi)。我們一步一步，通過(guò)判斷不同的條件，最后得出不同的結(jié)論。

我們首先選取了決定是否打籃球的條件，并且以是否下雨為根節(jié)點(diǎn)開(kāi)始分裂，然后根據(jù)不同情況構(gòu)造了一棵樹(shù)，最后根據(jù)該樹(shù)的分枝，來(lái)決定是否打籃球。

概括來(lái)說(shuō)，就是根據(jù)特征的值做判斷，最后得出不同的分類(lèi)。

決策樹(shù)學(xué)習(xí)過(guò)程

那么決策樹(shù)要如何構(gòu)建呢？通常，這一過(guò)程可以概括為3個(gè)步驟：特征選擇、決策樹(shù)生成和修剪。

特征選擇：特征選擇是指從訓(xùn)練數(shù)據(jù)中眾多的特征中選擇一個(gè)特征作為當(dāng)前節(jié)點(diǎn)的分裂標(biāo)準(zhǔn)，如何選擇特征有著很多不同量化評(píng)估標(biāo)準(zhǔn)標(biāo)準(zhǔn)，從而衍生出不同的決策樹(shù)算法。

決策樹(shù)生成：根據(jù)選擇的特征評(píng)估標(biāo)準(zhǔn)，從上至下遞歸地生成子節(jié)點(diǎn)，直到數(shù)據(jù)集不可分則停止決策樹(shù)生長(zhǎng)。

剪枝：決策樹(shù)容易過(guò)擬合，一般來(lái)需要剪枝，縮小樹(shù)結(jié)構(gòu)規(guī)模、緩解過(guò)擬合。剪枝技術(shù)有預(yù)剪枝和后剪枝兩種。

特征選擇

特征選擇是為了選擇出對(duì)于訓(xùn)練數(shù)據(jù)具有分類(lèi)能力的特征。比如說(shuō)，使用某一個(gè)特征進(jìn)行決策樹(shù)分類(lèi)的結(jié)果與隨機(jī)分類(lèi)的結(jié)果沒(méi)有任何區(qū)別，那么該特征就不具備分類(lèi)能力，可以直接丟棄掉該特征。當(dāng)然我們要選擇能夠分類(lèi)出更好的類(lèi)別的特征，作為根節(jié)點(diǎn)。

那么一般情況下該如何選擇特征呢，業(yè)界通常會(huì)使用信息增益的方式來(lái)選擇。

先來(lái)看幾個(gè)概念：

信息熵

條件熵

信息增益

信息熵

信息熵是信息的期望值，是用來(lái)衡量信息不確定性的指標(biāo)。信息的不確定性越大，熵越大。

比如說(shuō)對(duì)于拋硬幣事件，每次拋硬幣的結(jié)果就是一個(gè)不確定的信息。

如果根據(jù)我們的經(jīng)驗(yàn)，一個(gè)均勻的硬幣正面和反面出現(xiàn)的概率是相等的，都是50%。所以我們很難判斷下一次是出現(xiàn)正面還是反面，所以這個(gè)事件的信息熵值很高。

但是如果該硬幣不是均勻的，并且根據(jù)歷史數(shù)據(jù)顯示，100次試驗(yàn)中，出現(xiàn)正面的次數(shù)有98次，那么下一次拋硬幣，我們就很容易判斷結(jié)果了，故而該事件的信息熵很低。

其計(jì)算公式為：

 

 

其中：

P(X=i)為隨機(jī)變量 X 取值為 i 的概率

n 代表事件的 n 種情況

我們還是以上面拋硬幣的例子來(lái)求解下兩種情況下的信息熵各為多少

注意，由于編輯器的原因，以下所有 log(2) 均表示以2為底的對(duì)數(shù)

均勻硬幣

硬幣	P
正面	0.5
反面	0.5

信息熵 = -0.5 * log(2)0.5 - 0.5 * log(2)0.5 = 1

非均勻硬幣

硬幣	P
正面	0.98
反面	0.02

信息熵 = -0.98 * log(2)0.98 - 0.02 * log(2)0.02 = 0.14

思考：如果正面的概率是100%，那么此時(shí)的信息熵是多少呢

答：此時(shí)信息熵是0，也可以說(shuō)明，信息熵是0到1之間的數(shù)值。

條件熵

條件熵是通過(guò)獲得更多的信息來(lái)減小不確定性。當(dāng)我們知道的信息越多時(shí)，信息的不確定性越小。

比如說(shuō)某個(gè)用戶曾經(jīng)購(gòu)買(mǎi)了一種商品，但是我們沒(méi)有辦法僅僅根據(jù)這個(gè)信息來(lái)判斷，該用戶是否會(huì)再次購(gòu)買(mǎi)該商品。但是如果我們?cè)黾右恍l件，比如雙十一促銷(xiāo)活動(dòng)信息之后，我們就能夠更加容易的發(fā)現(xiàn)用戶購(gòu)買(mǎi)商品與促銷(xiāo)活動(dòng)之間的聯(lián)系，并通過(guò)不同促銷(xiāo)力度時(shí)用戶購(gòu)買(mǎi)的概率來(lái)降低不確定性。

其計(jì)算公式為：

 

 

其中：

Y 為條件

P(Y = v)表示 Y 有多種情況，當(dāng) Y 處于 v 的概率

H(X|Y = v)表示 Y 處于 v 條件時(shí)的信息熵

信息增儀

信息增益的定義就是信息熵減去條件熵

 

 

這里只是數(shù)學(xué)上的定義，那么該如何使用信息增益來(lái)創(chuàng)建決策樹(shù)呢，還是舉例來(lái)看。

 

 

在上圖中，我先按照某種條件，把紅點(diǎn)和黃框分成了如圖所示的兩類(lèi)，接下來(lái)我們計(jì)算下熵值

父節(jié)點(diǎn)信息熵 = -(6/10log(2)6/10)-(4/10log(2)4/10) = 0.97

上面子節(jié)點(diǎn)信息熵 = -(2/6log(2)2/6)-(4/6log(2)4/6) = 0.91

下面子節(jié)點(diǎn)信息熵 = -(2/4log(2)2/4)-(2/4log(2)2/4) = 1

此處兩個(gè)子節(jié)點(diǎn)其實(shí)就是某種條件下的信息熵，因?yàn)樵诜诸?lèi)的時(shí)候，是隱含了某種分類(lèi)條件的。

下面根據(jù)條件熵的定義，可以得到條件熵

條件熵 = 上面子節(jié)點(diǎn)出現(xiàn)的概率 * 該條件下的信息熵 + 下面子節(jié)點(diǎn)出現(xiàn)的概率 * 該條件下的信息熵

= 6/10 * 0.91 + 4/10 * 1

= 0.946

再根據(jù)信息增益的定義，可以得到信息增益

信息增益 = 父節(jié)點(diǎn)信息熵 - 條件熵

= 0.97 - 0.946

= 0.024

再來(lái)看另一種分類(lèi)方式

 

 

父節(jié)點(diǎn)信息熵 = -(6/10log(2)6/10)-(4/10log(2)4/10) = 0.442

上面子節(jié)點(diǎn)信息熵 = -(6/6log(2)6/6)-(0/6log(2)0/6) = 0

下面子節(jié)點(diǎn)信息熵 = -(4/4log(2)4/4)-(0/4log(2)0/4) = 0

條件熵 = 0

信息增益 = 0.442

從圖中明顯可以看出，第二種分類(lèi)是好于第一種的，而此時(shí)第二種的信息增益是較大的，由此可以得到，在通過(guò)信息增益來(lái)確定節(jié)點(diǎn)時(shí)，需要使用信息增益最大的那個(gè)特征。   也就是說(shuō)，信息增益是相對(duì)于特征而言的，信息增益越大，特征對(duì)最終的分類(lèi)結(jié)果影響也就越大，我們就應(yīng)該選擇對(duì)最終分類(lèi)結(jié)果影響最大的那個(gè)特征作為我們的分類(lèi)特征。

決策樹(shù)生成

構(gòu)建決策樹(shù)的工作原理：

拿到原始數(shù)據(jù)集，然后基于最好的屬性值劃分?jǐn)?shù)據(jù)集，由于特征值可能多于兩個(gè)，因此此時(shí)可能存在大于兩個(gè)分支的數(shù)據(jù)集劃分。第一次劃分之后，數(shù)據(jù)集被向下傳遞到樹(shù)的分支的下一個(gè)結(jié)點(diǎn)。在這個(gè)結(jié)點(diǎn)上，我們可以再次劃分?jǐn)?shù)據(jù)。因此我們可以采用遞歸的原則處理數(shù)據(jù)集。

構(gòu)建決策樹(shù)的算法有很多，比如 C4.5、ID3 和 CART，這些算法在運(yùn)行時(shí)并不總是在每次劃分?jǐn)?shù)據(jù)分組時(shí)都會(huì)消耗特征。ID3 和 C4.5 算法可以生成二叉樹(shù)或多叉樹(shù)，而 CART 只支持二叉樹(shù)。

基于 ID3 算法

ID3 算法其實(shí)就是計(jì)算信息增益，在決策樹(shù)各個(gè)結(jié)點(diǎn)上對(duì)應(yīng)信息增益準(zhǔn)則（選取信息增益最大的）選擇特征，遞歸地構(gòu)建決策樹(shù)。

具體方法是：從根結(jié)點(diǎn)(root node)開(kāi)始，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征，由該特征的不同取值建立子節(jié)點(diǎn)；再對(duì)子結(jié)點(diǎn)遞歸地調(diào)用以上方法，構(gòu)建決策樹(shù)；直到所有特征的信息增益均很小或沒(méi)有特征可以選擇為止，最后得到一個(gè)決策樹(shù)。

我們使用如下的數(shù)據(jù)集來(lái)演示下該如何通過(guò) ID3 算法構(gòu)建決策樹(shù)，該數(shù)據(jù)集記錄的是某位客戶，在不同天氣下打高爾夫的情況。

weather	temp	wind	play golf
rainy	hot	false	no
rainy	hot	ture	no
overcast	hot	false	yes
sunny	mild	false	yes
sunny	cool	false	yes
sunny	cool	ture	no
overcast	cool	ture	yes
rainy	mild	false	no
rainy	cool	false	yes
sunny	mild	false	yes
rainy	mild	ture	yes
overcast	mild	ture	yes
overcast	hot	false	yes
sunny	mild	ture	no

計(jì)算根節(jié)點(diǎn)

我們首先來(lái)計(jì)算是否打高爾夫球的信息熵

是否打高爾夫	頻度	概率	信息熵
No	5	5/14 = 0.36	-0.531
Yes	9	9/14 = 0.64	-0.410

根據(jù)信息熵的計(jì)算公式可以得出，Play Golf 的信息熵為

H(play golf) = -[-0.531 + (-0.410) ] = 0.940

下面計(jì)算3種天氣狀況下的條件熵

以天氣狀況為節(jié)點(diǎn)

各種天氣狀況出現(xiàn)的概率

weather	Yes	No	天氣狀況各情況出現(xiàn)頻度	概率
rainy	2	3	5	5/14 = 0.36
overcast	4	0	4	4/14 = 0.29
sunny	3	2	5	5/14 = 0.36

各種天氣狀況下的條件熵

weather	Yes（打高爾夫的概率）	No（不打高爾夫的概率）	信息熵
rainy	2/5 = 0.4	3/5 = 0.6	0.971
overcast	4/4 = 1	0/4 = 0	0
sunny	3/5 = 0.6	2/5 = 0.4	0.971

以 weather 為節(jié)點(diǎn)的條件熵 0.36 * 0.971 + 0.29 * 0 + 0.36 * 0.971 = 0.69

此時(shí)的信息增益為 0.94 - 0.69 = 0.25

以溫度為節(jié)點(diǎn)

各種溫度出現(xiàn)的概率

temp	Yes	No	溫度個(gè)情況出現(xiàn)頻度	概率
hot	2	2	4	4/14 = 0.29
mild	4	2	6	6/14 = 0.43
cool	3	1	4