概念

決策樹(Decision Tree)分為兩大類虑灰，回歸樹(Regression Decision Tree)和分類樹(Classification Decision Tree)吨瞎。前者用于預(yù)測(cè)實(shí)數(shù)值，如明天的溫度穆咐、用戶的年齡颤诀、網(wǎng)頁(yè)的相關(guān)程度；后者用于分類標(biāo)簽值对湃，如晴天/陰天/霧/雨崖叫、用戶性別、網(wǎng)頁(yè)是否是垃圾頁(yè)面拍柒。這里要強(qiáng)調(diào)的是心傀，前者的結(jié)果加減是有意義的，如10歲+5歲-3歲=12歲，后者則無(wú)意義拦英，如男+男+女=到底是男是女内狸？下面先介紹分類樹惑惶，決策樹一般情況下指的是分類樹太援。

分類樹是一種非線性有監(jiān)督分類模型全跨，隨機(jī)森林是一種非線性有監(jiān)督分類模型惶室。線性分類模型比如說邏輯回歸神年，可能會(huì)存在不可分問題汁讼，但是非線性分類就不存在潘飘。決策樹是機(jī)器學(xué)習(xí)中最接近人類思考問題的過程的一種算法，通過若干個(gè)節(jié)點(diǎn)掉缺，對(duì)特征進(jìn)行提問并分類（可以是二分類也可以使多分類）卜录，直至最后生成葉節(jié)點(diǎn)（也就是只剩下一種屬性）。

分類樹是一種簡(jiǎn)單但是廣泛使用的分類器眶明。通過訓(xùn)練數(shù)據(jù)構(gòu)建決策樹艰毒，可以高效的對(duì)未知的數(shù)據(jù)進(jìn)行分類。決策數(shù)有兩大優(yōu)點(diǎn)：1）決策樹模型可以讀性好搜囱，具有描述性丑瞧，有助于人工分析；2）效率高蜀肘，決策樹只需要一次構(gòu)建绊汹，反復(fù)使用，每一次預(yù)測(cè)的最大計(jì)算次數(shù)不超過決策樹的深度扮宠。

信息熵：熵代表信息的不確定性西乖，信息的不確定性越大，熵越大坛增；比如“明天太陽(yáng)從東方升起”這一句話代表的信息我們可以認(rèn)為為0获雕；因?yàn)樘?yáng)從東方升起是個(gè)特定的規(guī)律，我們可以把這個(gè)事件的信息熵約等于0收捣；說白了届案，信息熵和事件發(fā)生的概率成反比：數(shù)學(xué)上把信息熵定義如下：H(X)＝H(P1，P2罢艾，…楣颠，Pn)＝-∑P(xi)logP(xi)

互信息：指的是兩個(gè)隨機(jī)變量之間的關(guān)聯(lián)程度，即給定一個(gè)隨機(jī)變量后咐蚯，另一個(gè)隨機(jī)變量不確定性的削弱程度童漩，因而互信息取值最小為0，意味著給定一個(gè)隨機(jī)變量對(duì)確定一另一個(gè)隨機(jī)變量沒有關(guān)系仓蛆，最大取值為隨機(jī)變量的熵睁冬，意味著給定一個(gè)隨機(jī)變量挎春，能完全消除另一個(gè)隨機(jī)變量的不確定性看疙。

一豆拨、分類決策樹

一個(gè)簡(jiǎn)單的決策樹示意圖：

有人找我借錢（當(dāng)然不太可能。能庆。施禾。），借還是不借搁胆？我會(huì)結(jié)合根據(jù)我自己有沒有錢弥搞、我自己用不用錢、對(duì)方信用好不好這三個(gè)特征來(lái)決定我的答案渠旁，即分成兩類攀例。

轉(zhuǎn)到更普遍一點(diǎn)的視角，對(duì)于一些有特征的數(shù)據(jù)顾腊，如果我們能夠有這么一顆決策樹粤铭，我們也就能非常容易地預(yù)測(cè)樣本的結(jié)論。所以問題就轉(zhuǎn)換成怎么求一顆合適的決策樹杂靶，也就是怎么對(duì)這些特征進(jìn)行排序梆惯。

在對(duì)特征排序前先設(shè)想一下，對(duì)某一個(gè)特征進(jìn)行決策時(shí)吗垮，我們肯定希望分類后樣本的純度越高越好垛吗，也就是說分支結(jié)點(diǎn)的樣本盡可能屬于同一類別。

