close

清華大數據軟件團隊官方微信公眾號
來源：知乎

本文約5000字，建議閱讀5分鐘

本文為你系統總結關於決策樹、隨機森林等相關內容。

一、決策樹

決策樹是一個有監督分類模型，本質是選擇一個最大信息增益的特徵值進行輸的分割，直到達到結束條件或葉子節點純度達到閾值。下圖是決策樹的一個示例圖：

根據分割指標和分割方法，可分為：ID3、C4.5、CART算法。

1.ID3算法：以信息增益為準則來選擇最優劃分屬性

信息增益的計算是基於信息熵（度量樣本集合純度的指標）

信息熵越小，數據集的純度越大

假設基於數據集上建立決策樹，數據有個類別：

公式(1)中：

表示第K類樣本的總數占數據集D樣本總數的比例。

公式(2)表示是以特徵A作為分割的屬性，得到的信息熵：Di表示的是以屬性A為劃分，分成n個分支，第i個分支的節點集合。因此，該公式求得的是以屬性A為劃分，n個分支的信息熵總和。

公式(3)是以A為屬性劃分前和劃分後的信息熵差值，也就是信息增益，越大越好。

假設每個記錄有一個屬性'ID',若按照ID進行分割的話，在這個屬性上，能夠取得的特徵值是樣本數，特徵數目太多，無論以哪一個ID進行劃分，葉子節點的值只會有一個，純度很大，得到的信息增益很大，這樣劃分出來的決策樹沒有意義，即，ID3偏向於取值較多的屬性進行分割，存在一定的偏好。為減少這一影響，有學者提出了C4.5算法。

2. C4.5基於信息增益率準則 選擇最有分割屬性的算法

信息增益率通過引入一個被稱為分裂信息(Split information)的懲罰項來懲罰取值較多的屬性：

,

其中，IV(a)是由屬性A的特徵值個數決定的，個數越多，IV值越大，信息增益率越小，這樣就可以避免模型偏好特徵值多的屬性，如果簡單按這個規則分割，模型又會偏好特徵值少的特徵，因此C4.5決策樹先從候選劃分屬性中找出信息增益高於平均水平的屬性，在從中選擇增益率最高的。

對於連續值屬性來說，可取值數目不再有限，因此可以採用離散化技術（如二分法）進行處理。將屬性值從小到大排序，然後選擇中間值作為分割點，數值比它小的點被劃分到左子樹，數值不小於它的點被分到右子樹，計算分割的信息增益率，選擇信息增益率最大的屬性值進行分割。

3. CART:以基尼係數為準則選擇最優劃分屬性，可用於分類和回歸

CART是一棵二叉樹，採用二元切分法，每次把數據分成兩份，分別進入左子樹、右子樹。並且每個非葉子節點都有兩個孩子，所以CART的葉子節點比非葉子節點多一。相比於ID3和C4.5，CART的應用要多一些，既可以用於分類也可以用於回歸。CART分類時，選擇基尼指數（Gini）為最好的分類特徵，gini描述的是純度，與信息熵含義類似，CART中每次迭代都會降低基尼係數。

Gini(D)反映了數據集D的純度，值越小，純度越高。我們在候選集合中選擇使得劃分後基尼指數最小的屬性作為最優化分屬性。

分類樹和回歸樹

先說分類樹，ID3、C4.5在每一次分支時，是窮舉每一個特徵屬性的每一個閾值，找到使得按照特徵值<=閾值，和特徵值>閾值分成的兩個分支的熵最大的特徵和閾值。按照該標準分支得到兩個新節點，用同樣的方法進行分支，直到所有人被分入性別唯一的葉子節點，或達到預設的終止條件，若最終葉子節點中性別不唯一，則以多數人的性別作為該葉子節點的性別。

回歸樹總體流程也是類似，不過在每個節點(不一定是葉子節點)都會得到預測值，以年齡為例，該預測值等於屬於這個節點的所有人年齡的平均值。分支時窮舉每個特徵的每個閾值，找最好的分割點，但衡量的標準變成了最小化均方誤差，即（每個人的年齡-預測年齡）^2 的總和 / N，或者說是每個人的預測誤差平方和 除以 N。這很好理解，被預測出粗的人數越多，錯的越離譜，均方誤差越大，通過最小化均方誤差找最靠譜的分支依據。分支直到每個葉子節點上的人的年齡都唯一(這太難了)，或者達到預設的終止條件(如葉子個數上限)，若最終葉子節點上人的年齡不唯一，則以該節點上所有人的平均年齡作為該葉子節點的預測年齡。

二、隨機森林

先補充組合分類器的概念，將多個分類器的結果進行多票表決或取平均值，以此作為最終的結果。

1.構建組合分類器的好處：

(1)提升模型精度：整合各個模型的分類結果，得到更合理的決策邊界，減少整體錯誤呢，實現更好的分類效果：

