學(xué)習(xí)筆記-隨機(jī)森林捺癞、提升樹(shù)夷蚊、GBDT

在之前的章節(jié)里，學(xué)習(xí)了集成學(xué)習(xí)的兩個(gè)代表方式：bagging和boosting髓介，現(xiàn)在來(lái)看如果將bagging和boosting運(yùn)用在決策樹(shù)中惕鼓。

隨機(jī)森林(random forest)

隨機(jī)森林是決策樹(shù)和Bagging的結(jié)合體，并且為了增加多樣性唐础，隨機(jī)森林加入了樣本的隨機(jī)選擇箱歧。

隨機(jī)采樣的到m個(gè)子集
隨機(jī)森林使用boostrap的方式對(duì)原始數(shù)據(jù)集采樣，即有放回的采樣一膨。每個(gè)子集采樣n(數(shù)據(jù)集的大小)次呀邢，所以子集中可能有的樣本出現(xiàn)多次，有的樣本沒(méi)有出現(xiàn)豹绪。所以得到m個(gè)大小和原始數(shù)據(jù)大小一樣的樣本子集价淌。

圖片來(lái)自于網(wǎng)絡(luò)

對(duì)特征采樣
傳統(tǒng)決策樹(shù)在選擇劃分屬性時(shí)，選擇當(dāng)前所有屬性中的最優(yōu)屬性作為決策樹(shù)的劃分屬性。但隨機(jī)森林中输钩，對(duì)決策樹(shù)中的每個(gè)結(jié)點(diǎn)豺型，先從該結(jié)點(diǎn)中隨機(jī)選取k個(gè)屬性作為當(dāng)前結(jié)點(diǎn)的屬性子集仲智，然后再?gòu)倪@子集中選擇最優(yōu)的屬性买乃。下圖展示的是兩次不同結(jié)點(diǎn)所選擇的特征。通常推薦 $k=log_2d$ ,d表示當(dāng)前結(jié)點(diǎn)所有屬性的個(gè)數(shù)钓辆。

圖片來(lái)自網(wǎng)絡(luò)
最終決策
最終決策使用的是投票方式剪验，少數(shù)服從多數(shù)。

圖片來(lái)網(wǎng)絡(luò)

需要注意的是：并不是決策樹(shù)的個(gè)數(shù)越多越好前联。
優(yōu)點(diǎn)
簡(jiǎn)單功戚、容易實(shí)現(xiàn)、計(jì)算開(kāi)銷(xiāo)小似嗤、具有強(qiáng)大的性能啸臀。性能強(qiáng)大的原因是不僅包含了bagging中的樣本多樣性，還包含了來(lái)自樣本自己特征的多樣性烁落。

提升樹(shù)

在之前的筆記中乘粒，學(xué)習(xí)了cart如果解決回歸問(wèn)題和boosting集成方式，現(xiàn)在來(lái)看看如何將boosting集成方法應(yīng)用到回歸問(wèn)題中伤塌。

提升樹(shù)：以決策樹(shù)為基函數(shù)的提升方法灯萍。在提升樹(shù)中，每個(gè)基決策樹(shù)是由一個(gè)根結(jié)點(diǎn)直接連接的兩個(gè)也結(jié)點(diǎn)的簡(jiǎn)單決策樹(shù)每聪，即決策樹(shù)樁旦棉。提升樹(shù)模型可以表示為決策樹(shù)的加法模型
$f_M(x)=\sum_{m=1}^M T(x;\theta _m) \tag{1}，T(x\theta)=\sum^J_{j=1} c_jI(x \in R_j)$
其中药薯， $T(x;\theta _m)$ 表示決策樹(shù)绑洛，m表示第m課決策樹(shù)樁，M為決策樹(shù)的個(gè)數(shù), $J$ 表示將輸入空間劃分為 $J$ 個(gè)互不相交的區(qū)域童本， $R_1,R_2,...,R_J$ ,并且在每個(gè)區(qū)域上的輸出為 $c_1,c_2,...,c_J$ , $\theta=\{ (R_1,c_1), (R_2,c_2),...,(R_J,c_J)\}$ 表示樹(shù)的空間劃分和每個(gè)區(qū)域上確定的輸出常量 $c_j$ 真屯。

