python的決策樹和隨機森林,隨機森林特徵重要性python

本文目錄一覽：

• 1、決策樹、隨機森林
• 2、決策樹與隨機森林（三）–提升
• 3、12-分類演算法-決策樹、隨機森林
• 4、決策樹（DecisionTree）和隨機森林（Random Forests）
• 5、決策樹與隨機森林

決策樹、隨機森林

在了解樹模型之前，自然想到樹模型和線性模型，他們有什麼區別呢？

決策樹與邏輯回歸的分類區別也在於此。

樹形模型更加接近人的思維方式，可以 產生可視化的分類規則，產生的模型具有可解釋性 。樹模型擬合出來的函數其實是 分區間的階梯函數 。

決策樹（decision tree）是一種基本的分類與回歸方法，此處主要討論分類的決策樹。決策樹是一種十分常用的分類方法，屬於有監督學習（Supervised Learning）。所謂有監督學習，就是給出一堆樣本，每個樣本都有一組屬性和一個分類結果，也就是分類結果已知，那麼通過學習這些樣本得到一個決策樹，這個決策樹能夠對新的數據給出正確的分類。

決策樹是一種樹形結構，它主要有三種不同的節點：

決策樹演算法主要包括三個部分： 特徵選擇、樹的生成、樹的剪枝。

比較常用的決策樹演算法有ID3，C4.5和CART（Classification And Regression Tree），CART的分類效果一般優於其他決策樹。

樣本數量，特徵數量上面，一開始需要注意的：

當熵中的概率由數據估計(特別是最大似然估計)得到時，所對應的熵稱為 經驗熵 (empirical entropy)。

什麼叫由數據估計？比如有10個數據，一共有兩個類別，A類和B類。其中有7個數據屬於A類，則該A類的概率即為十分之七。其中有3個數據屬於B類，則該B類的概率即為十分之三。淺顯的解釋就是，這概率是我們根據數據數出來的。

訓練數據集D，則訓練數據集D的經驗熵為H(D)，|D|表示其樣本容量，及樣本個數。設有K個類Ck，k = 1,2,3,···,K，|Ck|為屬於類Ck的樣本個數，這經驗熵公式可以寫為：

信息增益表示得知特徵X的信息而使得類Y的信息不確定性減少的程度。

條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性，隨機變數X給定的條件下隨機變數Y的條件熵(conditional entropy) H(Y|X)，定義X給定條件下Y的條件概率分布的熵對X的數學期望：

當熵和條件熵中的概率由數據估計（特別是極大似然估計）得到時，所對應的分別為經驗熵和經驗條件熵，此時如果有0概率，令0log0=0。

信息增益

一般地， 熵H(D)與條件熵H(D|A)之差成為互信息(mutual information) 。決策樹學習中的信息增益等價於訓練數據集中類與特徵的互信息。

信息增益比

Gini 指數

舉例計算Gini指數（不純度）

這個分類結果明顯並不是很好，因為它沒有將見面與不見面完全的分開，在演算法中，當然不能憑我們的「感覺」去評價分類結果的好壞。我們需要用一個數去表示。（具體數值代入上面的基尼指數計算公式）

信息增益 vs 信息增益比

Gini 指數 vs 熵

ID3演算法的核心是在決策樹各個結點上對應信息增益準則選擇特徵，遞歸地構建決策樹。

具體方法是：

1）從根結點(root node)開始，對結點計算所有可能的特徵的信息增益，選擇信息增益最大的特徵作為結點的特徵。

2）由該特徵的不同取值建立子節點，再對子結點遞歸地調用以上方法，構建決策樹；直到 所有特徵的信息增益均很小或沒有特徵可以選擇 為止；

3）最後得到一個決策樹。

ID3相當於用 極大似然法進行概率模型的選擇 。

與ID3演算法相似，但是做了改進，將信息增益比作為選擇特徵的標準。

CART 的全稱是分類與回歸樹。從這個名字中就應該知道，CART 既可以用於分類問題，也可以用於回歸問題。

回歸樹中，使用平方誤差最小化準則來選擇特徵並進行劃分。每一個葉子節點給出的預測值，是劃分到該葉子節點的所有樣本目標值的均值，這樣只是在給定劃分的情況下最小化了平方誤差。

