XGBoost: A Scalable Tree Boosting System

論文地址：https://arxiv.org/pdf/1603.02754.pdf

代碼地址：https://github.com/dmlc/xgboost

1. ?INTRODUCTION

XGBoost 的全稱是 eXtreme Gradient Boosting，它是經(jīng)過優(yōu)化的分布式梯度提升庫，旨在高效、靈活且可移植。XGBoost 是大規(guī)模并行 boosting tree 的工具。在工業(yè)界大規(guī)模數(shù)據(jù)方面，XGBoost 的分布式版本有廣泛的可移植性，支持在 Kubernetes、Hadoop、SGE、MPI、 Dask 等各個分布式環(huán)境上運行，使得它可以很好地解決工業(yè)界大規(guī)模數(shù)據(jù)的問題。

XGBoost 成功背后最重要的因素是它在所有場景中的可擴展性。在單臺機器上的運行速度比現(xiàn)有流行解決方案快十倍以上，并且可以在分布式或內(nèi)存有限的設(shè)置中擴展到數(shù)十億個樣本。XGBoost 的可擴展性歸功于幾個重要的系統(tǒng)和算法優(yōu)化。這些創(chuàng)新包括：一種用于處理稀疏數(shù)據(jù)的新型樹學(xué)習(xí)算法；理論上合理的加權(quán)分位數(shù)略圖程序（a theoretically justified weighted quantile sketch procedure）能夠處理近似樹學(xué)習(xí)中的樣本權(quán)重。并行和分布式計算使學(xué)習(xí)速度更快，從而實現(xiàn)更快的模型探索。更重要的是，XGBoost 利用核外計算（out-of-core computation ），使數(shù)據(jù)科學(xué)家能夠處理數(shù)億個樣本。最后，更令人興奮的是將這些技術(shù)結(jié)合起來制作一個端到端系統(tǒng)，以最少的集群資源擴展到更大的數(shù)據(jù)。本文的主要貢獻如下：

• 作者設(shè)計并構(gòu)建了一個高度可擴展的端到端樹集成模型（tree boosting system）。
• 作者提出了一種理論上合理的加權(quán)分位數(shù)略圖，用于有效的提案計算。
• 作者為并行樹學(xué)習(xí)引入了一種新穎的稀疏感知算法。
• 作者提出了一種有效的緩存- 用于核外樹學(xué)習(xí)（out-of-core tree learning）的感知塊結(jié)構(gòu)。

2. ?TREE BOOSTING IN A NUTSHELL

2.1 Regularized Learning Objective

圖 1：樹集成模型，給定示例的最終預(yù)測是每棵樹的預(yù)測總和

對于給定 個樣本 個特征的數(shù)據(jù)集 ，一個 ?Tree ?ensemble ?model 使用 個累加函數(shù)去預(yù)測輸出

其中 是回歸樹的空間（CART）。其中 代表每棵樹的結(jié)構(gòu)，即將一個例子映射到相應(yīng)的葉子索引上。 是葉子節(jié)點是數(shù)量。每一個 對應(yīng)獨立的樹狀結(jié)構(gòu) 和葉子節(jié)點權(quán)重 。不同于決策樹，每個回歸樹在每個葉子上都包含一個連續(xù)的分?jǐn)?shù)，使用 代表第 個葉子節(jié)點的分?jǐn)?shù)。對于給定的樣本，將使用樹中的決策規(guī)則（）將其分類為葉子，并通過對相應(yīng)葉子（）的分?jǐn)?shù)求和來計算最終預(yù)測。學(xué)習(xí)模型中使用的函數(shù)集，作者最小化以下正則化目標(biāo)：

這里 是一個可微的凸損失函數(shù)，它衡量預(yù)測 和目標(biāo) 之間的差異。第二項 懲罰模型的復(fù)雜性（例如回歸樹函數(shù)）。額外的正則化項有助于平滑最終學(xué)習(xí)的權(quán)重以避免過度擬合。直觀地，正則化目標(biāo)將傾向于選擇使用簡單和預(yù)測函數(shù)的模型。在正則化貪婪森林 (RGF) 模型中使用了類似的正則化技術(shù)。作者提出的目標(biāo)和相應(yīng)的學(xué)習(xí)算法比 RGF 更簡單，更容易并行化。當(dāng)正則化參數(shù)設(shè)置為零時，目標(biāo)回落到傳統(tǒng)的 Gradient tree boosting 。

