Boosting

1、Boosting

1.1、Boosting算法

? Boosting算法核心思想：

1.2、Boosting實例

? 使用Boosting進行年齡預測：

2、XGBoosting

? XGBoost 是 GBDT 的一種改進形式，具有很好的性能。

2.1、XGBoosting 推導

? 經過 k 輪迭代后，GBDT/GBRT 的損失函數可以寫成 $L(y,f_k(x))$，將$f_k(x)$視為遍歷（是一個復合型變量），對 $L(y,f_k(x))$ 在 $f_{k?1}(x)$ 處進行二階泰勒展開，可得：
$$\begin{gathered} L(y,f_k(x)) \\ \approx L(y,f_{k?1}(x))+\frac{?L(y,f_{k?1}(x))}{?f_k(x)}[f_k(x)?f_{k?1}(x)]+\frac{1}{2}\times \frac{{?}^{2}L(y,f_{k?1}(x))}{{?}^2{f}_{k?1}(x)}[f_k(x)?f_{k?1}(x){]}^2 \end{gathered}$$
? 然后取 $g=\frac{?L(y,f_{k?1}(x))}{?f_k(x)}$ ，$h=\frac{{?}^{2}L(y,f_{k?1}(x))}{{?}^2{f}_k(x)}$ ，即 $g$ 和 $h$ 分別代表一階導數和二階導數，所以，展開式可以變形得：
$$L(y,f_k(x))\approx L(y,f_{k?1}(x))+g[f_k(x)?f_{k?1}(x)]+\frac{1}{2}h[f_k(x)?f_{k?1}(x){]}^2$$
? 又因為在 GBDT 中，利用前向分布算法，有 $f_k(x)=f_{k?1}(x)+T_k(x)$，即：
$$f_k(x)?f_{k?1}(x)=T_k(x)$$
? 代入上式，可得：
$$L(y,f_k(x))\approx L(y,f_{k?1}(x))+g?T_k(x)+\frac{1}{2}h?T_k^2(x)$$
? 上面的損失函數還是對于一個樣本數據而言，對于整體樣本數據，損失函數可得：
$$L=\sum _{i=1}^{N}L(y,f_k(x))\approx \sum _{i=1}^N[L(y,f_{k?1}(x))+g?T_k(x)+\frac{1}{2}h?T_k^2(x)]$$
? 等式右邊中的第一項 $L(y,f_{k?1}(x))$ 只與前 k-1 輪有關，第 k 輪優化中可將該項視為常數。在 GBDT 中的損失函數上再加上一項與第 k 輪的基學習器 CART 決策樹相關的正則化項 $\Omega (T_k(x))$ 防止過擬合，可得到新的第 k 輪迭代時的等價損失函數：
$$L_k=\sum _{i=1}^N[g_i?T_k(x_i)+\frac{1}{2}{h}_i?T_k^2(x_i)]+\Omega (T_k(x))$$
? 所以，$L_k$ 就是 XGBoost 模型的損失函數。

? 假設第 k 棵 CART 回歸樹其對一個的葉子區域樣本子集為 $D_{k1},D_{k2},...,D_{kT}$，且第 $j$ 個小單元 $D_{kj}$ 中仍然包含 $N_{kj}$ 個樣本數據，則計算每個小單元里面的樣本的輸出均值為：
$${\overline{c}}_{kj}=\frac{1}{N_{kj}}\sum _{x_i\in D_{kj}}{y}_i$$
? 得到：
$$T_k(x)=\sum _{j=1}^T{\overline{c}}_{kj}?I(x_i\in D_{kj})$$
? 正則化項 $\Omega (T_k(x))$ 的構造如下：
$$\Omega (T_k(x))=\gamma T+\frac{1}{2}\gamma \sum _{j=1}^T{\overline{c}}_{kj}^2$$
? 其中， 參數 $T$ 為 $T_k(x)$ 決策樹的葉子節點的個數，參數 ${\overline{c}}_{kj}，j=1,2,...,T$，是第 $j$ 個葉子節點的輸出均值；$\gamma$ 和 $\lambda$ 是兩個權衡因子。葉子節點的數量及權重因子一起用來控制決策樹模型的復雜度。

? 將 $T_k(x)$ 和 $\Omega (T_k(x))$ 一起帶入 $L_k$ ，可得：
$$\begin{gathered} L_k=\sum _{i=1}^N[g_i?T_k(x_i)+\frac{1}{2}{h}_i?T_k^2(x_i)]+\Omega (T_k(x)) \\ =\sum _{i=1}^N[g_i?T_k(x_i)+\frac{1}{2}{h}_i?T_k^2(x_i)]+\gamma T+\frac{1}{2}\gamma \sum _{j=1}^T{\overline{c}}_{kj}^2 \\ =\sum _{i=1}^N[(\sum _{x_i\in D_{kj}}{g}_i)?{\overline{c}}_{kj}+\frac{1}{2}(\sum _{x_i\in D_{kj}}{h}_i+\lambda )({\overline{c}}_{kj}{)}^2]+\gamma T \end{gathered}$$

? 由上公式可知，XGBoost 模型對應的損失函數 $L_k$ 主要與原損失函數的一階、二階梯度在當前模型的值 $g_i、h_i$ 及第 $k$ 棵 CART 樹的葉子節點參數值 ${\overline{c}}_{kj}$ 有關，而 $g_i、h_i$ 與第 $k$ 輪迭代無關，所以將其當做常數，在要訓練第 $k$ 棵 CART 樹，只需要考慮 ${\overline{c}}_{kj}$ 參數。