要確定最優化分，還需要遍歷所有屬性，以及其所有的取值來分別嘗試劃分並計算在此種劃分情況下的最小平方誤差，選取最小的作為此次劃分的依據。由於回歸樹生成使用平方誤差最小化準則，所以又叫做最小二乘回歸樹。

ID3

熵表示的是數據中包含的信息量大小。熵越小，數據的純度越高，也就是說數據越趨於一致，這是我們希望的劃分之後每個子節點的樣子。

信息增益 = 劃分前熵 – 劃分後熵。信息增益越大，則意味著使用屬性 a 來進行劃分所獲得的 「純度提升」 越大 **。也就是說，用屬性 a 來劃分訓練集，得到的結果中純度比較高。

ID3 僅僅適用於二分類問題。ID3 僅僅能夠處理離散屬性。

C4.5 克服了 ID3 僅僅能夠處理離散屬性的問題，以及信息增益偏向選擇取值較多特徵的問題，使用信息增益比來選擇特徵。 信息增益比 = 信息增益 / 劃分前熵 選擇信息增益比最大的作為最優特徵。

C4.5 處理連續特徵是先將特徵取值排序，以連續兩個值中間值作為劃分標準。嘗試每一種劃分，並計算修正後的信息增益，選擇信息增益最大的分裂點作為該屬性的分裂點。

CART 與 ID3，C4.5 不同之處在於 CART 生成的樹必須是二叉樹 。也就是說，無論是回歸還是分類問題，無論特徵是離散的還是連續的，無論屬性取值有多個還是兩個，內部節點只能根據屬性值進行二分。

決策樹生成演算法遞歸的產生決策樹，直到不能繼續下去為止，這樣產生的樹往往對訓練數據的分類很準確，但對未知測試數據的分類缺沒有那麼精確，即會出現過擬合現象。過擬合產生的原因在於在學習時過多的考慮如何提高對訓練數據的正確分類，從而構建出過於複雜的決策樹，解決方法是考慮決策樹的複雜度，對已經生成的樹進行簡化。

剪枝（pruning）：從已經生成的樹上裁掉一些子樹或葉節點，並將其根節點或父節點作為新的葉子節點，從而簡化分類樹模型。

實現方式：極小化決策樹整體的損失函數或代價函數來實現

決策樹學習的損失函數定義為：

鑒於決策樹容易過擬合的缺點，隨機森林採用多個決策樹的投票機制來改善決策樹，我們假設隨機森林使用了m棵決策樹，那麼就需要產生m個一定數量的樣本集來訓練每一棵樹，如果用全樣本去訓練m棵決策樹顯然是不可取的，全樣本訓練忽視了局部樣本的規律，對於模型的泛化能力是有害的。

產生n個樣本的方法採用Bootstraping法，這是一種有放回的抽樣方法，產生n個樣本。

而最終結果採用Bagging的策略來獲得，即多數投票機制。

隨機森林的生成方法：

1.從樣本集中通過重採樣的方式產生n個樣本

2.假設樣本特徵數目為a，對n個樣本選擇a中的k個特徵，用建立決策樹的方式獲得最佳分割點

3.重複m次，產生m棵決策樹

4.多數投票機制來進行預測

（需要注意的一點是，這裡m是指循環的次數，n是指樣本的數目，n個樣本構成訓練的樣本集，而m次循環中又會產生m個這樣的樣本集）

隨機森林是一個比較優秀的模型，在我的項目的使用效果上來看，它對於多維特徵的數據集分類有很高的效率，還可以做特徵重要性的選擇。運行效率和準確率較高，實現起來也比較簡單。 但是在數據噪音比較大的情況下會過擬合，過擬合的缺點對於隨機森林來說還是較為致命的。

機器學習實戰（三）——決策樹

決策樹與隨機森林（三）–提升

轉自July–4月機器學習演算法班

由決策樹和隨機森林引發思路

隨機森林的決策樹分布採樣建立，相對獨立。

思考：

前m-1棵樹是否會影響第m棵樹？

