概述

決策樹（Decision Tree）是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評(píng)價(jià)項(xiàng)目風(fēng)險(xiǎn)，判斷其可行性的決策分析方法，是直觀運(yùn)用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。在機(jī)器學(xué)習(xí)中，決策樹是一個(gè)預(yù)測(cè)模型，他代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。Entropy = 系統(tǒng)的凌亂程度，使用算法ID3， C4.5和C5.0生成樹算法使用熵。這一度量是基于信息學(xué)理論中熵的概念。

決策樹是一種樹形結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉節(jié)點(diǎn)代表一種類別。

分類樹（決策樹）是一種十分常用的分類方法。他是一種監(jiān)管學(xué)習(xí)，所謂監(jiān)管學(xué)習(xí)就是給定一堆樣本，每個(gè)樣本都有一組屬性和一個(gè)類別，這些類別是事先確定的，那么通過學(xué)習(xí)得到一個(gè)分類器，這個(gè)分類器能夠?qū)π鲁霈F(xiàn)的對(duì)象給出正確的分類。這樣的機(jī)器學(xué)習(xí)就被稱之為監(jiān)督學(xué)習(xí)。

畫法

機(jī)器學(xué)習(xí)中，決策樹是一個(gè)預(yù)測(cè)模型；他代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。樹中每個(gè)節(jié)點(diǎn)表示某個(gè)對(duì)象，而每個(gè)分叉路徑則代表的某個(gè)可能的屬性值，而每個(gè)葉結(jié)點(diǎn)則對(duì)應(yīng)從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)所經(jīng)歷的路徑所表示的對(duì)象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨(dú)立的決策樹以處理不同輸出。

數(shù)據(jù)挖掘中決策樹是一種經(jīng)常要用到的技術(shù)，可以用于分析數(shù)據(jù)，同樣也可以用來作預(yù)測(cè)。

從數(shù)據(jù)產(chǎn)生決策樹的機(jī)器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí)， 通俗說就是決策樹。

一個(gè)決策樹包含三種類型的節(jié)點(diǎn)：

① 決策節(jié)點(diǎn)：通常用矩形框來表示。

是對(duì)幾種可能方案的選擇，即最后選擇的最佳方案。

如果決策屬于多級(jí)決策，則決策樹的中間可以有多個(gè)決策點(diǎn)，

以決策樹根部的決策點(diǎn)為最終決策方案。

② 機(jī)會(huì)節(jié)點(diǎn)：通常用圓圈來表示。

代表備選方案的經(jīng)濟(jì)效果（期望值），

通過各狀態(tài)節(jié)點(diǎn)的經(jīng)濟(jì)效果的對(duì)比，

按照一定的決策標(biāo)準(zhǔn)就可以選出最佳方案。

由狀態(tài)節(jié)點(diǎn)引出的分支稱為概率枝，

概率枝的數(shù)目表示可能出現(xiàn)的自然狀態(tài)數(shù)目每個(gè)分枝上要注明該狀態(tài)出現(xiàn)的概率。

③ 終結(jié)點(diǎn)：通常用三角形來表示。

將每個(gè)方案在各種自然狀態(tài)下取得的損益值標(biāo)注于結(jié)果節(jié)點(diǎn)的右端。

決策樹學(xué)習(xí)也是資料探勘中一個(gè)普通的方法。在這里，每個(gè)決策樹都表述了一種樹型結(jié)構(gòu)，它由它的分支來對(duì)該類型的對(duì)象依靠屬性進(jìn)行分類。每個(gè)決策樹可以依靠對(duì)源數(shù)據(jù)庫(kù)的分割進(jìn)行數(shù)據(jù)測(cè)試。這個(gè)過程可以遞歸式的對(duì)樹進(jìn)行修剪。 當(dāng)不能再進(jìn)行分割或一個(gè)單獨(dú)的類可以被應(yīng)用于某一分支時(shí)，遞歸過程就完成了。另外，隨機(jī)森林分類器將許多決策樹結(jié)合起來以提升分類的正確率。

決策樹同時(shí)也可以依靠計(jì)算條件概率來構(gòu)造。

剪枝

