之前分別簡要講了RF與GBDT的原理募壕，現在終于要到XGB绽昼，這個算法之前也是困擾了我好久芭商，現在對它進行一個大概的梳理派草。
基于陳天奇的這篇文章，經典之作：https://arxiv.org/pdf/1603.02754v1.pdf

算法原理

首先我們知道樹的集成基本原理是多個分類器結果相加铛楣，用陳天奇的例子來說就是：

圖一

考慮這樣一種情況，我們有一個數據集簸州，包含m個樣本n個特征

根據樹的集成思想钳踊，為了得到每個樣本i最終的預測結果yi，我們需要使用K個additive functions

• 這樣我們就能把上面的每個fk每棵樹的結構對應起來了
  

• 這樣對于每一個樣本面氓，我們都可以把它分到某一棵樹的葉子節(jié)點i上兵钮，得到它在這棵樹上的預測分數wi
  這時我們可以得到帶正則的損失函數為：
  

• 在講解XGB具體的迭代過程之前，我們需要知道XGB也是一種gradient boosting的方法舌界，聯想到之前的GBDT掘譬，第t輪次的預測結果應該是等于t-1輪次的結果加上負梯度。接下來我們來看在XGB中呻拌，第t輪次的預測結果是怎么計算的葱轩。

• 針對第i個樣本的預測分數yi，其在第t輪次的預測結果為

  
  記第t輪次的結果可以表示為上一輪次的結果加上一個ft:
  因此我們在這一輪的目的就是要找出這樣的一個ft，使得損失函數最醒ス啊：
  對于凸函數L我們采用二階泰勒展開：
  關于gi和hi分別有：
  由于上一輪次的預測值已經確定了垃喊，我們去掉常數可以得到在第t輪次的損失函數：
  進一步將后面的損失函數展開：
  
  需要注意的是這里面的ij代筆第j個葉子節(jié)點上的所有樣本點集合，對于每一個樣本點i袜炕，我們的ft表示其在t輪次的預測分數本谜，因此具體到每個葉子節(jié)點上，則有因此我們可以將上圖中第一個等式的求和號換成第二個等式的求和號偎窘。即從以樣本為計數單位換為以每個葉子節(jié)點為計數單位乌助。

• 接下來就變得簡單了，我們可以認為這是一個關于wj的二次函數陌知，求導可得：

  wj
  損失函數最小值
  關于gi和hi他托，對于一顆確定的樹，我們是可以計算的纵诞，如
  計算gi hi
  上面的Lq(t)非常重要上祈，他可以評估某棵結構為q的樹的質量，類似于決策樹中的不純度浙芙，它可以作為建樹的評判標準登刺。我們馬上可以想到，是不是遍歷所有的樹結構q嗡呼，然后選出其中根據公式Lq(t)計算的損失函數最小的就可以了呢纸俭？答案是否定的，一棵樹可以非常復雜南窗，遍歷所有的樹結構顯然是不可能的揍很。

因此我們選取一種貪心算法來分裂，由于訓練數據可能有很多特征万伤，構建一棵樹可能有許多種不同的構建形式窒悔，我們不可能枚舉所有可能的樹結構q來一一計算它的分值。貪心算法從一個單獨樹葉開始迭代的增加分支敌买。假設ileft和iright是分割之后節(jié)點的左側和右側實例集合简珠，令I = ileft U iright，那么在節(jié)點分割后的損失減少量為：

這個公式通常用于在實踐中評估候選分裂節(jié)點是不是應該分裂虹钮。

過擬合—Shrinkage and Column Subsampling

上面介紹算法原理部分已經指出損失函數中帶有正則項聋庵，但是XGB中還有一些防止過擬合的方法。