回歸問(wèn)題下使用前向分布算法
第一步：設(shè)
$f(x)=0 \tag{2}$
第二步：
$f_m=f_{m-1} + T(x; \theta)，m=1,2,...,M \tag{3}$
第三步：整體模型表示
$f_M=\sum_{m=1}^M T(x;\theta) \tag{4}$
第四步：寫(xiě)出第m步的損失函數(shù)
在回歸問(wèn)題中巾陕，使用mse作為損失函數(shù) 讨跟，所以決策樹(shù)的目標(biāo)是最小化mse損失函數(shù)。
$argmin \sum_{i=1}^N L(y_i-f_m) \tag{5}$
在第m步鄙煤，給定當(dāng)前模型 $f_{m-1}(x)$ 晾匠，即前m-1個(gè)決策樹(shù)。（在第m步梯刚，前m-1個(gè)模型肯定是已經(jīng)求出）
所以第m步的損失函數(shù)可以將式（5）改寫(xiě)為：
$argmin \sum_{i=1}^N L(y_i-f_{m-1}(x_i) -T(x_i;\theta)) \tag{6}$
第五步：求參數(shù) $\theta$
回歸問(wèn)題使用MSE作為損失函數(shù)
$L(y, f(x))=(y-f_{m}(x))^2 \tag{7}$
$L(y, f(x))=(y-f_{m-1}(x) -T(x;\theta)) ^2 \tag{8}$
令 $r=y-f_{m-1}(x)$ 凉馆，損失函數(shù)變?yōu)?br> $L(y, f(x))=(r -T(x;\theta)) ^2 \tag{9}$

r就是當(dāng)前模型需要擬合的殘差，所以提升樹(shù)的回歸問(wèn)題來(lái)說(shuō)就是簡(jiǎn)單的擬合數(shù)據(jù)的殘差即可。
為什么擬合殘差就行
擬合殘差意味著使當(dāng)前模型的輸出逼近殘差澜共，從式(9)可以看到損失函數(shù)變?yōu)榱?img class="math-inline" src="https://math.jianshu.com/math?formula=(r%20-T(x%3B%5Ctheta))%20%5E2" alt="(r -T(x;\theta)) ^2" mathimg="1">,要最小化損失函數(shù)只需要最小化 $r$ 與當(dāng)前模型輸出的差值即可向叉，并且構(gòu)成 $r$ 的 $y$ 與 $f_{m-1}(x)$ 都是已知的。所以提升樹(shù)在回歸問(wèn)題中擬合殘差即可嗦董。
例子（來(lái)自于統(tǒng)計(jì)學(xué)習(xí)方法P180）
現(xiàn)在有輸入數(shù)據(jù)x和輸出數(shù)據(jù)y

對(duì)于以上數(shù)據(jù)母谎，可能的切分點(diǎn)有。
(1) 對(duì)于所有可能的切分點(diǎn)計(jì)算MSE損失和最優(yōu)輸出
例如以1.5作為分界點(diǎn)
,
,
所以
同理計(jì)算其他切分點(diǎn)的損失京革，如下圖所示

（2）選擇使損失最小的切分點(diǎn)
當(dāng)時(shí)奇唤，損失函數(shù)最小為1.93,對(duì)應(yīng)的劃分輸出為,,得到樹(shù)

(3) 根據(jù)樹(shù)計(jì)算下一個(gè)樹(shù)需要擬合的殘差

（4）重復(fù)上述過(guò)程，依次計(jì)算

(5) 將所有樹(shù)的區(qū)間疊加得到
這步根據(jù)式（1）得到

GBDT

