紅色石頭的個(gè)人網(wǎng)站：redstonewill.com

上節(jié)課我們主要介紹了Decision Tree模型。Decision Tree算法的核心是通過(guò)遞歸的方式，將數(shù)據(jù)集不斷進(jìn)行切割，得到子分支，最終形成數(shù)的結(jié)構(gòu)。C&RT算法是決策樹(shù)比較簡(jiǎn)單和常用的一種算法，其切割的標(biāo)準(zhǔn)是根據(jù)純度來(lái)進(jìn)行，每次切割都是為了讓分支內(nèi)部純度最大。最終，決策樹(shù)不同的分支得到不同的gt(x)gt(x)（即樹(shù)的葉子，C&RT算法中，gt(x)gt(x)是常數(shù)）。本節(jié)課將介紹隨機(jī)森林（Random Forest）算法，它是我們之前介紹的Bagging和上節(jié)課介紹的Decision Tree的結(jié)合。

Random Forest Algorithm

首先我們來(lái)復(fù)習(xí)一下之前介紹過(guò)的兩個(gè)機(jī)器學(xué)習(xí)模型：Bagging和Decision Tree。Bagging是通過(guò)bootstrap的方式，從原始的數(shù)據(jù)集D中得到新的D^D^；然后再使用一些base algorithm對(duì)每個(gè)D^D^都得到相應(yīng)的gtgt；最后將所有的gtgt通過(guò)投票uniform的形式組合成一個(gè)G，G即為我們最終得到的模型。Decision Tree是通過(guò)遞歸形式，利用分支條件，將原始數(shù)據(jù)集D切割成一個(gè)個(gè)子樹(shù)結(jié)構(gòu)，長(zhǎng)成一棵完整的樹(shù)形結(jié)構(gòu)。Decision Tree最終得到的G(x)是由相應(yīng)的分支條件b(x)和分支樹(shù)Gc(x)Gc(x)遞歸組成。

Bagging和Decison Tree算法各自有一個(gè)很重要的特點(diǎn)。Bagging具有減少不同gtgt的方差variance的特點(diǎn)。這是因?yàn)锽agging采用投票的形式，將所有gtgtuniform結(jié)合起來(lái)，起到了求平均的作用，從而降低variance。而Decision Tree具有增大不同gtgt的方差variance的特點(diǎn)。這是因?yàn)镈ecision Tree每次切割的方式不同，而且分支包含的樣本數(shù)在逐漸減少，所以它對(duì)不同的資料D會(huì)比較敏感一些，從而不同的D會(huì)得到比較大的variance。

所以說(shuō)，Bagging能減小variance，而Decision Tree能增大variance。如果把兩者結(jié)合起來(lái)，能否發(fā)揮各自的優(yōu)勢(shì)，起到優(yōu)勢(shì)互補(bǔ)的作用呢？這就是我們接下來(lái)將要討論的aggregation of aggregation，即使用Bagging的方式把眾多的Decision Tree進(jìn)行uniform結(jié)合起來(lái)。這種算法就叫做隨機(jī)森林（Random Forest），它將完全長(zhǎng)成的C&RT決策樹(shù)通過(guò)bagging的形式結(jié)合起來(lái)，最終得到一個(gè)龐大的決策模型。

Random Forest算法流程圖如下所示：

Random Forest算法的優(yōu)點(diǎn)主要有三個(gè)。第一，不同決策樹(shù)可以由不同主機(jī)并行訓(xùn)練生成，效率很高；第二，隨機(jī)森林算法繼承了C&RT的優(yōu)點(diǎn)；第三，將所有的決策樹(shù)通過(guò)bagging的形式結(jié)合起來(lái)，避免了單個(gè)決策樹(shù)造成過(guò)擬合的問(wèn)題。