其中N表示結(jié)論有多少種可能取值失受，p表示在取第k個(gè)值的時(shí)候發(fā)生的概率，對(duì)于樣本而言就是發(fā)生的頻率/總個(gè)數(shù)咏瑟。（注意log是以2為底拂到。）比如有20個(gè)樣本(X)的二分類問題，有15個(gè)樣本是狗码泞，5個(gè)樣本不是狗兄旬，那么此時(shí)的熵為：
H(X)=-(0.75xlog0.75+0.25xlog0.25)=0.811；如果20個(gè)樣本全部是一類，那么該樣本的熵為0领铐；如果20個(gè)樣本每類10個(gè)此時(shí)熵最大悯森。樣本分布越均勻越混亂，熵越大绪撵。熵越小瓢姻，說明樣本越純。擴(kuò)展一下音诈，樣本X可能取值為n種（x1幻碱。。细溅。褥傍。xn）±模可以證明摔桦，當(dāng)p（xi）都等于1/n 時(shí)，也就是樣本絕對(duì)均勻承疲，熵能達(dá)到最大邻耕。當(dāng)p（xi）有一個(gè)為1，其他都為0時(shí)燕鸽，也就是樣本取值都是xi兄世，熵最小。

1.1 決策樹算法

ID3

假設(shè)在樣本集X中啊研，對(duì)于一個(gè)特征a御滩，它可能有（a1，a2党远。削解。。an）這些取值沟娱，如果用特征a當(dāng)根節(jié)點(diǎn)對(duì)樣本集X進(jìn)行劃分氛驮，肯定會(huì)有n個(gè)分支結(jié)點(diǎn)。剛才提了济似，我們希望劃分后矫废，分支結(jié)點(diǎn)的樣本越純?cè)胶茫簿褪欠种ЫY(jié)點(diǎn)的“總熵”越小越好砰蠢。由于每個(gè)分支結(jié)點(diǎn)的樣本個(gè)數(shù)不一樣蓖扑，因此我們計(jì)算“總熵”時(shí)應(yīng)該做一個(gè)加權(quán)，假設(shè)第i個(gè)結(jié)點(diǎn)樣本個(gè)數(shù)為W(ai)台舱，其在所有樣本中的權(quán)值為W(ai) / W(X)律杠。所以我們可以得到一個(gè)總熵：

這個(gè)公式代表含義一句話：加權(quán)后各個(gè)結(jié)點(diǎn)的熵的總和。這個(gè)值應(yīng)該越小，分類后的樣本純度越高柜去。

這時(shí)候灰嫉，我們引入一個(gè)名詞叫信息增益G（X，a）诡蜓，意思就是a這個(gè)特征給樣本帶來(lái)的信息的提升。公式就是：

由于對(duì)一個(gè)樣本而言胰挑，H(X)是一個(gè)固定值蔓罚，因此信息增益G應(yīng)該越大越好。尋找使得信息增益最大的特征作為目標(biāo)結(jié)點(diǎn)瞻颂，并逐步遞歸構(gòu)建樹豺谈，這就是ID3算法的思想。

以一個(gè)簡(jiǎn)單的例子來(lái)說明信息增益的計(jì)算：

上面的例子贡这，我們計(jì)算一下如果以特征1作為目標(biāo)結(jié)點(diǎn)的信息增益：

首先計(jì)算樣本的熵H（X）：

再計(jì)算所有分支結(jié)點(diǎn)的總熵茬末，可以看到特征1有3個(gè)結(jié)點(diǎn)A、B盖矫、C丽惭，其分別為6個(gè)、6個(gè)辈双、5個(gè)樣本责掏。所以A的權(quán)值為6/17, B的權(quán)值為6/17, C的為5/17。因?yàn)槲覀兿Ｍ麆澐趾蠼Y(jié)點(diǎn)的純度越高越好湃望，即總熵最小换衬，因此還需要再分別計(jì)算結(jié)點(diǎn)A、B证芭、C的熵瞳浦。

特征1=A：樣本有3個(gè)是、3個(gè)否废士，其熵為：

特征1=B：2個(gè)是叫潦、4個(gè)否，其熵為0.918官硝；特征1=C：4個(gè)是诅挑、1個(gè)否，其熵為0.722泛源。這樣分支結(jié)點(diǎn)的總熵就等于：

特征1的信息增益G就等于0.998-0.889=0.109

