決策樹(shù)是一種基本的分類(lèi)與回歸方法。

在分類(lèi)問(wèn)題中，表示基于特征對(duì)實(shí)例進(jìn)行分類(lèi)的過(guò)程，可以認(rèn)為是if-then規(guī)則的集合，也可以認(rèn)為是定義在特征空間與類(lèi)空間上的條件概率分布[1]。

在回歸問(wèn)題中，回歸樹(shù)總體流程類(lèi)似于分類(lèi)樹(shù)，分枝時(shí)窮舉每一個(gè)特征的每一個(gè)閾值，來(lái)尋找最優(yōu)切分特征j和最優(yōu)切分點(diǎn)s，衡量的方法是平方誤差最小化。分枝直到達(dá)到預(yù)設(shè)的終止條件(如葉子個(gè)數(shù)上限)就停止。

0 決策樹(shù)主要學(xué)習(xí)內(nèi)容

1. 決策樹(shù)模型：掌握決策樹(shù)模型：根結(jié)點(diǎn)，子結(jié)點(diǎn)，葉結(jié)點(diǎn)。

2. 特征選擇：如何從特征空間中選擇最優(yōu)特征作為結(jié)點(diǎn)，常用方法信息熵，信息增益，信息增益比，基尼指數(shù)。

3. 不同特征選擇對(duì)應(yīng)不同算法:

ID3(基于信息增益作為特征選擇的度量）

C4.5(基于信息增益比作為特征選擇的度量)

CART(基于基尼指數(shù)作為特征選擇的度量)

4. 決策樹(shù)的修剪：縮小樹(shù)結(jié)構(gòu)規(guī)模、緩解訓(xùn)練集上的過(guò)擬合，提高模型的泛化能力。

1、決策樹(shù)模型

決策樹(shù)呈樹(shù)形結(jié)構(gòu)，由結(jié)點(diǎn)和有向邊組成。結(jié)點(diǎn)有兩種類(lèi)型：內(nèi)部結(jié)點(diǎn)和葉結(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)表示一個(gè)特征或?qū)傩?，葉結(jié)點(diǎn)表示一個(gè)類(lèi)別。

決策樹(shù)分類(lèi)，從根結(jié)點(diǎn)開(kāi)始，對(duì)實(shí)例進(jìn)行特征選擇，根據(jù)最優(yōu)特征選擇將實(shí)例分配到其子結(jié)點(diǎn)(如何求最優(yōu)特征，這將是決策樹(shù)的重中之重)，這時(shí)，每一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)著該特征的一個(gè)取值，如此遞歸地對(duì)實(shí)例進(jìn)行測(cè)試并分配，直到達(dá)到葉結(jié)點(diǎn)，將實(shí)例全部分到葉結(jié)點(diǎn)的類(lèi)中。

決策樹(shù)在邏輯上以樹(shù)的形式存在，包含根結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)(子結(jié)點(diǎn))和葉結(jié)點(diǎn)。

1）根結(jié)點(diǎn)：包含數(shù)據(jù)集中的所有數(shù)據(jù)的集合 ，根結(jié)點(diǎn)有且僅有一個(gè)。

2）內(nèi)部結(jié)點(diǎn)：每個(gè)內(nèi)部結(jié)點(diǎn)可看作一個(gè)判斷條件，并且包含數(shù)據(jù)集中滿(mǎn)足從根節(jié)點(diǎn)到該結(jié)點(diǎn)所有條件的數(shù)據(jù)的集合。根據(jù)內(nèi)部結(jié)點(diǎn)的判斷結(jié)果，將內(nèi)部結(jié)點(diǎn)所包含的數(shù)據(jù)集分到兩個(gè)或多個(gè)子結(jié)點(diǎn)中。

3）葉結(jié)點(diǎn)：葉結(jié)點(diǎn)為最終的類(lèi)別，包含在該葉結(jié)點(diǎn)的數(shù)據(jù)屬于該類(lèi)別。

例：

提出問(wèn)題：

為何要用特征“香不香”為根節(jié)點(diǎn)呢?為何不選“辣不辣”或者“甜不甜”為根節(jié)點(diǎn)呢？

答:這是因?yàn)椤跋悴幌恪边@一特征相比其他特征更具有將訓(xùn)練數(shù)據(jù)分類(lèi)的能力。

那是如何判斷這一特征更具有將訓(xùn)練數(shù)據(jù)分類(lèi)的能力呢？