以上是基本的Random Forest算法，我們?cè)賮?lái)看一下如何讓Random Forest中決策樹(shù)的結(jié)構(gòu)更有多樣性。Bagging中，通過(guò)bootstrap的方法得到不同于D的D’，使用這些隨機(jī)抽取的資料得到不同的gtgt。除了隨機(jī)抽取資料獲得不同gtgt的方式之外，還有另外一種方法，就是隨機(jī)抽取一部分特征。例如，原來(lái)有100個(gè)特征，現(xiàn)在只從中隨機(jī)選取30個(gè)來(lái)構(gòu)成決策樹(shù)，那么每一輪得到的樹(shù)都由不同的30個(gè)特征構(gòu)成，每棵樹(shù)都不一樣。假設(shè)原來(lái)樣本維度是d，則只選擇其中的d’（d’小于d）個(gè)維度來(lái)建立決策樹(shù)結(jié)構(gòu)。這類(lèi)似是一種從d維到d’維的特征轉(zhuǎn)換，相當(dāng)于是從高維到低維的投影，也就是說(shuō)d’維z空間其實(shí)就是d維x空間的一個(gè)隨機(jī)子空間（subspace）。通常情況下，d’遠(yuǎn)小于d，從而保證算法更有效率。Random Forest算法的作者建議在構(gòu)建C&RT每個(gè)分支b(x)的時(shí)候，都可以重新選擇子特征來(lái)訓(xùn)練，從而得到更具有多樣性的決策樹(shù)。

所以說(shuō)，這種增強(qiáng)的Random Forest算法增加了random-subspace。

上面我們講的是隨機(jī)抽取特征，除此之外，還可以將現(xiàn)有的特征x，通過(guò)數(shù)組p進(jìn)行線(xiàn)性組合，來(lái)保持多樣性：

?i(x)=pTix?i(x)=piTx

這種方法使每次分支得到的不再是單一的子特征集合，而是子特征的線(xiàn)性組合（權(quán)重不為1）。好比在二維平面上不止得到水平線(xiàn)和垂直線(xiàn)，也能得到各種斜線(xiàn)。這種做法使子特征選擇更加多樣性。值得注意的是，不同分支i下的pipi是不同的，而且向量pipi中大部分元素為零，因?yàn)槲覀冞x擇的只是一部分特征，這是一種低維映射。

所以，這里的Random Forest算法又有增強(qiáng)，由原來(lái)的random-subspace變成了random-combination。順便提一下，這里的random-combination類(lèi)似于perceptron模型。

Out-Of-Bag Estimate

上一部分我們已經(jīng)介紹了Random Forest算法，而Random Forest算法重要的一點(diǎn)就是Bagging。接下來(lái)將繼續(xù)探討bagging中的bootstrap機(jī)制到底蘊(yùn)含了哪些可以為我們所用的東西。

通過(guò)bootstrap得到新的樣本集D’，再由D’訓(xùn)練不同的gtgt。我們知道D’中包含了原樣本集D中的一些樣本，但也有些樣本沒(méi)有涵蓋進(jìn)去。如下表所示，不同的gtgt下，紅色的表示在D^tD^t中沒(méi)有這些樣本。例如對(duì)g1g1來(lái)說(shuō)，(x2,y2)(x2,y2)和(x3,y4)(x3,y4)沒(méi)有包含進(jìn)去，對(duì)g2g2來(lái)說(shuō)，(x1,y1)(x1,y1)和(x2,y2)(x2,y2)沒(méi)有包含進(jìn)去，等等。每個(gè)gtgt中，紅色表示的樣本被稱(chēng)為out-of-bag(OOB) example。

首先，我們來(lái)計(jì)算OOB樣本到底有多少。假設(shè)bootstrap的數(shù)量N’=N，那么某個(gè)樣本(xn,yn)(xn,yn)是OOB的概率是：

(1?1N)N=1(NN?1)N=1(1+1N?1)N≈1e(1?1N)N=1(NN?1)N=1(1+1N?1)N≈1e

其中，e是自然對(duì)數(shù)，N是原樣本集的數(shù)量。由上述推導(dǎo)可得，每個(gè)gtgt中，OOB數(shù)目大約是1eN1eN，即大約有三分之一的樣本沒(méi)有在bootstrap中被抽到。

然后，我們將OOB與之前介紹的Validation進(jìn)行對(duì)比：

