論文地址：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 等各個(gè)分布式環(huán)境上運(yùn)行，使得它可以很好地解決工業(yè)界大規(guī)模數(shù)據(jù)的問題。

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

• 作者設(shè)計(jì)并構(gòu)建了一個(gè)高度可擴(kuò)展的端到端樹集成模型（tree boosting system）。
• 作者提出了一種理論上合理的加權(quán)分位數(shù)略圖，用于有效的提案計(jì)算。
• 作者為并行樹學(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ù)測(cè)是每棵樹的預(yù)測(cè)總和

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

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

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

2.2 Gradient Tree Boosting

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

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

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

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

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

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

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

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

這個(gè)公式在實(shí)踐中通常被用來評(píng)估 。

2.3 ?Shrinkage and Column Subsampling

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

3. ?SPLIT FINDING ALGORITHMS

3.1 ?Basic Exact Greedy Algorithm

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

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

3.2 Approximate Algorithm

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

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

圖 4 ：Higgs 10M dataset 上測(cè)試 AUC 收斂性的比較。其中 eps 參數(shù)表示分桶數(shù)量的倒數(shù)，作者發(fā)現(xiàn)局部方案需要較少的桶，因?yàn)樗梢约?xì)化拆分的候選點(diǎn)。

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

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

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

3.3 Weighted Quantile Sketch

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

表示特征值 小于 的實(shí)例的比例。其目的就是為了找到拆分點(diǎn) ，以至于

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

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

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

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

3.4 Sparsity-aware Split Finding

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

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

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

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

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

4. ?SYSTEM DESIGN

4.1 ?Column Block for Parallel Learning

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

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

4.2 Cache-aware Access

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

4.3 ?Blocks for Out-of-core Computation

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

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

• 優(yōu)點(diǎn)

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

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

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

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

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

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

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

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

• 缺點(diǎn)

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

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

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

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

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

CART算法由以下兩步組成：

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

2.1 CART 生成算法

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

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

2.1.1 回歸數(shù)的生成

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

考慮如何生成回歸樹。

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

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

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

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

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

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

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

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

    遍歷變量 ，對(duì)固定的切分變量 掃描切分點(diǎn) ，選擇上式達(dá)到最小值的對(duì) 。

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

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

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

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

  • 輸出：回歸樹 。

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

2.1.2 分類樹的生成

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

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

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

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

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

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

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

• 算法（CART 生成算法）

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

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

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

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

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

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

  • 4.生成 CART 決策樹。

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

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

  • 輸出：CART 決策樹

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

    樹：

2.2 CART 減枝

CART 剪枝算法從“完全生長”的決策樹的底端剪去一些子樹，使決策樹變?。Ｐ妥兒唵危瑥亩軌?qū)ξ粗獢?shù)據(jù)有更準(zhǔn)確的預(yù)測(cè)。CART 剪枝算法由兩步組成：首先從生成算法產(chǎn)生的決策樹 底端開始不斷剪枝，直到 的根結(jié)點(diǎn)，形成一個(gè)子樹序列 ；然后通過交叉驗(yàn)證法在獨(dú)立的驗(yàn)證數(shù)據(jù)集上對(duì)子樹序列進(jìn)行測(cè)試，從中選擇最優(yōu)子樹。

1.剪枝，形成一個(gè)子樹序列

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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