剪枝是決策樹停止分支的方法之一，剪枝有分預(yù)先剪枝和后剪枝兩種。

預(yù)先剪枝是在樹的生長(zhǎng)過程中設(shè)定一個(gè)指標(biāo)，當(dāng)達(dá)到該指標(biāo)時(shí)就停止生長(zhǎng)，這樣做容易產(chǎn)生“視界局限”，就是一旦停止分支，使得節(jié)點(diǎn)N成為葉節(jié)點(diǎn)，就斷絕了其后繼節(jié)點(diǎn)進(jìn)行“好”的分支操作的任何可能性。不嚴(yán)格的說這些已停止的分支會(huì)誤導(dǎo)學(xué)習(xí)算法，導(dǎo)致產(chǎn)生的樹不純度降差最大的地方過分靠近根節(jié)點(diǎn)。

后剪枝中樹首先要充分生長(zhǎng)，直到葉節(jié)點(diǎn)都有最小的不純度值為止，因而可以克服“視界局限”。然后對(duì)所有相鄰的成對(duì)葉節(jié)點(diǎn)考慮是否消去它們，如果消去能引起令人滿意的不純度增長(zhǎng)，那么執(zhí)行消去，并令它們的公共父節(jié)點(diǎn)成為新的葉節(jié)點(diǎn)。這種“合并”葉節(jié)點(diǎn)的做法和節(jié)點(diǎn)分支的過程恰好相反，經(jīng)過剪枝后葉節(jié)點(diǎn)常常會(huì)分布在很寬的層次上，樹也變得非平衡。

后剪枝技術(shù)的優(yōu)點(diǎn)是克服了“視界局限”效應(yīng)，而且無需保留部分樣本用于交叉驗(yàn)證，所以可以充分利用全部訓(xùn)練集的信息。但后剪枝的計(jì)算量代價(jià)比預(yù)剪枝方法大得多，特別是在大樣本集中，不過對(duì)于小樣本的情況，后剪枝方法還是優(yōu)于預(yù)剪枝方法的。

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

優(yōu)點(diǎn)

決策樹易于理解和實(shí)現(xiàn)，人們?cè)谠趯W(xué)習(xí)過程中不需要使用者了解很多的背景知識(shí)，這同時(shí)是它的能夠直接體現(xiàn)數(shù)據(jù)的特點(diǎn)，只要通過解釋后都有能力去理解決策樹所表達(dá)的意義。

對(duì)于決策樹，數(shù)據(jù)的準(zhǔn)備往往是簡(jiǎn)單或者是不必要的，而且能夠同時(shí)處理數(shù)據(jù)型和常規(guī)型屬性，在相對(duì)短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果。

易于通過靜態(tài)測(cè)試來對(duì)模型進(jìn)行評(píng)測(cè)，可以測(cè)定模型可信度；如果給定一個(gè)觀察的模型，那么根據(jù)所產(chǎn)生的決策樹很容易推出相應(yīng)的邏輯表達(dá)式。

缺點(diǎn)

對(duì)連續(xù)性的字段比較難預(yù)測(cè)。

對(duì)有時(shí)間順序的數(shù)據(jù)，需要很多預(yù)處理的工作。

當(dāng)類別太多時(shí)，錯(cuò)誤可能就會(huì)增加的比較快。

一般的算法分類的時(shí)候，只是根據(jù)一個(gè)字段來分類。

ID3算法

決策樹基本上就是把我們以前的經(jīng)驗(yàn)總結(jié)出來。

如果我們要出門打籃球，一般會(huì)根據(jù)“天氣”、“溫度”、“濕度”、“刮風(fēng)”這幾個(gè)條件來判斷，最后得到結(jié)果：去打籃球？還是不去？

在這里我們先介紹兩個(gè)指標(biāo)：純度和信息熵。

純度

你可以把決策樹的構(gòu)造過程理解成為尋找純凈劃分的過程。數(shù)學(xué)上，我們可以用純度來表示，純度換一種方式來解釋就是讓目標(biāo)變量的分歧最小。

舉個(gè)例子，假設(shè)有 3 個(gè)集合：

集合 1：6 次都去打籃球；

