Python機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)

Author：louwill

Machine Learning Lab

? ? ?

???? 自從陳天奇于2015年提出XGBoost以來(lái)，該模型就一直在各大數(shù)據(jù)競(jìng)賽中當(dāng)作大殺器被頻繁祭出。速度快、效果好是XGBoost的最大優(yōu)點(diǎn)。XGBoost與GBDT同出一脈，都屬于boosting集成學(xué)習(xí)算法，但XGBoost相較于GBDT要青出于藍(lán)而勝于藍(lán)。

???? XGBoost的全程為eXtreme Gradient Boosting，即極端梯度提升樹。要深入理解整個(gè)XGBoost模型系統(tǒng)，建議還是要認(rèn)真研讀陳天奇的 XGBoost: A Scalable Tree Boosting System 論文，深入損失函數(shù)的推導(dǎo)，這樣才能更好的掌握XGBoost。本文僅對(duì)模型最重要的部分，即XGBoost損失函數(shù)的數(shù)學(xué)推導(dǎo)過(guò)程和結(jié)點(diǎn)分裂的增益計(jì)算方式進(jìn)行闡述。

XGBoost原理推導(dǎo)

???? 既然XGBoost整體上仍然屬于GBDT系統(tǒng)，那么XGBoost也一定是由多個(gè)基模型組成的一個(gè)加法模型，所以XGBoost可表示為：

???? 假設(shè)?第??次迭代要訓(xùn)練的樹模型是??，可得：

???? 下面進(jìn)入正題，推導(dǎo)XGBoost損失函數(shù)：

???? 損失函數(shù)原始形式可表示為：

???? 其中，??為損失函數(shù)的正則化項(xiàng)，表示全部??棵樹的復(fù)雜度之和，旨在防止模型過(guò)擬合。

???? XGBoost來(lái)自于GBDT，同樣也適用前向分步算法，以第??步的模型為例，模型對(duì)第??個(gè)樣本??的預(yù)測(cè)值為：

???? 其中，??是由第 ?? 步的模型給出的預(yù)測(cè)值，作為一個(gè)已知常數(shù)存在， ?? 是第??步樹模型的預(yù)測(cè)值。所以，目標(biāo)函數(shù)可以改寫為：

???? 同時(shí)也可以對(duì)正則化項(xiàng)進(jìn)行拆分，由于前?棵樹的結(jié)構(gòu)已經(jīng)確定，因此前?? 棵樹的復(fù)雜度之和也可以表示為常數(shù)：

???? 然后我們使用二階泰勒公式(這里需要大家回顧微積分相關(guān)知識(shí))，可以將損失函數(shù)改寫為：

???? 其中，??為損失函數(shù)的一階導(dǎo)，??為損失函數(shù)的二階導(dǎo)，需要注意的是這里是對(duì)??求導(dǎo)。XGBoost相較于GBDT而言用到了二階導(dǎo)數(shù)信息，所以如果要自定義損失函數(shù)，首要的要求是其二階可導(dǎo)。

???? 以平方損失函數(shù)為例：

???? 則有：

???? 將該二階泰勒展開式帶入前述推導(dǎo)的XGBoost損失函數(shù)中，可得損失函數(shù)的近似表達(dá)式：

???? 對(duì)上式去除相關(guān)常數(shù)項(xiàng)，簡(jiǎn)化后的損失函數(shù)為：

???? 所以只需要求出每一步損失函數(shù)的一階導(dǎo)和二階導(dǎo)的值，然后最優(yōu)化目標(biāo)函數(shù)，就可以得到每一步的??，最后根據(jù)加法模型得到一個(gè)boosting模型。

???? 然后重新定義一棵決策樹，其包括兩個(gè)部分：葉子結(jié)點(diǎn)的權(quán)重向量??和實(shí)例(樣本)到葉子結(jié)點(diǎn)的映射關(guān)系??(本質(zhì)是樹的分支結(jié)構(gòu))；

???? 所以一顆樹的數(shù)學(xué)表達(dá)為：

???? 再來(lái)看定義模型復(fù)雜度的正則化項(xiàng)。模型復(fù)雜度??可由單棵樹的葉子結(jié)點(diǎn)數(shù) ???和葉子權(quán)重 ?? ，具體來(lái)說(shuō)損失函數(shù)的復(fù)雜度由所有樹的葉子結(jié)點(diǎn)數(shù)和葉子權(quán)重所決定。數(shù)學(xué)表達(dá)如下式所示：

???? 然后我們對(duì)所有葉子結(jié)點(diǎn)進(jìn)行重新歸組。將屬于第??個(gè)葉子結(jié)點(diǎn)的所有樣本??劃入到一個(gè)葉子結(jié)點(diǎn)的樣本集合中，即：??，從而XGBoost的目標(biāo)函數(shù)可以改寫為：

定義??，??簡(jiǎn)化一下表達(dá)，含義如下：

• ?：葉子結(jié)點(diǎn) ?? 所包含樣本的一階偏導(dǎo)數(shù)累加之和，是一個(gè)常量；

• ?：葉子結(jié)點(diǎn) ?? 所包含樣本的二階偏導(dǎo)數(shù)累加之和，是一個(gè)常量；

