決策樹是一種基本的分類與回歸方法。

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

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

0 決策樹主要學習內(nèi)容

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

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

3. 不同特征選擇對應不同算法:

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

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

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

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

1、決策樹模型

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

決策樹分類，從根結(jié)點開始，對實例進行特征選擇，根據(jù)最優(yōu)特征選擇將實例分配到其子結(jié)點(如何求最優(yōu)特征，這將是決策樹的重中之重)，這時，每一個子結(jié)點對應著該特征的一個取值，如此遞歸地對實例進行測試并分配，直到達到葉結(jié)點，將實例全部分到葉結(jié)點的類中。

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

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

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

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

例：

提出問題：

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

答:這是因為“香不香”這一特征相比其他特征更具有將訓練數(shù)據(jù)分類的能力。

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

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

2、特征選擇及用其分類的算法

2.1 前期準備工作

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

2.1.1信息熵

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

當概率為0.5時，熵的取值最大，也就是說，隨機變量不確定性最大。

2.1.2 條件熵

如有兩個隨機變量呢？

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

 2.2 信息增益[1]

信息增益，主要看一個特征能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多，則該特征越重要。沒它和有它的信息量（信息熵）差值就是這個特征給系統(tǒng)帶來的信息量，也稱信息增益。簡單來說就是在現(xiàn)有訓練集包含的信息熵和已知某特征下的信息熵的差值即該特征的信息增益。

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

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

ID3算法的核心：是在決策樹各個節(jié)點上應用信息增益準則選擇特征，遞歸地構(gòu)建決策樹。

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

該決策樹模型圖為：

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

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

C4.5算法與ID3算法相似，C4.5算法對ID3算法做了改進，在進行特征選擇時，采用信息增益比來代替信息增益進行特征選擇。

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

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

對于分類樹，用基尼指數(shù)最小化準則進行特征選擇，生成二叉樹。

對于回歸樹，使用平方誤差最小化方法。

例

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

1）{老師,上班族}，{學生}

2）{學生,上班族}，{老師}

3）{老師,學生}，{上班族}

最小平方誤差計算得：

m=42+226.8=268.8

2.5 決策樹剪枝[1]

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

剪枝往往通過極小化決策樹整體的損失函數(shù)或代價函數(shù)來減小模型復雜度，提高全局學習效果。

2.5 決策樹剪枝[1]

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

剪枝往往通過極小化決策樹整體的損失函數(shù)或代價函數(shù)來減小模型復雜度，提高全局學習效果。

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

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

? 有監(jiān)督的學習

? 非參數(shù)學習算法

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

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

3.2 決策樹的優(yōu)點：

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

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

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

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

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

3.3 決策樹的缺點：

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

(2)易于過擬合

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

4 決策樹的運用

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

第二：信用評分

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

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

參考文獻

[1]李航，《統(tǒng)計學習方法》.

[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實現(xiàn).

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