2.1.決策樹和隨機(jī)森林

決策樹(Decision Tree)是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評價(jià)項(xiàng)目風(fēng)險(xiǎn)，判斷其可行性的決策分析方法，是直觀運(yùn)用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。決策樹是一種基本的分類和回歸方法，學(xué)習(xí)通常包含三個(gè)步驟：特征選擇、決策樹的生成和決策樹的剪枝。在機(jī)器學(xué)習(xí)中，決策樹是一個(gè)預(yù)測模型，他代表的是對象屬性與對象值之間的一種映射關(guān)系。分類樹(決策樹)是一種十分常用的分類方法。數(shù)據(jù)挖掘中決策樹是一種經(jīng)常要用到的技術(shù)，可以用于分析數(shù)據(jù)，同樣也可以用來做預(yù)測。

一個(gè)簡單的決策樹分類模型：紅色框出的是特征。

在機(jī)器學(xué)習(xí)中，隨機(jī)森林是一個(gè)包含多個(gè)決策樹的分類器，并且其輸出的類別是由個(gè)別樹輸出的類別的眾數(shù)而定。Leo Breiman和Adele Cutler發(fā)展出推論出隨機(jī)森林的算法。隨機(jī)森林在過去幾年一直是新興的機(jī)器學(xué)習(xí)技術(shù)。它是基于非線性的決策樹模型，通常能夠提供準(zhǔn)確的結(jié)果。然而，隨機(jī)森林大多是黑盒子，經(jīng)常難以解讀和充分理解。

2.1.1.預(yù)備知識

2.1.1.1.條件熵

在信息論中，條件熵描述了在已知第二個(gè)隨機(jī)變量X的前提下，隨機(jī)變量Y的信息熵還剩多少。基于X條件的Y的信息熵，用H(Y|X)表示。
如果H(Y|X=x)為變數(shù)Y在變數(shù)X取特定值x條件下的熵，那么H(Y|X)就是H(Y|X=x)在X取遍所有可能的x后取平均的結(jié)果。

我們可以借助上圖來幫助理解熵和條件熵：紅色的整個(gè)圓表示變量X的熵，藍(lán)色的整個(gè)圓表示變量Y的熵。
首先，熵可以理解為事件的不確定性，聯(lián)系到上面的X, Y就是H(X)表示的是未知的不確定的X（也即紅色的圓），而藍(lán)色的則表示未知不確定的Y，而條件熵表示的是在知道某一事件后對另一事件未知性的減少（前提是這兩個(gè)事件有交集）。放在上面則是知道確定了X后Y的不確定性還剩多少，也就是右側(cè)藍(lán)色的圓減去兩個(gè)圓交叉的部分后剩余的，這就是條件熵H(Y|X)。
現(xiàn)在理解了條件熵，那么兩事件X, Y中間的交集互信息該如何理解呢？既然條件熵是知曉了X后Y未知性還剩余的多少，那么互信息就可以理解為知曉了事件X后Y事件有多少也是可以確定的，也即X對Y造成的干擾部分，即為互信息I(X; Y)。
而聯(lián)合熵就比較好理解了，就是事件X未知性和事件Y的未知性之和減去他們的交集部分。

首先需要知道的是熵的公式：
對上式做簡單的說明：
（1）P(xi)表示事件xi的概率；
（2）-P(xi)logP(xi)表示事件xi的熵；

2.1.2.決策樹生成算法

決策樹分類從根節(jié)點(diǎn)開始，對實(shí)例的某一特征進(jìn)行測試，根據(jù)測試結(jié)果將實(shí)例分配到其子節(jié)點(diǎn)。每一個(gè)子節(jié)點(diǎn)對應(yīng)著該特征的一個(gè)取值。如此遞歸地對實(shí)例進(jìn)行測試并分配，直至達(dá)到葉節(jié)點(diǎn)，最后將實(shí)例分配到葉節(jié)點(diǎn)的類中。

決策樹學(xué)習(xí)的算法通常是一個(gè)遞歸地選擇最優(yōu)特征，并根據(jù)該特征對訓(xùn)練數(shù)據(jù)進(jìn)行劃分。如果利用一個(gè)特征進(jìn)行分類的結(jié)果與隨機(jī)分類的結(jié)果沒有很大差別，則稱這個(gè)特征是沒有分類能力的。通常特征選擇的準(zhǔn)則是信息增益或信息增益比，特征選擇的常用算法有ID3，C4.5，CART。