(2)處理過大或過小的數據集：數據集較大時，可將數據集劃分成多個子集，對子集構建分類器；當數據集較小時，通過自助採樣(bootstrap)從原始數據集採樣產生多組不同的數據集，構建分類器。

(3)若決策邊界過於複雜，則線性模型不能很好地描述真實情況。因此，現對於特定區域的數據集，訓練多個線性分類器，再將他們集成。

(4)比較適合處理多源異構數據（存儲方式不同（關係型、非關係型），類別不同（時序型、離散型、連續型、網絡結構數據））
隨機森林是一個多決策樹的組合分類器，隨機主要體現在兩個方面：數據選取的隨機性和特徵選取的隨機性。

(1)數據的隨機選取

第一，從原始數據集中採取有放回的抽樣(bootstrap),構造子數據集，子數據集扥數量和原始數據集的數量一樣。不同的子數據集的元素可以重複，同一個子數據集中的元素也可以重複。

第二，利用子數據集構建子決策樹，將這個數據放到每個子決策樹中，每個子決策樹輸出一個結果。最後，如果有了新的數據需啊喲通過隨機森林得到分類結果，就可以通過子決策樹的判斷結果來投票，得到隨機森林的輸出結果。如下圖，假設隨機森林中有3棵子決策樹，2棵子樹的分類結果是A類，1棵子樹的分類結果是B類，那麼隨機森林的分類結果就是A類。

(2)待選特徵的隨機選取

類似於數據集的隨機選取，隨即森林中的子樹的每一個分裂過程並未用到所有的待選特徵，而是從所有的待選特徵中隨機選取一定的特徵，之後再在隨機選取的特徵中選擇最優的特徵。這樣能使隨機森林中的決策樹能不同，提升系統的多樣性，從而提升分類性能。

組合樹示例圖

三、GBDT和XGBoost

1.在講GBDT和XGBoost之前先補充Bagging和Boosting的知識。

Bagging是並行的學習算法，思想很簡單，即每一次從原始數據中根據均勻概率分布有放回的抽取和原始數據集一樣大小的數據集合。樣本點可以出現重複，然後對每一次產生的數據集構造一個分類器，再對分類器進行組合。

Boosting的每一次抽樣的樣本分布是不一樣的，每一次迭代，都是根據上一次迭代的結果，增加被錯誤分類的樣本的權重。使模型在之後的迭代中更加注重難以分類的樣本。這是一個不斷學習的過程，也是一個不斷提升的過程，這就是Boosting思想的本質所在。迭代之後，將每次迭代的基分類器進行集成，那麼如何進行樣本權重的調整和分類器的集成是我們需要考慮的關鍵問題。

Boosting算法結構圖

以著名的Adaboost算法舉例：

有一個數據集，樣本大小為N，每一個樣本對應一個原始標籤起初，我們初始化樣本的權重為1/N

計算的是當前數據下，模型的分類誤差率，模型的係數值是基於分類誤差率的

根據模型的分類結果，更新原始數據中數據的分布，增加被錯分的數據被抽中的概率，以便下一次迭代的時候能被模型重新訓練

最終的分類器是各個基分類器的組合

2.GBDT

GBDT是以決策樹(CART)為基學習器的GB算法，是迭代樹而不是分類樹，Boost是"提升"的意思，一般Boosting算法都是一個迭代的過程，每一次新的訓練都是為了改進上一次的結果。有了前面Adaboost的鋪墊，大家應該能很容易理解大體思想。

GBDT的核心是：每一棵樹學習的是之前所有樹結論和的殘差。這個殘差就是一個加預測值後能得真實值的累加量。比如A的真實年齡是18歲，但第一棵樹的預測年齡是12歲，差了6歲，即殘差為6歲。那麼在第二棵樹里我們把A的年齡設為6歲去學習，如果第二棵樹真的能把A分到6歲的葉子節點，那累加兩棵樹的結論就是A的真實年齡；如果第二棵樹的結論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續學習。

3.XGBoost

XGBoostt相比於GBDT來說，更加有效應用了數值優化，最重要是對損失函數（預測值和真實值的誤差）變得更複雜。目標函數依然是所有樹的預測值相加等於預測值。

損失函數如下，引入了一階導數，二階導數：

好的模型需要具備兩個基本要素：一是要有好的精度（即好的擬合程度），二是模型要儘可能的簡單（複雜的模型容易出現過擬合，並且更加不穩定）因此，我們構建的目標函數右邊第一項是模型的誤差項，第二項是正則化項（也就是模型複雜度的懲罰項）

常用的誤差項有平方誤差和邏輯斯蒂誤差，常見的懲罰項有l1，l2正則，l1正則是將模型各個元素進行求和，l2正則是對元素求平方。

每一次迭代，都在現有樹的基礎上，增加一棵樹去擬合前面樹的預測結果與真實值之間的殘差