將??和??帶入前述XGBoost損失函數(shù)，可得最終的損失函數(shù)表達(dá)式為：

根據(jù)一元二次方程的求解公式，可得：

代入到XGBoost的最終損失函數(shù)，可得損失為：

對(duì)于每個(gè)葉子結(jié)點(diǎn) ??將其從目標(biāo)函數(shù)中拆解出來(lái)，有:

???? 由前述推導(dǎo)可知，??和??相對(duì)于第??棵樹來(lái)說(shuō)是可以計(jì)算出來(lái)的。所以該式就是一個(gè)只包含一個(gè)變量葉子結(jié)點(diǎn)權(quán)重??的一元二次函數(shù)，可根據(jù)最值公式求其最值點(diǎn)。當(dāng)相互獨(dú)立的每棵樹的葉子結(jié)點(diǎn)都達(dá)到最優(yōu)值時(shí)，整個(gè)損失函數(shù)也相應(yīng)的達(dá)到最優(yōu)。

???? 當(dāng)樹結(jié)構(gòu)固定的情況下，對(duì)上式求導(dǎo)并令其為0，可得最優(yōu)點(diǎn)和最優(yōu)值為：

???? 以上就是XGBoost完整的損失函數(shù)推導(dǎo)過(guò)程。基本框架仍然是GBDT框架，但XGBoost的最大特色是用到了損失函數(shù)的二階導(dǎo)數(shù)信息，目的就在于能夠更加準(zhǔn)確的逼近真實(shí)損失。

???? 下圖是XGBoost論文中給出的葉子結(jié)點(diǎn)權(quán)重計(jì)算：

???? 根據(jù)二階導(dǎo)信息把XGBoost的優(yōu)化推到了極為逼近真實(shí)損失的狀態(tài)，其結(jié)點(diǎn)分裂方式就跟CART樹的結(jié)點(diǎn)分裂方式本質(zhì)上并沒有太大區(qū)別，但信息增益的計(jì)算方式有所不同。

???? 假設(shè)模型在某一節(jié)點(diǎn)完成特征分裂，分裂前的目標(biāo)函數(shù)可以寫為：

???? 分裂后的目標(biāo)函數(shù)為：

???? 則對(duì)于目標(biāo)函數(shù)來(lái)說(shuō)，分裂后的收益為：

???? 如果增益Gain>0，即分裂為兩個(gè)葉子節(jié)點(diǎn)后，目標(biāo)函數(shù)下降了，則考慮此次分裂的結(jié)果。實(shí)際處理時(shí)需要遍歷所有特征尋找最佳分裂特征。

???? 以上就是XGBoost模型核心數(shù)學(xué)推導(dǎo)部分。完整的XGBoost模型還有很多工程上的細(xì)節(jié)，這里不做過(guò)多闡述，各位讀者最好把XGBoost論文認(rèn)真研讀一遍。完整的XGBoost推導(dǎo)示意圖如下所示。

XGBoost算法實(shí)現(xiàn)

???? 有了GBDT的算法實(shí)現(xiàn)經(jīng)驗(yàn)，XGBoost實(shí)現(xiàn)起來(lái)就并沒有太多困難了，大多數(shù)底層代碼都較為類似，主要是在信息增益計(jì)算、葉子得分計(jì)算和損失函數(shù)的二階導(dǎo)信息上做一些變動(dòng)。同樣先列出代碼框架：

???? 底層的決策樹結(jié)點(diǎn)和樹模型定義基本差別不大，具體這里不再列出，可參考第15講GBDT實(shí)現(xiàn)方式。主要是繼承底層的樹結(jié)點(diǎn)和樹來(lái)定義XGBoost單棵樹和XGBoost樹模型擬合方式。

???? 定義XGBoost單棵樹模型如下：

class XGBoostTree(Tree):# 結(jié)點(diǎn)分裂def _split(self, y):col = int(np.shape(y)[1]/2)y, y_pred = y[:, :col], y[:, col:]return y, y_pred# 信息增益計(jì)算公式def _gain(self, y, y_pred):Gradient = np.power((y * self.loss.gradient(y, y_pred)).sum(), 2)Hessian = self.loss.hess(y, y_pred).sum()return 0.5 * (Gradient / Hessian)# 樹分裂增益計(jì)算def _gain_by_taylor(self, y, y1, y2):# 結(jié)點(diǎn)分裂y, y_pred = self._split(y)y1, y1_pred = self._split(y1)y2, y2_pred = self._split(y2)true_gain = self._gain(y1, y1_pred)false_gain = self._gain(y2, y2_pred)gain = self._gain(y, y_pred)return true_gain + false_gain - gain# 葉子結(jié)點(diǎn)最優(yōu)權(quán)重def _approximate_update(self, y):# y split into y, y_predy, y_pred = self._split(y)# Newton's Methodgradient = np.sum(y * self.loss.gradient(y, y_pred), axis=0)hessian = np.sum(self.loss.hess(y, y_pred), axis=0)update_approximation = gradient / hessianreturn update_approximation# 樹擬合方法def fit(self, X, y):self._impurity_calculation = self._gain_by_taylorself._leaf_value_calculation = self._approximate_updatesuper(XGBoostTree, self).fit(X, y)