提升樹(shù)利用加法模型與前向分步算法實(shí)現(xiàn)學(xué)習(xí)的優(yōu)化過(guò)程匹摇。當(dāng)損失函數(shù)使平方損失和指數(shù)損失時(shí)咬扇，每一步的優(yōu)化是很簡(jiǎn)單的。但對(duì)于一般損失函數(shù)而言廊勃，每一步優(yōu)化并不容易懈贺。GBDT利用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值
$-[\frac {\partial L(y,f(x_i)) }{\partial f(x_i)}]_{f(x)= f_{m-1}(x)}$
作為回歸問(wèn)題提升樹(shù)算法中的殘差的近似值，擬合一個(gè)回歸樹(shù)坡垫。
注意：當(dāng)損失函數(shù)為MSE時(shí)梭灿，負(fù)梯度就是殘差，其他損失函數(shù)時(shí)葛虐，只是近似殘差胎源。

從泰勒展開(kāi)看看GBDT
泰勒展開(kāi)式如下:

來(lái)自[5]

GBDT的損失函數(shù)如下：
$L(y, f_m(x_i))=L(y, f_{m-1}(x)+T(x;\theta))$
使用一階泰勒展開(kāi)損失函數(shù)，將此處的 $f_{m-1}$ 當(dāng)作a屿脐， $T(x;\theta)$ 當(dāng)作h涕蚤，帶入泰勒展開(kāi)式得到
$L(y, f_{m-1}(x)+T(x_i;\theta)=L(y, f_{m-1})+f^{\prime }_{m- 1(x)} T(x;\theta)$
要使損失函數(shù)最小，等式右邊 $L(y, f_{m-1})$ 是個(gè)常數(shù)的诵，那么令 $T(x;\theta)$ 為 $f^{\prime }_{m- 1(x)}$ 的負(fù)方向即可保證等式右邊的損失函數(shù)比前一個(gè)樹(shù)的損失函數(shù)小
$T(x;\theta)=-f^{\prime }_{m- 1(x)}$
帶入式中得到
$L(y, f_{m-1}(x)+T(x_i;\theta)=L(y, f_{m-1})+f^{\prime }_{m- 1(x)} T(x;\theta)$ 變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=L(y%2C%20f_%7Bm-1%7D(x)%2BT(x_i%3B%5Ctheta)%3DL(y%2C%20f_%7Bm-1%7D)-f%5E%7B%5Cprime%202%7D_%7Bm-%201(x)%7D" alt="L(y, f_{m-1}(x)+T(x_i;\theta)=L(y, f_{m-1})-f^{\prime 2}_{m- 1(x)}" mathimg="1">
綜上所述万栅，擬合損失函數(shù)的負(fù)梯度即可保證模型趨向擬合。

GDBT流程
輸入：訓(xùn)練數(shù)據(jù)集 $T={(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}$ ,損失函數(shù)為 $L(y,f(x))$
輸出回歸樹(shù)
（1）初始化
$f_0(x)=\underset{c}{argmin} \sum^{N}_{i=1} L(y_i,c)$ 西疤，這里的c是所有均值
（2）對(duì) $m=1,2,...,M$

對(duì) $i=1,2,...,N$ ,計(jì)算
$r_{mi}=-[\frac {\partial L(y,f(x_i)) }{\partial f(x_i)}]_{f(x)= f_{m-1}(x)}$ ,這里計(jì)算每個(gè)x對(duì)于的殘差值
對(duì) $r_{mi}$ 擬合一個(gè)回歸樹(shù)烦粒，得到第m棵樹(shù)的葉結(jié)點(diǎn)區(qū)域 $R_{mj}$ , $j=1,2,...,J$ .
對(duì), $j=1,2,...,J$ ,計(jì)算
$c_{mj}=\underset{c}{argmin} \sum_{x_i \in R_{mj}} L(y_i,f_{m-1}(x_i)+c)$ ,這里的c是每一個(gè)子區(qū)域 $R_{mj}$ 的均值，具體的代赁，這里的 $c$ 表示第m棵樹(shù)在 $j$ 這個(gè)子領(lǐng)域的輸出值扰她。
更新 $f_m(x)=f_{m-1}(x) + \sum^J_{j=1} c_{mj}I(x \in R_{mj})$
(3) 得到回歸樹(shù)
$\hat{f(}x)=f_M(x)=\sum^M_{m=1} \sum^J_{j=1} c_{mj}I(x \in R_{mj})$

**優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

準(zhǔn)確度高
適合低維復(fù)雜度
能靈活的處理各種類(lèi)型的數(shù)據(jù)，連續(xù)值和離散值

缺點(diǎn)

不能并行
數(shù)據(jù)高維會(huì)加大復(fù)雜度

參考文獻(xiàn)

[1] 《統(tǒng)計(jì)學(xué)習(xí)方法》李航第二版
[2] 《機(jī)器學(xué)習(xí)》周志華
[3] http://ihoge.cn/2018/boosting.html
[4] https://juejin.im/post/5cd1828af265da038364dbba
[5] 泰勒公式 https://blog.csdn.net/weixin_37697191/article/details/89303042

最后編輯于：2020.03.13 08:47:07

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末芭碍，一起剝皮案震驚了整個(gè)濱河市徒役，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌窖壕，老刑警劉巖忧勿，帶你破解...
沈念sama閱讀 212,816評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件杉女，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡鸳吸，警方通過(guò)查閱死者的電腦和手機(jī)熏挎，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,729評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)晌砾，“玉大人坎拐，你說(shuō)我怎么就攤上這事」备幔” “怎么了廉白？”我有些...
開(kāi)封第一講書(shū)人閱讀 158,300評(píng)論 0贊 348
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)乖寒。經(jīng)常有香客問(wèn)我，道長(zhǎng)院溺，這世上最難降的妖魔是什么楣嘁？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,780評(píng)論 1贊 285
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮珍逸，結(jié)果婚禮上逐虚，老公的妹妹穿的比我還像新娘。我一直安慰自己谆膳，他們只是感情好叭爱，可當(dāng)我...
茶點(diǎn)故事閱讀 65,890評(píng)論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著漱病，像睡著了一般买雾。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上杨帽，一...
開(kāi)封第一講書(shū)人閱讀 50,084評(píng)論 1贊 291
城市分裂傳說(shuō)
那天漓穿，我揣著相機(jī)與錄音，去河邊找鬼注盈。笑死晃危，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的老客。我是一名探鬼主播僚饭，決...
沈念sama閱讀 39,151評(píng)論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼胧砰！你這毒婦竟也來(lái)了鳍鸵？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 37,912評(píng)論 0贊 268
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤朴则，失蹤者是張志新（化名）和其女友劉穎权纤，沒(méi)想到半個(gè)月后钓简，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,355評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡汹想，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,666評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年外邓，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片古掏。...
茶點(diǎn)故事閱讀 38,809評(píng)論 1贊 341
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡损话，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出槽唾，到底是詐尸還是另有隱情丧枪，我是刑警寧澤，帶...
沈念sama閱讀 34,504評(píng)論 4贊 334
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布庞萍，位于F島的核電站拧烦，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏钝计。R本人自食惡果不足惜恋博，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 40,150評(píng)論 3贊 317
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望私恬。院中可真熱鬧债沮，春花似錦、人聲如沸本鸣。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,882評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)荣德。三九已至闷煤，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間命爬，已是汗流浹背曹傀。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,121評(píng)論 1贊 267
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留饲宛，地道東北人皆愉。一個(gè)月前我還...
沈念sama閱讀 46,628評(píng)論 2贊 362
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像艇抠，于是被迫代替她去往敵國(guó)和親幕庐。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,724評(píng)論 2贊 351

學(xué)習(xí)筆記-隨機(jī)森林圾叼、提升樹(shù)、GBDT

學(xué)習(xí)筆記-隨機(jī)森林捺癞、提升樹(shù)夷蚊、GBDT

隨機(jī)森林(random forest)

提升樹(shù)

GBDT

參考文獻(xiàn)

推薦閱讀更多精彩內(nèi)容