集合 2：4 次去打籃球，2 次不去打籃球；

集合 3：3 次去打籃球，3 次不去打籃球。

按照純度指標(biāo)來說，集合 1》 集合 2》 集合 3。因?yàn)榧? 的分歧最小，集合 3 的分歧最大。

信息熵

表示信息的不確定度

在信息論中，隨機(jī)離散事件出現(xiàn)的概率存在著不確定性。為了衡量這種信息的不確定性，信息學(xué)之父香農(nóng)引入了信息熵的概念，并給出了計(jì)算信息熵的數(shù)學(xué)公式：

p（i|t） 代表了節(jié)點(diǎn) t 為分類 i 的概率，其中 log2 為取以 2 為底的對(duì)數(shù)。存在一種度量，它能幫我們反映出來這個(gè)信息的不確定度。當(dāng)不確定性越大時(shí)，它所包含的信息量也就越大，信息熵也就越高。

舉個(gè)例子，假設(shè)有 2 個(gè)集合：

? 集合 1：5 次去打籃球，1 次不去打籃球；

? 集合 2：3 次去打籃球，3 次不去打籃球。

在集合 1 中，有 6 次決策，其中打籃球是 5 次，不打籃球是 1 次。那么假設(shè)：類別 1 為“打籃球”，即次數(shù)為 5；類別 2 為“不打籃球”，即次數(shù)為 1。那么節(jié)點(diǎn)劃分為類別1的概率是 5/6，為類別2的概率是1/6，帶入上述信息熵公式可以計(jì)算得出：

同樣，集合 2 中，也是一共 6 次決策，其中類別 1 中“打籃球”的次數(shù)是 3，類別 2“不打籃球”的次數(shù)也是 3，那么信息熵為多少呢？我們可以計(jì)算得出：

從上面的計(jì)算結(jié)果中可以看出，信息熵越大，純度越低。當(dāng)集合中的所有樣本均勻混合時(shí)，信息熵最大，純度最低。

我們?cè)跇?gòu)造決策樹的時(shí)候，會(huì)基于純度來構(gòu)建。而經(jīng)典的 “不純度”的指標(biāo)有三種，分別是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指數(shù)（Cart 算法）。

信息增益

信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計(jì)算公式，是父親節(jié)點(diǎn)的信息熵減去所有子節(jié)點(diǎn)的信息熵。在計(jì)算的過程中，我們會(huì)計(jì)算每個(gè)子節(jié)點(diǎn)的歸一化信息熵，即按照每個(gè)子節(jié)點(diǎn)在父節(jié)點(diǎn)中出現(xiàn)的概率，來計(jì)算這些子節(jié)點(diǎn)的信息熵。

所以信息增益的公式可以表示為：

公式中 D 是父親節(jié)點(diǎn)，Di 是子節(jié)點(diǎn)，Gain（D，a）中的 a 作為 D 節(jié)點(diǎn)的屬性選擇。

假設(shè)D 天氣 = 晴的時(shí)候，會(huì)有 5 次去打籃球，5 次不打籃球。其中 D1 刮風(fēng) = 是，有 2 次打籃球，1 次不打籃球。D2 刮風(fēng) = 否，有 3 次打籃球，4 次不打籃球。那么a 代表節(jié)點(diǎn)的屬性，即天氣 = 晴。

針對(duì)圖上這個(gè)例子，D 作為節(jié)點(diǎn)的信息增益為：

也就是 D 節(jié)點(diǎn)的信息熵 -2 個(gè)子節(jié)點(diǎn)的歸一化信息熵。2個(gè)子節(jié)點(diǎn)歸一化信息熵 =3/10 的 D1 信息熵 +7/10 的 D2 信息熵。

我們基于 ID3 的算法規(guī)則，完整地計(jì)算下我們的訓(xùn)練集，訓(xùn)練集中一共有 7 條數(shù)據(jù)，3 個(gè)打籃球，4 個(gè)不打籃球，所以根節(jié)點(diǎn)的信息熵是：

