XGBoost和LightGBM

語言: CN / TW / HK

時間 2021-10-05 17:01:22 演算法之名

主題: xgb wise leaf 決策樹過擬合 def

這兩個模型都屬於整合學習中的樹模型，每個機器學習模型都有它特定的應用場景，不同的資料集適合用到的模型是不一樣的。

結構化資料、非結構化資料

結構化資料：規整，維度固定；一般我們的表格資料都屬於結構化資料。
非結構化資料：非規整，維度不固定；比如說一些文字、影象、音訊、視訊等

結構化資料的特點：

類別欄位較多
聚合特徵較多

對於結構化資料集，如果我們遇到的資料集有很多類別型別的特徵，而且特徵與特徵之間是相互獨立的，非常適合使用樹模型。

XGBoost

提出時間較早的高階樹模型，精度較好。比隨機森林較晚，比LightGBM、Catboost較早。

缺點：訓練時間較長，對類別特徵支援不友好。

介面：scikit-learn介面和原聲介面。

XGBoost是基於GBDT(Gradient Boosting Decision Tree)的一種演算法模型，有關Gradient Boosting的介紹可以參考機器學習演算法整理(四)

XGBoost首先是樹模型，Xgboost就是由很多CART樹整合。一般有分類樹和迴歸樹，分類樹是使用資料集的特徵(維度)以及資訊熵或者基尼係數來進行節點分裂。對於迴歸樹則無法使用資訊熵和基尼係數來判定樹的節點分裂，包括預測誤差（常用的有均方誤差、對數誤差等）。而且節點不再是類別，是數值（預測值），那麼怎麼確定呢？有的是節點內樣本均值，有的是最優化算出來的比如XGBoost。

CART迴歸樹是假設樹為二叉樹，通過不斷將特徵進行分裂。比如當前樹結點是基於第j個特徵值進行分裂的，設該特徵值小於s的樣本劃分為左子樹，大於s的樣本劃分為右子樹。

而CART迴歸樹實質上就是在該特徵維度對樣本空間進行劃分，而這種空間劃分的優化是一種NP難問題，因此，在決策樹模型中是使用啟發式方法解決。典型CART迴歸樹產生的目標函式為：

因此，當我們為了求解最優的切分特徵j和最優的切分點s，就轉化為求解這麼一個目標函式：

所以我們只要遍歷所有特徵的的所有切分點，就能找到最優的切分特徵和切分點。最終得到一棵迴歸樹。

我們之前在Gradient Boosting的介紹中說，每次訓練出一個模型m後會產生一個錯誤e，這個錯誤就是殘差。GBDT是計算負梯度，用負梯度近似殘差。迴歸任務下，GBDT 在每一輪的迭代時對每個樣本都會有一個預測值，此時的損失函式為均方差損失函式

此時的負梯度

所以，當損失函式選用均方損失函式時，每一次擬合的值就是（真實值 - 當前模型預測的值），即殘差。此時的變數是，即“當前預測模型的值”，也就是對它求負梯度。殘差在數理統計中是指實際觀察值與估計值（擬合值）之間的差。“殘差”蘊含了有關模型基本假設的重要資訊。如果迴歸模型正確的話，我們可以將殘差看作誤差的觀測值。GBDT需要將多棵樹的得分累加得到最終的預測得分，且每一次迭代，都在現有樹的基礎上，增加一棵樹去擬合前面樹的預測結果與真實值之間的殘差。

XGBoost與GBDT比較大的不同就是目標函式的定義。XGBoost的目標函式如下圖所示(注意這裡是已經迭代切分之後的)：

其中

紅色箭頭所指向的L 即為損失函式（比如平方損失函式：，或邏輯迴歸損失函式：
紅色方框所框起來的是正則項（包括L1正則、L2正則）
紅色圓圈所圈起來的為常數項
對於 $f(x)$ ，XGBoost利用泰勒展開三項，做一個近似。t是迭代次數。

我們可以很清晰地看到，最終的目標函式只依賴於每個資料點在誤差函式上的一階導數和二階導數(泰勒展開，請參考高等數學整理中的泰勒公式定義)

XGBoost的核心演算法思想

不斷地新增樹，不斷地進行特徵分裂來生長一棵樹，每次新增一個樹，其實是學習一個新函式，去擬合上次預測的殘差。