2.1.3.信息增益

信息增益表示得知特征A的信息而使得數(shù)據(jù)X的信息的不確定性的程度。
信息增益定義：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g(D, A)定義為集合D的經(jīng)驗(yàn)熵H(D)與給定特征A的條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差，即：

（信息增益，也叫作互信息）

根據(jù)信息增益選擇特征的方法是：對于給定數(shù)據(jù)集D，計(jì)算其每個(gè)特征的信息增益，并比較他們的大小，選擇信息增益最大的特征。使用信息增益選擇特征的算法稱為C3算法。

基本記號：

信息增益的計(jì)算方法：

2.1.3.1.信息增益比

信息增益值的大小是相對于訓(xùn)練數(shù)據(jù)集而言的，并沒有絕對意義。在分類為題困難時(shí)，也就是說在訓(xùn)練數(shù)據(jù)集的經(jīng)驗(yàn)熵大的時(shí)候，信息增益值會偏大。反之，信息增益值會偏小。因此，使用信息增益比可以對這一問題進(jìn)行校正，這是另一種特征選擇算法，也即C4.5算法。

2.1.4.基尼系數(shù)

基尼指數(shù)是CART分類樹用來選擇最優(yōu)特征的算法，同時(shí)決定了該特征的最優(yōu)二值切分點(diǎn)。


對于給定的樣本集合D,其基尼指數(shù)為：


一個(gè)特征的信息增益/基尼系數(shù)越大，表明特征對樣本的熵減少的能力更強(qiáng)，這個(gè)特征使得數(shù)據(jù)由不確定性變成確定性的能力越強(qiáng)。

2.1.5.決策樹的剪枝

決策樹生成算法產(chǎn)生的決策樹對于訓(xùn)練數(shù)據(jù)的分類往往很準(zhǔn)確，但對于未知數(shù)據(jù)的分類卻沒有這么準(zhǔn)確，即容易出現(xiàn)過擬合情況。解決的辦法便是考慮樹的復(fù)雜度，對已生成的樹進(jìn)行剪枝簡化。

決策樹的剪枝往往通過極小化決策樹整體的損失函數(shù)來實(shí)現(xiàn)。


其中經(jīng)驗(yàn)熵為：

在損失函數(shù)式子中，等式右端第一項(xiàng)記作：

最后，損失函數(shù)表示為：

2.1.6.Bootstraping

2.2.課程資料

決策樹（decision tree）是一種基本的分類與回歸方法，本文主要討論用于分類的決策樹。決策樹模型呈樹形結(jié)構(gòu)，在分類問題中，表示基于特征對實(shí)例進(jìn)行分類的過程。它可以認(rèn)為是if-then規(guī)則的集合，也可以認(rèn)為是定義在特征空間與類空間上的條件概率分布，其主要優(yōu)點(diǎn)是模型具有可讀性，分類速度快。決策樹學(xué)習(xí)通常包括三個(gè)步驟：特征選擇，決策樹的生成和決策樹的修剪。而隨機(jī)森林則是由多個(gè)決策樹所構(gòu)成的一種分類器，更準(zhǔn)確的說，隨機(jī)森林是由多個(gè)弱分類器組合形成的強(qiáng)分類器。

樹模型

• 決策樹：從根節(jié)點(diǎn)開始一步步走到葉子節(jié)點(diǎn)（決策）。
• 所有的數(shù)據(jù)最終都會落到葉子節(jié)點(diǎn)，既可以做分類也可以做回歸。
  
  樹的組成
• 根節(jié)點(diǎn)：第一個(gè)選擇點(diǎn)
• 非葉子節(jié)點(diǎn)與分支：中間過程。
• 葉子節(jié)點(diǎn)：最終的決策結(jié)果
  
  決策樹的訓(xùn)練與測試
• 訓(xùn)練階段：從給定的訓(xùn)練集構(gòu)造出來一棵樹（從根節(jié)點(diǎn)開始選擇特征，如何進(jìn)行特征切分）
• 測試階段：根據(jù)構(gòu)造出來的樹模型從上到下去走一遍就好了。
• 一旦構(gòu)造好了決策樹，那么分類或者預(yù)測任務(wù)就很簡單了，只需要走一遍就可以了，那么難點(diǎn)就在于如何構(gòu)造出來一顆樹，這就沒那么容易了，需要考慮的問題還有很多的！