答:這需要進(jìn)行特征選擇，常用方法有信息增益、信息增益比、基尼指數(shù)。

2、特征選擇及用其分類(lèi)的算法

2.1 前期準(zhǔn)備工作

首先需要介紹一下信息熵，條件熵。

2.1.1信息熵

在信息論中，一個(gè)特征所帶的信息量又稱(chēng)信息熵，熵度量了事物的不確定性，越不確定的事物，它的熵就越大。

當(dāng)概率為0.5時(shí)，熵的取值最大，也就是說(shuō)，隨機(jī)變量不確定性最大。

2.1.2 條件熵

如有兩個(gè)隨機(jī)變量呢？

設(shè)有隨機(jī)變量(X,Y),其聯(lián)合概率分布為：

 2.2 信息增益[1]

信息增益，主要看一個(gè)特征能夠?yàn)榉诸?lèi)系統(tǒng)帶來(lái)多少信息，帶來(lái)的信息越多，則該特征越重要。沒(méi)它和有它的信息量（信息熵）差值就是這個(gè)特征給系統(tǒng)帶來(lái)的信息量，也稱(chēng)信息增益。簡(jiǎn)單來(lái)說(shuō)就是在現(xiàn)有訓(xùn)練集包含的信息熵和已知某特征下的信息熵的差值即該特征的信息增益。

由于熵和條件熵中的概率通常無(wú)法直接得到，所以在實(shí)際中用頻率代替概率。使用頻率的熵和條件熵也分別稱(chēng)經(jīng)驗(yàn)熵和條件經(jīng)驗(yàn)熵。

2.2.1 基于信息增益的ID3算法[1]