類似地拔妥，我們也能算出其他的特征的信息增益，最終取信息增益最大的特征作為根節(jié)點(diǎn)达箍。

C4.5

在ID3算法中其實(shí)有個(gè)很明顯的問題没龙。如果有一個(gè)樣本集，它有一個(gè)叫id或者姓名之類的（唯一的）的特征，那就完蛋了硬纤。設(shè)想一下解滓，如果有N個(gè)樣本，id這個(gè)特征肯定會(huì)把這個(gè)樣本也分成N份筝家，也就是有N個(gè)結(jié)點(diǎn)洼裤。由于每個(gè)結(jié)點(diǎn)只有一個(gè)值，那每個(gè)結(jié)點(diǎn)的熵就為0溪王。就是說所有分支結(jié)點(diǎn)的總熵為0腮鞍，那么這個(gè)特征的信息增益一定會(huì)達(dá)到最大值。因此如果此時(shí)用ID3作為決策樹算法移国，根節(jié)點(diǎn)必然是id這個(gè)特征。這顯然這是不合理的。一般情況下，如果一個(gè)特征對(duì)樣本劃分的過于稀疏怜械，這個(gè)也是不合理的（取值特別多的特征不適合做根節(jié)點(diǎn)）。

為了解決這個(gè)問題，C4.5算法采用了信息增益率來(lái)作為特征選取標(biāo)準(zhǔn)驾霜。所謂信息增益率忿项，是在信息增益基礎(chǔ)上寞酿，除了一項(xiàng)split information,來(lái)懲罰值更多的屬性拉馋。

而這個(gè)split information其實(shí)就是特征個(gè)數(shù)的熵H（A）景馁。還以上面的例子說明绰精，如果以特征1作為結(jié)點(diǎn)，可以分為A B C三種結(jié)點(diǎn)繁调，那么：
H(A)=H(特征1)=-(6/17xlog(6/17)x2+5/17(log(5/17))).

為什么這樣可以減少呢，以上面id的例子來(lái)理解一下。如果id把n個(gè)樣本分成了n份，那id這個(gè)特征的取值的概率都是1/n，文章引言已經(jīng)說了阅悍，樣本絕對(duì)均勻的時(shí)候，熵最大。

因此這種情況，以id為特征，雖然信息增益最大析校，但是懲罰因子split information也最大芙代，以此來(lái)拉低其增益率，這就是C4.5的思想。

CART（Classification And Regression Tree邦马，分類與回歸樹）

決策樹的目的最終還是尋找到區(qū)分樣本的純度的量化標(biāo)準(zhǔn)随闽。在CART決策樹中蛾扇，采用的是基尼指數(shù)來(lái)作為其衡量標(biāo)準(zhǔn)鼠次。基尼系數(shù)（和基尼指數(shù)有區(qū)別的）直觀的理解是赦役，從集合中隨機(jī)抽取兩個(gè)樣本术羔，如果樣本集合越純，取到不同樣本的概率越小。這個(gè)概率反應(yīng)的就是基尼系數(shù)。因此如果一個(gè)樣本有K個(gè)分類，假設(shè)樣本的某一個(gè)特征a有n個(gè)取值的話萍膛，那么以a為根節(jié)點(diǎn)會(huì)有n個(gè)子節(jié)點(diǎn)蝌戒，其某一個(gè)結(jié)點(diǎn)下取到不同樣本的概率為：

而基尼指數(shù)，則是對(duì)所有結(jié)點(diǎn)的基尼系數(shù)進(jìn)行加權(quán)處理

計(jì)算出來(lái)后延届，我們會(huì)選擇基尼指數(shù)最小的那個(gè)特征作為最優(yōu)劃分特征。

1.2 過擬合解決辦法

剪枝

剪枝的目的其實(shí)就是防止過擬合贸诚，它是決策樹防止過擬合的最主要手段方庭。決策樹中，為了盡可能爭(zhēng)取的分類訓(xùn)練樣本赦颇，所以我們的決策樹也會(huì)一直生長(zhǎng)二鳄。但是呢赴涵，有時(shí)候訓(xùn)練樣本可能會(huì)學(xué)的太好媒怯，以至于把某些樣本的特有屬性當(dāng)成一般屬性。這時(shí)候就我們就需要主動(dòng)去除一些分支髓窜，來(lái)降低過擬合的風(fēng)險(xiǎn)扇苞。

