龔奎 孫宇

（廣西大學計算機與電子信息學院 廣西壯族自治區(qū)南寧市 530004）

XGBoost[1]是2016年陳天奇發(fā)布的基于分類與回歸樹的提升樹系統(tǒng)，在很多針對結(jié)構(gòu)化數(shù)據(jù)的機器學習任務(wù)中，它達到了前沿水平。XGBoost 對于特征相互獨立的數(shù)據(jù)集具有極好的效果，得到了廣泛使用。XGBoost 發(fā)布后，不少學者也在探索對XGBoost 進行改進，Chen 等采用將LSTM 與XGBoost 預(yù)測結(jié)果聯(lián)合預(yù)測的方法，提出LSTM-XGBoost 模型[2]，并證明該方法優(yōu)于單一組合模型。岳鵬等提出使用Stacking 方法集成XGBoost，CatBoost，LightGBM等的XLC-Stacking 方法[3]，提高了模型的最終預(yù)測精度。

目前改進XGBoost 的方法大多采用集成其他算法的方案，對于XGBoost 和數(shù)據(jù)本身的探索尚不充分。對于數(shù)據(jù)集本身存在的在特征之間互相干涉的情況下，基于樹的模型有可能過學習訓(xùn)練數(shù)據(jù)，容易在樹中出現(xiàn)過擬合的噪音結(jié)構(gòu)。在2018年，XGBoost 增加了特征交互約束參數(shù)[4](Feature Interaction Constraints)以抑制這一問題，該參數(shù)可以將預(yù)先知道的具有交互作用的特征集作為參數(shù)傳遞給模型。

但XGBoost 并沒有提供獲取特征交互約束參數(shù)的方法，需要對于領(lǐng)域本身已經(jīng)有足夠的了解，或者需要針對性對于數(shù)據(jù)進行預(yù)先分析處理，這些問題限制了該參數(shù)的普遍使用。本文通過對XGBoost 模型信息的分析挖掘，直接從模型中提取潛在的交互特征并應(yīng)用于下一輪訓(xùn)練，實驗表明，提取的信息有助于預(yù)測效果提升。

1 相關(guān)概念

XGBoost 的訓(xùn)練方式是一顆回歸樹訓(xùn)練結(jié)束后，下一顆樹以上一顆樹的預(yù)測值與實際值之間的殘差作為輸入進行訓(xùn)練，通過迭代提升訓(xùn)練，減少最終回歸偏差。模型可表示為：

1.1 目標函數(shù)

對于每一顆樹，訓(xùn)練中需要評估殘差，得到殘差最小的樹。評估殘差的目標函數(shù)由損失函數(shù)和正則化項組成。XGBoost 允許自定義損失函數(shù)，損失函數(shù)須可以二階導(dǎo)。評估樹的殘差的目標函數(shù)為：

其中Obj(t)是第t 顆樹的目標函數(shù)，是用于衡量yi和差異的損失函數(shù)，Ω(ft)是正則化項，n 是樣本數(shù)量。

其中，ft (Xi)是正在訓(xùn)練的第t 顆樹的預(yù)測結(jié)果，y(t-1)表示前面t - 1 輪的預(yù)測結(jié)果，在當前樹生成過程中是常量。

將目標函數(shù)進行泰勒二階展開，可以得到公式：

當訓(xùn)練第t 顆樹時，y(t-1)已經(jīng)確定，屬于常量。移除常量，可得簡化后的目標函數(shù)：

1.2 葉節(jié)點權(quán)重

函數(shù)ft(x)是每顆樹計算預(yù)測值的函數(shù)，可以重新定義為：

其中，ω 是葉節(jié)點的權(quán)重，q(x)是把樣本x 映射到對應(yīng)葉節(jié)點的函數(shù)。

在XGBoost 中，正則項可以定義為：

其中，T 是葉節(jié)點數(shù)量，γ 和λ 是對應(yīng)項的權(quán)重，作為參數(shù)傳遞給模型。

為了度量一顆樹的好壞，代入以上公式到目標函數(shù)轉(zhuǎn)換得到：其中，Ij是分配到第j 個葉節(jié)點的樣本集合。

再定義Gj=∑i∈Ijgi，Hj=∑i∈Ijhi以上公式可簡化為：

設(shè)第j 個葉節(jié)點最優(yōu)葉節(jié)點權(quán)重為ωj*，由上式可得最優(yōu)葉節(jié)點權(quán)重計算公式：

1.3 增益

在能評估一棵樹的好壞之后，就可以確定樹的節(jié)點如何分裂。XGBoost 采用貪心策略[5]，每次選取所有特征，用于分裂當前同一深度節(jié)點。度量分裂時分別計算左子樹和右子樹的G 和H，則增益定義為：

僅在增益大于0 時才發(fā)生分裂，也即分裂收益大于γ 時進行分裂。

1.4 模型信息結(jié)構(gòu)

在訓(xùn)練后的模型中，包含每棵回歸樹的每個節(jié)點的下列信息：