ID3算法的核心：是在決策樹(shù)各個(gè)節(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸地構(gòu)建決策樹(shù)。

選擇信息增益最大的特征A2(有工作)作為結(jié)點(diǎn)的特征，由于A2有兩個(gè)可能取值，從這一結(jié)點(diǎn)可引發(fā)兩個(gè)子結(jié)點(diǎn)，一個(gè)“是”有工作，一個(gè)“否”有工作。據(jù)實(shí)例，在D2訓(xùn)練集下(9個(gè)人)，有工作的3人屬于同類(lèi)(批準(zhǔn)貸款申請(qǐng))，所以為一個(gè)葉結(jié)點(diǎn)。類(lèi)標(biāo)記為“是”，另一個(gè)無(wú)工作的6人也屬于同類(lèi)(未批準(zhǔn)貸款申請(qǐng))，也可為一個(gè)葉結(jié)點(diǎn)，類(lèi)標(biāo)記為“否”。

該決策樹(shù)模型圖為：

該實(shí)例的ID3決策樹(shù)構(gòu)建完成。 

2.3.1 基于信息增益比的C4.5算法

C4.5算法與ID3算法相似，C4.5算法對(duì)ID3算法做了改進(jìn)，在進(jìn)行特征選擇時(shí)，采用信息增益比來(lái)代替信息增益進(jìn)行特征選擇。

2.4.1 基于基尼指數(shù)的CART算法[1]

CART同樣由特征選擇、樹(shù)的生成、修剪組成。既可以用于分類(lèi)也可以用于回歸。該算法下是遞歸地構(gòu)建二叉樹(shù)決策樹(shù)的過(guò)程。

對(duì)于分類(lèi)樹(shù)，用基尼指數(shù)最小化準(zhǔn)則進(jìn)行特征選擇，生成二叉樹(shù)。

對(duì)于回歸樹(shù)，使用平方誤差最小化方法。

例

如下表2，需要利用實(shí)例數(shù)據(jù)對(duì)年齡進(jìn)行預(yù)測(cè)，若將j屬性選為職業(yè)，則有三種劃分情況，

1）{老師,上班族}，{學(xué)生}

2）{學(xué)生,上班族}，{老師}

3）{老師,學(xué)生}，{上班族}

最小平方誤差計(jì)算得：

m=42+226.8=268.8

2.5 決策樹(shù)剪枝[1]

決策樹(shù)生成算法遞歸地產(chǎn)生決策樹(shù)，直到不能繼續(xù)下去為止，這樣的樹(shù)往往對(duì)訓(xùn)練數(shù)據(jù)集有很好的擬合，但對(duì)未知的測(cè)試數(shù)據(jù)的分類(lèi)就不太理想，這就是出現(xiàn)了過(guò)擬合現(xiàn)象，出現(xiàn)這一問(wèn)題，解決方法就是要考慮決策樹(shù)的復(fù)雜度，對(duì)已有的決策樹(shù)進(jìn)行簡(jiǎn)化，簡(jiǎn)稱(chēng)剪枝。

剪枝往往通過(guò)極小化決策樹(shù)整體的損失函數(shù)或代價(jià)函數(shù)來(lái)減小模型復(fù)雜度，提高全局學(xué)習(xí)效果。

2.5 決策樹(shù)剪枝[1]

決策樹(shù)生成算法遞歸地產(chǎn)生決策樹(shù)，直到不能繼續(xù)下去為止，這樣的樹(shù)往往對(duì)訓(xùn)練數(shù)據(jù)集有很好的擬合，但對(duì)未知的測(cè)試數(shù)據(jù)的分類(lèi)就不太理想，這就是出現(xiàn)了過(guò)擬合現(xiàn)象，出現(xiàn)這一問(wèn)題，解決方法就是要考慮決策樹(shù)的復(fù)雜度，對(duì)已有的決策樹(shù)進(jìn)行簡(jiǎn)化，簡(jiǎn)稱(chēng)剪枝。

剪枝往往通過(guò)極小化決策樹(shù)整體的損失函數(shù)或代價(jià)函數(shù)來(lái)減小模型復(fù)雜度，提高全局學(xué)習(xí)效果。

3 決策樹(shù)算法總結(jié)

3.1 決策樹(shù)算法(貪心算法)

? 有監(jiān)督的學(xué)習(xí)

? 非參數(shù)學(xué)習(xí)算法

? 自頂向下遞歸方式構(gòu)造決策樹(shù)

? 在每一步選擇中都采取在當(dāng)前狀態(tài)下最好的選擇

3.2 決策樹(shù)的優(yōu)點(diǎn)：

(1)速度快：計(jì)算量相對(duì)較小，且容易轉(zhuǎn)化成分類(lèi)規(guī)則。只要沿著樹(shù)根向下一直走到葉，沿途的分裂條件就能夠唯一確定一條分類(lèi)的路徑。

(2)準(zhǔn)確性高：挖掘出的分類(lèi)規(guī)則準(zhǔn)確性高，便于理解，決策樹(shù)可以清晰的顯示哪些字段比較重要，即可以生成可以理解的規(guī)則。

(3)適合高維數(shù)據(jù)

(4)可以處理連續(xù)變量和種類(lèi)字段

(5)不需要任何領(lǐng)域知識(shí)和參數(shù)假設(shè)

3.3 決策樹(shù)的缺點(diǎn)：

(1)對(duì)于各類(lèi)樣本數(shù)量不一致的數(shù)據(jù)，信息增益偏向于那些具有更多數(shù)值的特征。

(2)易于過(guò)擬合

(3)忽略屬性之間的相關(guān)性

4 決策樹(shù)的運(yùn)用

第一：決策樹(shù)法作為一種決策技術(shù)，已被廣泛地應(yīng)用于企業(yè)的投資決策之中，它是隨機(jī)決策模型中最常見(jiàn)、最普及的一種規(guī)策模式和方法，有效地控制了決策帶來(lái)的風(fēng)險(xiǎn)。所謂決策樹(shù)法，就是運(yùn)用樹(shù)狀圖表示各決策的期望值，通過(guò)計(jì)算，最終優(yōu)選出效益最大、成本最小的決策方法。

第二：信用評(píng)分

第三：工廠(chǎng)生產(chǎn)能力計(jì)劃

第四：隨機(jī)森林的基礎(chǔ)

參考文獻(xiàn)

[1]李航，《統(tǒng)計(jì)學(xué)習(xí)方法》.

[2] https://www.cnblogs.com/yjd_hycf_space/p/6940068.html

[3] https://blog.csdn.net/gzj_1101/article/details/78355234

[4] 常用數(shù)據(jù)挖掘算法總結(jié)及python實(shí)現(xiàn).

(部分文字、圖片來(lái)自網(wǎng)絡(luò)，如涉及侵權(quán)，請(qǐng)及時(shí)與我們聯(lián)系，我們會(huì)在第一時(shí)間刪除或處理侵權(quán)內(nèi)容。電話(huà)：4006770986    負(fù)責(zé)人：張明）