剪枝一般有兩種方式：預(yù)剪枝和后剪枝。

預(yù)剪枝

一般情況下寄纵，只要結(jié)點(diǎn)樣本已經(jīng)100%純了鳖敷，樹才會(huì)停止生長(zhǎng)。但這個(gè)可能會(huì)產(chǎn)生過擬合程拭，因此我們沒有必要讓它100%生長(zhǎng)定踱，所以在這之前，設(shè)定一些終止條件來(lái)提前終止它恃鞋。這就叫預(yù)剪枝崖媚，這個(gè)過程發(fā)生在決策樹生成之前亦歉。

一般我們預(yù)剪枝的手段有：
1、限定樹的深度
2畅哑、節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目小于閾值
3肴楷、設(shè)定結(jié)點(diǎn)熵的閾值

后剪枝

顧名思義，這個(gè)剪枝是在決策樹建立過程后荠呐。后剪枝算法的算法很多赛蔫，有些也挺深?yuàn)W，這里提一個(gè)簡(jiǎn)單的算法的思想Reduced-Error Pruning (REP)泥张。該剪枝方法考慮將樹上的每個(gè)節(jié)點(diǎn)都作為修剪的候選對(duì)象呵恢，但是有一些條件決定是否修剪，通常有這幾步：

1媚创、刪除其所有的子樹瑰剃，使其成為葉節(jié)點(diǎn)。
2筝野、賦予該節(jié)點(diǎn)最關(guān)聯(lián)的分類
3晌姚、用驗(yàn)證數(shù)據(jù)驗(yàn)證其準(zhǔn)確度與處理前比較

如果不比原來(lái)差，則真正刪除其子樹歇竟。然后反復(fù)從下往上對(duì)結(jié)點(diǎn)處理挥唠。這個(gè)處理方式其實(shí)是處理掉那些“有害”的節(jié)點(diǎn)。

1.3 隨機(jī)森林

構(gòu)建大量的決策樹組成森林來(lái)防止過擬合焕议；雖然單個(gè)樹可能存在過擬合宝磨，但通過廣度的增加就會(huì)消除過擬合現(xiàn)象。隨機(jī)森林（Random forest）：生成多顆決策樹盅安，投票選舉的原則唤锉。

集成學(xué)習(xí)的概念：

圖中可以看到，每個(gè)個(gè)體學(xué)習(xí)器（弱學(xué)習(xí)器）都可包含一種算法别瞭，算法可以相同也可以不同窿祥。如果相同，我們把它叫做同質(zhì)集成蝙寨，反之則為異質(zhì)晒衩。

隨機(jī)森林則是集成學(xué)習(xí)采用基于bagging策略的一個(gè)特例。

從上圖可以看出墙歪，bagging的個(gè)體學(xué)習(xí)器的訓(xùn)練集是通過隨機(jī)采樣得到的听系。通過n次的隨機(jī)采樣，我們就可以得到n個(gè)樣本集虹菲。對(duì)于這n個(gè)樣本集靠胜，我們可以分別獨(dú)立的訓(xùn)練出n個(gè)個(gè)體學(xué)習(xí)器，再對(duì)這n個(gè)個(gè)體學(xué)習(xí)器通過集合策略來(lái)得到最終的輸出，這n個(gè)個(gè)體學(xué)習(xí)器之間是相互獨(dú)立的浪漠，可以并行菠赚。

Baggging 與 Boosting

Baggging 和Boosting都是模型融合的方法，可以將弱分類器融合之后形成一個(gè)強(qiáng)分類器郑藏，而且融合之后的效果會(huì)比最好的弱分類器更好衡查。

Baggging

隨機(jī)森林使用的是baggging，即從原始樣本集中抽取訓(xùn)練集必盖，每輪使用 bootstraping 的方法抽取 n 個(gè)訓(xùn)練樣本拌牲，然后放回（在訓(xùn)練集中，有些樣本可能被多次抽取到歌粥，而有些樣本可能一次都沒有被抽中）塌忽。經(jīng)過 k 輪抽取，得到 k 個(gè)訓(xùn)練集（k個(gè)訓(xùn)練集之間是相互獨(dú)立的）失驶。每次使用一個(gè)訓(xùn)練集得到一個(gè)模型土居，k 個(gè)訓(xùn)練集共得到 k 個(gè)模型。由于是隨機(jī)采樣嬉探，這樣每次的采樣集是和原始樣本集不同的擦耀，和其他采樣集也是不同的，這樣得到的個(gè)體學(xué)習(xí)器也是不同的涩堤。（注：這里并沒有具體的分類算法或回歸方法眷蜓，我們可以根據(jù)具體問題采用不同的分類或回歸方法，如決策樹胎围、感知器等吁系。）

