【51CTO.com快譯】眾所周知，決策樹在現(xiàn)實(shí)生活中有著許多實(shí)用的場(chǎng)景，它深刻地影響著包括分類和回歸在內(nèi)的、非常廣泛的機(jī)器學(xué)習(xí)領(lǐng)域。可以說，在各種決策分析中，決策樹能夠起到直觀且明確的決策輔助性作用。

什么是決策樹?

決策樹是一系列相關(guān)選擇所產(chǎn)生的可能性結(jié)果的“展示圖”。它允許個(gè)人或組織根據(jù)其成本、概率和效益，來對(duì)各種可能采取的行動(dòng)進(jìn)行權(quán)衡。

顧名思義，決策樹使用的是樹狀的決策模型。它既可以被用于推進(jìn)各種非正式的討論，又可以被用來通過“繪制”算法，以預(yù)測(cè)那些在數(shù)學(xué)上的***選擇。

決策樹通常是從單個(gè)節(jié)點(diǎn)開始的。該節(jié)點(diǎn)可以分支出各種可能性的結(jié)果。同時(shí)，這些結(jié)果都會(huì)導(dǎo)致新的節(jié)點(diǎn)產(chǎn)生，而這些節(jié)點(diǎn)則會(huì)繼續(xù)分枝出另一些其他類型的可能性。因此，這些最終形成一個(gè)樹狀的結(jié)構(gòu)。

在決策樹中一般有三種不同類型的節(jié)點(diǎn)：機(jī)會(huì)節(jié)點(diǎn)、決策節(jié)點(diǎn)和末端節(jié)點(diǎn)(end node)。我們用圓形來表示的機(jī)會(huì)節(jié)點(diǎn)，代表某些結(jié)果的概率;用正方形來表示的決策節(jié)點(diǎn)，代表要做出的各種決策；結(jié)束節(jié)點(diǎn)表示某個(gè)決策路徑的最終結(jié)果。

決策樹的優(yōu)缺點(diǎn)

優(yōu)勢(shì)

• 決策樹能夠生成各種可理解的規(guī)則。
• 無需大量計(jì)算，決策樹即可執(zhí)行分類。
• 決策樹能夠處理連續(xù)變量和分類變量。
• 決策樹能夠清楚地表明哪些字段對(duì)于預(yù)測(cè)或分類是最為重要的。

缺點(diǎn)

• 決策樹不太適合于那些目標(biāo)為預(yù)測(cè)連續(xù)屬性值的估算類任務(wù)。
• 在面對(duì)有著多個(gè)類、和相對(duì)較少的訓(xùn)練樣本的分類問題時(shí)，決策樹容易出現(xiàn)錯(cuò)誤。
• 在訓(xùn)練的過程中，決策樹在計(jì)算成本上的開銷比較高。在每個(gè)節(jié)點(diǎn)上，我們必須先對(duì)每個(gè)候選字段進(jìn)行排序，然后才能找到其***的拆分方式。某些算法會(huì)使用字段的組合，以對(duì)***組合的權(quán)重進(jìn)行搜索。另外，由于必須形成和比較各種候選子樹，因此修剪算法(Pruning algorithms，https://www.edureka.co/blog/implementation-of-decision-tree/)的開銷會(huì)更大。

創(chuàng)建決策樹

讓我們考慮一個(gè)場(chǎng)景，有一組天文學(xué)家發(fā)現(xiàn)了一顆新的行星，他們感興趣的問題是：它是否可能是下一個(gè)地球呢?

顯然，在做出明智的判斷之前，我們值得深入研究的決定性因素有許多，包括：該星球上是否存在著水、溫度是多少、地表是否容易持續(xù)遭受暴風(fēng)雨的影響、動(dòng)植物是否在此類特定的氣候中能生存活下來等方面。

下面，讓我們通過創(chuàng)建一個(gè)決策樹，來判定它是否人類下一個(gè)“棲息地”。

首先，我們?cè)O(shè)定宜居的溫度在0到100攝氏度之間。