2.2 Gradient Tree Boosting

公式 （2）中的樹集成模型包含函數(shù)作為參數(shù)，無法在歐幾里德空間中使用傳統(tǒng)的優(yōu)化方法進行優(yōu)化。相反，模型以加法方式進行訓(xùn)練。形式上，讓 是第 個樣本在第 次迭代時的預(yù)測，需要添加 以最小化以下目標(biāo)：

其中 , ?是損失函數(shù)的一階和二階梯度統(tǒng)計，則可以在第 次迭代去除常數(shù)項以獲得以下簡化目標(biāo)：

圖2：結(jié)構(gòu)分?jǐn)?shù)計算。只需要將每片葉子的梯度和二階梯度統(tǒng)計量相加，然后應(yīng)用評分公式就可以得到質(zhì)量分?jǐn)?shù)

定義 為葉子節(jié)點 的樣本集。則能通過擴展 將等式 (3) 改寫為:

對于固定結(jié)構(gòu) ，可以通過以下計算方式計算葉子節(jié)點 的最佳權(quán)重 :

并計算相應(yīng)的最優(yōu)值：

公式 (6) 可以作為一個評價函數(shù)來衡量一個樹結(jié)構(gòu)的質(zhì)量 。這個分?jǐn)?shù)就像評估決策樹的 impurity score 一樣，只是它是針對更廣泛的目標(biāo)函數(shù)得出的。圖 2 說明了這個分?jǐn)?shù)的計算方式。

通常情況下，我們不可能列舉出所有可能的樹結(jié)構(gòu) 。?取而代之的是一種貪婪的算法，它從單一的葉子開始，迭代地在樹上添加分支。假設(shè) 和 是分裂后的左右節(jié)點的實例集。假設(shè) ，則分裂后的損失減少量為:

這個公式在實踐中通常被用來評估 。

2.3 ?Shrinkage and Column Subsampling

除了第 2.1節(jié)中提到的正則化目標(biāo)外，還有兩項技術(shù)被用來進一步防止過度擬合。第一種方法是 Friedman 引入的縮減技術(shù)。縮減是在每一步 Tree boosting 之后，將新增加的權(quán)重按系數(shù) η 進行縮減。類似于彈性優(yōu)化中的學(xué)習(xí)率，收縮減少了每個單獨的樹的影響，并為未來的樹留下空間以改進模型。第二種技術(shù)是列（特征）抽樣。該技術(shù)用于隨機深林，它在一個用于梯度提升的商業(yè)軟件 TreeNet 中實現(xiàn)，但沒有在現(xiàn)有的開源軟件包中實現(xiàn)。根據(jù)用戶的反饋，使用列子采樣甚至比傳統(tǒng)的行采樣（也支持）更能防止過度擬合。

3. ?SPLIT FINDING ALGORITHMS

3.1 ?Basic Exact Greedy Algorithm

樹狀學(xué)習(xí)中的一個關(guān)鍵問題是找到如公式（7）所示的最佳拆分，即為樹如何生長。為了做到這一點，一個尋找分裂的算法列舉了所有特征上的所有可能的拆分。?大多數(shù)現(xiàn)有的單機樹形提升實現(xiàn)，如 scikit-learn、R 的 gbm 以及 XGBoost 的單機版都支持精確的貪婪算法。精確的貪心算法要列舉出連續(xù)特征的所有可能的拆分，在計算上是很困難的。為了有效地做到這一點，該算法必須首先根據(jù)特征值對數(shù)據(jù)進行排序，并按排序順序訪問數(shù)據(jù)，以積累公式（7）中結(jié)構(gòu)得分的梯度統(tǒng)計。

圖 3. 為一次拆分步驟，其基本思路同 CART 一樣，對特征值排序后遍歷拆分點，將其中最優(yōu)二叉拆分作為當(dāng)前結(jié)點的拆分，得到左右子樹。

3.2 Approximate Algorithm

精確貪心算法非常強大，因為它枚舉所有可能的拆分點。但是，當(dāng)數(shù)據(jù)不能完全裝入內(nèi)存時，就不可能有效地這樣做。同樣的問題也出現(xiàn)在分布式環(huán)境中。為了在這兩種設(shè)置中支持有效的 gradient tree boosting 就需要一種近似算法。