隨機(jī)森林最主要的問題是有了 k 個(gè)模型，怎么設(shè)定結(jié)合策略白魂，主要方式也有這么幾種：

• 加權(quán)平均法

當(dāng)學(xué)習(xí)器的權(quán)值都為1/n時(shí)，這個(gè)平均法叫簡(jiǎn)單平均法逞姿。

• 投票法

對(duì)分類問題：將上步得到的 k 個(gè)模型采用投票的方式得到分類結(jié)果辞嗡。投票法類似我們生活中的投票，如果每個(gè)學(xué)習(xí)器的權(quán)值都是一樣的滞造。有絕對(duì)投票法，也就是票數(shù)過半栋烤；相對(duì)投票法谒养，少數(shù)服從多數(shù)。如果有加權(quán)，依然是少數(shù)服從多數(shù)买窟，只不過這里面的數(shù)是加權(quán)后的丰泊。

Boosting

AdaBoosting方式每次都使用全部的樣本，每輪訓(xùn)練改變樣本的權(quán)重始绍。下一輪訓(xùn)練的目標(biāo)是找到一個(gè)函數(shù) f 來(lái)擬合上一輪的殘差瞳购。當(dāng)殘差足夠小或者達(dá)到設(shè)置的最大迭代次數(shù)則停止。Boosting會(huì)減小在上一輪訓(xùn)練正確的樣本的權(quán)重亏推，增大錯(cuò)誤樣本的權(quán)重学赛。（對(duì)的殘差小，錯(cuò)的殘差大）梯度提升的Boosting方式是使用代價(jià)函數(shù)對(duì)上一輪訓(xùn)練出的模型函數(shù)f的偏導(dǎo)來(lái)擬合殘差吞杭。

二者之間的區(qū)別

• 樣本選擇
  Bagging：訓(xùn)練集是在原始集中有放回選取的盏浇，從原始集中選出的各輪訓(xùn)練集之間是獨(dú)立的。
  Boosting：每一輪的訓(xùn)練集不變芽狗，只是訓(xùn)練集中每個(gè)樣例在分類器中的權(quán)重發(fā)生變化绢掰。而權(quán)值是根據(jù)上一輪的分類結(jié)果進(jìn)行調(diào)整。

• 樣例權(quán)重
  Bagging：使用均勻取樣童擎，每個(gè)樣例的權(quán)重相等滴劲。
  Boosting：根據(jù)錯(cuò)誤率不斷調(diào)整樣例的權(quán)值，錯(cuò)誤率越大則權(quán)重越大顾复。

• 預(yù)測(cè)函數(shù)
  Bagging：所有預(yù)測(cè)函數(shù)的權(quán)重相等哑芹。
  Boosting：每個(gè)弱分類器都有相應(yīng)的權(quán)重，對(duì)于分類誤差小的分類器會(huì)有更大的權(quán)重捕透。

• 并行計(jì)算
  Bagging：各個(gè)預(yù)測(cè)函數(shù)可以并行生成聪姿。
  Boosting：各個(gè)預(yù)測(cè)函數(shù)只能順序生成，因?yàn)楹笠粋€(gè)模型參數(shù)需要前一輪模型的結(jié)果乙嘀。

這兩種方法都是把若干個(gè)分類器整合為一個(gè)分類器的方法末购，只是整合的方式不一樣，最終得到不一樣的效果虎谢，將不同的分類算法套入到此類算法框架中一定程度上會(huì)提高了原單一分類器的分類效果盟榴，但是也增大了計(jì)算量。下面是將決策樹與這些算法框架進(jìn)行結(jié)合所得到的新的算法：

• Bagging + 決策樹 = 隨機(jī)森林
• AdaBoost + 決策樹 = 提升樹
• Gradient Boosting + 決策樹 = GBDT

提升樹和GBDT婴噩，下面會(huì)分別介紹擎场。

1.4 例子

以一個(gè)簡(jiǎn)單的二次函數(shù)的代碼來(lái)看看決策樹怎么用吧。