? 對 $c_{kj}$ 求導并令其導數等于 0 ，可得：
$$\frac{?L_k}{?{\overline{c}}_{kj}}=\sum _{j=1}^T[(\sum _{x_i\in D_{kj}}{g}_i)+(\sum _{x_i\in D_{kj}}{h}_i+\lambda )?{\overline{c}}_{kj}]=0$$

$${\overline{c}}_{kj}=?\frac{\sum _{x_i\in D_{kj}}{g}_i}{\sum _{x_i\in D_{kj}}{h}_i+\lambda }$$

? 將其帶入上式可得第 $k$ 輪迭代時等價的損失函數為：
$$L_k=?\frac{1}{2}\sum _{j=1}^T[\frac{(\sum _{x_i\in D_{kj}}{g}_i{)}^2}{(\sum _{x_i\in D_{kj}}{h}_i+\lambda )}]+\lambda T$$
? 實際上，第 $k$ 輪迭代的損失函數的優化過程對應的就是第 $k$ 棵樹的分裂過程：每次分裂對應于將屬于某個葉子結點下的訓練樣本分配到兩個新的葉子節點上；而損失函數滿足樣本之間的累積性，所以可以通過將分裂前葉子節點上所有樣本的損失函數與分裂之后兩個新葉子節點上的樣本的損失函數進行比較，以此作為各個特征分裂點的打分標準；最后選擇一個生成該樹的最佳分裂方案。

? 在實踐中，當訓練數據量較大時，不可能窮舉出每一棵樹進行打分來選擇最好的，因為這個過程計算量太大。所以，通常采用貪心算法的方式來進行逐層選擇最佳分裂點。假設一個葉子節點 $I$ 分裂成兩個新的葉子節點 $I_L$ 和 $I_R$ ，則該節點分裂產生的增益為：
$$G_{split}=\frac{1}{2}[\frac{(\sum _{x_i\in I_L}{g}_i{)}^2}{(\sum _{x_i\in I_L}{h}_i+\lambda )}+\frac{(\sum _{x_i\in I_R}{g}_i{)}^2}{(\sum _{x_i\in I_R}{h}_i+\lambda )}?\frac{(\sum _{x_i\in I}{g}_i{)}^2}{(\sum _{x_i\in I}{h}_i+\lambda )}]?\gamma$$
? 上面的 $G_{split}$ 表示的就是一個葉子節點 $I$ 按照某特征下的某分裂點分成兩個新的葉子節點 $I_L$ 和 $I_R$ 后可以得到的“增益”，該增益值與模型的損失函數值成負相關關系（因為在損失函數的基礎上取了負號），即該值越大，就表示按照該分裂方式分裂可以使模型的整體損失減小得越多。

? 所以，XGBoost 采用的是解析解思維，即對損失函數進行二階泰勒展開，求得解析解，然后用這個解析解作為“增益”來輔助簡歷 CART 回歸樹，最終使得整體損失達到最優。

3、XGBoosting 實踐

1. 讀取數據

import os
import pandas as pd
import numpy as npfrom sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score
import matplotlib.pyplot as plt
import seaborn as sns
%matplotlib inlineimport xgboost as xgbdf = pd.read_csv('LoanStats3a 2.csv',low_memory=False,skiprows=1)
print(df.shape)
df.head()

(42538, 144)

2. 數據預處理

df = df.iloc[:,2:111]  # 刪掉很多空的列
empty_cols = [i for i in range(45,72)]   # 刪除更多的列
df = df.drop(df.columns[empty_cols],axis=1)
df.shapedf = df[(df['loan_status']=="Fully Paid") | (df['loan_status']=="Charged Off")]
df['loan_status'] = df['loan_status'].map({'Fully Paid':0, 'Charged Off':1})
df=df.dropna(axis=1) #340000 is minimum number of non-NA values
df

3. 數據獨熱編碼

df_grade = df['grade'].str.get_dummies().add_prefix('grade: ')
# 把類型獨熱編碼
df_subgrad = df['sub_grade'].apply(str).str.get_dummies().add_prefix('sub_grade: ')
df_home = df['home_ownership'].apply(str).str.get_dummies().add_prefix('home_ownership: ')
df_addr = df['addr_state'].apply(str).str.get_dummies().add_prefix('addr_state: ')
df_term = df['term'].apply(str).str.get_dummies().add_prefix('term: ')# 添加獨熱編碼數據列
df = pd.concat([df, df_grade, df_subgrad, df_home, df_addr, df_term], axis=1)
# 去除獨熱編碼對應的原始列
df = df.drop(['grade', 'sub_grade', 'home_ownership', 'addr_state', 'int_rate', 'term', 'zip_code','purpose','initial_list_status','initial_list_status','pymnt_plan','issue_d','earliest_cr_line','verification_status'], axis=1)

4. 準備數據

# 準備數據
X = df.drop('loan_status', axis=1)
y = df['loan_status']
print (X.shape, y.shape)

(39786, 122) (39786,)

5. 預測的實現

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=123)
xg_classifier = xgb.XGBClassifier(objective ='binary:logistic', colsample_bytree = 0.3, learning_rate = 0.1,max_depth = 5, alpha = 10, n_estimators = 10)xg_classifier.fit(X_train,y_train)
xg_classifier.score(X_test, y_test)

0.9889419452123649

文中實例及參考：

• 《機器學習基礎》
• 貪心學院，https://www.greedyai.com