決策樹算法綜述

決策樹算法，顧名思義，是一種用于分類的樹型決策結(jié)構(gòu)。事實(shí)上，決策樹算法在行業(yè)中得到廣泛應(yīng)用，不僅因?yàn)樗哂辛己玫姆诸惸芰Γ匾氖撬哂泻軓?qiáng)的可解釋性，直觀易懂。事實(shí)上，基于決策樹的邏輯結(jié)構(gòu)與現(xiàn)實(shí)社會(huì)環(huán)境中人類的決策邏輯非常相似。例如，有一天，郝斌在思考人生中的三個(gè)主要問題:

這個(gè)思考過(guò)程可以簡(jiǎn)單的用下面的話來(lái)表達(dá):

(1)今天是周末嗎？如果不是周末，不要去，如果是周末，繼續(xù)思考下一個(gè)問題；

(2)這周的工作完成了嗎？如果還沒有完成，就不要走，如果已經(jīng)完成，繼續(xù)思考下一個(gè)問題；

(3)今天是晴天嗎？如果不是晴天，就不要去，如果是晴天，繼續(xù)思考下一個(gè)問題；

(4)你今天能在電影院找到一個(gè)好位置嗎？如果找不到好位置，就不要去了。如果能找到好位置，決定去電影院看電影；

如果思維過(guò)程是以決策樹的形式表達(dá)的，那么它的形式如下:

在這種看電影的決策邏輯中，其實(shí)是由郝斌通過(guò)自己的歷史多次看電影的經(jīng)歷總結(jié)出來(lái)的。這種形式的決策樹算法其實(shí)是一種訓(xùn)練數(shù)據(jù)集，通過(guò)一系列的試題(比如“今天是周末嗎？”)以輸出分類目標(biāo)進(jìn)行判斷。

決策樹的表達(dá)形式非常直觀，容易理解。一般來(lái)說(shuō)，決策樹由一個(gè)根節(jié)點(diǎn)、幾個(gè)內(nèi)部節(jié)點(diǎn)和幾個(gè)葉節(jié)點(diǎn)組成。根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)代表相應(yīng)的測(cè)試條件，而葉節(jié)點(diǎn)代表最終的輸出結(jié)果:

(1)根節(jié)點(diǎn):根節(jié)點(diǎn)位于頂層，代表第一個(gè)測(cè)試條件。決策樹只有一個(gè)根節(jié)點(diǎn)，根節(jié)點(diǎn)有零個(gè)或多個(gè)輸出邊。

(2)內(nèi)部節(jié)點(diǎn):位于根節(jié)點(diǎn)之下，代表一個(gè)測(cè)試條件。中間節(jié)點(diǎn)有一個(gè)輸入邊和兩個(gè)或多個(gè)輸出邊。

(3)葉節(jié)點(diǎn):決策樹的終端節(jié)點(diǎn)，代表決策樹的決策結(jié)果。葉節(jié)點(diǎn)只有一個(gè)傳入邊，但沒有傳出邊。

可以看出，這種樹狀表達(dá)式實(shí)際上可以和前面提到的If-Then規(guī)則相互轉(zhuǎn)換，其中從根節(jié)點(diǎn)到任意葉節(jié)點(diǎn)都會(huì)形成一個(gè)規(guī)則:If“是周末嗎？”=“假”，然后“別走?！?。值得注意的是，決策樹形成的規(guī)則應(yīng)該是互斥且完備的，即對(duì)于任何樣本數(shù)據(jù)，只有一個(gè)與之對(duì)應(yīng)的規(guī)則來(lái)輸出分類結(jié)果。

決策樹的生成

在實(shí)際應(yīng)用過(guò)程中，我們不僅僅針對(duì)一個(gè)樣本，而是要從大量的數(shù)據(jù)中找到規(guī)律。所以接下來(lái)的問題就是如何借助決策樹算法總結(jié)內(nèi)在蘊(yùn)涵邏輯?；叵霙Q策樹是用測(cè)試條件劃分屬性的方法，所以決策樹的生成需要先回答兩個(gè)問題:

(1)如何選擇劈裂的試驗(yàn)條件？

(2)什么情況下可以選擇結(jié)束分裂？

總的來(lái)說(shuō)，我們分類的目標(biāo)是希望“一個(gè)是一個(gè)，一個(gè)是兩個(gè)”。所以我們希望當(dāng)原始數(shù)據(jù)集被一個(gè)測(cè)試條件劃分為兩個(gè)或兩個(gè)以上的數(shù)據(jù)集時(shí)，劃分出來(lái)的數(shù)據(jù)集會(huì)更加“純粹”，即劃分后的任何子集都盡可能屬于同一類別。

關(guān)于子集的“純度”，我們可以通過(guò)下面的例子來(lái)理解:

1936年，我們的“漁夫”(R.A.Fisher)提供了虹膜數(shù)據(jù)集，這可能是機(jī)器學(xué)習(xí)領(lǐng)域最著名的分類數(shù)據(jù)集。

從鳶尾山和多色鳶尾中提取13個(gè)樣品，用X(花瓣長(zhǎng)度)和Y(萼片寬度)分割?？梢钥闯?，兩種類型的鳶尾都可以通過(guò)花瓣長(zhǎng)度完全準(zhǔn)確的區(qū)分出來(lái)，但被萼片寬度分割后仍有混雜的情況。我們可以認(rèn)為特征x劃分的子集純度更高。

顯然，在生成樹模型的過(guò)程中，我們應(yīng)該為每個(gè)劃分選擇能夠使子集更加純粹的劃分條件。隨著數(shù)據(jù)集的不斷劃分，我們子集的純度越來(lái)越高，直到這個(gè)節(jié)點(diǎn)下的樣本屬于同一個(gè)范疇。那么分裂應(yīng)該在什么時(shí)候終止呢？一個(gè)直觀的答案顯然可以是“該節(jié)點(diǎn)下的所有樣本都屬于同一個(gè)類別(無(wú)需劃分)”或者“該節(jié)點(diǎn)下的所有樣本都具有相同的屬性(繼續(xù)劃分并不能提高結(jié)果)”。下圖顯示了決策樹的增長(zhǎng)過(guò)程:

從以上決策樹生長(zhǎng)的流程圖中，我們可以發(fā)現(xiàn)決策樹的生長(zhǎng)重點(diǎn)在于“純度”計(jì)算公式，即如何選擇最優(yōu)的特征過(guò)程。接下來(lái)，我們將簡(jiǎn)要介紹不同決策樹算法的劃分方法。

(1)ID3系列算法:采用信息熵作為集合純度的評(píng)價(jià)

假設(shè)我們的樣本集D包含M個(gè)樣本，每個(gè)樣本的比例為

那么集合d的信息熵定義為:

計(jì)算時(shí)定義0log0=0。

ENT(D)越大，集合D的雜質(zhì)度越高，越小。ENT(D)越低，集合D的純度越高。因此，一些文獻(xiàn)提到用信息熵來(lái)衡量樣本集的“不純”純度。

信息熵的一個(gè)流行介紹可以在文章中找到:

(2)CART算法:采用GINI系數(shù)作為采集純度的評(píng)價(jià)；

對(duì)于集合d，其純度的相應(yīng)計(jì)算公式為:

其中m是目標(biāo)變量的類別數(shù)。類似于信息熵，基尼指數(shù)越低，代表集純度越高。當(dāng)節(jié)點(diǎn)只包含一個(gè)類別時(shí)，基尼系數(shù)取最小值0。5%.

由于每個(gè)算法都有很多內(nèi)容，本期只簡(jiǎn)單介紹決策樹的概念問題，下一期我們將詳細(xì)介紹決策樹中最經(jīng)典的ID3系列算法。

注意:由于老坨最近比較忙，有些消息沒有及時(shí)查看和回復(fù)(微信規(guī)定48小時(shí)內(nèi)沒有回復(fù)，不能再回復(fù))，所以如果郝斌老坨沒有及時(shí)回復(fù)，可以再留言。