訓(xùn)練數(shù)據(jù)是100個(gè)隨機(jī)的真實(shí)的平方數(shù)據(jù)几莽，不同的深度將會(huì)得到不同的曲線迅办；測(cè)試數(shù)據(jù)也是隨機(jī)數(shù)據(jù)，但是不同深度的樹的模型章蚣，產(chǎn)生的預(yù)測(cè)值也不太一樣站欺，如圖：

這幅圖的代碼如下：

我的是python 3.6環(huán)境，需要安裝numpy、matplotlib矾策、sklearn這三個(gè)庫(kù)磷账，需要的話直接pip install，大家可以跑跑看看贾虽，雖然簡(jiǎn)單但挺有趣逃糟。

# -*- coding:utf-8 -*- 
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt 
from sklearn.tree import DecisionTreeRegressor 


if __name__ == "__main__":

    # 準(zhǔn)備訓(xùn)練數(shù)據(jù)
    N = 100 
    x = np.random.rand(N) * 6 - 3 
    x.sort()
    y = x*x
    x = x.reshape(-1, 1)

    mpl.rcParams['font.sans-serif'] = ['SimHei']
    mpl.rcParams['axes.unicode_minus'] = False

    # 決策樹深度及其曲線顏色
    depth = [2, 4, 6, 8, 10]
    clr = 'rgbmy' # 實(shí)際值
    plt.figure(facecolor='w')
    plt.plot(x, y, 'ro', ms=5, mec='k', label='實(shí)際值')

    # 準(zhǔn)備測(cè)試數(shù)據(jù)
    x_test = np.linspace(-3, 3, 50).reshape(-1, 1)

    # 構(gòu)建決策樹
    dtr = DecisionTreeRegressor()
    # 循環(huán)不同深度情況下決策樹的模型，并用之測(cè)試數(shù)據(jù)的輸出 
    for d, c in zip(depth, clr):
        # 設(shè)置最大深度（預(yù)剪枝）
        dtr.set_params(max_depth=d)
        # 訓(xùn)練決策樹
        dtr.fit(x, y)
        # 用訓(xùn)練數(shù)據(jù)得到的模型來(lái)驗(yàn)證測(cè)試數(shù)據(jù)
        y_hat = dtr.predict(x_test)
        # 畫出模型得到的曲線
        plt.plot(x_test, y_hat, '-', color=c, linewidth=2, markeredgecolor='k', label='Depth=%d' % d)
    # 一些畫圖的基本參數(shù)
    plt.legend(loc='upper center', fontsize=12)
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.grid(b=True, ls=':', color='#606060')
    plt.title('二次函數(shù)決策樹', fontsize=15)
    plt.tight_layout(2)
    plt.show()

二蓬豁、回歸決策樹

2.1 回歸樹

首先看看回歸樹是如何工作的绰咽。下面我們以對(duì)人的性別判別/年齡預(yù)測(cè)為例來(lái)說明，每個(gè)instance都是一個(gè)我們已知性別/年齡的人庆尘，而feature則包括這個(gè)人上網(wǎng)的時(shí)長(zhǎng)剃诅、上網(wǎng)的時(shí)段、網(wǎng)購(gòu)所花的金額等驶忌。

作為對(duì)比矛辕，先說分類樹，我們知道C4.5分類樹在每次分枝時(shí)付魔，會(huì)選取信息增益率最大的特征几苍，按照該標(biāo)準(zhǔn)分枝得到新節(jié)點(diǎn)，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點(diǎn)妻坝，或達(dá)到預(yù)設(shè)的終止條件伸眶，若最終葉子節(jié)點(diǎn)中的性別不唯一厘贼，則以多數(shù)人的性別作為該葉子節(jié)點(diǎn)的性別。

回歸樹總體流程也是類似圣拄，不過在每個(gè)節(jié)點(diǎn)（不一定是葉子節(jié)點(diǎn)）都會(huì)得一個(gè)預(yù)測(cè)值嘴秸，以年齡為例岳掐，該預(yù)測(cè)值等于屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值串述。分枝時(shí)窮舉每一個(gè)feature的每個(gè)閾值找最好的分割點(diǎn)哥攘，但衡量最好的標(biāo)準(zhǔn)不再是和熵有關(guān)的標(biāo)準(zhǔn)逝淹，而是最小化均方差--即（每個(gè)人的年齡-預(yù)測(cè)年齡）平方和除以 N栅葡。這很好理解，被預(yù)測(cè)出錯(cuò)的人數(shù)越多规脸，錯(cuò)的越離譜莫鸭，均方差就越大被因，通過最小化均方差能夠找到最靠譜的分枝依據(jù)衫仑。分枝直到每個(gè)葉子節(jié)點(diǎn)上人的年齡都唯一（這太難了）或者達(dá)到預(yù)設(shè)的終止條件（如葉子個(gè)數(shù)上限）文狱，若最終葉子節(jié)點(diǎn)上人的年齡不唯一瞄崇，則以該節(jié)點(diǎn)上所有人的平均年齡做為該葉子節(jié)點(diǎn)的預(yù)測(cè)年齡苏研。

