8.Xgboost
8.Xgboost
8.1.XGBoost算法
https://www.cnblogs.com/mantch/p/11164221.html
XGBoost是陳天奇等人開發的一個開源機器學習項目，高效地實現了GBDT算法并進行了算法和工程上的許多改進，被廣泛應用在Kaggle競賽及其他許多機器學習競賽中并取得了不錯的成績。
說到XGBoost，不得不提GBDT(Gradient Boosting Decision Tree)。因為XGBoost本質上還是一個GBDT，但是力爭把速度和效率發揮到極致，所以叫X (Extreme) GBoosted。包括前面說過，兩者都是boosting方法。
關于GBDT，這里不再提，可以查看我前面一篇的介紹。點此跳轉（https://github.com/NLP-LOVE/ML-NLP/blob/master/Machine%20Learning/3.2%20GBDT/3.2%20GBDT.md）
8.1.1.什么是XGBoost
8.1.2.XGBoost樹的定義
先來舉個例子，我們要預測一家人對電子游戲的喜好程度，考慮到年輕和年老相比，年輕更可能喜歡電子游戲，以及男性和女性相比，男性更喜歡電子游戲，故先根據年齡大小區分小孩和大人，然后再通過性別區分開是男是女，逐一給各人在電子游戲喜好程度上打分，如下圖所示：
就這樣，訓練出了2棵樹tree1和tree2，類似之前gbdt的原理，兩棵樹的結論累加起來便是最終的結論，所以小孩的預測分數就是兩棵樹中小孩所落到的結點的分數相加：2 + 0.9 = 2.9。爺爺的預測分數同理：-1 + （-0.9）= -1.9。具體如下圖所示：
恩，你可能要拍案而起了，驚呼，這不是跟上文介紹的GBDT乃異曲同工么？
事實上，如果不考慮工程實現、解決問題上的一些差異，XGBoost與GBDT比較大的不同就是目標函數的定義。XGBoost的目標函數如下圖所示：
其中：
- 紅色箭頭所指向的L即為損失函數
（比如平方損失函數：） - 紅色方框所框起來的正則項（包括L1正則、L2正則）
- 紅色圓圈所圈起來的為常數項。
- 對于、XGBoost利用泰勒展開三項，做一個近似。表示的是其中一顆回歸樹。
看到這里可能有些讀者會頭暈了，這么多公式，我在這里只做一個簡要式的講解，具體的算法細節和公式求解請查看這篇博文，講得很仔細：通俗理解kaggle比賽大殺器xgboost
XGBoost的核心算法思想不難，基本就是：
1.不斷地添加樹，不斷地進行特征分裂來生長一棵樹，每次添加一個數，其實是學習一個新函數f(x),去擬合上次預測的殘差。
2.當我們訓練完成得到k棵樹，我們要預測一個樣本的分數，其實就是根據這個樣本的特征，在每棵樹中會落到對應的一個葉子節點，每個葉子節點就對應一個分數。
3.最后只需要將每棵樹對應的分數加起來就是該樣本的預測值。
顯然，我們的目標是要使得樹群的預測值盡量接近真實值,而且有盡量大的泛化能力。類似之前GBDT的套路，XGBoost也是需要將多棵樹的得分累加得到最終的預測得分（每一次迭代，都在現有樹的基礎上，增加一棵樹去擬合前面樹的預測結果與真實值之間的殘差）。
那接下來，我們如何選擇每一輪加入什么f呢？答案是非常直接的，選取一個f來使得我們的目標函數盡量最大地降低。這里f可以使用泰勒展開公式近似。
實質是把樣本分配到葉子結點會對應一個obj，優化過程就是obj優化。也就是分裂節點到葉子不同的組合，不同的組合對應不同obj，所有的優化圍繞這個思想展開。到目前為止我們討論了目標函數中的第一個部分：訓練誤差。接下來我們討論目標函數的第二個部分：正則項，即如何定義樹的復雜度。
8.1.3.正則項：樹的復雜度
XGBoost對樹的復雜度包含了兩個部分：
- 一個是樹里面葉子節點的個數T
- 一個是樹上葉子節點的得分w的L2模平方（對w進行L2正則化，相當于針對每個葉結點的得分增加L2平滑，目的是為了避免過擬合）
我們再來看一下XGBoost的目標函數（損失函數揭示訓練誤差 + 正則化定義復雜度）：
我們再來看一下XGBoost的目標函數（損失函數揭示訓練誤差 + 正則化定義復雜度）：
正則化公式也就是目標函數的后半部分，對于上式而言，是整個累加模型的輸出，正則化項是則表示樹的復雜度的函數，值越小復雜度越低，泛化能力越強。
8.1.4.樹該怎樣長
很有意思的一個事是，我們從頭到尾了解了xgboost如何優化、如何計算，但樹到底長啥樣，我們卻一直沒看到。很顯然，一棵樹的生成是由一個節點一分為二，然后不斷分裂最終形成為整棵樹。那么樹怎么分裂的就成為了接下來我們要探討的關鍵。對于一個葉子節點如何進行分裂，XGBoost作者在其原始論文中給出了一種分裂節點的方法：枚舉所有不同樹結構的貪心法
不斷地枚舉不同樹的結構，然后利用打分函數來尋找出一個最優結構的樹，接著加入到模型中，不斷重復這樣的操作。這個尋找的過程使用的就是貪心算法。選擇一個feature分裂，計算loss function最小值，然后再選一個feature分裂，又得到一個loss function最小值，你枚舉完，找一個效果最好的，把樹給分裂，就得到了小樹苗。
總而言之，XGBoost使用了和CART回歸樹一樣的想法，利用貪婪算法，遍歷所有特征的所有特征劃分點，不同的是使用的目標函數不一樣。具體做法就是分裂后的目標函數值比單子葉子節點的目標函數的增益，同時為了限制樹生長過深，還加了個閾值，只有當增益大于該閾值才進行分裂。從而繼續分裂，形成一棵樹，再形成一棵樹，每次在上一次的預測基礎上取最優進一步分裂/建樹。
8.1.5.如何停止樹的循環生成
凡是這種循環迭代的方式必定有停止條件，什么時候停止呢？簡言之，設置樹的最大深度、當樣本權重和小于設定閾值時停止生長以防止過擬合。具體而言，則
1.當引入的分裂帶來的增益小于設定閥值的時候，我們可以忽略掉這個分裂，所以并不是每一次分裂loss function整體都會增加的，有點預剪枝的意思，閾值參數為（即正則項里葉子節點數T的系數）；
2.當樹達到最大深度時則停止建立決策樹，設置一個超參數max_depth，避免樹太深導致學習局部樣本，從而過擬合；
樣本權重和小于設定閾值時則停止建樹。什么意思呢，即涉及到一個超參數-最小的樣本權重和min_child_weight，和GBM的 min_child_leaf 參數類似，
3.但不完全一樣。大意就是一個葉子節點樣本太少了，也終止同樣是防止過擬合；
8.1.6.XGBoost與GBDT有什么不同
除了算法上與傳統的GBDT有一些不同外，XGBoost還在工程實現上做了大量的優化。總的來說，兩者之間的區別和聯系可以總結成以下幾個方面。
?GBDT是機器學習算法，XGBoost是該算法的工程實現。
?在使用CART作為基分類器時，XGBoost顯式地加入了正則項來控制模 型的復雜度，有利于防止過擬合，從而提高模型的泛化能力。
?GBDT在模型訓練時只使用了代價函數的一階導數信息，XGBoost對代 價函數進行二階泰勒展開，可以同時使用一階和二階導數。
?傳統的GBDT采用CART作為基分類器，XGBoost支持多種類型的基分類 器，比如線性分類器。
?傳統的GBDT在每輪迭代時使用全部的數據，XGBoost則采用了與隨機 森林相似的策略，支持對數據進行采樣。
?傳統的GBDT沒有設計對缺失值進行處理，XGBoost能夠自動學習出缺 失值的處理策略。
8.1.7.為什么XGBoost要用泰勒展開，優勢在哪里？
XGBoost使用了一階和二階偏導, 二階導數有利于梯度下降的更快更準. 使用泰勒展開取得函數做自變量的二階導數形式, 可以在不選定損失函數具體形式的情況下, 僅僅依靠輸入數據的值就可以進行葉子分裂優化計算, 本質上也就把損失函數的選取和模型算法優化/參數選擇分開了. 這種去耦合增加了XGBoost的適用性, 使得它按需選取損失函數, 可以用于分類, 也可以用于回歸。
8.2.XGBoost算法原理小結
本部分轉自：https://www.cnblogs.com/pinard/p/10979808.html
8.2.1.從GBDT到XGBoost
作為GBDT的高效實現，XGBoost是一個上限特別高的算法，因此在算法競賽中比較受歡迎。簡單來說，對比原算法GBDT，XGBoost主要從下面三個方面做了優化：
一是算法本身的優化：在算法的弱學習器模型選擇上，對比GBDT只支持決策樹，還可以直接很多其他的弱學習器。在算法的損失函數上，除了本身的損失，還加上了正則化部分。在算法的優化方式上，GBDT的損失函數只對誤差部分做負梯度（一階泰勒）展開，而XGBoost損失函數對誤差部分做二階泰勒展開，更加準確。算法本身的優化是我們后面討論的重點。
二是算法運行效率的優化：對每個弱學習器，比如決策樹建立的過程做并行選擇，找到合適的子樹分裂特征和特征值。在并行選擇之前，先對所有的特征的值進行排序分組，方便前面說的并行選擇。對分組的特征，選擇合適的分組大小，使用CPU緩存進行讀取加速。將各個分組保存到多個硬盤以提高IO速度。
三是算法健壯性的優化：對于缺失值的特征，通過枚舉所有缺失值在當前節點是進入左子樹還是右子樹來決定缺失值的處理方式。算法本身加入了L1和L2正則化項，可以防止過擬合，泛化能力更強。
在上面三方面的優化中，第一部分算法本身的優化是重點也是難點。現在我們就來看看算法本身的優化內容。
8.2.2.XGBoost損失函數
在看XGBoost本身的優化內容前，我們先回顧下GBDT的回歸算法迭代的流程，詳細算法流程見梯度提升樹(GBDT)原理小結（https://www.cnblogs.com/pinard/p/6140514.html）第三節，對于GBDT的第t顆決策樹，主要是走下面4步：
8.3.XGBoost入門第一講
轉自：https://zhuanlan.zhihu.com/p/27816315
8.3.1.Boosted Trees介紹
XGBoost是“Extreme Gradient Boosting”的簡稱，其中“Gradient Boosting”來源于附錄1.Friedman的這篇論文。本文基于 gradient boosted tree，中文可以叫梯度提升決策樹，下面簡稱GBDT，同時也有簡稱GBRT，GBM。
8.3.2.監督學習
XGBoost 主要是用來解決有監督學習問題，此類問題利用包含多個特征的訓練數據，來預測目標變量。在我們深入探討GBDT前，我們先來簡單回顧一下監督學習的一些基本概念。
8.3.3.模型與參數
在監督學習中模型(model)表示一種數學函數，通過給定來對進行預測。以最常見的線性模型（linear model）舉例來說，模型可以表述為
，這是一個輸入特性進行線性加權的函數。那么針對預測值的不同，可以分為回歸或者分類兩種。
在監督學習中參數（parameters）是待定的部分，我們需要從數據中進行學習得到。在線性回歸問題中，參數用來表示。
答案是用紅色標注出來的這幅圖。為什么呢？因為我們對于好的模型的判斷依據是 簡單（simple）并且 準確（predictive）。但這兩者又是相互矛盾的，在機器學習中我們也把這兩者也用 bias-variance 來表述。
8.3.5.復合樹模型（Tree Ensemble）
在前面我們已經介紹了監督學習，現在讓我們開始了解樹模型。首先先來了解一下xgboost所對應的模型：復合樹模型。復合樹模型是一組分類和回歸樹（classification and regression trees - CART）。這里我們舉CART中的一個例子，一類分類器用來辨別某人是否喜歡計算機游戲。
我們把家庭中的成員分到不同的葉子節點，同時每個葉子節點上都有一個分數。CART與決策樹相比，細微差別在于CART的葉子節點僅包含判斷分數。在CART中，相比較與分類結果，每個葉子節點的分數給我們以更多的解釋。這讓CART統一優化節點更為容易，這在后面會有具體介紹。
通常情況下，在實踐中往往一棵樹是不夠用的。這個時候往往需要把多棵樹的預測結果綜合起來，這就是所謂的復合樹模型。
上面就是由兩棵樹組成的復合樹的例子。每棵樹上的分數簡單相加就得到了最終的分數。用數學式子可以表達如下：
現在問題來了，隨機森林對應的模型是什么呢？對了，也是復合樹模型。所以在模型的表述上，隨機森林和提升樹是一樣的，他們倆的區別只是在于如何訓練。這也就意味著，如果要寫一個關于復合樹模型的預測服務，我們只需要寫一個就可以同時支持隨機森林和提升樹。
8.3.6.提升樹（Tree Boosting）
介紹了模型之后，讓我們看看訓練部分。那么我們是怎么訓練這些樹的呢？對于所有的監督學習模型，答案也都是同樣，只需要做兩件事，定義目標函數，然后優化它。
假如我們有如下目標函數（需要切記目標函數必須包含損失函數及正則項）
8.3.7.增量訓練（Additive Training）
首先我們需要問的是，這些樹的參數是什么？我們會發現，我們所要學習的就是這些 fi方法，每個方法中定義樹的結構以及葉子節點的分數。這比傳統最優化問題要更難，傳統最優化問題我們可以通過梯度來解決。而且我們無法在一次訓練所有的樹。相反，我們用增量（additive）的方式：每一步我們都是在前一步的基礎上增加一棵樹，而新增的這棵樹是為修復上一顆樹的不足。，我們把每t步的預測用表示，這樣我們就有了：
這里還有疑問的是，在每一步中如何確定哪棵樹是我們需要的呢？一個很自然的想法就是，增加這棵樹有助于我們的目標函數。
總結
- 上一篇： 面条是什么？
- 下一篇： 毫米换算米lisp语言怎么写（毫米换算米