注：為葉子節點q的分數，F對應了所有K棵迴歸樹（regression tree）的集合，而f(x)為其中一棵迴歸樹。T表示葉子節點的個數，w表示葉子節點的分數。

當我們訓練完成得到k棵樹，我們要預測一個樣本的分數，其實就是根據這個樣本的特徵，在每棵樹中會落到對應的一個葉子節點，每個葉子節點就對應一個分數
最後只需要將每棵樹對應的分數加起來就是該樣本的預測值。

顯然，我們的目標是要使得樹群的預測值儘量接近真實值，而且有儘量大的泛化能力。

所以，從數學角度看這是一個泛函最優化問題，故把目標函式簡化如下：

這個目標函式分為兩部分：損失函式和正則化項。且損失函式揭示訓練誤差（即預測分數和真實分數的差距），正則化定義複雜度。對於上式而言，是整個累加模型的輸出，正則化項是則表示樹的複雜度的函式，值越小複雜度越低，泛化能力越強，其表示式為

T表示葉子節點的個數，w表示葉子節點的分數。直觀上看，目標要求預測誤差儘量小，且葉子節點T儘量少（γ控制葉子結點的個數），節點數值w儘量不極端（λ控制葉子節點的分數不會過大），防止過擬合。

具體來說，目標函式第一部分中的i表示第i個樣本，表示第i個樣本的預測誤差，我們的目標當然是誤差越小越好。

類似之前GBDT的套路，XGBoost也是需要將多棵樹的得分累加得到最終的預測得分(每一次迭代，都在現有樹的基礎上，增加一棵樹去擬合前面樹的預測結果與真實值之間的殘差)。

我們如何選擇每一輪加入什麼 $f$ 呢？答案是非常直接的，選取一個 $f$ 來使得我們的目標函式儘可能的小。

第t輪的模型預測值 = 前t-1輪的模型預測 + ，因此誤差函式記為： ( , + )，後面一項為正則化項。對於這個誤差函式的式子而言，在第t步，是真實值，即已知，可由上一步第t-1步中的加上計算所得，某種意義上也算已知值，故模型學習的是 $f$ 。

我們可以考慮當是平方誤差的情況（相當於），這個時候我們的目標可以被寫成下面這樣的二次函式（圖中畫圈的部分表示的就是預測值和真實值之間的殘差）：

更加一般的，損失函式不是二次函式咋辦？利用泰勒展開，不是二次的想辦法近似為二次

為什麼損失函式一定要有二次項，因為損失函式必須可導。通過求導，可以尋找能夠使損失函式最小的引數，這些引數對應的對映即最佳線性迴歸或者邏輯迴歸。所以泰勒展開可以在沒有二次項的情況下，人為創造一個二次項。

考慮到我們的第t 顆迴歸樹是根據前面的t-1顆迴歸樹的殘差得來的，相當於t-1顆樹的值是已知的。換句話說，對目標函式的優化不影響，可以直接去掉，且常數項也可以移除，從而得到如下一個比較統一的目標函式。

這時，目標函式只依賴於每個資料點在誤差函式上的一階導數 $g$ 和二階導數 $h$ 。

XGBoost總的指導原則：實質是把樣本分配到葉子結點會對應一個目標函式obj，優化過程就是目標函式obj優化。也就是分裂節點到葉子不同的組合，不同的組合對應不同目標函式obj，所有的優化圍繞這個思想展開。

正則項：樹的複雜度

在這種新的定義下，我們可以把之前的目標函式進行如下變形，這裡L2正則

其中被定義為每個葉節點 j 上面樣本下標的集合，g是一階導數，h是二階導數。這一步是由於XGBoost目標函式第二部分加了兩個正則項，一個是葉子節點個數(T),一個是葉子節點的分數(w)。

從而，加了正則項的目標函式裡就出現了兩種累加

一種是i - > n（樣本數）
一種是j -> T（葉子節點數）

這一個目標包含了T個相互獨立的單變數二次函式。接著，我們可以定義

最終公式可以化簡為

通過對求導等於0，可以得到

然後把最優解代入得到：

現在我們來看一下程式碼示例

資料下載地址：http://www.kaggle.com/c/ga-customer-revenue-prediction/data?select=train.csv