2.2 提升樹

提升樹以回歸樹為基分類器。它的idea在于凿掂，第一個(gè)回歸樹預(yù)測(cè)的效果可能一般庄萎，但是第二個(gè)回歸樹把第一個(gè)預(yù)測(cè)錯(cuò)的殘差作為輸入糠涛。也就是說忍捡，如果一個(gè)點(diǎn)的值被預(yù)測(cè)錯(cuò)誤砸脊，那么在下一個(gè)回歸樹里面的模型的權(quán)值會(huì)變大凌埂。通過這個(gè)方式，來(lái)提高模型的效果埃疫。

訓(xùn)練提升樹的步驟：

• step1 構(gòu)建第一個(gè)回歸樹T1(x)
  如何構(gòu)建回歸樹T1(x)？
  a. 從數(shù)據(jù)集里面找到一個(gè)切分點(diǎn)s横蜒，將數(shù)據(jù)集分成兩個(gè)部分。
  b. 對(duì)于每個(gè)部分鹰霍，找到一個(gè)值c茂洒，使得內(nèi)部的y到所有的平方損失函數(shù)最小督勺。
  (遍歷所有可能的切分點(diǎn)s智哀，找到最好的效果瓷叫。那么問題又來(lái)了送巡，如何判斷一個(gè)點(diǎn)的切分的效果好與壞骗爆？）
• 在上一顆回歸樹回歸的基礎(chǔ)上摘投，把殘差作為下一棵回歸樹的任務(wù)，繼續(xù)構(gòu)造回歸樹薇组。
• 不斷循環(huán)這個(gè)過程

計(jì)算c的公式是：

判斷一個(gè)點(diǎn)s体箕，切分效果的好與壞的評(píng)價(jià)標(biāo)準(zhǔn)的時(shí)候：

下面跃须，我們帶入這個(gè)具體的例子里面進(jìn)行分析。假設(shè)尽楔，現(xiàn)在的切分點(diǎn)是s=1.5 阔馋， 那么數(shù)據(jù)集就會(huì)被分成兩個(gè)部分呕寝，一個(gè)是R1={1} 下梢， R2={2, 3 , ..., 10} 孽江。對(duì)于切分的兩個(gè)部分里面岗屏，求c1和c2这刷。根據(jù)上面的公式洼冻，c1=5.56 , c2=7.50 撞牢。那么，在我們這個(gè)例子里面绒尊，m(s)的值是：

如果婴谱，遍歷所有可能的切分點(diǎn)谭羔，對(duì)于每一個(gè)切分點(diǎn)都會(huì)有一個(gè)值瘟裸。

也就說，當(dāng)在s=6.5的時(shí)候沙郭，切分的效果是最好的裳朋。

也就是說泛范，我們現(xiàn)在得到了第一顆回歸樹赡突，T1（x）。對(duì)于小于6.5的數(shù)據(jù)漱受，我們把他預(yù)測(cè)成6.24昂羡，對(duì)于大于等于6.5的數(shù)據(jù)怨愤，我們把它預(yù)測(cè)成8.91。然后，就到了最重要的一步柿汛，將殘差數(shù)據(jù)放入下一個(gè)回歸樹進(jìn)行訓(xùn)練裁替。

下面去訓(xùn)練下一個(gè)學(xué)習(xí)器：

判斷的終止條件是：

對(duì)于求出的第一個(gè)回歸樹：

對(duì)于求出的第二個(gè)回歸樹：

依次類推：

最后：

2.3 梯度提升樹GBDT

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)开伏，是一種迭代的決策樹算法固灵，該算法由多棵決策樹組成巫玻，所有樹的結(jié)論累加起來(lái)做最終答案仍秤。它在被提出之初就和SVM一起被認(rèn)為是泛化能力（generalization)較強(qiáng)的算法诗力。近些年更因?yàn)楸挥糜谒阉髋判虻臋C(jī)器學(xué)習(xí)模型而引起大家關(guān)注苇本。

