【轉】知乎
最近心血來潮，整理了一下和樹有關的方法和模型，請多擔待！
一、決策樹
首先，決策樹是一個有監督的分類模型，其本質是選擇一個能帶來最大資訊增益的特征值進行樹的分割，直到到達結束條件或者葉子結點純度到達一定門檻值。下圖是決策樹的一個簡單例子
按照分割名額和分割方法，決策樹的經典模型可以分為ID3、C4.5以及CART
(1)、ID3：以資訊增益為準則來選擇最優劃分屬性
資訊增益的計算要基于資訊熵(度量樣本集合純度的名額)
資訊熵越小，資料集X的純度越大
是以，假設于資料集D上建立決策樹，資料有K個類别：
公式(1)中：
表示第k類樣本的資料占資料集D樣本總數的比例
公式(2)表示的是以特征A作為分割的屬性，得到的資訊熵：
Di表示的是以屬性A為劃分，分成n個分支，第i個分支的節點集合
是以，該公式求的是以屬性A為劃分，n個分支的資訊熵總和
公式(3)為分割後與分割前的資訊熵的內插補點，也就是資訊增益，越大越好
但是這種分割算法存在一定的缺陷：
假設每個記錄有一個屬性“ID”，若按照ID來進行分割的話，由于ID是唯一的，是以在這一個屬性上，能夠取得的特征值等于樣本的數目，也就是說ID的特征值很多。那麼無論以哪個ID為劃分，葉子結點的值隻會有一個，純度很大，得到的資訊增益會很大，但這樣劃分出來的決策樹是沒意義的。由此可見，ID3決策樹偏向于取值較多的屬性進行分割，存在一定的偏好。為減小這一影響，有學者提出C4.5的分類算法。
(2)、C4.5：基于資訊增益率準則選擇最優分割屬性的算法
資訊增益比率通過引入一個被稱作分裂資訊(Split information)的項來懲罰取值較多的屬性。
上式，分子計算與ID3一樣，分母是由屬性A的特征值個數決定的，個數越多，IV值越大，資訊增益率越小，這樣就可以避免模型偏好特征值多的屬性，但是聰明的人一看就會發現，如果簡單的按照這個規則來分割，模型又會偏向特征數少的特征。是以C4.5決策樹先從候選劃分屬性中找出資訊增益高于平均水準的屬性，在從中選擇增益率最高的。
對于連續值屬性來說，可取值數目不再有限，是以可以采用離散化技術(如二分法)進行處理。将屬性值從小到大排序，然後選擇中間值作為分割點，數值比它小的點被劃分到左子樹，數值不小于它的點被分到又子樹，計算分割的資訊增益率，選擇資訊增益率最大的屬性值進行分割。
(3)CART：以基尼系數為準則選擇最優劃分屬性，可以應用于分類和回歸
CART是一棵二叉樹，采用二進制切分法，每次把資料切成兩份，分别進入左子樹、右子樹。而且每個非葉子節點都有兩個孩子，是以CART的葉子節點比非葉子多1。相比ID3和C4.5，CART應用要多一些，既可以用于分類也可以用于回歸。CART分類時，使用基尼指數(Gini)來選擇最好的資料分割的特征，gini描述的是純度，與資訊熵的含義相似。CART中每一次疊代都會降低GINI系數。
Di表示以A是屬性值劃分成n個分支裡的數目
Gini(D)反映了資料集D的純度，值越小，純度越高。我們在候選集合中選擇使得劃分後基尼指數最小的屬性作為最優化分屬性。
分類樹和回歸樹
提到決策樹算法，很多想到的就是上面提到的ID3、C4.5、CART分類決策樹。其實決策樹分為分類樹和回歸樹，前者用于分類，如晴天/陰天/雨天、使用者性别、郵件是否是垃圾郵件，後者用于預測實數值，如明天的溫度、使用者的年齡等。
作為對比，先說分類樹，我們知道ID3、C4.5分類樹在每次分枝時，是窮舉每一個特征屬性的每一個門檻值，找到使得按照feature<=門檻值，和feature>門檻值分成的兩個分枝的熵最大的feature和門檻值。按照該标準分枝得到兩個新節點，用同樣方法繼續分枝直到所有人都被分入性别唯一的葉子節點，或達到預設的終止條件，若最終葉子節點中的性别不唯一，則以多數人的性别作為該葉子節點的性别。
回歸樹總體流程也是類似，不過在每個節點(不一定是葉子節點)都會得一個預測值，以年齡為例，該預測值等于屬于這個節點的所有人年齡的平均值。分枝時窮舉每一個feature的每個門檻值找最好的分割點，但衡量最好的标準不再是最大熵，而是最小化均方差--即(每個人的年齡-預測年齡)^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
em計算的是目前資料下，模型的分類誤差率，模型的系數值是基于分類誤差率的
根據模型的分類結果，更新原始資料中資料的分布，增加被錯分的資料被抽中的機率，以便下一次疊代的時候能被模型重新訓練
最終的分類器是各個基分類器的組合
(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
Xgboost相比于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的創新之處：
傳統GBDT以CART作為基分類器，xgboost還支援線性分類器，這個時候xgboost相當于帶L1和L2正則化項的邏輯斯蒂回歸(分類問題)或者線性回歸(回歸問題)。
傳統GBDT在優化時隻用到一階導數資訊，xgboost則對代價函數進行了二階泰勒展開，同時用到了一階和二階導數。順便提一下，xgboost工具支援自定義代價函數，隻要函數可一階和二階求導。xgboost在代價函數裡加入了正則項，用于控制模型的複雜度。正則項裡包含了樹的葉子節點個數、每個葉子節點上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來講，正則項降低了模型的variance，使學習出來的模型更加簡單，防止過拟合，這也是xgboost優于傳統GBDT的一個特性。Shrinkage(縮減)，相當于學習速率(xgboost中的eta)。每次疊代，增加新的模型，在前面成上一個小于1的系數，降低優化的速度，每次走一小步逐漸逼近最優模型比每次走一大步逼近更加容易避免過拟合現象；列抽樣(column subsampling)。xgboost借鑒了随機森林的做法，支援列抽樣(即每次的輸入特征不是全部特征)，不僅能降低過拟合，還能減少計算，這也是xgboost異于傳統gbdt的一個特性。忽略缺失值：在尋找splitpoint的時候，不會對該特征為missing的樣本進行周遊統計，隻對該列特征值為non-missing的樣本上對應的特征值進行周遊，通過這個工程技巧來減少了為稀疏離散特征尋找splitpoint的時間開銷指定缺失值的分隔方向：可以為缺失值或者指定的值指定分支的預設方向，為了保證完備性，會分别處理将missing該特征值的樣本配置設定到左葉子結點和右葉子結點的兩種情形，分到那個子節點帶來的增益大，預設的方向就是哪個子節點，這能大大提升算法的效率。并行化處理：在訓練之前，預先對每個特征内部進行了排序找出候選切割點，然後儲存為block結構，後面的疊代中重複地使用這個結構，大大減小計算量。在進行節點的分裂時，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂，那麼各個特征的增益計算就可以開多線程進行，即在不同的特征屬性上采用多線程并行方式尋找最佳分割點。