• XGBOOST怎么生成一棵樹？

• GBDT算法是什么？

• GBDT與BT(提升樹)是一回事嗎？

本篇文章結(jié)構(gòu):

Boosting Tree(提升樹)

其中2.a步是計(jì)算殘差，2.b步通過把2.a的殘差當(dāng)作標(biāo)簽,可以使用線性回歸的方法進(jìn)行擬合殘差。通過M次循環(huán)一共得到M+1顆樹，每個(gè)輸入數(shù)據(jù)X的結(jié)果，是M+1棵樹預(yù)測的結(jié)果之和。 

GB算法

當(dāng)提升樹的損失函數(shù)是平方損失和指數(shù)損失時(shí)，每一步優(yōu)化很簡單；但是對于一般函數(shù)，優(yōu)化不是非常簡單，因此采用梯度下降法進(jìn)行優(yōu)化。至于為什么是“梯度提升”，我的理解是首先基于當(dāng)前模型損失函數(shù)的負(fù)梯度信息進(jìn)行擬合形成新的弱分類器,然后根據(jù)殘差進(jìn)行尋找該新分類器的權(quán)重!由此，即為梯度提升!

具體算法如下:

第4步，使用梯度作為標(biāo)簽進(jìn)行擬合新的一棵樹；第5步是基于殘差進(jìn)行得到新的一顆樹的權(quán)重，其中殘差來自于第i個(gè)數(shù)據(jù)的標(biāo)簽y與前m-1棵樹的差得到的。其中F(x)表示前幾棵樹的總的函數(shù)。

GBDT算法

 

有了上面的GB算法介紹，那么使用決策樹作為弱分類器的GB算法被稱為GBDT(Gradient Boosting Decision Tree)。一般采用CART得到?jīng)Q策樹，CART是采用基尼指數(shù)作為決策樹的損失增益函數(shù)?；嶂笖?shù)反應(yīng)了數(shù)據(jù)集D中任意兩個(gè)樣本不一致的概率。其基尼指數(shù)越高則數(shù)據(jù)集D的純度越高；純度越高正是決策樹每個(gè)葉子節(jié)點(diǎn)的類別越一致。信息熵和基尼指數(shù)都是《信息論》中的內(nèi)容。

XGBOOST

 

XGBOOST是GBDT算法的工程實(shí)現(xiàn)，XGBOOST的公式推導(dǎo)采用二階泰勒公式的展開形式進(jìn)行推導(dǎo)，使得每棵樹之間得變化更小，而且還使用了正則化項(xiàng)，控制了每棵樹的復(fù)雜度,進(jìn)而防止過擬合。

公式推導(dǎo)也可以參見論文XGBoost: A Scalable Tree Boosting System

XGBOOST在生成一顆樹的時(shí)候，使用如下公式進(jìn)行左右分支。

訓(xùn)練得到第M棵樹的損失函數(shù)：   

其實(shí)XGBOOST每一次分支采用的是貪心算法，對于決策說來說每次分支也是采用貪心算法，只不過每次進(jìn)行分支使用的損失函數(shù)不一樣。對于決策樹有基尼指數(shù)、信息熵等loss函數(shù)。