試想一下，如果一群宇航員發(fā)現(xiàn)了一個(gè)新星球，那么問(wèn)題就來(lái)了：這個(gè)星球能否成為下一個(gè)地球？

在現(xiàn)實(shí)生活中，決策樹(shù)有許多類(lèi)似的例子，也影響著機(jī)器學(xué)習(xí)的許多領(lǐng)域，比如說(shuō)分類(lèi)和回歸分析。在進(jìn)行決策分析時(shí)，決策樹(shù)可以明確直觀地表示決策和決策制定的過(guò)程。

什么是決策樹(shù)？

決策樹(shù)是一系列相關(guān)選擇的可能結(jié)果的映射。決策者可以基于不同選擇的成本、可能性和收益來(lái)進(jìn)行權(quán)衡。

決策樹(shù)，顧名思義，是樹(shù)狀的決策模型。它們既可以推動(dòng)非正式討論的進(jìn)程，也可以制定能夠預(yù)測(cè)數(shù)學(xué)上的最優(yōu)解算法。決策樹(shù)通常從一個(gè)節(jié)點(diǎn)開(kāi)始，引申出不同的結(jié)果。每個(gè)結(jié)果又引向另一個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)又會(huì)產(chǎn)生其他的結(jié)果。最后形成了一個(gè)樹(shù)狀圖形。

節(jié)點(diǎn)有三種類(lèi)型：機(jī)會(huì)節(jié)點(diǎn)、決策節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)。機(jī)會(huì)節(jié)點(diǎn)，用圓表示，顯示結(jié)果的概率；決策節(jié)點(diǎn)，用正方形表示，顯示做出的決策；結(jié)束節(jié)點(diǎn)則顯示決策的最終結(jié)果。

決策樹(shù)的利與弊

優(yōu)勢(shì)

· 決策樹(shù)生成的規(guī)則都是可理解的。

· 決策樹(shù)執(zhí)行分類(lèi)不需要太多的計(jì)算。

· 決策樹(shù)能夠處理連續(xù)變量和分類(lèi)變量。

· 決策樹(shù)可以清楚地指出在預(yù)測(cè)和分類(lèi)中哪些字段最重要。

劣勢(shì)

· 決策樹(shù)不適用于評(píng)估預(yù)測(cè)連續(xù)值域的價(jià)值。

· 決策樹(shù)在分類(lèi)類(lèi)別多而訓(xùn)練實(shí)例相對(duì)較少的情況下容易出現(xiàn)分類(lèi)錯(cuò)誤。

· 訓(xùn)練決策樹(shù)需要大量計(jì)算，創(chuàng)建決策樹(shù)也是如此。在每個(gè)節(jié)點(diǎn)上都必須對(duì)所有候選分割字段進(jìn)行排序，然后才能找到其最佳分割。在一些使用了字段組合的算法中，必須搜索才能得到最優(yōu)的組合權(quán)值。修剪算法也很復(fù)雜，因?yàn)樾枰稍S多候選子樹(shù)并且進(jìn)行比較。

創(chuàng)建決策樹(shù)

再回到一開(kāi)始宇航員發(fā)現(xiàn)新星球的例子，要做出正確的決定需要對(duì)大量的因素進(jìn)行全面的研究。比如說(shuō)，這個(gè)星球上有水嗎？溫度是多少？易發(fā)生連續(xù)性暴雨嗎？動(dòng)植物能否適應(yīng)那里的氣候？

現(xiàn)在創(chuàng)建一棵決策樹(shù)，看看是否可以發(fā)現(xiàn)一個(gè)新的棲息地。

人類(lèi)適宜居住的溫度在0到100攝氏度之間。

有水嗎？

動(dòng)植物能繁衍下去嗎？

這顆行星表面有暴風(fēng)雨嗎?

這樣就有了一顆完整的決策樹(shù)。

分類(lèi)規(guī)則

分類(lèi)規(guī)則是要考慮到所有的場(chǎng)景以及其中的類(lèi)變量。

類(lèi)變量