INPUT_TRAIN = "/Users/admin/Downloads/ga-customer-revenue-prediction/train.csv"
INPUT_TEST = "/Users/admin/Downloads/ga-customer-revenue-prediction/test.csv"
TRAIN = "/Users/admin/Downloads/ga-customer-revenue-prediction/train-processed.csv"
TEST = "/Users/admin/Downloads/ga-customer-revenue-prediction/test-processed.csv"
Y = "/Users/admin/Downloads/ga-customer-revenue-prediction/y.csv"
import os
import gc
import json
import time
from datetime import datetime
import timeit
import numpy as np
import pandas as pd
from pandas.io.json import json_normalize
import xgboost as xgb
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error
import warnings
warnings.filterwarnings('ignore')

if __name__ == "__main__":

    pd.set_option('display.max_columns', 1000)
    pd.set_option('display.width', 1000)
    pd.set_option('display.max_colwidth', 1000)

    def load_df(csv_path=INPUT_TRAIN, nrows=None):
        # 匯入csv檔案
        print(f"Loading {csv_path}")
        JSON_COLUMNS = ['device', 'geoNetwork', 'totals', 'trafficSource']
        # 讀取檔案的資料，並將JSON_COLUMNS中的欄位讀取成json格式
        df = pd.read_csv(csv_path, converters={column: json.loads for column in JSON_COLUMNS},
                         dtype={'fullVisitorId': 'str'}, nrows=nrows)
        # 將json格式的每一個欄位變成pandas表本身的欄位
        for column in JSON_COLUMNS:
            column_as_df = json_normalize(df[column])
            column_as_df.columns = [f"{column}.{subcolumn}" for subcolumn in column_as_df.columns]
            df = df.drop(column, axis=1).merge(column_as_df, right_index=True, left_index=True)
        print(f"Loaded {os.path.basename(csv_path)}. Shape: {df.shape}")
        return df

    def process_dfs(train_df, test_df):
        # 資料預處理
        print("Processing dfs...")
        print("Dropping repeated columns...")
        # 去重
        columns = [col for col in train_df.columns if train_df[col].nunique() > 1]
        train_df = train_df[columns]
        test_df = test_df[columns]
        trn_len = train_df.shape[0]
        merged_df = pd.concat([train_df, test_df])
        merged_df['diff_visitId_time'] = merged_df['visitId'] - merged_df['visitStartTime']
        merged_df['diff_visitId_time'] = (merged_df['diff_visitId_time'] != 0).astype('int')
        del merged_df['visitId']
        del merged_df['sessionId']
        print("Generating date columns...")
        format_str = "%Y%m%d"
        merged_df['formated_date'] = merged_df['date'].apply(lambda x: datetime.strptime(str(x), format_str))
        merged_df['WoY'] = merged_df['formated_date'].apply(lambda x: x.isocalendar()[1])
        merged_df['month'] = merged_df['formated_date'].apply(lambda x: x.month)
        merged_df['quarter_month'] = merged_df['formated_date'].apply(lambda x: x.day // 8)
        merged_df['weekday'] = merged_df['formated_date'].apply(lambda x: x.weekday())
        del merged_df['date']
        del merged_df['formated_date']
        merged_df['formated_visitStartTime'] = merged_df['visitStartTime'].apply(
            lambda x: time.strftime('%Y-%m-%d %H:%M:%S', time.localtime(x)))
        merged_df['formated_visitStartTime'] = pd.to_datetime(merged_df['formated_visitStartTime'])
        merged_df['visit_hour'] = merged_df['formated_visitStartTime'].apply(lambda x: x.hour)
        del merged_df['visitStartTime']
        del merged_df['formated_visitStartTime']
        print("Encoding columns with pd.factorize()")
        for col in merged_df.columns:
            if col in ['fullVisitorId', 'month', 'quarter_month', 'weekday', 'visit_hour', 'Woy']:
                continue
            if merged_df[col].dtypes == object or merged_df[col].dtypes == bool:
                merged_df[col], indexer = pd.factorize(merged_df[col])
        print("Splitting back...")
        train_df = merged_df[:trn_len]
        test_df = merged_df[trn_len:]
        return train_df, test_df

    def preprocess():
        train_df = load_df()
        test_df = load_df(INPUT_TEST)
        target = train_df['totals.transactionRevenue'].fillna(0).astype('float')
        target = target.apply(lambda x: np.log1p(x))
        del train_df['totals.transactionRevenue']
        train_df, test_df = process_dfs(train_df, test_df)
        train_df.to_csv(TRAIN, index=False)
        test_df.to_csv(TEST, index=False)
        target.to_csv(Y, index=False)

    preprocess()

    def rmse(y_true, y_pred):
        # 均方根誤差
        return round(np.sqrt(mean_squared_error(y_true, y_pred)), 5)

    def load_preprocessed_dfs(drop_full_visitor_id=True):
        # 匯入預處理完的資料
        X_train = pd.read_csv(TRAIN, converters={'fullVisitorId': str})
        X_test = pd.read_csv(TEST, converters={'fullVisitorId': str})
        y_train = pd.read_csv(Y, names=['LogRevenue']).T.squeeze()
        y_train = y_train[1:]
        if drop_full_visitor_id:
            X_train = X_train.drop('fullVisitorId', axis=1)
            X_test = X_test.drop('fullVisitorId', axis=1)
        return X_train, y_train, X_test

    X, y, X_test = load_preprocessed_dfs()
    print(X.shape)
    print(y.shape)
    X_train, X_val, y_train, y_val = train_test_split(X, y, test_size=0.15, random_state=1)
    print(f"Train shape: {X_train.shape}")
    print(f"Validation shape: {X_val.shape}")
    print(f"Test (submit) shape: {X_test.shape}")

    def run_xgb(X_train, y_train, X_val, y_val, X_test):
        params = {'objective': 'reg:linear',   # 線性迴歸的學習目標
                  'eval_metric': 'rmse',       # 均方根誤差校驗
                  'eta': 0.001,                # 更新過程中用到的收縮步長
                  'max_depth': 10,             # 樹最大深度
                  'subsample': 0.6,            # 用於訓練模型的子樣本佔整個樣本集合的比例
                  'colsample_bytree': 0.6,     # 在建立樹時對特徵取樣的比例
                  'alpha': 0.001,              # L1正則化項
                  'random_state': 42,          # 隨機種子
                  'silent': True}              # 列印模式
        xgb_train_data = xgb.DMatrix(X_train, y_train)
        xgb_val_data = xgb.DMatrix(X_val, y_val)
        xgb_submit_data = xgb.DMatrix(X_test)
        # num_boost_round進行2000次迭代，evals用於對訓練過程中進行評估列表中的元素
        # early_stopping_rounds早期停止次數100，驗證集的誤差迭代到一定程度在100次內不能再繼續降低，就停止迭代。
        # verbose_eval進行500次迭代輸出一次
        model = xgb.train(params, xgb_train_data, num_boost_round=2000,
                          evals=[(xgb_train_data, 'train'), (xgb_val_data, 'valid')],
                          early_stopping_rounds=100, verbose_eval=500)
        y_pred_train = model.predict(xgb_train_data, ntree_limit=model.best_ntree_limit)
        y_pred_val = model.predict(xgb_val_data, ntree_limit=model.best_ntree_limit)
        y_pred_submit = model.predict(xgb_submit_data, ntree_limit=model.best_ntree_limit)
        print(f"XGB : RMSE val: {rmse(y_val, y_pred_val)}  - RMSE train: {rmse(y_train, y_pred_train)}")
        return y_pred_submit, model

    start_time = timeit.default_timer()
    xgb_preds, xgb_model = run_xgb(X_train, y_train, X_val, y_val, X_test)
    print('total time is:' + str(timeit.default_timer() - start_time))

執行結果

Loading /Users/admin/Downloads/ga-customer-revenue-prediction/train.csv
Loaded train.csv. Shape: (903653, 55)
Loading /Users/admin/Downloads/ga-customer-revenue-prediction/test.csv
Loaded test.csv. Shape: (804684, 53)
Processing dfs...
Dropping repeated columns...
Generating date columns...
Encoding columns with pd.factorize()
Splitting back...
(903653, 31)
(903653,)
Train shape: (768105, 31)
Validation shape: (135548, 31)
Test (submit) shape: (804684, 31)
[06:20:31] WARNING: /Users/travis/build/dmlc/xgboost/src/objective/regression_obj.cu:171: reg:linear is now deprecated in favor of reg:squarederror.
[06:20:31] WARNING: /Users/travis/build/dmlc/xgboost/src/learner.cc:573: 
Parameters: { "silent" } might not be used.

  This may not be accurate due to some parameters are only used in language bindings but
  passed down to XGBoost core.  Or some parameters are not used but slip through this
  verification. Please open an issue if you find above cases.


[0]	train-rmse:2.02025	valid-rmse:2.02937
[500]	train-rmse:1.81049	valid-rmse:1.83542
[1000]	train-rmse:1.68934	valid-rmse:1.73293
[1500]	train-rmse:1.61610	valid-rmse:1.67851
[1999]	train-rmse:1.56843	valid-rmse:1.64969
XGB : RMSE val: 1.6497  - RMSE train: 1.5682
total time is:669.2252929020001

XGBoost引數

General Parameters

booster [default=gbtree]

有兩中模型可以選擇gbtree和gblinear。gbtree使用基於樹的模型進行提升計算，gblinear使用線性模型進行提升計算。預設值為gbtree。

silent [default=0]

取0時表示打印出執行時資訊，取1時表示以緘默方式執行，不列印執行時資訊。預設值為0。

nthread [default to maximum number of threads available if not set]

XGBoost執行時的執行緒數。預設值是當前系統可以獲得的最大執行緒數

num_pbuffer [set automatically by xgboost, no need to be set by user]

size of prediction buffer, normally set to number of training instances. The buffers are used to save the prediction results of last boosting step.

num_feature [set automatically by xgboost, no need to be set by user]

boosting過程中用到的特徵維數，設定為特徵個數。XGBoost會自動設定，不需要手工設定。
Booster Parameters

eta [default=0.3]

為了防止過擬合，更新過程中用到的收縮步長。在每次提升計算之後，演算法會直接獲得新特徵的權重。 eta通過縮減特徵的權重使提升計算過程更加保守。預設值為0.3
取值範圍為：[0,1]

gamma [default=0]

minimum loss reduction required to make a further partition on a leaf node of the tree. the larger, the more conservative the algorithm will be.
range: [0,∞]

max_depth [default=6]

樹的最大深度。預設值為6
取值範圍為：[1,∞]

min_child_weight [default=1]

孩子節點中最小的樣本權重和。如果一個葉子節點的樣本權重和小於min_child_weight則拆分過程結束。在現行迴歸模型中，這個引數是指建立每個模型所需要的最小樣本數。該成熟越大演算法越conservative
取值範圍為: [0,∞]

max_delta_step [default=0]

Maximum delta step we allow each tree’s weight estimation to be. If the value is set to 0, it means there is no constraint. If it is set to a positive value, it can help making the update step more conservative. Usually this parameter is not needed, but it might help in logistic regression when class is extremely imbalanced. Set it to value of 1-10 might help control the update
取值範圍為：[0,∞]

subsample [default=1]

用於訓練模型的子樣本佔整個樣本集合的比例。如果設定為0.5則意味著XGBoost將隨機的衝整個樣本集合中隨機的抽取出50%的子樣本建立樹模型，這能夠防止過擬合。
取值範圍為：(0,1]

colsample_bytree [default=1]

在建立樹時對特徵取樣的比例。預設值為1
取值範圍：(0,1]
Task Parameters

objective [ default=reg:linear ]

定義學習任務及相應的學習目標，可選的目標函式如下：

“reg:linear” –線性迴歸。
“reg:logistic” –邏輯迴歸。
“binary:logistic”–二分類的邏輯迴歸問題，輸出為概率。
“binary:logitraw”–二分類的邏輯迴歸問題，輸出的結果為wTx。
“count:poisson”–計數問題的poisson迴歸，輸出結果為poisson分佈。在poisson迴歸中，max_delta_step的預設值為0.7。(used to safeguard optimization)
“multi:softmax” –讓XGBoost採用softmax目標函式處理多分類問題，同時需要設定引數num_class（類別個數）
“multi:softprob” –和softmax一樣，但是輸出的是ndata * nclass的向量，可以將該向量reshape成ndata行nclass列的矩陣。沒行資料表示樣本所屬於每個類別的概率。
“rank:pairwise”–set XGBoost to do ranking task by minimizing the pairwise loss

base_score [ default=0.5 ]

the initial prediction score of all instances, global bias

eval_metric [ default according to objective ]

校驗資料所需要的評價指標，不同的目標函式將會有預設的評價指標（rmse for regression, and error for classification, mean average precision for ranking）
使用者可以新增多種評價指標，對於Python使用者要以list傳遞引數對給程式，而不是map引數list引數不會覆蓋’eval_metric’
The choices are listed below:

“rmse”: root mean square error
“logloss”: negative log-likelihood
“error”: Binary classification error rate. It is calculated as #(wrong cases)/#(all cases). For the predictions, the evaluation will regard the instances with prediction value larger than 0.5 as positive instances, and the others as negative instances.
“merror”: Multiclass classification error rate. It is calculated as #(wrong cases)/#(all cases).
“mlogloss”: Multiclass logloss
“auc”: Area under the curve for ranking evaluation.
“ndcg”:Normalized Discounted Cumulative Gain
“map”:Mean average precision
“ndcg@n”,”map@n”: n can be assigned as an integer to cut off the top positions in the lists for evaluation.
“ndcg-”,”map-”,”ndcg@n-”,”map@n-”: In XGBoost, NDCG and MAP will evaluate the score of a list without any positive samples as 1. By adding “-” in the evaluation metric XGBoost will evaluate these score as 0 to be consistent under some conditions. training repeatively
“gamma-deviance”: [residual deviance for gamma regression]

seed[ default=0 ]

random number seed.

隨機數的種子。預設值為0

dtrain：訓練的資料
num_boost_round：這是指提升迭代的次數，也就是生成多少基模型
evals：這是一個列表，用於對訓練過程中進行評估列表中的元素。形式是evals = [(dtrain,'train'),(dval,'val')]或者是evals = [(dtrain,'train')]，對於第一種情況，它使得我們可以在訓練過程中觀察驗證集的效果
obj：自定義目的函式
feval：自定義評估函式
maximize：是否對評估函式進行最大化
early_stopping_rounds：早期停止次數，假設為100，驗證集的誤差迭代到一定程度在100次內不能再繼續降低，就停止迭代。這要求evals 裡至少有一個元素，如果有多個，按最後一個去執行。返回的是最後的迭代次數（不是最好的）。如果early_stopping_rounds存在，則模型會生成三個屬性，bst.best_score，bst.best_iteration和bst.best_ntree_limit
evals_result：字典，儲存在watchlist中的元素的評估結果。
verbose_eval ：(可以輸入布林型或數值型)，也要求evals裡至少有一個元素。如果為True,則對evals中元素的評估結果會輸出在結果中；如果輸入數字，假設為5，則每隔5個迭代輸出一次。
learning_rates：每一次提升的學習率的列表，
xgb_model：在訓練之前用於載入的xgb model。

XGBoost的缺點及LightGBM的優化

XGBoost的缺點

在LightGBM提出之前，最有名的GBDT工具就是XGBoost了，它是基於預排序方法的決策樹演算法。這種構建決策樹的演算法基本思想是：首先，對所有特徵都按照特徵的數值進行預排序。其次，在遍歷分割點的時候用O(#data)的代價找到一個特徵上的最好分割點。最後，在找到一個特徵的最好分割點後，將資料分裂成左右子節點。

這樣的預排序演算法的優點是能精確地找到分割點。但是缺點也很明顯：首先，空間消耗大。這樣的演算法需要儲存資料的特徵值，還儲存了特徵排序的結果（例如，為了後續快速的計算分割點，儲存了排序後的索引），這就需要消耗訓練資料兩倍的記憶體。其次，時間上也有較大的開銷，在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。最後，對cache優化不友好。在預排序後，特徵對梯度的訪問是一種隨機訪問，並且不同的特徵訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的陣列，並且不同特徵訪問的順序也不一樣，也會造成較大的cache miss。

LightGBM的優化

為了避免上述XGBoost的缺陷，並且能夠在不損害準確率的條件下加快GBDT模型的訓練速度，lightGBM在傳統的GBDT演算法上進行了如下優化：

基於Histogram的決策樹演算法。
單邊梯度取樣 Gradient-based One-Side Sampling(GOSS)：使用GOSS可以減少大量只具有小梯度的資料例項，這樣在計算資訊增益的時候只利用剩下的具有高梯度的資料就可以了，相比XGBoost遍歷所有特徵值節省了不少時間和空間上的開銷。
互斥特徵捆綁 Exclusive Feature Bundling(EFB)：使用EFB可以將許多互斥的特徵繫結為一個特徵，這樣達到了降維的目的。
帶深度限制的Leaf-wise的葉子生長策略：大多數GBDT工具使用低效的按層生長 (level-wise) 的決策樹生長策略，因為它不加區分的對待同一層的葉子，帶來了很多沒必要的開銷。實際上很多葉子的分裂增益較低，沒必要進行搜尋和分裂。LightGBM使用了帶有深度限制的按葉子生長 (leaf-wise) 演算法。
直接支援類別特徵(Categorical Feature)
支援高效並行
Cache命中率優化

LightGBM的基本原理

基於Histogram的決策樹演算法

直方圖演算法

Histogram algorithm應該翻譯為直方圖演算法，直方圖演算法的基本思想是：先把連續的浮點特徵值離散化成 $k$ 個整數，同時構造一個寬度為 $k$ 的直方圖。在遍歷資料的時候，根據離散化後的值作為索引在直方圖中累積統計量，當遍歷一次資料後，直方圖累積了需要的統計量，然後根據直方圖的離散值，遍歷尋找最優的分割點。

直方圖演算法簡單理解為：首先確定對於每一個特徵需要多少個箱子（bin）併為每一個箱子分配一個整數；然後將浮點數的範圍均分成若干區間，區間個數與箱子個數相等，將屬於該箱子的樣本資料更新為箱子的值；最後用直方圖（#bins）表示。看起來很高大上，其實就是直方圖統計，將大規模的資料放在了直方圖中。

我們知道特徵離散化具有很多優點，如儲存方便、運算更快、魯棒性強、模型更加穩定等。對於直方圖演算法來說最直接的有以下兩個優點：

記憶體佔用更小：直方圖演算法不僅不需要額外儲存預排序的結果，而且可以只儲存特徵離散化後的值，而這個值一般用 $8$ 位整型儲存就足夠了，記憶體消耗可以降低為原來的 $\frac{1}{8}$ 。也就是說XGBoost需要用 $32$ 位的浮點數去儲存特徵值，並用 $32$ 位的整形去儲存索引，而 LightGBM只需要用 $8$ 位去儲存直方圖，記憶體相當於減少為 $\frac{1}{8}$ ；

計算代價更小：預排序演算法XGBoost每遍歷一個特徵值就需要計算一次分裂的增益，而直方圖演算法LightGBM只需要計算 $k$ 次（ $k$ 可以認為是常數），直接將時間複雜度從 $O(\#data * \#feature)$ 降低到 $O(k * \#feature)$ ，而我們知道 $\#data >> k$ 。

當然，Histogram演算法並不是完美的。由於特徵被離散化後，找到的並不是很精確的分割點，所以會對結果產生影響。但在不同的資料集上的結果表明，離散化的分割點對最終的精度影響並不是很大，甚至有時候會更好一點。原因是決策樹本來就是弱模型，分割點是不是精確並不是太重要；較粗的分割點也有正則化的效果，可以有效地防止過擬合；即使單棵樹的訓練誤差比精確分割的演算法稍大，但在梯度提升（Gradient Boosting）的框架下沒有太大的影響。

直方圖做差加速

LightGBM另一個優化是Histogram（直方圖）做差加速。一個葉子的直方圖可以由它的父親節點的直方圖與它兄弟的直方圖做差得到，在速度上可以提升一倍。通常構造直方圖時，需要遍歷該葉子上的所有資料，但直方圖做差僅需遍歷直方圖的k個桶。在實際構建樹的過程中，LightGBM還可以先計算直方圖小的葉子節點，然後利用直方圖做差來獲得直方圖大的葉子節點，這樣就可以用非常微小的代價得到它兄弟葉子的直方圖。

注意：XGBoost 在進行預排序時只考慮非零值進行加速，而 LightGBM 也採用類似策略：只用非零特徵構建直方圖。

帶深度限制的 Leaf-wise 演算法

在Histogram演算法之上，LightGBM進行進一步的優化。首先它拋棄了大多數GBDT工具使用的按層生長 (level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 演算法。

XGBoost 採用 Level-wise 的增長策略，該策略遍歷一次資料可以同時分裂同一層的葉子，容易進行多執行緒優化，也好控制模型複雜度，不容易過擬合。但實際上Level-wise是一種低效的演算法，因為它不加區分的對待同一層的葉子，實際上很多葉子的分裂增益較低，沒必要進行搜尋和分裂，因此帶來了很多沒必要的計算開銷。

LightGBM採用Leaf-wise的增長策略，該策略每次從當前所有葉子中，找到分裂增益最大的一個葉子，然後分裂，如此迴圈。因此同Level-wise相比，Leaf-wise的優點是：在分裂次數相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度；Leaf-wise的缺點是：可能會長出比較深的決策樹，產生過擬合。因此LightGBM會在Leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。

「其他文章」