作者總結(jié)了一個近似的框架，它類似于過去文獻中提出的想法，在算法 2 中。?概括地說，該算法首先根據(jù)特征分布的百分位數(shù)提出候選分割點（具體標(biāo)準(zhǔn)將在第 3.3 節(jié)給出）。然后，該算法將連續(xù)特征映射到由這些候選點分割的桶中，匯總統(tǒng)計數(shù)據(jù)，并根據(jù)匯總的統(tǒng)計數(shù)據(jù)在提案中找到最佳解決方案。

圖 4 ：Higgs 10M dataset 上測試 AUC 收斂性的比較。其中 eps 參數(shù)表示分桶數(shù)量的倒數(shù)，作者發(fā)現(xiàn)局部方案需要較少的桶，因為它可以細(xì)化拆分的候選點。

該算法有兩種變體，取決于對特征分位數(shù)的選取。全局變體在樹構(gòu)建的初始階段在全體樣本上的特征值中選取特征分位數(shù)，并在所有級別上使用相同的策略來尋找分位數(shù)。本地變體則是在待拆分節(jié)點包含的樣本特征值上選取，每個節(jié)點拆分前都要進行。全局方法比局部方法需要更少的提議步驟，在根節(jié)點拆分之前進行一次即可。然而，通常全局提議需要更多的候選點，因為候選點在每次拆分后都不會被完善。局部提議在拆分后完善候選點，可能更適合于較深的樹。圖 4 給出了不同算法在 Higgs boson dataset 上的比較。實驗發(fā)現(xiàn)，局部方案需要較少的候選點。?如果有足夠多的候選點，全局方案可以和局部方案一樣準(zhǔn)確。

大多數(shù)現(xiàn)有的分布式樹狀學(xué)習(xí)的近似算法也遵循這個框架。值得注意的是，直接構(gòu)建梯度統(tǒng)計的近似直方圖也是可行。也可以使用其他變種的分桶策略來代替分位數(shù)。?分位數(shù)策略的優(yōu)點是可分配和可重新計算，將在下一小節(jié)中詳細(xì)介紹。從圖 4 中，作者還發(fā)現(xiàn)，在合理的近似水平下，分位數(shù)策略可以獲得與精確貪心算法相同的精度。

這三類配置在 XGBoost 包均有實現(xiàn)。

3.3 Weighted Quantile Sketch

近似算法的一個重要步驟是提出候選拆分點。通常使用特征分位數(shù)來使候選拆分點在數(shù)據(jù)上均勻分布。記多重集合 表示第 個特征值和每個訓(xùn)練實例的二階梯度統(tǒng)計。作者定義排序函數(shù) 為：

表示特征值 小于 的實例的比例。其目的就是為了找到拆分點 ，以至于

其中 為近似因子，直觀地說，這意味著每個分桶大約有 個候選點。這里每個數(shù)據(jù)點都由 加權(quán)。

要理解為什么 代表權(quán)重大小，作者將等式 3 寫為：

可以理解為該目標(biāo)函數(shù)以 為權(quán)重，以 為標(biāo)簽的平方損失函數(shù)，所以近似算法取分位數(shù)時，會以二階偏導(dǎo) 為權(quán)重進行劃分。

圖 5. 按照 進行加權(quán)取分位數(shù)

3.4 Sparsity-aware Split Finding

圖 6. 具有默認(rèn)方向的樹結(jié)構(gòu)。當(dāng)分割所需的特征缺失時，一個示例將被歸類到默認(rèn)方向。

在許多實際問題中，輸入 稀疏是很常見的。造成稀疏的原因有多種：1）數(shù)據(jù)中存在缺失值；2) 統(tǒng)計中經(jīng)常出現(xiàn)零條目；3）特征工程的產(chǎn)物，例如 one-hot 編碼。讓算法了解數(shù)據(jù)中的稀疏模式很重要。為此，作者建議在每個樹節(jié)點中添加一個默認(rèn)方向，如圖 6 所示。當(dāng)稀疏矩陣 x 中缺少一個值時，實例被分類為默認(rèn)方向。

每個分支有兩種默認(rèn)方向選擇。從數(shù)據(jù)中學(xué)習(xí)最佳默認(rèn)方向。算法 3 關(guān)鍵的改進是只訪問非缺失條目 。所提出的算法將不存在視為缺失值，并學(xué)習(xí)處理缺失值的最佳方向。當(dāng)不存在對應(yīng)于用戶指定的值時，也可以應(yīng)用相同的算法，方法是將枚舉限制為一致的解決方案。