（1）分裂特征與分裂條件：分裂條件為真走yes 方向，分裂條件為假走no 方向，特征值缺失走missing 方向；

（2）節(jié)點增益gain；

（3）分類到葉節(jié)點上的訓(xùn)練數(shù)據(jù)的二階梯度之和cover。

也可以看到看到每個葉節(jié)點的以下信息：

（1）葉節(jié)點權(quán)重值leaf；

（2）分類到葉節(jié)點上的訓(xùn)練數(shù)據(jù)的二階梯度之和cover。

1.5 特征交互

對于函數(shù)Y=f(X1,X2)，假如Y 隨X1變化受X2值的影響，則說X1和X2是交互特征[6]，也即存在特征交互[7]。具有特征交互的特征之間可能是任意的函數(shù)關(guān)系。特征交互典型的例子是異或[8]。

表1：異或問題

從表1 中可以看到，X1和X2分別對于Y 線性無關(guān)，無法單獨根據(jù)X1或X2獲取有助于判斷Y 值的信息。但是在X1和X2聯(lián)合的情況下，可以對Y 值給出有效判斷。

1.6 特征交互約束參數(shù)

在最小化目標函數(shù)的時候，對于具有特征交互作用的數(shù)據(jù)集，訓(xùn)練回歸樹會得到不反應(yīng)真實規(guī)律的結(jié)構(gòu)關(guān)系。2018年，XGBoost項目貢獻者討論并實現(xiàn)了特征交互約束參數(shù)，發(fā)布在0.81 版的XGBoost 中。特征交互參數(shù)允許用戶根據(jù)預(yù)先得知的交互特征，帶入模型訓(xùn)練。

將真實存在的特征約束關(guān)系作為特征交互約束參數(shù)傳入訓(xùn)練有助于得到更加穩(wěn)定和準確的結(jié)果。對模型的具體約束是指，如果約束列表中的參數(shù)作為特征用于分裂回歸樹，則其子樹的節(jié)點只能從此列表中取得。特征約束的原理是，如果多個特征聯(lián)合進行預(yù)測具有更好的效果，那么就應(yīng)該在構(gòu)建樹的過程中，將交互特征作為直接上下級聯(lián)合一起對樣本進行預(yù)測，從而避免因特征交互產(chǎn)生的噪音節(jié)點得到更好的結(jié)果。

2 改進原理與計算過程

XGBoost 的模型包含所有節(jié)點的增益，因此可以統(tǒng)計出各節(jié)點特征的增益之和，和所有處于同一分支并且相連的節(jié)點組合的增益之和。節(jié)點的增益之和除以節(jié)點出現(xiàn)次數(shù)，可以得到單個節(jié)點的平均增益；節(jié)點組合的增益之和除以同一組合的出現(xiàn)次數(shù)，可以得到組合的平均增益。如果發(fā)現(xiàn)某特征組合的平均增益，大于對應(yīng)特征單獨計算的增益平均值之和，則可以認為模型中，特征組合情況下的獲得的增益高于非組合情況下的增益，可以將其帶入特征交互參數(shù)重新訓(xùn)練，從而檢驗是否能提高模型性能?？紤]到會有平均增益大于單個增益和的特征組合數(shù)量較大的情況，為了控制時間復(fù)雜度，這里將平均增益除以單個增益和，逆序排序，取前N 項。

計算過程可以分成3 部分，以下列為算法1，算法2，算法3，位于前面的算法是后面算法的基礎(chǔ)。算法1，用于統(tǒng)計所有從根節(jié)點到葉節(jié)點的路徑和路徑的所有連通子集，算法2，用于獲取平均增益比率最高的前N 個特征集合，算法3，帶入特征集合到模型重新訓(xùn)練，取得效果最好的模型。

2.1 算法1

步驟1：定義路徑列表P，P 為節(jié)點對象的集合，節(jié)點對象包含增益與編號信息；

步驟2：定義遞歸方法F，參數(shù)為根節(jié)點R 和節(jié)點列表L，L初始值為空；

步驟3：如果根節(jié)點R 是空，返回；

步驟4：節(jié)點列表L 添加根節(jié)點R 的增益與編號，L 為當前已遍歷路徑節(jié)點；

步驟5：如果根節(jié)點左子樹和右子樹均為空，則遍歷此時的節(jié)點列表L，取得路徑L 的所有連通子集，將編號與增益之和添加到路徑列表P 中；

步驟5.1：以方法F 遍歷根節(jié)點R 的左子樹，以R 的左子樹為根節(jié)點參數(shù)，L 為節(jié)點列表參數(shù)；

步驟5.2：以方法F 遍歷根節(jié)點R 的右子樹，以R 的右子樹為根節(jié)點參數(shù)，L 為節(jié)點列表參數(shù)。

2.2 算法2

步驟1：輸入模型樹的集合和特征集合數(shù)量N；

步驟2：循環(huán)取每一顆樹，帶入算法1，取得所有路徑；

步驟3：對以上過程獲得的路徑列表，統(tǒng)計相同路徑出現(xiàn)次數(shù)，對于節(jié)點完全相同的路徑，累加增益；

