|
一,、引言 GBDT(Gradient Boosting Decision Tree)在數(shù)據(jù)分析和預(yù)測(cè)中的效果很好。它是一種基于決策樹的集成算法,。其中Gradient Boosting 是集成方法boosting中的一種算法,，通過(guò)梯度下降來(lái)對(duì)新的學(xué)習(xí)器進(jìn)行迭代。而GBDT中采用的就是CART決策樹,。 Boosting指把多個(gè)弱學(xué)習(xí)器相加,，產(chǎn)生一個(gè)新的強(qiáng)學(xué)習(xí)器。經(jīng)典的例子有：adaboost, GBDT, xgboost等,。如果每一個(gè)弱學(xué)習(xí)器用fi(x) 來(lái)表示的話,，那么Boosting的強(qiáng)學(xué)習(xí)器就可以表示為：
通俗的來(lái)說(shuō)就相當(dāng)于把多個(gè)學(xué)習(xí)器串聯(lián)（bagging是并聯(lián)）。 二,、Regression Desicion Tree：回歸樹 2.1 回歸樹簡(jiǎn)介 決策樹模型分為分類樹和回歸樹,，分類樹常用來(lái)分類問(wèn)題，回歸樹常用來(lái)預(yù)測(cè)問(wèn)題,。分類樹常用于分類標(biāo)簽值,，比如用戶性別、網(wǎng)頁(yè)是否是垃圾頁(yè)面,、用戶是不是作弊,；而回歸樹常用于預(yù)測(cè)真實(shí)數(shù)值,，比如用戶的年齡、用戶點(diǎn)擊的概率,、網(wǎng)頁(yè)相關(guān)程度等等,。 回歸樹總體流程類似于分類樹，區(qū)別在于,，回歸樹的每一個(gè)節(jié)點(diǎn)都會(huì)得到一個(gè)預(yù)測(cè)值,，以年齡為例，該預(yù)測(cè)值等于屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值,。分枝時(shí)窮舉每一個(gè)feature的每個(gè)閾值尋找最優(yōu)切分變量和最優(yōu)切分點(diǎn),，但衡量的準(zhǔn)則不再是分類樹中的基尼系數(shù)，而是平方誤差最小化,。也就是被預(yù)測(cè)錯(cuò)誤的人數(shù)越多,，平方誤差就越大，通過(guò)最小化平方誤差找到最可靠的分枝依據(jù),。分枝直到每個(gè)葉子節(jié)點(diǎn)上人的年齡都唯一或者達(dá)到預(yù)設(shè)的終止條件(如葉子個(gè)數(shù)上限),，若最終葉子節(jié)點(diǎn)上人的年齡不唯一，則以該節(jié)點(diǎn)上所有人的平均年齡做為該葉子節(jié)點(diǎn)的預(yù)測(cè)年齡,。 由于GBDT的核心在于累加所有樹的結(jié)果作為最終結(jié)果,，而分類樹得到的離散分類結(jié)果對(duì)于預(yù)測(cè)分類并不是這么的容易疊加（稍等后面會(huì)看到，其實(shí)并不是簡(jiǎn)單的疊加,，而是每一步每一棵樹擬合的殘差和選擇分裂點(diǎn)評(píng)價(jià)方式都是經(jīng)過(guò)公式推導(dǎo)得到的）,，而對(duì)基于回歸樹所得到的數(shù)值進(jìn)行加減是有意義的（例如10歲+5歲-3歲=12歲），這是區(qū)別于分類樹的一個(gè)顯著特征（畢竟男+女=是男是女?,，這樣的運(yùn)算是毫無(wú)道理的）,，GBDT在運(yùn)行時(shí)就使用到了回歸樹的這個(gè)性質(zhì)，它將累加所有樹的結(jié)果作為最終結(jié)果,。所以GBDT中的樹都是回歸樹,，而不是分類樹，它用來(lái)做回歸預(yù)測(cè),，當(dāng)然回歸樹經(jīng)過(guò)調(diào)整之后也能用來(lái)做分類。（如何做分類,，稍后會(huì)介紹,，這是一個(gè)需要注意的地方） 2.2 回歸樹的生成 首先看一個(gè)簡(jiǎn)單的回歸樹生成實(shí)例：
接下來(lái)具體說(shuō)說(shuō)回歸樹是如何進(jìn)行特征選擇生成二叉回歸樹的。 假設(shè)X 與Y 分別為輸入和輸出變量,，并且Y 是連續(xù)變量,，給定訓(xùn)練數(shù)據(jù)集
我們利用最小二乘回歸樹生成算法來(lái)生成回歸樹f(x)，即在訓(xùn)練數(shù)據(jù)集所在的輸入空間中,，遞歸地將每個(gè)區(qū)域分為兩個(gè)子區(qū)域并決定每個(gè)子區(qū)域上的輸出值,，構(gòu)建二叉決策樹,，步驟如下： 1）選擇最優(yōu)切分變量j 與切分點(diǎn)s ，求解
遍歷變量j ,，對(duì)固定的切分變量j 掃描切分點(diǎn)s，選擇使上式達(dá)到最小值得對(duì)j ,s 2）用選定的對(duì)( j , s ) 劃分區(qū)域并決定相應(yīng)的輸出值：
3）繼續(xù)對(duì)兩個(gè)子區(qū)域調(diào)用步驟（1）,，（2）,，直至滿足停止條件。 4）將輸入空間劃分為M MM個(gè)區(qū)域R 1 , R 2 , ? ? ? , Rm ,，在每個(gè)單元R m上有一個(gè)固定的輸出值cm,生成決策樹
三,、Boosting Decision Tree：提升樹 3.1 提升樹模型 提升方法采用加法模型（即基函數(shù)的線性組合）與前向分布算法。以決策樹為基函數(shù)的提升方法稱為提升樹（Boosting tree）,。對(duì)分類問(wèn)題構(gòu)建的決策樹是二叉分類樹,，對(duì)回歸問(wèn)題構(gòu)建決策樹是二叉回歸樹。提升樹是迭代多棵回歸樹來(lái)共同決策,。當(dāng)采用平方誤差損失函數(shù)時(shí),，每一棵回歸樹學(xué)習(xí)的是之前所有樹的結(jié)論和殘差,，擬合得到一個(gè)當(dāng)前的殘差回歸樹,，殘差的意義如公式：殘差 = 真實(shí)值 - 預(yù)測(cè)值 ,。提升樹即是整個(gè)迭代過(guò)程生成的回歸樹的累加。提升樹模型可以表示為決策樹的加法模型,。
其中T ( x ; Θ m ) 表示決策樹；Θ m為決策樹的參數(shù),；M 為樹的個(gè)數(shù)。 3.2 提升樹算法 對(duì)回歸問(wèn)題的提升樹算法來(lái)說(shuō),，給定當(dāng)前模型fm?1 ( x )只需要簡(jiǎn)單地?cái)M合當(dāng)前模型的殘差。現(xiàn)將回歸問(wèn)題的提升樹算法敘述如下: 1）初始化f 0 ( x ) = 0 2）對(duì)m = 1 , 2 , ? ? ? , M a）計(jì)算殘差
b）擬合殘差rmi學(xué)習(xí)一個(gè)回歸樹,，得到T ( x ; Θ m ) c）更新f m ( x ) = f m ? 1 ( x ) + T ( x ; Θ m ) 3）得到回歸問(wèn)題提升樹
接下來(lái)通過(guò)訓(xùn)練一個(gè)用于預(yù)測(cè)年齡的模型來(lái)展現(xiàn)算法的運(yùn)行流程: 1）首先,，訓(xùn)練集有4個(gè)人A , B , C , D，它們的年齡分別是14 , 16 , 24 , 26 ,，其中A , B分別是高一和高三學(xué)生,；C , D 分別是應(yīng)屆畢業(yè)生和工作兩年的員工，可用于分枝的特征包括上網(wǎng)時(shí)長(zhǎng)、購(gòu)物金額,、上網(wǎng)時(shí)段和對(duì)百度知道的使用方式,。如果是一棵傳統(tǒng)的回歸決策樹來(lái)訓(xùn)練，會(huì)得到下圖所示結(jié)果：
2）但是如果用GBDT來(lái)做這件事,，由于數(shù)據(jù)太少,，我們限定葉子節(jié)點(diǎn)最多有兩個(gè)，即每棵樹都只有一個(gè)分枝,，并且限定只限定兩棵樹。我們會(huì)得到如下所示結(jié)果：
第一棵樹的分枝與之前一樣,，也是使用購(gòu)物金額進(jìn)行區(qū)分,，兩撥人各自用年齡均值作為預(yù)測(cè)值，得到殘差值-1,、1,、-1、1,，然后拿這些殘差值替換初始值去訓(xùn)練生成第二棵回歸樹,，如果新的預(yù)測(cè)值和殘差相等，則只需把第二棵樹的結(jié)論累加到第一棵樹上就能得到真實(shí)年齡了,。第二棵樹只有兩個(gè)值1和-1,，直接可分成兩個(gè)節(jié)點(diǎn)。此時(shí)所有人的殘差都是0,，即每個(gè)人都得到了真實(shí)的預(yù)測(cè)值,。 3）將兩棵回歸樹預(yù)測(cè)結(jié)果進(jìn)行匯總，解釋如下： A：14歲高一學(xué)生,；購(gòu)物較少,；經(jīng)常問(wèn)學(xué)長(zhǎng)問(wèn)題；預(yù)測(cè)年齡A = 15 – 1 = 14 B：16歲高三學(xué)生,；購(gòu)物較少,；經(jīng)常被學(xué)弟問(wèn)問(wèn)題；預(yù)測(cè)年齡B = 15 + 1 = 16 C：24歲應(yīng)屆畢業(yè)生,；購(gòu)物較多,，經(jīng)常問(wèn)師兄問(wèn)題；預(yù)測(cè)年齡C = 25 – 1 = 24 D：26歲工作兩年員工,；購(gòu)物較多,，經(jīng)常被師弟問(wèn)問(wèn)題；預(yù)測(cè)年齡D = 25 + 1 = 26 對(duì)比初始的回歸樹與GBDT所生成的回歸樹,，可以發(fā)現(xiàn)，最終的結(jié)果是相同的，那我們?yōu)槭裁催€要使用GBDT呢,？答案就是對(duì)模型過(guò)擬合的考慮,。過(guò)擬合是指為了讓訓(xùn)練集精度更高，學(xué)到了很多“僅在訓(xùn)練集上成立的規(guī)律”,，導(dǎo)致?lián)Q一個(gè)數(shù)據(jù)集后,，當(dāng)前規(guī)律的預(yù)測(cè)精度就不足以使人滿意了。畢竟,，在訓(xùn)練精度和實(shí)際精度（或測(cè)試精度）之間,，后者才是我們想要真正得到的。 在上面這個(gè)例子中,，初始的回歸樹為達(dá)到100%精度使用了3個(gè)特征（上網(wǎng)時(shí)長(zhǎng),、時(shí)段、網(wǎng)購(gòu)金額）,，但觀察發(fā)現(xiàn),，分枝“上網(wǎng)時(shí)長(zhǎng)>1.1h”很顯然過(guò)擬合了，不排除恰好A上網(wǎng)1.5h, B上網(wǎng)1小時(shí),，所以用上網(wǎng)時(shí)間是不是>1.1小時(shí)來(lái)判斷所有人的年齡很顯然是有悖常識(shí)的,。 而在GBDT中，兩棵回歸樹僅使用了兩個(gè)特征（購(gòu)物金額與對(duì)百度知道的使用方式）就實(shí)現(xiàn)了100%的預(yù)測(cè)精度,，其分枝依據(jù)更合乎邏輯（當(dāng)然這里是相比較于上網(wǎng)時(shí)長(zhǎng)特征而言）,，算法在運(yùn)行中也體現(xiàn)了“如無(wú)必要，勿增實(shí)體”的奧卡姆剃刀原理,。 3.3 提升樹實(shí)例 下表為訓(xùn)練數(shù)據(jù),，x xx的取值范圍為區(qū)間[ 0.5 , 10.5 ]，y yy的取值范圍為區(qū)間[ 5.0 , 10.0 ] ,，學(xué)習(xí)這個(gè)回歸問(wèn)題的提升樹模型,，考慮只用二叉樹作為基函數(shù)：
（1）步驟一：求f 1 ( x ) 即回歸樹T 1 ( x ) 首先通過(guò)以下優(yōu)化問(wèn)題：
求解訓(xùn)練數(shù)據(jù)的切分點(diǎn)s：
容易求得在R 1 ， R 2 內(nèi)部使平方誤差達(dá)到最小值的c 1 , c 2 為
這里N 1 , N 2 是R 1 , R 2 的樣本點(diǎn)數(shù),。具體地,，求解訓(xùn)練數(shù)據(jù)的切分點(diǎn)。根據(jù)所給數(shù)據(jù),，考慮如下切分點(diǎn)：
對(duì)各切分點(diǎn),，不難求出相應(yīng)的R 1 , R 2 , c 1 , c 2 及
例如，當(dāng)s = 2.5時(shí),，
遍歷所有的s,，計(jì)算m ( s )，結(jié)果列表如下：
可知當(dāng)s = 6.5 時(shí)m ( s ) 達(dá)到最小值,，此時(shí)
所以回歸樹T 1 ( x ) 為
用f 1 ( x )擬合訓(xùn)練數(shù)據(jù)的殘差,，表中r 2 i = y i ? f 1 ( x i )
平方損失誤差為：
（2）步驟二：求T 2 ( x ) 方法與求T 1 ( x )一樣,，只是擬合的數(shù)據(jù)是上一步得到的殘差，可以得到：
用f 2 ( x )擬合訓(xùn)練數(shù)據(jù)的平方損失誤差是：
繼續(xù)迭代
用f 6 ( x )擬合訓(xùn)練數(shù)據(jù)的平方損失誤差是
假設(shè)此時(shí)已滿足誤差要求,，那么f ( x ) = f 6 ( x )即為所求提升樹,。 四、Gradient Boosting Decision Tree：梯度提升決策樹 4.1 GBDT簡(jiǎn)介 提升樹利用加法模型與前向分布算法實(shí)現(xiàn)學(xué)習(xí)的優(yōu)化過(guò)程,，即是通過(guò)迭代得到一系列的弱分類器,，進(jìn)而通過(guò)不同的組合策略得到相應(yīng)的強(qiáng)學(xué)習(xí)器。在GBDT的迭代中,，假設(shè)前一輪得到的學(xué)習(xí)器為f t ? 1 ( x ) 對(duì)應(yīng)的損失函數(shù)則為L(zhǎng) ( y , f t ? 1 ( x ) ) ,。因此新一輪迭代的目的就是找到一個(gè)弱分類器h t ( x ) ，使得損失函數(shù)L ( y , f t ? 1 ( x ) + h t ( x ) ) 達(dá)到最小,。因此問(wèn)題的關(guān)鍵就在于對(duì)損失函數(shù)的度量,，這也正是難點(diǎn)所在。當(dāng)損失函數(shù)是平方損失和指數(shù)損失時(shí),，每一步優(yōu)化是很簡(jiǎn)單的,。但對(duì)一般損失函數(shù)而言，往往每一步優(yōu)化沒(méi)那么容易,，如絕對(duì)值損失函數(shù)和Huber損失函數(shù),。常見的損失函數(shù)及其梯度如下表所示：
那我們?cè)趺礃硬拍苷业揭环N通用的擬合方法呢？ 針對(duì)這一問(wèn)題,，F(xiàn)reidman提出了梯度提升算法：利用最速下降的近似方法,，即利用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值
作為回歸問(wèn)題中提升樹算法的殘差的近似值（與其說(shuō)負(fù)梯度作為殘差的近似值，不如說(shuō)殘差是負(fù)梯度的一種特例,，擬合一個(gè)回歸樹）,，這就是梯度提升決策樹。 4.2 GBDT算法步驟算法步驟如下：
接下來(lái)對(duì)上圖中的算法步驟進(jìn)行詳細(xì)解釋： 1）初始化弱分類器,，估計(jì)使損失函數(shù)極小化的一個(gè)常數(shù)值,，此時(shí)樹僅有一個(gè)根結(jié)點(diǎn)
2）對(duì)迭代輪數(shù)1 , 2 , ? ? ? , M(即產(chǎn)生樹的個(gè)數(shù)為M ) a）對(duì)i = 1 , 2 , ? ? ? , N（N 個(gè)樣本），計(jì)算損失函數(shù)的負(fù)梯度值在當(dāng)前模型的值,，將它作為殘差的估計(jì),。即
對(duì)于平方損失函數(shù)，它就是通常所說(shuō)的殘差,；對(duì)于一般損失函數(shù),，它就是殘差的近似值。 b）對(duì)rmi擬合一個(gè)回歸樹,，得到第m 棵樹的葉結(jié)點(diǎn)區(qū)域Rmj j=1,2 ,? ? ? ,J c）對(duì)j = 1 , 2 , ? ? ? , J 計(jì)算
即利用線性搜索估計(jì)葉結(jié)點(diǎn)區(qū)域的值,，使損失函數(shù)極小化。 d）更新回歸樹
I(x)為Indicator函數(shù),，即樣本x屬于哪個(gè)葉節(jié)點(diǎn),，即加上這個(gè)葉節(jié)點(diǎn)的cmj ,。在這里，其實(shí)應(yīng)該有ρ ,，只不過(guò)圖中沒(méi)有標(biāo)注而已,，具體在4.3節(jié)例子中可以看到。 3）得到輸出的最終模型
NOTE: 在這里,，需要仔細(xì)解釋下上述算法的注意事項(xiàng)： （1）選擇不同的損失函數(shù)，梯度值不一樣 當(dāng)損失函數(shù)為MSE時(shí),，梯度值為
當(dāng)損失函數(shù)為MAE時(shí),，梯度值為
當(dāng)損失函數(shù)為logistic loss時(shí)：(二分類任務(wù)） 損失函數(shù)為：
梯度值為：
（2）葉子節(jié)點(diǎn)的取值和所選擇的loss function有關(guān)。對(duì)于不同的Loss function,，葉子節(jié)點(diǎn)的值也不一樣,。 選擇MSE作為loss function時(shí)：
選擇MAE作為L(zhǎng)oss function時(shí)：
選擇Logistic loss作為L(zhǎng)oss function時(shí)：
選擇指數(shù)損失作為loss function時(shí)：
4.3 GBDT實(shí)例在介紹完GBDT的訓(xùn)練過(guò)程和細(xì)節(jié)后，可能大家還有些懵,。我們舉例來(lái)說(shuō)明GBDT的訓(xùn)練過(guò)程,，可以清晰地看明白過(guò)程。為了方便說(shuō)明,，我們用下面這個(gè)很簡(jiǎn)單的數(shù)據(jù),。
決策樹學(xué)習(xí)最關(guān)鍵的步驟就是選擇最優(yōu)劃分屬性,，一般而言,，隨著劃分過(guò)程不斷的進(jìn)行，我們希望決策樹的分支節(jié)點(diǎn)所包含的樣本盡可能屬于同一類別（方差?。?。通常，我們會(huì)選擇一個(gè)準(zhǔn)則來(lái)評(píng)價(jià)劃分的質(zhì)量,，比如回歸樹中經(jīng)常使用的MSE（這種方法屬于啟發(fā)式的）對(duì)于連續(xù)值,，我們可以窮盡每個(gè)值v ，把每個(gè)值v 作為一個(gè)分裂點(diǎn)(< = v 和> v ),然后計(jì)算兩個(gè)分支的MSE left ,、 MSE right ,。選擇最小的MSE sum =MSE left+ MSE right 的分裂點(diǎn)v。當(dāng)然關(guān)于連續(xù)值,，也可以把屬性值從小到大排序,，選擇每2個(gè)值的中值進(jìn)行判斷,。 對(duì)于類別型特征，我們有類似的做法,，通過(guò)= 和≠ 來(lái)劃分,。當(dāng)選擇1 作為分裂點(diǎn)時(shí)候，MSE left= 0 ,，MSE right= 1.747 ,；當(dāng)選擇2 作為分裂點(diǎn)時(shí)候，MSE left= 0.0049 ,， MSE right = 1.5091 依次,，窮盡所有取值?？梢缘玫疆?dāng)選擇6 66作為分裂點(diǎn)時(shí)MSE sum = 0.3276最小,。
至此，我們完成了第一顆樹的擬合,，擬合完之后我們得到了Rjm以及cjm ,具體為：
最后更新f1( x i )值
為了防止過(guò)擬合,，會(huì)增加一個(gè)學(xué)習(xí)率系數(shù)
當(dāng)ρ = 0.1 時(shí)，上面的計(jì)算結(jié)果變?yōu)?/p>
至此一輪迭代（第一個(gè)顆樹擬合）完成,，下面開始第二輪迭代（第二顆樹擬合）,。 （3）步驟三：擬合第二顆樹（m = 2 ) 比如，這里示范計(jì)算
其他由公式計(jì)算可以得到下表：
因此,，在第二顆樹中,，擬合的是新的梯度值。下面的過(guò)程就是建樹->計(jì)算葉子節(jié)點(diǎn)的值,、葉子節(jié)點(diǎn)的區(qū)間->更新f 2 ( x ),。所以就不在累述了。 最后得到兩個(gè)葉子節(jié)點(diǎn)值分別為：
最后,，我們來(lái)看一下如何進(jìn)行預(yù)測(cè),。
給定一個(gè)新樣本x時(shí)，預(yù)測(cè)值就是F2(x),。 五,、總結(jié) 我們來(lái)簡(jiǎn)單的總結(jié)一下。 回頭看,，其實(shí)GBDT的思路是很簡(jiǎn)單的,，每一次用一個(gè)回歸樹來(lái)擬合一個(gè)梯度值。而這個(gè)梯度值就只是損失函數(shù)的一階導(dǎo)數(shù)在當(dāng)前模型的取值,。擬合完一顆樹之后,，需要計(jì)算葉子節(jié)點(diǎn)的值，而這個(gè)值是和損失函數(shù)有關(guān)的,，當(dāng)然,，數(shù)學(xué)大神們已經(jīng)為我們計(jì)算好常用的一些損失函數(shù)的葉子節(jié)點(diǎn)取值,。最終預(yù)測(cè)結(jié)果其實(shí)就是每一顆樹的預(yù)測(cè)結(jié)果相加，所以整個(gè)過(guò)程都非常的好理解,。即為：初始化->計(jì)算負(fù)梯度值->用回歸樹擬合負(fù)梯度值->計(jì)算葉子節(jié)點(diǎn)值->更新f m ( x ),。 原文鏈接：https://blog.csdn.net/anshuai_aw1/article/details/82888222 |
|
|