GBDT的核心在于累加所有樹的結(jié)果作為最終結(jié)果圈澈，就像前面對(duì)年齡的累加（-3是加負(fù)3）康栈，而分類樹的結(jié)果顯然是沒辦法累加的，所以GBDT中的樹都是回歸樹登舞，不是分類樹菠秒，這點(diǎn)對(duì)理解GBDT相當(dāng)重要（盡管GBDT調(diào)整后也可用于分類但不代表GBDT的樹是分類樹）践叠。

GBDT主要由三個(gè)概念組成：Regression Decistion Tree（即DT)禁灼，Gradient Boosting（即GB)弄捕，Shrinkage (算法的一個(gè)重要演進(jìn)分枝守谓，目前大部分源碼都按該版本實(shí)現(xiàn)）斋荞。搞定這三個(gè)概念后就能明白GBDT是如何工作的譬猫，要繼續(xù)理解它如何用于搜索排序則需要額外理解 RankNet 概念染服，之后便功德圓滿柳刮。

算法原理

GBDT的原理和提升樹差不多秉颗，但是提升樹在某些時(shí)候不方便求殘差蚕甥，梯度提升樹則是用損失函數(shù)的負(fù)梯度方向值來(lái)近似擬合殘差菇怀。GBDT很好的結(jié)合了回歸樹與提升樹的思想爱沟，并將它們推廣到更一般的情形身冀。例如提升樹中第三步計(jì)算殘差是在損失函數(shù)為平方損失函數(shù)來(lái)計(jì)算的奶浦，如果損失函數(shù)為對(duì)數(shù)函數(shù)沐悦，則計(jì)算殘差 變得不是很方便，以及在第四步訓(xùn)練回歸樹時(shí)，計(jì)算節(jié)點(diǎn)輸出值 c_m 也變得不容易進(jìn)行。

算法過程如下：

以上算法將回歸樹和提升樹的算法結(jié)合起來(lái)，在第5步中求解 办铡，如果損失函數(shù)為平方損失函數(shù)凭豪，則解法與前面的回歸樹一致帖努，直接取均值即可亩歹。如果是其他損失函數(shù)，則需要具體進(jìn)行求解。具體而言粮揉，就是取導(dǎo)數(shù)為零來(lái)解等式蝠引。

不過對(duì)于分類情況，由于樣本輸出不是連續(xù)的值，而是離散的類別，導(dǎo)致我們無(wú)法直接從輸出類別去擬合類別輸出的誤差。為了解決這個(gè)問題檩奠，主要有兩個(gè)方法蕉扮，一個(gè)是用指數(shù)損失函數(shù)，此時(shí)GBDT退化為Adaboost算法应狱。另一種方法是用類似于邏輯回歸的對(duì)數(shù)似然損失函數(shù)的方法岸蜗。也就是說，我們用的是類別的預(yù)測(cè)概率值和真實(shí)概率值的差來(lái)擬合損失。本文僅討論用對(duì)數(shù)似然損失函數(shù)的GBDT分類。而對(duì)于對(duì)數(shù)似然損失函數(shù)，我們又有二元分類和多元分類的區(qū)別。

GBDT損失函數(shù)

對(duì)于分類算法，其損失函數(shù)一般有對(duì)數(shù)損失函數(shù)和指數(shù)損失函數(shù)兩種:

• 如果是指數(shù)損失函數(shù)，則損失函數(shù)表達(dá)式為：
  
• 如果是對(duì)數(shù)損失函數(shù)赂鲤，分為二元分類和多元分類兩種：
  二元：
  
  多元：
  

對(duì)于回歸算法，常用損失函數(shù)有如下4種:

• 均方差，這個(gè)是最常見的回歸損失函數(shù)：
  

• 絕對(duì)損失眼俊，這個(gè)損失函數(shù)也很常見：
  

• Huber損失闷板，它是均方差和絕對(duì)損失的折衷產(chǎn)物，對(duì)于遠(yuǎn)離中心的異常點(diǎn)，采用絕對(duì)損失，而中心附近的點(diǎn)采用均方差。這個(gè)界限一般用分位數(shù)點(diǎn)度量。

• 分位數(shù)損失。它對(duì)應(yīng)的是分位數(shù)回歸的損失函數(shù)兴垦。