???? 然后根據(jù)前向分步算法定義XGBoost模型：

class XGBoost(object):def __init__(self, n_estimators=200, learning_rate=0.001, min_samples_split=2,min_impurity=1e-7, max_depth=2):self.n_estimators = n_estimators # Number of treesself.learning_rate = learning_rate # Step size for weight updateself.min_samples_split = min_samples_split # The minimum n of sampels to justify splitself.min_impurity = min_impurity # Minimum variance reduction to continueself.max_depth = max_depth # Maximum depth for tree# 交叉熵?fù)p失self.loss = LogisticLoss()# 初始化模型self.estimators = []# 前向分步訓(xùn)練for _ in range(n_estimators):tree = XGBoostTree(min_samples_split=self.min_samples_split,min_impurity=min_impurity,max_depth=self.max_depth,loss=self.loss)self.estimators.append(tree)def fit(self, X, y):y = to_categorical(y)y_pred = np.zeros(np.shape(y))for?i?in?range(self.n_estimators):tree = self.trees[i]y_and_pred = np.concatenate((y, y_pred), axis=1)tree.fit(X, y_and_pred)update_pred?=?tree.predict(X)y_pred -= np.multiply(self.learning_rate, update_pred)def predict(self, X):y_pred = None# 預(yù)測(cè)for tree in self.estimators:update_pred = tree.predict(X)if y_pred is None:y_pred = np.zeros_like(update_pred)y_pred -= np.multiply(self.learning_rate, update_pred)y_pred = np.exp(y_pred) / np.sum(np.exp(y_pred), axis=1, keepdims=True)# 將概率預(yù)測(cè)轉(zhuǎn)換為標(biāo)簽y_pred = np.argmax(y_pred, axis=1)return y_pred

???? 使用sklearn數(shù)據(jù)作為示例：

from?sklearn?import?datasets data = datasets.load_iris() X = data.data y = data.targetX_train,?X_test,?y_train,?y_test?=?train_test_split(X,?y,?test_size=0.4,?seed=2)??clf = XGBoost() clf.fit(X_train, y_train) y_pred = clf.predict(X_test)accuracy?=?accuracy_score(y_test,?y_pred) print ("Accuracy:", accuracy) Accuracy: 0.9666666666666667

???? XGBoost也提供了原生的模型庫(kù)可供我們調(diào)用。pip安裝xgboost即可：

pip install xgboost

???? 同樣使用sklearn數(shù)據(jù)集進(jìn)行測(cè)試：

import xgboost as xgb from xgboost import plot_importance from matplotlib import pyplot as plt# 設(shè)置模型參數(shù) params = {'booster': 'gbtree','objective': 'multi:softmax', 'num_class': 3, 'gamma': 0.1,'max_depth': 2,'lambda': 2,'subsample': 0.7,'colsample_bytree': 0.7,'min_child_weight': 3,'silent': 1,'eta': 0.001,'seed': 1000,'nthread': 4, }plst = params.items()dtrain = xgb.DMatrix(X_train, y_train) num_rounds = 200 model = xgb.train(plst, dtrain, num_rounds)# 對(duì)測(cè)試集進(jìn)行預(yù)測(cè) dtest = xgb.DMatrix(X_test) y_pred = model.predict(dtest)# 計(jì)算準(zhǔn)確率 accuracy = accuracy_score(y_test, y_pred) print ("Accuracy:", accuracy) # 繪制特征重要性 plot_importance(model) plt.show(); Accuracy: 0.9166666666666666

參考資料：

XGBoost: A Scalable Tree Boosting System

https://www.jianshu.com/p/ac1c12f3fba1

往期精彩：

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法16：Adaboost

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法15：GBDT

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法14：Ridge嶺回歸

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法13：Lasso回歸

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法12：貝葉斯網(wǎng)絡(luò)

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法11：樸素貝葉斯

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法10：線性不可分支持向量機(jī)

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法8-9：線性可分支持向量機(jī)和線性支持向量機(jī)

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法7：神經(jīng)網(wǎng)絡(luò)

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法6：感知機(jī)

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法5：決策樹之CART算法

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法4：決策樹之ID3算法

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法3：k近鄰

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法2：邏輯回歸

數(shù)學(xué)推導(dǎo)+純Python實(shí)現(xiàn)機(jī)器學(xué)習(xí)算法1：線性回歸

往期精彩回顧適合初學(xué)者入門人工智能的路線及資料下載機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印機(jī)器學(xué)習(xí)在線手冊(cè)深度學(xué)習(xí)筆記專輯《統(tǒng)計(jì)學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯 AI基礎(chǔ)下載機(jī)器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)專輯獲取一折本站知識(shí)星球優(yōu)惠券，復(fù)制鏈接直接打開：https://t.zsxq.com/yFQV7am本站qq群1003271085。加入微信群請(qǐng)掃碼進(jìn)群： 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的【机器学习基础】数学推导+纯Python实现机器学习算法17：XGBoost的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。