如何切分特征（選擇節(jié)點(diǎn)）

• 問題：根節(jié)點(diǎn)的選擇該用哪個(gè)特征呢？接下來呢？如何切分呢？
• 想象一下：我們的目標(biāo)應(yīng)該是根節(jié)點(diǎn)就像是老大似的能更好的切分?jǐn)?shù)據(jù)（分類的效果更好），根節(jié)點(diǎn)下面的節(jié)點(diǎn)自然就是二當(dāng)家了。
• 目標(biāo)：通過一種衡量標(biāo)準(zhǔn)，來計(jì)算通過不同特征進(jìn)行分支選擇后的分類情況，找出最好的那個(gè)當(dāng)成根節(jié)點(diǎn)，以此類推。

衡量標(biāo)準(zhǔn)-熵

• 熵：熵是表示隨機(jī)變量不確定性的度量
  （解釋：說白了就是物體內(nèi)部的混亂程度，比如雜貨市場里什么都有那肯定混亂呀，專賣店里面只賣一個(gè)牌子的那就穩(wěn)定多了）
• 一個(gè)例子：
  A集合：[1,1,1,1,1,1,1,1,2,2]
  B集合：[1,2,3,4,5,6,7,8.9,1]

顯然A集合的熵值要低，因?yàn)锳里面只有兩種類別，相對穩(wěn)定一些，而B中類別太多了，熵值就會大很多（在分類任務(wù)中我們希望通過節(jié)點(diǎn)分支后數(shù)據(jù)類別的熵值大還是小呢？）

衡量標(biāo)準(zhǔn)-熵

• 熵：不確定性越大，得到的熵值也就越大。
  當(dāng)p=0或p=1時(shí)，H§=0,隨機(jī)變量完全沒有不確定性。
  當(dāng)p=0.5時(shí)，H§=1,此時(shí)隨機(jī)變量的不確定性最大。

• 如何決策一個(gè)節(jié)點(diǎn)的選擇呢？
  信息增益：表示特征X使得類Y的不確定性減少的程度。（分類后的專一性，希望分類后的結(jié)果是同類在一起）
  
  決策樹構(gòu)造實(shí)例

• 數(shù)據(jù)：14天打球情況

• 特征：4中環(huán)境變換

• 目標(biāo)：構(gòu)造決策樹

決策樹構(gòu)造實(shí)例
劃分方式：4種
問題：誰當(dāng)根節(jié)點(diǎn)呢？
依據(jù)：信息增益

決策樹構(gòu)造實(shí)例

• 在歷史數(shù)據(jù)中（14天）有9天打球，5天不打球，所以此時(shí)的熵應(yīng)為：
  
• 4個(gè)特征逐一分析，先從outlook特征開始：
  
  Outlook = sunny時(shí)，熵值為0.971
  Outlook = overcast時(shí)，熵值為0
  Outlook = rainy時(shí)，熵值為0.971

決策樹構(gòu)造實(shí)例

• 根據(jù)數(shù)據(jù)統(tǒng)計(jì)，outlook取值分別為sunny,overcast,rainy的概率分別為：
  5/14, 4/14, 5/14

• 熵值計(jì)算：5/14 * 0.971 + 4/14 * 0 + 5/14 * 0.971 = 0.693
  （gain(temperature)=0.029 gain(humidity)=0.152 gain(windy)=0.048）

• 信息增益：系統(tǒng)的熵值從原始的0.940下降到了0.693，增益為0.247

• 同樣的方式可以計(jì)算出其他特征的信息增益，那么我們選擇最大的那個(gè)就可以啦，相當(dāng)于是遍歷了一遍特征，找出來了大當(dāng)家，然后再其余的中繼續(xù)通過信息增益找二當(dāng)家!

決策樹算法

• ID3: 信息增益（有什么問題呢？）
• C4.5: 信息增益率（解決ID3問題，考慮自身熵）
• CART: 使用GINI系數(shù)來當(dāng)做衡量標(biāo)準(zhǔn)。
• GINI系數(shù)：
  （和熵的衡量標(biāo)準(zhǔn)類似，計(jì)算方式不相同）

連續(xù)值怎么辦？
選取（連續(xù)值的）哪個(gè)分界點(diǎn)？