圖 7.稀疏感知算法對 Allstate-10K 數(shù)據(jù)集的影響。數(shù)據(jù)集稀疏主要是由于 one-hot 編碼。稀疏感知算法比未考慮稀疏性的原始版本快 50 倍以上

大多數(shù)現(xiàn)有的樹形學(xué)習(xí)算法要么只對密集數(shù)據(jù)進行了優(yōu)化，要么需要特定的程序來處理有限的情況，如分類編碼。XGBoost 以一種統(tǒng)一的方式處理所有的稀疏模式。更重要的是，作者的方法利用了稀疏性，使計算復(fù)雜度與輸入中的非缺失項數(shù)量成線性關(guān)系。圖 7 顯示了在 Allstate-10K 數(shù)據(jù)集（數(shù)據(jù)集的描述見第 6 節(jié)）上稀疏意識和原始的實現(xiàn)的比較。作者發(fā)現(xiàn)稀疏意識算法比原始的版本快 50 倍。這證實了稀疏感知算法的重要性。

4. ?SYSTEM DESIGN

4.1 ?Column Block for Parallel Learning

XGBoost 將每一列特征提前進行排序，以塊（Block）的形式儲存在緩存中，并以索引將特征值和梯度統(tǒng)計量 對應(yīng)起來，每次節(jié)點拆分時會重復(fù)調(diào)用排好序的塊。而且不同特征會分布在獨立的塊中，因此可以進行分布式或多線程的計算。

圖 8.用于并行學(xué)習(xí)的塊狀結(jié)構(gòu)。塊中的每一列都是按相應(yīng)的特征值排序的。對塊中的一列進行線性掃描就足以列舉出所有的拆分點

4.2 Cache-aware Access

特征值排序后通過索引來取梯度 會導(dǎo)致訪問的內(nèi)存空間不一致，進而降低緩存的命中率，影響算法效率。為解決這個問題，XGBoost 為每個線程分配一個單獨的連續(xù)緩存區(qū)，用來存放梯度信息。

4.3 ?Blocks for Out-of-core Computation

數(shù)據(jù)量過大時，不能同時全部載入內(nèi)存。XGBoost 將數(shù)據(jù)分為多個 blocks 并儲存在硬盤中，使用一個獨立的線程專門從磁盤中讀取數(shù)據(jù)到內(nèi)存中，實現(xiàn)計算和讀取數(shù)據(jù)的同時進行。為了進一步提高磁盤讀取數(shù)據(jù)性能，XGBoost 還使用了兩種方法：一是通過壓縮 block，用解壓縮的開銷換取磁盤讀取的開銷；二是將block分散儲存在多個磁盤中，有助于提高磁盤吞吐量。

1. XGBoost 的優(yōu)缺點