如果你將天氣作為屬性的劃分，會(huì)有三個(gè)葉子節(jié)點(diǎn) D1、D2 和D3，分別對(duì)應(yīng)的是晴天、陰天和小雨。我們用 + 代表去打籃球，- 代表不去打籃球。那么第一條記錄，晴天不去打籃球，可以記為 1-，于是我們可以用下面的方式來記錄 D1，D2，D3：

D1（天氣 = 晴天）={1-，2-，6+}

D2（天氣 = 陰天）={3+，7-}

D3（天氣 = 小雨）={4+，5-}

我們先分別計(jì)算三個(gè)葉子節(jié)點(diǎn)的信息熵：

因?yàn)?D1 有 3 個(gè)記錄，D2 有 2 個(gè)記錄，D3 有2 個(gè)記錄，所以 D 中的記錄一共是 3+2+2=7，即總數(shù)為 7。所以 D1 在 D（父節(jié)點(diǎn)）中的概率是 3/7，D2在父節(jié)點(diǎn)的概率是 2/7，D3 在父節(jié)點(diǎn)的概率是 2/7。那么作為子節(jié)點(diǎn)的歸一化信息熵 = 3/70.918+2/71.0=0.965。

因?yàn)槲覀冇?ID3 中的信息增益來構(gòu)造決策樹，所以要計(jì)算每個(gè)節(jié)點(diǎn)的信息增益。

天氣作為屬性節(jié)點(diǎn)的信息增益為，Gain（D ， 天氣）=0.985-0.965=0.020。

同理我們可以計(jì)算出其他屬性作為根節(jié)點(diǎn)的信息增益，它們分別為：

Gain（D ， 溫度）=0.128

Gain（D ， 濕度）=0.020

Gain（D ， 刮風(fēng)）=0.020

我們能看出來溫度作為屬性的信息增益最大。因?yàn)?ID3 就是要將信息增益最大的節(jié)點(diǎn)作為父節(jié)點(diǎn)，這樣可以得到純度高的決策樹，所以我們將溫度作為根節(jié)點(diǎn)。其決策樹狀圖分裂為下圖所示：

然后我們要將上圖中第一個(gè)葉節(jié)點(diǎn)，也就是 D1={1-，2-，3+，4+}進(jìn)一步進(jìn)行分裂，往下劃分，計(jì)算其不同屬性（天氣、濕度、刮風(fēng)）作為節(jié)點(diǎn)的信息增益，可以得到：

Gain（D ， 天氣）=0

Gain（D ， 濕度）=0

Gain（D ， 刮風(fēng)）=0.0615

我們能看到刮風(fēng)為 D1 的節(jié)點(diǎn)都可以得到最大的信息增益，這里我們選取刮風(fēng)作為節(jié)點(diǎn)。同理，我們可以按照上面的計(jì)算步驟得到完整的決策樹，結(jié)果如下：

于是我們通過 ID3 算法得到了一棵決策樹。ID3 的算法規(guī)則相對(duì)簡(jiǎn)單，可解釋性強(qiáng)。同樣也存在缺陷，比如我們會(huì)發(fā)現(xiàn)ID3 算法傾向于選擇取值比較多的屬性。這樣，如果我們把“編號(hào)”作為一個(gè)屬性（一般情況下不會(huì)這么做，這里只是舉個(gè)例子），那么“編號(hào)”將會(huì)被選為最優(yōu)屬性 。但實(shí)際上“編號(hào)”是無關(guān)屬性的，它對(duì)“打籃球”的分類并沒有太大作用。

所以 ID3 有一個(gè)缺陷就是，有些屬性可能對(duì)分類任務(wù)沒有太大作用，但是他們?nèi)匀豢赡軙?huì)被選為最優(yōu)屬性。這種缺陷不是每次都會(huì)發(fā)生，只是存在一定的概率。在大部分情況下，ID3 都能生成不錯(cuò)的決策樹分類。針對(duì)可能發(fā)生的缺陷，后人提出了新的算法進(jìn)行改進(jìn)。

C4.5 算法

信息增益率

因?yàn)?ID3 在計(jì)算的時(shí)候，傾向于選擇取值多的屬性。為了避免這個(gè)問題，C4.5 采用信息增益率的方式來選擇屬性。信息增益率 = 信息增益 / 屬性熵