其次，是否存在著水?

然后，動(dòng)植物是否繁茂?

組后，該星球的表面是否有風(fēng)暴?

至此，我們就得到了一個(gè)完整的決策樹。

分類規(guī)則

分類規(guī)則是：在考慮了所有的可能性之后，為每種方案分配一個(gè)類變量(class variable)的狀況。

類變量

我們?yōu)槊恳粋€(gè)葉節(jié)點(diǎn)都分配一個(gè)類變量。類變量將直接影響我們判斷的最終輸出。

下面讓我們從上面創(chuàng)建的決策樹中，推導(dǎo)出如下的分類規(guī)則：

1. 如果溫度不在273至373K(開爾文，熱力學(xué)單位)之間,則視為：生存困難。

2. 如果溫度在273至373K之間，且不存在水,則視為：生存困難。

3. 如果溫度在273至373K之間，存在水，但沒有動(dòng)植物，則視為：生存困難。

4. 如果溫度在273至373K之間，存在水，存在動(dòng)植物，且無地表暴風(fēng)雨，則視為：生存可能。

5. 如果溫度在273至373K之間，存在水，存在動(dòng)植物，但存在地表暴風(fēng)雨，則視為：生存困難。

決策樹

本例的決策樹由如下部分組成:

• 根節(jié)點(diǎn)：在上例中，“溫度”因素被視為根。
• 內(nèi)部節(jié)點(diǎn)：具有一個(gè)傳入邊(incoming edge)和兩到多個(gè)傳出邊(outgoing edge)的節(jié)點(diǎn)。
• 葉子節(jié)點(diǎn)：不再具有傳出邊的末端節(jié)點(diǎn)。

根據(jù)上述三個(gè)部分，我們從根節(jié)點(diǎn)開始，逐個(gè)檢查測(cè)試條件(test condition)，并將判斷結(jié)果(或稱控制)分配給其中一個(gè)傳出邊，以便將其作為另一個(gè)節(jié)點(diǎn)的傳入邊，進(jìn)行下一輪條件測(cè)試。當(dāng)所有測(cè)試條件都遍歷完畢并到達(dá)葉子節(jié)點(diǎn)時(shí)，該決策樹完畢。而葉子節(jié)點(diǎn)則包含了是否認(rèn)可該決策(判斷)的各種類標(biāo)簽(class labels)。

您一定有些疑惑：為什么我們會(huì)將“溫度”屬性作為根，來構(gòu)造決策樹呢?如果選擇其他屬性，將有什么不同呢?的確，不同的屬性特征會(huì)創(chuàng)建出許多不同的樹。我們需要通過遵循某種算法來選擇***的決策樹。下面我們來討論一種被稱為“貪婪法則(Greedy Approach)”的決策樹創(chuàng)建算法。

貪婪法則

根據(jù)維基百科，貪婪法則是基于啟發(fā)式問題解決(Heuristic Problem Solving)的概念，在每個(gè)節(jié)點(diǎn)上做出***的局部選擇。然后通過這些局部的***選擇，在全局范圍內(nèi)找到了近似的***解。

該算法包括:

1. 在每個(gè)階段(節(jié)點(diǎn))，選擇出***特征作為測(cè)試條件。

2. 接著將節(jié)點(diǎn)拆分為各種可能性的輸出(內(nèi)部節(jié)點(diǎn))。

3. 重復(fù)上述步驟，直到所有測(cè)試條件都在葉子節(jié)點(diǎn)中被遍歷到。

我們回到剛才的問題：如何選擇初始的測(cè)試條件呢?這里會(huì)涉及到兩個(gè)概念：熵(Entropy)和信息增益(Information Gain)。

熵：在決策樹中，熵表示同質(zhì)性。如果數(shù)據(jù)是完全均勻的，則熵為0;否則，如果數(shù)據(jù)被分割了(如50比50%)，那么熵為1。