• 優(yōu)點

  • 精度更高：GBDT 只用到一階泰勒展開，而 XGBoost 對損失函數(shù)進行了二階泰勒展開。XGBoost 引入二階導(dǎo)一方面是為了增加精度，另一方面也是為了能夠自定義損失函數(shù)，二階泰勒展開可以近似大量損失函數(shù)；

  • 靈活性更強：GBDT 以 CART 作為基分類器，XGBoost 不僅支持 CART 還支持線性分類器，使用線性分類器的 XGBoost 相當(dāng)于帶 L1 和 L2 正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）。此外，XGBoost 工具支持自定義損失函數(shù)，只需函數(shù)支持一階和二階求導(dǎo)；

  • 正則化：XGBoost 在目標(biāo)函數(shù)中加入了正則項，用于控制模型的復(fù)雜度。正則項里包含了樹的葉子節(jié)點個數(shù)、葉子節(jié)點權(quán)重的 ?L2 范式。正則項降低了模型的方差，使學(xué)習(xí)出來的模型更加簡單，有助于防止過擬合，這也是 XGBoost 優(yōu)于傳統(tǒng) GBDT 的一個特性。

  • Shrinkage（縮減）：相當(dāng)于學(xué)習(xí)速率。XGBoost 在進行完一次迭代后，會將葉子節(jié)點的權(quán)重乘上該系數(shù)，主要是為了削弱每棵樹的影響，讓后面有更大的學(xué)習(xí)空間。傳統(tǒng) GBDT 的實現(xiàn)也有學(xué)習(xí)速率；

  • 列抽樣：XGBoost 借鑒了隨機森林的做法，支持列抽樣，不僅能降低過擬合，還能減少計算。這也是 XGBoost 異于傳統(tǒng) GBDT 的一個特性；

  • 缺失值處理：對于特征的值有缺失的樣本，XGBoost 采用的稀疏感知算法可以自動學(xué)習(xí)出它的分裂方向；

  • XGBoost 工具支持并行：boosting 不是一種串行的結(jié)構(gòu)嗎? 怎么并行的？注意 XGBoost 的并行不是 tree 粒度的并行，XGBoost 也是一次迭代完才能進行下一次迭代的（第 t 次迭代的代價函數(shù)里包含了前面 t-1 次迭代的預(yù)測值）。XGBoost 的并行是在特征粒度上的。我們知道，決策樹的學(xué)習(xí)最耗時的一個步驟就是對特征的值進行排序（因為要確定最佳分割點），XGBoost 在訓(xùn)練之前，預(yù)先對數(shù)據(jù)進行了排序，然后保存為 block 結(jié)構(gòu)，后面的迭代中重復(fù)地使用這個結(jié)構(gòu)，大大減小計算量。這個 block 結(jié)構(gòu)也使得并行成為了可能，在進行節(jié)點的分裂時，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂，那么各個特征的增益計算就可以開多線程進行。

  • 可并行的近似算法：樹節(jié)點在進行分裂時，我們需要計算每個特征的每個分割點對應(yīng)的增益，即用貪心法枚舉所有可能的分割點。當(dāng)數(shù)據(jù)無法一次載入內(nèi)存或者在分布式情況下，貪心算法效率就會變得很低，所以 XGBoost 還提出了一種可并行的近似算法，用于高效地生成候選的分割點。

• 缺點

  • 雖然利用預(yù)排序和近似算法可以降低尋找最佳分裂點的計算量，但在節(jié)點分裂過程中仍需要遍歷數(shù)據(jù)集；

  • 預(yù)排序過程的空間復(fù)雜度過高，不僅需要存儲特征值，還需要存儲特征對應(yīng)樣本的梯度統(tǒng)計值的索引，相當(dāng)于消耗了兩倍的內(nèi)存。

2.分類回歸樹 Classification And Regression Tree,CART

參考自：《統(tǒng)計學(xué)習(xí)方法》【李航】第 5 章 5.5 節(jié)

CART 是在給定輸入隨機變量 X 條件下輸出隨機變量 Y 的條件概率分布的學(xué)習(xí)方法。CART 假設(shè)決策樹是二叉樹， 內(nèi)部結(jié)點特征的取值為“是”和“否”， 左分支是取值為“是”的 分支， 右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征， 將輸入空 間即特征空間劃分為有限個單元， 并在這些單元上確定預(yù)測的概率分布， 也就是在輸入給 定的條件下輸出的條件概率分布。

CART算法由以下兩步組成：

• 決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹， 生成的決策樹要盡量大；
• 決策樹剪枝：用驗證數(shù)據(jù)集對已生成的樹進行剪枝并選擇最優(yōu)子樹， 這時用損 失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。

2.1 CART 生成算法

決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。對回歸樹用平方誤差最小化準(zhǔn)則，

對分類樹用基尼指數(shù)（Gini index） 最小化準(zhǔn)則， 進行特征選擇， 生成二叉樹。

2.1.1 回歸數(shù)的生成

假設(shè) 與 分別為輸入和輸出變量，且 是連續(xù)變量，給定訓(xùn)練數(shù)據(jù)集

考慮如何生成回歸樹。

一個回歸樹對應(yīng)于輸入空間（即特征空間）的一個劃分以及劃分的單元的輸出值。假設(shè)已將輸入空間劃分為 個單元 ，并且在每個單元 上有一個固定的輸出值 ，于是回歸樹模型可表示為：

當(dāng)輸入空間的劃分確定時，可以用平方誤差 來表示回歸樹對于訓(xùn)練數(shù)據(jù)的預(yù)測誤差，用平方誤差最小準(zhǔn)則求解每個單元上的最優(yōu)輸出值。易知，單元 上的 的最優(yōu)值 是 上的所有的輸入實例 對應(yīng)的輸出 的均值，即

問題在于如何對輸入空間進行劃分。這里采用啟發(fā)式的方法，選擇第 個變量 和它的取值 作為切分變量（Splitting Variable）和切分點（Splitting Point），并定義兩個區(qū)域：