各個決策樹組成決策森林後，最後的投票過程可否在建立決策樹時決定呢？

提升

Adaboost/GDBT

提升的概念：提升是一個機器學習技術，可以用於回歸和分類，它每一步產生一個弱預測模型（如決策樹），並加權累加到總模型中；如果每一步的弱預測模型生成都是依據 損失函數的梯度方向 ，則稱之為提升（Gradient boosting）

梯度提升演算法首先給定一個目標損失函數，它的定義域是所有可行的 弱函數集合（基函數） ；提升演算法通過迭代的選擇一個 負梯度方向上 的基函數來逐漸逼近 局部極小值 。這種在 函數域 的梯度提升觀點對機器學習的很多領域有深刻影響

提升的理論意義：如果一個問題存在弱分類器，則可以通過提升的辦法得到強分類器。

Adaboost

Adaboost，是英文「Adaptive Boosting」自適應增強的縮寫，是一種機器學習方法

其自適應性在於：前一個分類器分錯的樣本會被用來訓練下一個分類器。AdaBoost方法對於雜訊數據和異常數據很敏感。

但在一些問題中，AdaBoost方法相對於大多數其他學習演算法而言，不會很容易出現過擬合現象。

梯度提升決策樹GBDT

梯度提升的典型基函數即決策樹（尤其是CART）

在第m步的梯度提升是根據偽殘差數據計算決策樹tm(x)。

參數設置與正則化

對於訓練集擬合過高會降低模型的泛化能力，需要使用 正則化 技術來降低過擬合。

–對於複雜模型增加懲罰項，如：模型複雜度正比於葉節點數目或者葉節點預測值的平方和等。

–用於決策樹剪枝

葉節點數目控制了樹的層數，一般選擇4J8

葉節點包含的最少樣本數目

防止出現過小的葉節點，降低預測方差

梯度提升迭代次數M：

增加M可降低訓練集的損失值，有過擬合風險

交叉驗證

12-分類演算法-決策樹、隨機森林

決策樹

生活中的決策樹模型：

顯然：判斷依據的重要性從前往後越來越小

信息的度量和作用

在不知道任何信息的情況下猜測32支球隊中的冠軍：如果用二分法，需要猜5次，即需要的代價為5bit，這個5bit我們稱之為信息熵（H）

5 = -(1/32log(1/32) + 1/32log(1/32) + … + 1/32log(1/32))

公式：概率log概率 之和

如果我們知道了一些球隊的信息，需要的代價會小於5bit

5 -(1/4log(1/32) + 1/8log(1/32) + … + 1/24log(1/32))

信息熵越大(比如，當每個球隊的奪冠幾率相等)，不確定性越大

結合決策數，之所以我們先對某些條件進行判斷，是因為能夠減少我們更多的不確定性

決策樹的劃分依據——信息增益

信息增益：當得知一個條件之後，減少的信息熵的大小

決策樹的api

在泰坦尼克號和titanic2數據幀描述泰坦尼克號上的個別乘客的生存狀態。在泰坦尼克號的數據幀不包含從劇組信息，但它確實包含了乘客的一半的實際年齡。關於泰坦尼克號旅客的數據的主要來源是百科全書Titanica。這裡使用的數據集是由各種研究人員開始的。其中包括許多研究人員創建的旅客名單，由Michael A. Findlay編輯。

我們提取的數據集中的特徵是票的類別，存活，乘坐班，年齡，登陸，home.dest，房間，票，船和性別。乘坐班是指乘客班（1，2，3），是社會經濟階層的代表。

其中age數據存在缺失。

決策樹部分圖例：

決策樹的優缺點以及改進

優點：

缺點：

改進：

集成學習方法

集成學習通過建立幾個模型組合的來解決單一預測問題。它的工作原理是 生成多個分類器/模型 ，各自獨立地學習和作出預測。這些預測最後結合成單預測，因此優於任何一個單分類的做出預測。

隨機森林是一個包含多個決策樹的分類器，並且其輸出的類別是由個別樹輸出的類別的眾數而定。

隨機森林建立多個決策樹的過程：