在Validation表格中，藍(lán)色的DtrainDtrain用來(lái)得到不同的g?mgm?，而紅色的DvalDval用來(lái)驗(yàn)證各自的g?mgm?。DtrainDtrain與DvalDval沒(méi)有交集，一般DtrainDtrain是DvalDval的數(shù)倍關(guān)系。再看左邊的OOB表格，之前我們也介紹過(guò)，藍(lán)色的部分用來(lái)得到不同的gtgt，而紅色的部分是OOB樣本。而我們剛剛也推導(dǎo)過(guò)，紅色部分大約占N的1e1e。通過(guò)兩個(gè)表格的比較，我們發(fā)現(xiàn)OOB樣本類(lèi)似于DvalDval，那么是否能使用OOB樣本來(lái)驗(yàn)證gtgt的好壞呢？答案是肯定的。但是，通常我們并不需要對(duì)單個(gè)gtgt進(jìn)行驗(yàn)證。因?yàn)槲覀兏P(guān)心的是由許多gtgt組合成的G，即使gtgt表現(xiàn)不太好，只要G表現(xiàn)足夠好就行了。那么問(wèn)題就轉(zhuǎn)化成了如何使用OOB來(lái)驗(yàn)證G的好壞。方法是先看每一個(gè)樣本(xn,yn)(xn,yn)是哪些gtgt的OOB資料，然后計(jì)算其在這些gtgt上的表現(xiàn)，最后將所有樣本的表現(xiàn)求平均即可。例如，樣本(xN,yN)(xN,yN)是g2g2，g3g3，gTgT的OOB，則可以計(jì)算(xN,yN)(xN,yN)在G?N(x)GN?(x)上的表現(xiàn)為：

G?N(x)=average(g2,g3,gT)GN?(x)=average(g2,g3,gT)

這種做法我們并不陌生，就像是我們之前介紹過(guò)的Leave-One-Out Cross Validation，每次只對(duì)一個(gè)樣本進(jìn)行g?g?的驗(yàn)證一樣，只不過(guò)這里選擇的是每個(gè)樣本是哪些gtgt的OOB，然后再分別進(jìn)行G?n(x)Gn?(x)的驗(yàn)證。每個(gè)樣本都當(dāng)成驗(yàn)證資料一次（與留一法相同），最后計(jì)算所有樣本的平均表現(xiàn)：

Eoob(G)=1N∑n=1Nerr(yn,G?n(xn))Eoob(G)=1N∑n=1Nerr(yn,Gn?(xn))

Eoob(G)Eoob(G)估算的就是G的表現(xiàn)好壞。我們把EoobEoob稱(chēng)為bagging或者Random Forest的self-validation。

這種self-validation相比于validation來(lái)說(shuō)還有一個(gè)優(yōu)點(diǎn)就是它不需要重復(fù)訓(xùn)練。如下圖左邊所示，在通過(guò)DvalDval選擇到表現(xiàn)最好的g?m?gm??之后，還需要在DtrainDtrain和DvalDval組成的所有樣本集D上重新對(duì)該模型g?m?gm??訓(xùn)練一次，以得到最終的模型系數(shù)。但是self-validation在調(diào)整隨機(jī)森林算法相關(guān)系數(shù)并得到最小的EoobEoob之后，就完成了整個(gè)模型的建立，無(wú)需重新訓(xùn)練模型。隨機(jī)森林算法中，self-validation在衡量G的表現(xiàn)上通常相當(dāng)準(zhǔn)確。

Feature Selection

如果樣本資料特征過(guò)多，假如有10000個(gè)特征，而我們只想從中選取300個(gè)特征，這時(shí)候就需要舍棄部分特征。通常來(lái)說(shuō)，需要移除的特征分為兩類(lèi)：一類(lèi)是冗余特征，即特征出現(xiàn)重復(fù)，例如“年齡”和“生日”；另一類(lèi)是不相關(guān)特征，例如疾病預(yù)測(cè)的時(shí)候引入的“保險(xiǎn)狀況”。這種從d維特征到d’維特征的subset-transform Φ(x)Φ(x)稱(chēng)為Feature Selection，最終使用這些d’維的特征進(jìn)行模型訓(xùn)練。

特征選擇的優(yōu)點(diǎn)是：

• 提高效率，特征越少，模型越簡(jiǎn)單

• 正則化，防止特征過(guò)多出現(xiàn)過(guò)擬合

• 去除無(wú)關(guān)特征，保留相關(guān)性大的特征，解釋性強(qiáng)

同時(shí)，特征選擇的缺點(diǎn)是：

• 篩選特征的計(jì)算量較大

• 不同特征組合，也容易發(fā)生過(guò)擬合

• 容易選到無(wú)關(guān)特征，解釋性差

值得一提的是，在decision tree中，我們使用的decision stump切割方式也是一種feature selection。

那么，如何對(duì)許多維特征進(jìn)行篩選呢？我們可以通過(guò)計(jì)算出每個(gè)特征的重要性（即權(quán)重），然后再根據(jù)重要性的排序進(jìn)行選擇即可。