然后尋找最優(yōu)切分變量 和最優(yōu)切分點 。具體地，求解

對固定輸入變量 可以找到最優(yōu)切分點 。

遍歷所有輸入變量，找到最優(yōu)的切分變量 ，構(gòu)成一個對 。依此將輸入空間劃分為兩個區(qū)域。接著，對每個區(qū)域重復(fù)上述劃分過程，直到滿足停止條件為止。這樣就生成一棵回歸樹。這樣的回歸樹通常稱為最小二乘回歸樹（least squares regression tree），現(xiàn)將算法敘述如下：

• 算法（最小二乘回歸樹生成算法）

  • 1.選擇最優(yōu)切分變量 與切分點 ，求解

    遍歷變量 ，對固定的切分變量 掃描切分點 ，選擇上式達到最小值的對 。

  • 2.用選定的對 劃分區(qū)域并決定相應(yīng)的輸出值：

  • 3.繼續(xù)對兩個子區(qū)域調(diào)用 1、2，直到滿足停止條件。

  • 4.將輸入空間劃分為 個區(qū)域 ，生成決策樹：

  • 輸入：訓(xùn)練數(shù)據(jù)集 ；

  • 輸出：回歸樹 。

  • 具體細(xì)節(jié)：在訓(xùn)練數(shù)據(jù)集所在的輸入空間中，遞歸地將每個區(qū)域劃分為兩個子區(qū)域并決定每個子區(qū)域上的輸出值，構(gòu)建二叉決策樹：

2.1.2 分類樹的生成

分類樹用基尼指數(shù)選擇最優(yōu)特征，同時決定該特征的最優(yōu)二值切分點。

基尼指數(shù)定義：分類問題中，假設(shè)有 個類，樣本點屬于第 類的概率為 ，則概率分布的基尼指數(shù)定義為

對于二分類問題，若樣本點屬于第 1 個類的概率是 ，則概率分布的基尼指數(shù)為

對于給定的樣本集合 ，其基尼指數(shù)為

這里， 是 中屬于第 類的樣本子集， 是類的個數(shù)。

如果樣本集合 根據(jù)特征 是否取某一可能值 被分割成 和 兩部分，即

基尼指數(shù) 表示集合 的不確定性，基尼指數(shù) 表示經(jīng) 分割后集合 的不確定性?；嶂笖?shù)越大，樣本集合的不確定性也就越大，這一點與熵相似。

• 算法（CART 生成算法）

  • 1.設(shè)結(jié)點的訓(xùn)練數(shù)據(jù)集為 ，計算現(xiàn)有特征對該數(shù)據(jù)集的基尼指數(shù)。此時，對每

    一個特征 ，對其可能取的每個值 ，根據(jù)樣本點對 ＝ 的測試為“是”或“否”將 分割成 和 兩部分，利用 計算 ＝ 時的基尼指數(shù)。

  • 2.在所有可能的特征 以及它們所有可能的切分點 中，選擇基尼指數(shù)最小的特征

    及其對應(yīng)的切分點作為最優(yōu)特征與最優(yōu)切分點。依最優(yōu)特征與最優(yōu)切分點，從現(xiàn)結(jié)點生成

    兩個子結(jié)點，將訓(xùn)練數(shù)據(jù)集依特征分配到兩個子結(jié)點中去。

  • 3.對兩個子結(jié)點遞歸地調(diào)用 1，2 直至滿足停止條件。

  • 4.生成 CART 決策樹。

  • 5.算法停止計算的條件是結(jié)點中的樣本個數(shù)小于預(yù)定閾值，或樣本集的基尼指數(shù)小于預(yù) 定閾值（樣本基本屬于同一類），或者沒有更多特征

  • 輸入：訓(xùn)練集 ；停止計算的條件；

  • 輸出：CART 決策樹

  • 具體細(xì)節(jié)：根據(jù)訓(xùn)練數(shù)據(jù)集，從根結(jié)點開始，遞歸地對每個結(jié)點進行以下操作，構(gòu)建二叉決策

    樹：

2.2 CART 減枝