ps：為什麼要隨機抽樣？避免每顆樹的訓練集的一樣，那麼最終訓練出的上面的分類結果也是完全一樣的

隨機森林案例：

隨機森林的優點：

隨機森林幾乎沒有缺點

決策樹（DecisionTree）和隨機森林（Random Forests）

    令N為訓練樣例的個數，則單棵決策樹的輸入樣例的個數為N個從訓練集中有放回的 隨機 抽取N個訓練樣例。

    令訓練樣例的輸入特徵的個數為M，我們在每顆決策樹的每個節點上進行分裂時，從M個輸入特徵里 隨機 選擇m個輸入特徵，且m遠遠小於M。然後從這m個輸入特徵里選擇一個最好的進行分裂。 m在構建決策樹的過程中不會改變 。

構建決策樹的演算法主要有以下三種，且根據決策樹的輸出結果，決策樹可以分為 分類樹 和 回歸樹 ，分類樹輸出的結果為具體的類別，而回歸樹輸出的結果為一個確定的數值。其中 ID3 和 C4.5 是分類樹， CART 是分類回歸樹，且 在ID3 和 C4.5 中，特徵（屬性）只能選一次，而 CART 沒有這樣的要求 ：

    a. ID3    在決策樹生成過程中，以 信息增益 為特徵選擇的準則。

    b. C4.5    在決策樹生成過程中，以 信息增益比 為特徵選擇的準則。

    c. CART    對回歸樹用 平方誤差最小化準則 ，對分類樹用 基尼指數 （Gini index） 最小化準則 ，進行特徵選擇，生成二叉樹。

例：

圖1左中的信息增益InfoGain1 及信息增益比 InfoRatio1為：

同理，圖1右的信息增益 InfoGain2 及 InfoRatio2 分別為：

由於 InfoGain1  InfoGain2， 所以由ID3演算法選擇第一種方法；

由於InfoRatio1  InfoRatio2 ，所以根據C4.5演算法選擇第一種方法

    當節點的數據量小於一個指定的數量時，不繼續分裂。兩個原因：一是數據量較少時，再做分裂容易強化雜訊數據的作用；二是降低樹生長的複雜性。提前結束分裂一定程度上有利於降低過擬合的影響。

    由上述可知，熵和基尼值的大小表示數據的複雜程度，當熵或者基尼值過小時，表示數據的純度比較大，如果熵或者基尼值小於一定程度數，節點停止分裂。

    節點的深度可以理解為節點與決策樹跟節點的距離，如根節點的子節點的深度為1，因為這些節點與跟節點的距離為1，子節點的深度要比父節點的深度大1。決策樹的深度是所有葉子節點的最大深度，當深度到達指定的上限大小時，停止分裂。

    按照1生成t個決策樹之後，對於每個新的測試樣例，綜合多個決策樹的分類結果來作為隨機森林的分類結果。

    （1）目標特徵為 數字類型 ：取t個決策樹的 平均值 作為分類結果。

    （2）目標特徵為 類別類型 ： 少數服從多數 ，取單棵樹分類結果最多的那個類別作為整個隨機森林的分類結果。

在隨機森林中，無需交叉驗證來評價其分類的準確性，隨機森林自帶 OOB（out-of-bag）錯誤估計 ：

OOB：在構造單棵決策樹時我們只是隨機有放回的抽取了N個樣例，所以可以用沒有抽取到的樣例來測試這棵決策樹的分類準確性，這些樣例大概佔總樣例數目的三分之一。

所以對於每個樣例j，都有大約三分之一的決策樹（記為SetT（j））在構造時沒用到該樣例，我們就用這些決策樹來對這個樣例進行分類。我們對於所有的訓練樣例 j，用SetT（j）中的樹組成的森林對其分類，然後看其分類結果和實際的類別是否相等，不相等的樣例所佔的比例就是OOB錯誤估計。OOB錯誤估計被證明是無偏的。

決策樹與隨機森林