• 其中一種是Shrinkage方法芙粱，這種方法會在每輪迭代中的葉子節(jié)點分數wj上增加一個縮減因子祭玉，這樣會減少每棵單獨的樹和其葉子節(jié)點對未來的樹的影響。
• 另外一種方法是Column Subsampling春畔，這中對特征進行子采樣的方法之前在RF中已經介紹過脱货，它是每次建樹時抽取一部分特征來建樹岛都，這里選擇特征可以是根據GINI指數來選擇，即選擇GINI指數較大（即信息量最大蹭劈，最不純的特征）的一些特征來建樹（當然這里前提是基分類器是CART的情況）他可以起到防止過擬合作用疗绣，甚至還有助于加快并行算法的運行速度。

選取分裂節(jié)點

Basic Exact Greedy Algorithm

• 對于一個單獨的特征铺韧，我們先將它的所有取值排序多矮，然后依次選取分裂節(jié)點計算Lsplit，選取最大的節(jié)點進行分裂哈打。
• 之前一直愁于找不到具體的計算來練練手塔逃，想要自己真正用XGB算法來建幾棵樹，這里有一篇博客講的非常好料仗，安利一下（除了一些公式的拼寫問題）
  https://blog.csdn.net/qq_22238533/article/details/79477547

Approximate Algorithm

exact greedy algorithm使用貪婪算法非常有效的找到分裂節(jié)點湾盗，但是當數據量很大時，數據不可能一次性的全部讀入到內存中立轧，或者在分布式計算中格粪，這樣不可能事先對所有值進行排序，且無法使用所有數據來計算分裂節(jié)點之后的樹結構得分氛改。為解決這個問題帐萎，近似算法被應用進來。近似算法首先按照特征取值的統(tǒng)計分布的一些百分位點確定一些候選分裂點胜卤，然后算法將連續(xù)的值映射到 buckets中疆导，然后匯總統(tǒng)計數據，并根據聚合統(tǒng)計數據在候選節(jié)點中找到最佳節(jié)點葛躏。

這個近似算法其實在陳天奇的論文是最難的部分了澈段，因為這里好像也涉及到XGB的分布式與并行實現，會有一個buckets分桶的思想舰攒，好像也是面試問XGB最高階的問題了

• 對于每個特征败富，只考察分位點，減少計算復雜度摩窃。
• 該算法會首先根據特征分布的百分位數 (percentiles of feature distribution)兽叮，提出候選劃分點 (candidate splitting points)。接著偶芍，該算法將連續(xù)型特征映射到由這些候選點劃分的分桶(buckets) 中，聚合統(tǒng)計信息德玫，基于該聚合統(tǒng)計找到在 proposal 間的最優(yōu)解匪蟀。
• Global：學習每棵樹前，提出候選切分點宰僧；
• Local：每次分裂前材彪，重新提出候選切分點；
  算法圖看得我眼都花了：
  
  
  算法講解

處理缺失值

Sparsity-aware Split Finding

XGB處理缺失值的方式其實很簡單，就是比較把缺失值放在左節(jié)點還是右節(jié)點好段化，比較的準則就是之前的Lsplit（還記得之前面試時被問到這個問題嘁捷，當時還不會答...）

首先需要注意到兩個集合一個是I,其包含所有的樣本（包括含空缺值的樣本）。
Ik是不包含空缺值樣本的集合显熏。
在計算總的G和H時用的是IＰ巯！也就說空缺值的一階導數和二階導數已經包含進去了喘蟆。
可以看到內層循環(huán)里面有兩個for缓升，第一個for是從Ik中把特征取值從小到大排序，這里不包括空缺值樣本蕴轨，然后從小到大進行掃描港谊，這個時候在計算GR的時候是用總的G減去GL，HR也是同樣用總的H減去HL,這意味著把空缺樣本歸到了右子結點橙弱。

第二個for相反過來歧寺，把空缺樣本歸到了左子結點。
只要比較這兩次最大增益出現在第一個for中還是第二個for中就可以知道對于空缺值的分裂方向棘脐，這就是xgboost如何學習空缺值的思想斜筐。

XGB的主要原理和一些優(yōu)點就先講到這兒，之后會補充一些近似算法的詳細方法以及XGB為什么能實現并行運算荆残，有時間的話會補上python中XGB包的參數吧奴艾，畢竟算法工程師的“主要工作”還是—調參，哈哈哈内斯。