步驟4：對各路徑用增益除以出現(xiàn)次數(shù)，得到平均增益；

步驟5：對平均增益從大到小排序，輸出前N 個路徑的列表。

2.3 算法3

步驟1：初次訓(xùn)練；

步驟2：訓(xùn)練得到的模型M1 帶入算法2，得到路徑列表；

步驟3：分別將路徑列表轉(zhuǎn)為特征交互約束參數(shù)，分別加入?yún)?shù)中訓(xùn)練得到多個模型，取效果最好的模型MB；

步驟4：將M1 與MB 比較，取效果較好的模型作為最終輸出。

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

實驗數(shù)據(jù)集來自UCI 數(shù)據(jù)集[9]、OpenML 數(shù)據(jù)集和Kaggle 數(shù)據(jù)集，表2 描述了實驗所用數(shù)據(jù)集。數(shù)據(jù)集按訓(xùn)練集和測試集各50%，以類別等比例隨機劃分。

3.2 評價指標

對于二分類任務(wù)的評估標準設(shè)為AUC(Area Under roc Curve)，對于多分類的評估標準設(shè)為Kappa 系數(shù)。

表2：數(shù)據(jù)集信息

表3：實驗結(jié)果對照表

3.2.1 AUC

在輸出為類別概率的二分類問題中，設(shè)TP(True Positive)表示將正類預(yù)測為正類的樣本數(shù)量，TN(False Negative)表示將負類預(yù)測為負類的樣本數(shù)量，F(xiàn)P(False Negative)表示將負類預(yù)測為正類的樣本數(shù)量，F(xiàn)N(False Negative)表示將正類預(yù)測為負類的樣本數(shù)量，定義真陽率TPR(True Positive Rate)：

假陽率FPR(False Positive Rate)：

使用FPR 作為橫坐標，TPR 作為縱坐標得到ROC 曲線(receiver operating characteristic curve)。AUC 即ROC 曲線下的面積。AUC范圍是[0,1]，越大預(yù)測結(jié)果越好。對于隨機的預(yù)測結(jié)果，值期望接近0.5，對于高度準確的結(jié)果，值接近1。

3.2.2 Kappa 系數(shù)

對多分類問題，得出預(yù)測結(jié)果和真實結(jié)果的混淆矩陣[11]，即可計算Kappa 系數(shù)。計算公式為：

其中，p0是每一類正確分類的樣本數(shù)量之和除以總樣本數(shù)，pe是所有類別分別對應(yīng)的“實際與預(yù)測數(shù)量的乘積”。Kappa 系數(shù)范圍是 [-1,1]，越大預(yù)測越準確。對于隨機的預(yù)測結(jié)果，值期望接近0，對于高度準確的結(jié)果，值接近1。

3.3 實驗環(huán)境與參數(shù)

實驗硬件電腦CPU 配置為Intel 酷睿i7 處理器，16G 內(nèi)存。軟件采用Anaconda 構(gòu)建虛擬Python 環(huán)境，conda 版本4.5.11，Python版本3.7.9，XGBoost 版本0.81。

實驗對照組采用默認參數(shù)，其特征交互參數(shù)默認為空。對比實驗采用統(tǒng)計得到的特征交互列表作為特征交互參數(shù)，其他參數(shù)與對照組一樣，實驗組取具有最佳效果的特征交互的模型預(yù)測結(jié)果。

為顯示效果改變程度，實驗僅對尋找具有最優(yōu)預(yù)測結(jié)果的特征交互過程進行測試，所有結(jié)果取4 位小數(shù)。

3.4 實驗結(jié)果

實驗結(jié)果如表3 所示，對于4 個二分類問題，AUC 均得到提升，對于4 個多分類問題，Kappa 系數(shù)有3 個得到了提升，1 個下降。

4 總結(jié)

實驗表明，采用算法在多個數(shù)據(jù)集上有效取得精度提升。但是對于部分問題，找到的特征交互信息在對照組導(dǎo)致精度下降。事實上，并不是所有數(shù)據(jù)集的特征之間都具有特征交互關(guān)系，特征交互約束僅當客觀存在才能提高精度，如果特征之間相互獨立，那么預(yù)測效果無法得到通過尋找特征交互得到有效改善。

因此，為了確保模型精度不下降，應(yīng)該將所有訓(xùn)練后模型結(jié)果在同一評價指標下進行對比，僅在取得提升時采用特征交互約束，最終選擇精度最高的模型作為輸出模型。

該方法的優(yōu)勢在于不影響原有訓(xùn)練過程，在訓(xùn)練時間允許的情況下，可以有效探索對模型精度的進一步提高和數(shù)據(jù)內(nèi)在關(guān)系的發(fā)現(xiàn)，更加充分利用了XGBoost 模型本身提供的信息。

還需要進一步探索的是，特征交互約束允許以多個集合的方式傳入模型，本文為了降低復(fù)雜度，僅對單一特征集合傳入實驗。如果采用多個集合同時傳入，效果有進一步提升的空間。