每個(gè)葉子節(jié)點(diǎn)都有一個(gè)類(lèi)變量。類(lèi)變量是引向決策的最終輸出。

從所創(chuàng)建的決策樹(shù)中推導(dǎo)出分類(lèi)規(guī)則：

1. 如果溫度不在273 ~ 373K之間，->難以存活

2. 如果溫度在273到373K之間，沒(méi)有水，->難以存活

3. 如果溫度在273到373K之間，有水，沒(méi)有動(dòng)植物，->難以存活

4. 如果溫度在273到373K之間，有水，有動(dòng)植物，表面沒(méi)有暴風(fēng)雨，->可能存活

5. 如果溫度在273到373K之間，有水，有動(dòng)植物，表面有暴風(fēng)雨，->難以存活

決策樹(shù)

決策樹(shù)由以下部分組成：

· 根節(jié)點(diǎn)：本例中“溫度”即為根。

· 內(nèi)部節(jié)點(diǎn)：有一個(gè)傳入邊，兩個(gè)或多個(gè)傳出邊的節(jié)點(diǎn)。

· 葉子節(jié)點(diǎn)：終端節(jié)點(diǎn)，沒(méi)有傳出邊。

在構(gòu)建決策樹(shù)時(shí)，從根節(jié)點(diǎn)開(kāi)始，檢查測(cè)試條件并將控件分配給一個(gè)輸出邊，這樣就測(cè)試好了條件也創(chuàng)建好了節(jié)點(diǎn)。當(dāng)所有測(cè)試條件都指向葉子節(jié)點(diǎn)時(shí)，決策樹(shù)就創(chuàng)建好了。葉子節(jié)點(diǎn)包含了評(píng)估決策是好是壞的類(lèi)標(biāo)簽。

你可能想知道為什么選擇從溫度屬性開(kāi)始?如果選擇其他任何屬性，所構(gòu)造出的決策樹(shù)將是不同的。

是的，對(duì)于一組特定的屬性，可以創(chuàng)建許多不同的樹(shù)，需要按照算法來(lái)選擇最優(yōu)。接下來(lái)，我們將學(xué)習(xí)使用“貪婪算法”來(lái)創(chuàng)建完美的決策樹(shù)。

貪婪算法

貪婪算法基于啟發(fā)式問(wèn)題求解的思想，在每個(gè)節(jié)點(diǎn)上進(jìn)行最優(yōu)局部選擇。通過(guò)這些局部最優(yōu)解，得到了全局的近似最優(yōu)解?！S基百科

這種算法可以總結(jié)為：

1. 在每個(gè)節(jié)點(diǎn)，選出測(cè)試條件的最優(yōu)項(xiàng)。

2. 將節(jié)點(diǎn)分出可能的結(jié)果(內(nèi)部節(jié)點(diǎn))。

3. 重復(fù)上述兩個(gè)步驟，直到所有的測(cè)試條件都選擇完成，最后歸到葉子節(jié)點(diǎn)處。

開(kāi)始操作這個(gè)算法時(shí)，就會(huì)產(chǎn)生第一個(gè)問(wèn)題：怎么確定第一個(gè)測(cè)試條件呢？

可以從熵增和信息增益的值來(lái)得到問(wèn)題的答案。首先看看它們是什么，然后了解它們是如何影響決策樹(shù)的創(chuàng)建的。

熵：決策樹(shù)中的熵表示同質(zhì)性。如果數(shù)據(jù)完全同質(zhì)，熵為0；如果數(shù)據(jù)被分為(50-50%)，熵為1。

信息增益：信息增益是節(jié)點(diǎn)發(fā)散時(shí)熵值的減小/增大。

用于切分的屬性應(yīng)該最高信息增益。根據(jù)熵和信息增益的計(jì)算值，在每個(gè)步驟中選擇最優(yōu)的屬性。

看下面的數(shù)據(jù)：

這些數(shù)據(jù)可以生成無(wú)數(shù)棵決策樹(shù)。

決策樹(shù)創(chuàng)建嘗試1：