當(dāng)屬性有很多值的時(shí)候，相當(dāng)于被劃分成了許多份，雖然信息增益變大了，但是對(duì)于 C4.5 來說，屬性熵也會(huì)變大，所以整體的信息增益率并不大。

悲觀剪枝

ID3 構(gòu)造決策樹的時(shí)候，容易產(chǎn)生過擬合的情況。在 C4.5中，會(huì)在決策樹構(gòu)造之后采用悲觀剪枝（PEP），這樣可以提升決策樹的泛化能力。

悲觀剪枝是后剪枝技術(shù)中的一種，通過遞歸估算每個(gè)內(nèi)部節(jié)點(diǎn)的分類錯(cuò)誤率，比較剪枝前后這個(gè)節(jié)點(diǎn)的分類錯(cuò)誤率來決定是否對(duì)其進(jìn)行剪枝。這種剪枝方法不再需要一個(gè)單獨(dú)的測(cè)試數(shù)據(jù)集。

離散化處理連續(xù)屬性

C4.5 可以處理連續(xù)屬性的情況，對(duì)連續(xù)的屬性進(jìn)行離散化的處理。比如打籃球存在的“濕度”屬性，不按照“高、中”劃分，而是按照濕度值進(jìn)行計(jì)算，那么濕度取什么值都有可能。該怎么選擇這個(gè)閾值呢，C4.5 選擇具有最高信息增益的劃分所對(duì)應(yīng)的閾值。

處理缺失值

針對(duì)數(shù)據(jù)集不完整的情況，C4.5 也可以進(jìn)行處理。

假如我們得到的是如下的數(shù)據(jù)，你會(huì)發(fā)現(xiàn)這個(gè)數(shù)據(jù)中存在兩點(diǎn)問題。第一個(gè)問題是，數(shù)據(jù)集中存在數(shù)值缺失的情況，如何進(jìn)行屬性選擇？第二個(gè)問題是，假設(shè)已經(jīng)做了屬性劃分，但是樣本在這個(gè)屬性上有缺失值，該如何對(duì)樣本進(jìn)行劃分？

我們不考慮缺失的數(shù)值，可以得到溫度 D={2-，3+，4+，5-，6+，7-}。溫度 = 高：D1={2-，3+，4+}；溫度 = 中：D2={6+，7-}；溫度 = 低：D3={5-} 。這里 + 號(hào)代表打籃球，- 號(hào)代表不打籃球。比如ID=2 時(shí)，決策是不打籃球，我們可以記錄為 2-。

所以三個(gè)葉節(jié)點(diǎn)的信息熵可以結(jié)算為：

這三個(gè)節(jié)點(diǎn)的歸一化信息熵為 3/60.918+2/61.0+1/6*0=0.792。

針對(duì)將屬性選擇為溫度的信息增益率為：

Gain（D′， 溫度）=Ent（D′）-0.792=1.0-0.792=0.208

D′的樣本個(gè)數(shù)為 6，而 D 的樣本個(gè)數(shù)為 7，所以所占權(quán)重比例為 6/7，所以 Gain（D′，溫度） 所占權(quán)重比例為6/7，所以：

Gain（D， 溫度）=6/7*0.208=0.178

這樣即使在溫度屬性的數(shù)值有缺失的情況下，我們依然可以計(jì)算信息增益，并對(duì)屬性進(jìn)行選擇。

小結(jié)

首先 ID3 算法的優(yōu)點(diǎn)是方法簡(jiǎn)單，缺點(diǎn)是對(duì)噪聲敏感。訓(xùn)練數(shù)據(jù)如果有少量錯(cuò)誤，可能會(huì)產(chǎn)生決策樹分類錯(cuò)誤。C4.5 在 IID3 的基礎(chǔ)上，用信息增益率代替了信息增益，解決了噪聲敏感的問題，并且可以對(duì)構(gòu)造樹進(jìn)行剪枝、處理連續(xù)數(shù)值以及數(shù)值缺失等情況，但是由于 C4.5 需要對(duì)數(shù)據(jù)集進(jìn)行多次掃描，算法效率相對(duì)較低。