這種方法在線(xiàn)性模型中比較容易計(jì)算。因?yàn)榫€(xiàn)性模型的score是由每個(gè)特征經(jīng)過(guò)加權(quán)求和而得到的，而加權(quán)系數(shù)的絕對(duì)值|wi||wi|正好代表了對(duì)應(yīng)特征xixi的重要性為多少。|wi||wi|越大，表示對(duì)應(yīng)特征xixi越重要，則該特征應(yīng)該被選擇。w的值可以通過(guò)對(duì)已有的數(shù)據(jù)集(xi,yi)(xi,yi)建立線(xiàn)性模型而得到。

然而，對(duì)于非線(xiàn)性模型來(lái)說(shuō)，因?yàn)椴煌卣骺赡苁欠蔷€(xiàn)性交叉在一起的，所以計(jì)算每個(gè)特征的重要性就變得比較復(fù)雜和困難。例如，Random Forest就是一個(gè)非線(xiàn)性模型，接下來(lái)，我們將討論如何在RF下進(jìn)行特征選擇。

RF中，特征選擇的核心思想是random test。random test的做法是對(duì)于某個(gè)特征，如果用另外一個(gè)隨機(jī)值替代它之后的表現(xiàn)比之前更差，則表明該特征比較重要，所占的權(quán)重應(yīng)該較大，不能用一個(gè)隨機(jī)值替代。相反，如果隨機(jī)值替代后的表現(xiàn)沒(méi)有太大差別，則表明該特征不那么重要，可有可無(wú)。所以，通過(guò)比較某特征被隨機(jī)值替代前后的表現(xiàn)，就能推斷出該特征的權(quán)重和重要性。

那么random test中的隨機(jī)值如何選擇呢？通常有兩種方法：一是使用uniform或者gaussian抽取隨機(jī)值替換原特征；一是通過(guò)permutation的方式將原來(lái)的所有N個(gè)樣本的第i個(gè)特征值重新打亂分布（相當(dāng)于重新洗牌）。比較而言，第二種方法更加科學(xué)，保證了特征替代值與原特征的分布是近似的（只是重新洗牌而已）。這種方法叫做permutation test（隨機(jī)排序測(cè)試），即在計(jì)算第i個(gè)特征的重要性的時(shí)候，將N個(gè)樣本的第i個(gè)特征重新洗牌，然后比較D和D(p)D(p)表現(xiàn)的差異性。如果差異很大，則表明第i個(gè)特征是重要的。

知道了permutation test的原理后，接下來(lái)要考慮的問(wèn)題是如何衡量上圖中的performance，即替換前后的表現(xiàn)。顯然，我們前面介紹過(guò)performance可以用Eoob(G)Eoob(G)來(lái)衡量。但是，對(duì)于N個(gè)樣本的第i個(gè)特征值重新洗牌重置的D(p)D(p)，要對(duì)它進(jìn)行重新訓(xùn)練，而且每個(gè)特征都要重復(fù)訓(xùn)練，然后再與原D的表現(xiàn)進(jìn)行比較，過(guò)程非常繁瑣。為了簡(jiǎn)化運(yùn)算，RF的作者提出了一種方法，就是把permutation的操作從原來(lái)的training上移到了OOB validation上去，記為Eoob(G(p))→E(p)oob(G)Eoob(G(p))→Eoob(p)(G)。也就是說(shuō)，在訓(xùn)練的時(shí)候仍然使用D，但是在OOB驗(yàn)證的時(shí)候，將所有的OOB樣本的第i個(gè)特征重新洗牌，驗(yàn)證G的表現(xiàn)。這種做法大大簡(jiǎn)化了計(jì)算復(fù)雜度，在RF的feature selection中應(yīng)用廣泛。

Random Forest in Action

最后，我們通過(guò)實(shí)際的例子來(lái)看一下RF的特點(diǎn)。首先，仍然是一個(gè)二元分類(lèi)的例子。如下圖所示，左邊是一個(gè)C&RT樹(shù)沒(méi)有使用bootstrap得到的模型分類(lèi)效果，其中不同特征之間進(jìn)行了隨機(jī)組合，所以有斜線(xiàn)作為分類(lèi)線(xiàn)；中間是由bootstrap（N’=N/2）后生成的一棵決策樹(shù)組成的隨機(jī)森林，圖中加粗的點(diǎn)表示被bootstrap選中的點(diǎn)；右邊是將一棵決策樹(shù)進(jìn)行bagging后的分類(lèi)模型，效果與中間圖是一樣的，都是一棵樹(shù)。