將“學(xué)生”屬性作為第一個(gè)測(cè)試條件。

決策樹(shù)創(chuàng)建嘗試2：

為什么選擇“學(xué)生”屬性呢？也可以試試用“收入”開(kāi)頭。

用“貪婪算法”創(chuàng)建最優(yōu)決策樹(shù)

讓我們按照貪婪算法的步驟創(chuàng)建最優(yōu)決策樹(shù)。

這里涉及到兩個(gè)選擇:“Yes”表示此人購(gòu)買(mǎi)了一臺(tái)計(jì)算機(jī)，“No”表示他沒(méi)有購(gòu)買(mǎi)計(jì)算機(jī)。為了計(jì)算熵增和信息增益的值，需要先計(jì)算這兩個(gè)選擇的概率值。

?肯定：' 是否買(mǎi)了電腦=yes '可能性是：

?否定：'是否買(mǎi)了電腦=no'可能性是：

D中的熵：現(xiàn)在把概率值代入上面的公式來(lái)計(jì)算熵。

我們已經(jīng)對(duì)熵值進(jìn)行了分類(lèi)，分別為：

熵= 0：數(shù)據(jù)完全同質(zhì)(純)

熵= 1：數(shù)據(jù)被分成50%/ 50%(不純)

現(xiàn)在我們的熵值是0.940，幾乎是不純的。

繼續(xù)深入研究，找出合適的屬性然后計(jì)算信息增益。

如果細(xì)分“年齡”屬性，信息增益會(huì)是多少呢？

這個(gè)數(shù)據(jù)代表了不同年齡階段的人對(duì)產(chǎn)品的購(gòu)買(mǎi)情況。

例如，對(duì)于30歲以下的人，2人購(gòu)買(mǎi)(Yes)，3人不購(gòu)買(mǎi)（No）。在最后一列中表示的信息值(D)是對(duì)這3類(lèi)人進(jìn)行計(jì)算。

年齡屬性的信息值 (D)是這三個(gè)年齡值范圍的總和計(jì)算?，F(xiàn)在的問(wèn)題是，如果我們將“年齡”屬性繼續(xù)細(xì)分，那么“信息增益”是什么?

總信息值(0.940)與年齡屬性計(jì)算的信息值(0.694)之差則為“信息增益”。

這就是決定我們是否應(yīng)該在“年齡”或其他任何屬性上繼續(xù)細(xì)分的因素。同樣地，可以計(jì)算其余屬性的“信息增益”：

信息增益(年齡)= 0.246

信息收益(收益)= 0.029

信息增益(學(xué)生身份) = 0.151

信息增益(信用評(píng)估) = 0.048

比較所有屬性的增益值，我們發(fā)現(xiàn)“年齡”的“信息增益”最高。因此，需要將“年齡”屬性細(xì)分。

類(lèi)似地，每次在決定是否細(xì)分時(shí)，比較一下信息增益，以確定是否選擇該屬性進(jìn)行細(xì)分。

因此，最終創(chuàng)建的最優(yōu)樹(shù)如下：

該樹(shù)的分類(lèi)規(guī)則可記為：

如果年齡小于30歲，且不是學(xué)生，則不會(huì)購(gòu)買(mǎi)該產(chǎn)品。

Age (<30) ^ student(no) = NO

如果年齡小于30歲，且是一名學(xué)生，則會(huì)購(gòu)買(mǎi)該產(chǎn)品。

Age (<30) ^ student(yes) = YES

如果年齡在31歲到40歲之間，極有可能購(gòu)買(mǎi)該產(chǎn)品。

Age (31…40) = YES

如果年齡大于40歲，且信用評(píng)估良好，則不會(huì)購(gòu)買(mǎi)該產(chǎn)品。

Age (>40) ^ credit_rating(excellent) = NO

如果年齡大于40歲，且信用評(píng)估一般，則可能會(huì)購(gòu)買(mǎi)該產(chǎn)品。

Age (>40) ^ credit_rating(fair) = Yes

這樣，就創(chuàng)建了一棵完美的決策樹(shù)！