決策樹（decision tree）是一種基本的分類與回歸方法，本文主要討論用於分類的決策樹。決策樹模型呈樹形結構，在分類問題中，表示基於特徵對實例進行分類的過程。它可以認為是if-then規則的集合，也可以認為是定義在特徵空間與類空間上的條件概率分布，其主要優點是模型具有可讀性，分類速度快。決策樹學習通常包括三個步驟：特徵選擇，決策樹的生成和決策樹的修剪。而隨機森林則是由多個決策樹所構成的一種分類器，更準確的說，隨機森林是由多個弱分類器組合形成的強分類器。

本文將先對決策樹特徵選擇的演算法ID3, C4.5和CART進行計算，然後介紹決策樹的剪枝策略，最後介紹隨機森林。

在 資訊理論 中， 條件熵 描述了在已知第二個隨機變數X的前提下，隨機變數Y的信息熵還剩多少。基於X條件的Y的信息熵，用H(Y|X)表示。

如果H(Y|X=x)為變數Y在變數X取特定值x條件下的熵，那麼H(Y|X)就是H(Y|X=x)在X取遍所有可能的x後取平均的結果。

首先需要知道的是熵的公式：

條件熵的推導公式如下：

決策樹分類從根節點開始，對實例的某一特徵進行測試，根據測試結果將實例分配到其子節點。每一個子節點對應著該特徵的一個取值。如此遞歸地對實例進行測試並分配，直至達到葉節點，最後將實例分配到葉節點的類中。

決策樹學習的演算法通常是一個遞歸地選擇最優特徵，並根據該特徵對訓練數據進行劃分。如果利用一個特徵進行分類的結果與隨機分類的結果沒有很大差別，則稱這個特徵是沒有分類能力的。通常特徵選擇的準則是信息增益或信息增益比，特徵選擇的常用演算法有ID3，C4.5，CART。

信息增益表示得知特徵A的信息而使得數據X的信息的不確定性的程度。

信息增益定義：特徵A對訓練數據集D的信息增益g(D, A)定義為集合D的經驗熵H(D)與給定特徵A的條件下D的經驗條件熵H(D|A)之差，即：

根據信息增益選擇特徵的方法是：對於給定數據集D，計算其每個特徵的信息增益，並比較他們的大小，選擇信息增益最大的特徵。使用信息增益選擇特徵的演算法稱為C3演算法。

信息增益值的大小是相對於訓練數據集而言的，並沒有絕對意義。在分類為題困難時，也就是說在訓練數據集的經驗熵大的時候，信息增益值會偏大。反之，信息增益值會偏小。因此，使用信息增益比可以對這一問題進行校正，這是另一種特徵選擇演算法，也即C4.5演算法。

信息增益比定義 ：特徵A對訓練數據集D的信息增益比g R (D, A)定義為其信息增益g(D, A)與訓練集D的經驗熵之比：

基尼指數是CART分類樹用來選擇最優特徵的演算法，同時決定了該特徵的最優二值切分點。

定義：假設有K個類，樣本點屬於第k類的概率為p k ，則概率分布的基尼指數定義：

對於給定的樣本集合D，其基尼指數為：

一個特徵的信息增益/基尼係數越大，表明特徵對樣本的熵減少的能力更強，這個特徵使得數據由不確定性變成確定性的能力越強。

決策樹生成演算法產生的決策樹對於訓練數據的分類往往很準確，但對於未知數據的分類卻沒有這麼準確，即容易出現過擬合情況。解決的辦法便是考慮樹的複雜度，對已生成的樹進行剪枝簡化。

決策樹的剪枝往往通過極小化決策樹整體的損失函數來實現。

設樹T的葉節點個數為|T|，t是樹T的葉節點，該葉節點有N t 個樣本點，其中k類的樣本點有N tk 個，k=1,2,3…K, H t (T)為葉節點t上的經驗熵, α=0為參數，則決策樹學習的損失函數可以定義為：

損失函數中C(T)表示模型對訓練數據的預測誤差，也即擬合程度。|T|表示模型複雜度，即節點越多模型越複雜，使用參數α來控制兩者之間的影響。α越大模型越簡單，對數據擬合差；α越小模型越複雜，對數據擬合性好；α=0時則不考慮模型複雜度。

因此，剪枝就是在確定了α時，選擇損失函數最小的樹。

參考：

《統計學習方法》李航

機器學習. 鄒博