目標函數如上圖，最後一行畫圈部分實際上就是預測值和真實值之間的殘差

先對訓練誤差進行展開：

xgboost則對代價函數進行了二階泰勒展開，同時用到了殘差平方和的一階和二階導數
再研究目標函數中的正則項：

樹的複雜度可以用樹的分支數目來衡量，樹的分支我們可以用葉子結點的數量來表示

那麼樹的複雜度式子：右邊第一項是葉子結點的數量T，第二項是樹的葉子結點權重w的l2正則化，正則化是為了防止葉子結點過多

此時，每一次迭代，相當於在原有模型中增加一棵樹，目標函數中，我們用wq（x）表示一棵樹，包括了樹的結構以及葉子結點的權重，w表示權重（反映預測的概率），q表示樣本所在的索引號（反映樹的結構）

將最終得到的目標函數對參數w求導，帶回目標函數，可知目標函數值由紅色方框部分決定：

因此，xgboost的迭代是以下圖中gain式子定義的指標選擇最優分割點的：

那麼如何得到優秀的組合樹呢？

一種辦法是貪心算法，遍歷一個節點內的所有特徵，按照公式計算出按照每一個特徵分割的信息增益，找到信息增益最大的點進行樹的分割。增加的新葉子懲罰項對應了樹的剪枝，當gain小於某個閾值的時候，我們可以剪掉這個分割。但是這種辦法不適用於數據量大的時候，因此，我們需要運用近似算法。

另一種方法：XGBoost在尋找splitpoint的時候，不會枚舉所有的特徵值，而會對特徵值進行聚合統計，按照特徵值的密度分布，構造直方圖計算特徵值分布的面積，然後劃分分布形成若干個bucket(桶)，每個bucket的面積相同，將bucket邊界上的特徵值作為split
point的候選，遍歷所有的候選分裂點來找到最佳分裂點。

上圖近似算法公式的解釋：將特徵k的特徵值進行排序，計算特徵值分布，rk（z）表示的是對於特徵k而言，其特徵值小於z的權重之和占總權重的比例，代表了這些特徵值的重要程度，我們按照這個比例計算公式，將特徵值分成若干個bucket，每個bucket的比例相同，選取這幾類特徵值的邊界作為劃分候選點，構成候選集；選擇候選集的條件是要使得相鄰的兩個候選分裂節點差值小於某個閾值

綜合以上所述，我們可以得到xgboost相比於GBDT的創新之處：

1、傳統GBDT以CART作為基分類器，xgboost還支持線性分類器，這個時候xgboost相當於帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）。

2、傳統GBDT在優化時只用到一階導數信息，xgboost則對代價函數進行了二階泰勒展開，同時用到了一階和二階導數。順便提一下，xgboost工具支持自定義代價函數，只要函數可一階和二階求導。

3、xgboost在代價函數裡加入了正則項，用於控制模型的複雜度。正則項里包含了樹的葉子節點個數、每個葉子節點上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來講，正則項降低了模型的variance，使學習出來的模型更加簡單，防止過擬合，這也是xgboost優於傳統GBDT的一個特性。

4、Shrinkage（縮減），相當於學習速率（xgboost中的eta）。每次迭代，增加新的模型，在前面成上一個小於1的係數，降低優化的速度，每次走一小步逐步逼近最優模型比每次走一大步逼近更加容易避免過擬合現象；

5、列抽樣（column subsampling）。xgboost借鑑了隨機森林的做法，支持列抽樣（即每次的輸入特徵不是全部特徵），不僅能降低過擬合，還能減少計算，這也是xgboost異於傳統gbdt的一個特性。

6、忽略缺失值：在尋找splitpoint的時候，不會對該特徵為missing的樣本進行遍歷統計，只對該列特徵值為non-missing的樣本上對應的特徵值進行遍歷，通過這個工程技巧來減少了為稀疏離散特徵尋找splitpoint的時間開銷。

7、指定缺失值的分隔方向：可以為缺失值或者指定的值指定分支的默認方向，為了保證完備性，會分別處理將missing該特徵值的樣本分配到左葉子結點和右葉子結點的兩種情形，分到那個子節點帶來的增益大，默認的方向就是哪個子節點，這能大大提升算法的效率。

8、並行化處理：在訓練之前，預先對每個特徵內部進行了排序找出候選切割點，然後保存為block結構，後面的迭代中重複地使用這個結構，大大減小計算量。在進行節點的分裂時，需要計算每個特徵的增益，最終選增益最大的那個特徵去做分裂，那麼各個特徵的增益計算就可以開多線程進行，即在不同的特徵屬性上採用多線程並行方式尋找最佳分割點。

編輯：王菁
arrow
arrow
    全站熱搜
    創作者介紹
    創作者 鑽石舞台 的頭像
    鑽石舞台

    鑽石舞台

    鑽石舞台 發表在 痞客邦 留言(0) 人氣()