當(dāng)t=100，即選擇了100棵樹(shù)時(shí)，中間的模型是第100棵決策樹(shù)構(gòu)成的，還是只有一棵樹(shù)；右邊的模型是由100棵決策樹(shù)bagging起來(lái)的，如下圖所示：

當(dāng)t=200時(shí)：

當(dāng)t=300時(shí)：

當(dāng)t=400時(shí)：

當(dāng)t=500時(shí)：

當(dāng)t=600時(shí)：

當(dāng)t=700時(shí)：

當(dāng)t=800時(shí)：

當(dāng)t=900時(shí)：

當(dāng)t=1000時(shí)：

隨著樹(shù)木個(gè)數(shù)的增加，我們發(fā)現(xiàn)，分界線(xiàn)越來(lái)越光滑而且得到了large-margin-like boundary，類(lèi)似于SVM一樣的效果。也就是說(shuō)，樹(shù)木越多，分類(lèi)器的置信區(qū)間越大。

然后，我們?cè)賮?lái)看一個(gè)比較復(fù)雜的例子，二維平面上分布著許多離散點(diǎn)，分界線(xiàn)形如sin函數(shù)。當(dāng)只有一棵樹(shù)的時(shí)候（t=1），下圖左邊表示單一樹(shù)組成的RF，右邊表示所有樹(shù)bagging組合起來(lái)構(gòu)成的RF。因?yàn)橹挥幸豢脴?shù)，所以左右兩邊效果一致。

當(dāng)t=6時(shí)：

當(dāng)t=11時(shí)：

當(dāng)t=16時(shí)：

當(dāng)t=21時(shí)：

可以看到，當(dāng)RF由21棵樹(shù)構(gòu)成的時(shí)候，分界線(xiàn)就比較平滑了，而且它的邊界比單一樹(shù)構(gòu)成的RF要robust得多，更加平滑和穩(wěn)定。

最后，基于上面的例子，再讓問(wèn)題復(fù)雜一點(diǎn)：在平面上添加一些隨機(jī)噪聲。當(dāng)t=1時(shí)，如下圖所示：

當(dāng)t=6時(shí)：

當(dāng)t=11時(shí)：

當(dāng)t=16時(shí)：

當(dāng)t=21時(shí)：

從上圖中，我們發(fā)現(xiàn)21棵樹(shù)的時(shí)候，隨機(jī)noise的影響基本上能夠修正和消除。這種bagging投票的機(jī)制能夠保證較好的降噪性，從而得到比較穩(wěn)定的結(jié)果。

經(jīng)過(guò)以上三個(gè)例子，我們發(fā)現(xiàn)RF中，樹(shù)的個(gè)數(shù)越多，模型越穩(wěn)定越能表現(xiàn)得好。在實(shí)際應(yīng)用中，應(yīng)該盡可能選擇更多的樹(shù)。值得一提的是，RF的表現(xiàn)同時(shí)也與random seed有關(guān)，即隨機(jī)的初始值也會(huì)影響RF的表現(xiàn)。

總結(jié)：

本節(jié)課主要介紹了Random Forest算法模型。RF將bagging與decision tree結(jié)合起來(lái)，通過(guò)把眾多的決策樹(shù)組進(jìn)行組合，構(gòu)成森林的形式，利用投票機(jī)制讓G表現(xiàn)最佳，分類(lèi)模型更穩(wěn)定。其中為了讓decision tree的隨機(jī)性更強(qiáng)一些，可以采用randomly projected subspaces操作，即將不同的features線(xiàn)性組合起來(lái)，從而進(jìn)行各式各樣的切割。同時(shí)，我們也介紹了可以使用OOB樣本來(lái)進(jìn)行self-validation，然后可以使用self-validation來(lái)對(duì)每個(gè)特征進(jìn)行permutaion test，得到不同特征的重要性，從而進(jìn)行feature selection。總的來(lái)說(shuō)，RF算法能夠得到比較平滑的邊界，穩(wěn)定性強(qiáng)，前提是有足夠多的樹(shù)。

注明：

文章中所有的圖片均來(lái)自臺(tái)灣大學(xué)林軒田《機(jī)器學(xué)習(xí)技法》課程

更多AI資源請(qǐng)關(guān)注公眾號(hào)：AI有道（ID：redstonewill）

總結(jié)

以上是生活随笔為你收集整理的台湾大学林轩田机器学习技法课程学习笔记10 -- Random Forest的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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