• 貪婪算法！
  排序
  60 70 75 85 90 95 100 120 125 220
  若進(jìn)行”二分”，則可能有9個(gè)分界點(diǎn)（上面數(shù)據(jù)中的9個(gè)空格部分）。
  
• 實(shí)際上，這就是”離散化”過程

決策樹剪枝策略

• 為什么要剪枝：決策樹過擬合風(fēng)險(xiǎn)很大，理論上可以完全分得開數(shù)據(jù)。
  （想象一下，如果樹足夠龐大，每個(gè)葉子節(jié)點(diǎn)不就一個(gè)數(shù)據(jù)了嘛）
• 剪枝策略：預(yù)剪枝，后剪枝
• 預(yù)剪枝：邊建立決策樹邊進(jìn)行剪枝的操作（更實(shí)用）
• 后剪枝：當(dāng)建立完決策樹后來進(jìn)行剪枝操作。

決策樹剪枝策略

• 預(yù)剪枝：限制深度，葉子節(jié)點(diǎn)個(gè)數(shù)，葉子節(jié)點(diǎn)樣本數(shù)，信息增益量等。
• 后剪枝：通過一定的衡量標(biāo)準(zhǔn)
  
  （葉子節(jié)點(diǎn)越多，損失越大）
  

Ensemble learning

• 目標(biāo)：讓機(jī)器學(xué)習(xí)效果更好，單個(gè)不行，群毆走起
• Bagging: 訓(xùn)練多個(gè)分類器取平均
• Boosting: 從弱學(xué)習(xí)器開始加強(qiáng)，通過加權(quán)來進(jìn)行訓(xùn)練。
  （加入一棵樹，要比原來強(qiáng)）
• Stacking: 聚合多個(gè)分類或回歸模型（可以分階段來做）

Bagging模型
?全稱：bootstrap aggregation(說白了就是并行訓(xùn)練一堆分類器)
?最典型的代表就是隨機(jī)深林啦
?隨機(jī)：數(shù)據(jù)采樣隨機(jī)，特征選擇隨機(jī)
?森林：很多決策樹并行放在一起

隨機(jī)森林

• 構(gòu)造樹模型：
  
• 由于二重隨機(jī)性，使得每個(gè)樹基本上都不會一樣，最終的結(jié)果也會不一樣。

Bagging模型

• 樹模型：
  
• 之所以要進(jìn)行隨機(jī)，是要保證泛化能力，如果樹都一樣，那就沒意義了！

隨機(jī)森林優(yōu)勢

• 它能夠處理很高維度（feature很多）的數(shù)據(jù)，并且不用做特征選擇
• 在訓(xùn)練完后，它能夠給出哪些feature比較重要。
• 容易做成并行化方法，速度比較快。
• 可以進(jìn)行可視化展示，便于分析。
  
  Bagging模型
• KNN模型：
  
• KNN就不太適合，因?yàn)楹茈y去隨機(jī)讓泛化能力變強(qiáng)！

Bagging模型

• 樹模型：
  
• 理論上越多的樹效果會越好，但實(shí)際上基本超過一定數(shù)量就差不多上下浮動(dòng)了。

Boosting算法

• 典型代表：AdaBoost， Xgboost
• Adaboost會根據(jù)前一次的分類效果調(diào)整數(shù)據(jù)權(quán)重。
• 解釋：如果某一個(gè)數(shù)據(jù)在這次分錯(cuò)了，那么在下一次我就會給它更大的權(quán)重。
• 最終的結(jié)果：每個(gè)分類器根據(jù)自身的準(zhǔn)確性來確定各自的權(quán)重，再合體。

Adaboost工作流程

• 每一次切一刀。
• 最終合在一起。
• 弱分類器這就升級了。
  
  Stacking模型
• 堆疊：很暴力，拿來一堆直接上（各種分類器都來了）
• 可以堆疊各種各樣的分類器（KNN,SVM,RF等等）
• 分階段：第一階段得出各自結(jié)果，第二階段再用前一階段結(jié)果訓(xùn)練。
• 為了刷結(jié)果，不擇手段。

Stacking模型

• 堆疊在一起確實(shí)能使得準(zhǔn)確率提升，但是速度是問題
  集成算法是競賽與論文神器，當(dāng)我們更關(guān)注與結(jié)果時(shí)不妨來實(shí)時(shí)。

總結(jié)

以上是生活随笔為你收集整理的2.1.决策树和随机森林的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。