CART 剪枝算法從“完全生長”的決策樹的底端剪去一些子樹，使決策樹變小（模型變簡單），從而能夠?qū)ξ粗獢?shù)據(jù)有更準(zhǔn)確的預(yù)測。CART 剪枝算法由兩步組成：首先從生成算法產(chǎn)生的決策樹 底端開始不斷剪枝，直到 的根結(jié)點，形成一個子樹序列 ；然后通過交叉驗證法在獨立的驗證數(shù)據(jù)集上對子樹序列進行測試，從中選擇最優(yōu)子樹。

1.剪枝，形成一個子樹序列

在剪枝過程中，計算子樹的損失函數(shù)： 。其中， 為任意子樹， 為訓(xùn)練數(shù)據(jù)的預(yù)測誤差（如基尼指數(shù)）， 為子樹的葉結(jié)點個數(shù)， 為參數(shù)， 為參數(shù)是 時的子樹 的整體損失。參數(shù) 權(quán)衡訓(xùn)練數(shù)據(jù)的擬合程度與模型的復(fù)雜度。

對于固定的 ,一定存在使損失函數(shù) 最小的子樹，將其表示為 。 在損失函數(shù) 最小的意義下是最優(yōu)的。任意驗證這樣的最優(yōu)子樹是唯一的。當(dāng) 大的時候，最優(yōu)子樹 偏小；當(dāng) 小的時候，最優(yōu)子樹 偏大。極端情況下，當(dāng) 時，整體樹是最優(yōu)的。當(dāng) 時，根節(jié)點組成的單結(jié)點樹是最優(yōu)的。

Breiman 等人證明：可以用遞歸的方法對樹進行剪枝。將 從小增大，，產(chǎn)生一系列區(qū)間 ；剪枝得到的子樹序列對應(yīng)著區(qū)間 ?的最優(yōu)子樹序列 ，序列中子樹是嵌套的。

具體為，從整體樹 開始剪枝。對 的任意內(nèi)部結(jié)點 ，以 為單結(jié)點樹的損失函數(shù)是：

以 為根結(jié)點的子樹 的損失函數(shù)為：

當(dāng) 及 充分小時，有不等式：

當(dāng) 增大時，在某一 有：

當(dāng) 再增大時，。只要 ， 與 有相同的損失函數(shù)值，而 的結(jié)點少，因此 比 更可取，對 進行剪枝。

為此，對 中每一內(nèi)部結(jié)點 ，計算

它表示剪枝后函數(shù)減少的程度。在 中減去 最小的 ，將得到的子樹作為 ，同時將最小的 設(shè)為 。 為區(qū)間 的最優(yōu)子樹。

如此剪枝下去，直至得到根結(jié)點。在這一過程中，不斷地增加 的值，產(chǎn)生新的區(qū)間。

2.在剪枝得到的子樹序列 中通過交叉驗證選取最優(yōu)子樹

具體地，利用獨立的驗證數(shù)據(jù)集，測試子樹序列 中各棵子樹的平方誤差或基尼指數(shù)。平方誤差或基尼指數(shù)最小的決策樹被認(rèn)為是最優(yōu)的決策樹。在子樹序列中，每棵子樹 都對應(yīng)于一個參數(shù) 。所以，當(dāng)最優(yōu)子樹 確定時，對應(yīng)的 也確定了，即得到最優(yōu)決策樹 。

• CART 剪枝算法
  • 1.設(shè) ；
  • 2.設(shè) ；
  • 3.自下而上對內(nèi)部結(jié)點 計算 以及 。其中 表示以 為根節(jié)點的子樹， 是對訓(xùn)練數(shù)據(jù)的預(yù)測誤差， 是 的葉節(jié)點個數(shù)；
  • 4.自上而下地訪問內(nèi)部結(jié)點 ，如果有 ，進行剪枝，并對葉節(jié)點 以多數(shù)表決法決定其類，得到樹 ；
  • 5.設(shè) ；
  • 6.如果 不是由根結(jié)點單獨構(gòu)成的樹，則回到步驟 4；
  • 7.采用交叉驗證法在子樹序列 中選取最優(yōu)子樹 ；
  • 輸入：CART 算法生成的決策樹 ?；
  • 輸出：最優(yōu)決策樹 ；
  • 具體過程：

• XGBoost: A Scalable Tree Boosting System: https://arxiv.org/pdf/1603.0275
• 機器學(xué)習(xí) | XGBoost詳解：https://zhuanlan.zhihu.com/p/142413825
• 《統(tǒng)計學(xué)習(xí)方法》【李航】第 5 章 5.5 節(jié)