信息增益：信息增益表示節(jié)點(diǎn)被拆分時(shí)，其熵值的增與減。

我們的目的是，讓被選取進(jìn)行拆分的屬性特征具有***的信息增益。因此，根據(jù)熵和信息增益的計(jì)算值，我們需要在任何特定步驟中，選取***的屬性。

我們來看下圖的一組數(shù)據(jù)：

我們可以根據(jù)上圖中各種維度的屬性特征集合，得出一系列不同種類的決策樹。下面 是兩種創(chuàng)建試驗(yàn)：

樹的創(chuàng)建試驗(yàn) 1:

在此，我們使用“學(xué)生”，這一屬性特征作為初始化的測(cè)試條件，其決策樹如下圖所示。

樹的創(chuàng)建試驗(yàn) 2:

同樣，我們可以選擇“收入”作為測(cè)試條件，如下圖所示：

用貪婪法則創(chuàng)建***的決策樹

在此，我們涉及到兩個(gè)類：“Yes”表示此人會(huì)購買電腦;“No”表示不購買。為了計(jì)算熵和信息增益，我們來看看這兩個(gè)類分別的概率值。

»Positive：“buys_computer=yes”的概率為：

»Negative：“buys_computer=no”的概率為：

D的熵：我們將概率值放入上面的公式，以求出熵。

在準(zhǔn)備階段，我們預(yù)先對(duì)熵的值進(jìn)行了分類，它們分別為：

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

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

由于我們算出的熵值是0.940，可見是不純的。

下面讓我們通過深入研究，來找出合適的屬性特征，以計(jì)算信息增益。

如果我們?cè)?ldquo;年齡”上進(jìn)行拆分，那么就能夠按照年齡的不同階段，來區(qū)分是否購買電腦產(chǎn)品。

例如，對(duì)于年齡在30歲及以下的人來說，有2人購買(Yes)，3人不購買(No)電腦。那么我們針對(duì)三個(gè)年齡階段(將年齡屬性特征值進(jìn)行拆分)的人，計(jì)算出針對(duì)***一列(是否購買電腦)的Info(D)。

可見，信息增益便是總的Info(0.940)與以年齡為屬性計(jì)算的Info(0.694)的差。

因此，這就是我們?nèi)绻褂?ldquo;年齡”為屬性進(jìn)行拆分的因子。同理，我們也可以計(jì)算出其余屬性特征維度的“信息增益”，如：

信息增益 (年齡) = 0.246

信息增益 (收入) = 0.029

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

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

通過對(duì)上述值的綜合比較，我們不難發(fā)現(xiàn)：“年齡”的“信息增益”***，因此，拆分“年齡”是一個(gè)比較好的決策。

可見，我們應(yīng)該創(chuàng)建的***決策樹應(yīng)該如下圖所示：

由上圖可見，我們應(yīng)該按照如下邏輯“繪制”出該決策樹的分類規(guī)則：

如果某人的年齡小于30歲，而且他不是學(xué)生，那么他就不會(huì)買產(chǎn)品。

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

如果某人的年齡小于30歲，并且他是學(xué)生，那么他就會(huì)購買該產(chǎn)品。

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

如果某人的年齡在31歲至40歲之間，那么他最有可能購買產(chǎn)品。

Age (31…40) = YES

如果某人的年齡超過了40歲，且信用評(píng)級(jí)非常好，那么他就不會(huì)買產(chǎn)品。

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

如果某人的年齡超過了40歲，且信用評(píng)級(jí)尚可，那么他很可能會(huì)購買產(chǎn)品。

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

這便是我們根據(jù)上例所實(shí)現(xiàn)的***決策樹。

原文標(biāo)題：How to Create a Perfect Decision Tree，作者：Upasana Priyadarshiny

【51CTO譯稿，合作站點(diǎn)轉(zhuǎn)載請(qǐng)注明原文譯者和出處為51CTO.com】