R語(yǔ)言︱決策樹(shù)族——隨機(jī)森林算法

一、隨機(jī)森林理論介紹
1.1 優(yōu)缺點(diǎn)
優(yōu)點(diǎn)。
(1)不必?fù)?dān)心過(guò)度擬合；
(2)適用于數(shù)據(jù)集中存在大量未知特征；
(3)能夠估計(jì)哪個(gè)特征在分類(lèi)中更重要；
(4)具有很好的抗噪聲能力；
(5)算法容易理解；
(6)可以并行處理。
缺點(diǎn)。
（1）對(duì)小量數(shù)據(jù)集和低維數(shù)據(jù)集的分類(lèi)不一定可以得到很好的效果。
（2）執(zhí)行速度雖然比Boosting等快，但是比單個(gè)的決策樹(shù)慢很多。
（3）可能會(huì)出現(xiàn)一些差異度非常小的樹(shù)，淹沒(méi)了一些正確的決策。
1.2 生成步驟介紹
1、從原始訓(xùn)練數(shù)據(jù)集中，應(yīng)用bootstrap方法有放回地隨機(jī)抽取k個(gè)新的自助樣本集，并由此構(gòu)建k棵分類(lèi)回歸樹(shù)，每次未被抽到的樣本組成了Ｋ個(gè)袋外數(shù)據(jù)（out-of-bag,BBB）。
2、設(shè)有n 個(gè)特征，則在每一棵樹(shù)的每個(gè)節(jié)點(diǎn)處隨機(jī)抽取mtry 個(gè)特征，通過(guò)計(jì)算每個(gè)特征蘊(yùn)含的信息量，特征中選擇一個(gè)最具有分類(lèi)能力的特征進(jìn)行節(jié)點(diǎn)分裂。
3、每棵樹(shù)最大限度地生長(zhǎng)， 不做任何剪裁
4、將生成的多棵樹(shù)組成隨機(jī)森林， 用隨機(jī)森林對(duì)新的數(shù)據(jù)進(jìn)行分類(lèi)， 分類(lèi)結(jié)果按樹(shù)分類(lèi)器投票多少而定。
1.3 隨機(jī)森林與SVM的比較
（1）不需要調(diào)節(jié)過(guò)多的參數(shù)，因?yàn)?a href='/map/suijisenlin/' style='color:#000;font-size:inherit;'>隨機(jī)森林只需要調(diào)節(jié)樹(shù)的數(shù)量，而且樹(shù)的數(shù)量一般是越多越好，而其他機(jī)器學(xué)習(xí)算法，比如SVM，有非常多超參數(shù)需要調(diào)整，如選擇最合適的核函數(shù)，正則懲罰等。
（2）分類(lèi)較為簡(jiǎn)單、直接。隨機(jī)深林和支持向量機(jī)都是非參數(shù)模型（復(fù)雜度隨著訓(xùn)練模型樣本的增加而增大）。相較于一般線(xiàn)性模型，就計(jì)算消耗來(lái)看，訓(xùn)練非參數(shù)模型因此更為耗時(shí)耗力。分類(lèi)樹(shù)越多，需要更耗時(shí)來(lái)構(gòu)建隨機(jī)森林模型。同樣，我們訓(xùn)練出來(lái)的支持向量機(jī)有很多支持向量，最壞情況為，我們訓(xùn)練集有多少實(shí)例，就有多少支持向量。雖然，我們可以使用多類(lèi)支持向量機(jī)，但傳統(tǒng)多類(lèi)分類(lèi)問(wèn)題的執(zhí)行一般是one-vs-all（所謂one-vs-all 就是將binary分類(lèi)的方法應(yīng)用到多類(lèi)分類(lèi)中。比如我想分成K類(lèi)，那么就將其中一類(lèi)作為positive），因此我們還是需要為每個(gè)類(lèi)訓(xùn)練一個(gè)支持向量機(jī)。相反，決策樹(shù)與隨機(jī)深林則可以毫無(wú)壓力解決多類(lèi)問(wèn)題。
（3）比較容易入手實(shí)踐。隨機(jī)森林在訓(xùn)練模型上要更為簡(jiǎn)單。你很容易可以得到一個(gè)又好且具魯棒性的模型。隨機(jī)森林模型的復(fù)雜度與訓(xùn)練樣本和樹(shù)成正比。支持向量機(jī)則需要我們?cè)谡{(diào)參方面做些工作，除此之外，計(jì)算成本會(huì)隨著類(lèi)增加呈線(xiàn)性增長(zhǎng)。
（4）小數(shù)據(jù)上，SVM優(yōu)異，而隨機(jī)森林對(duì)數(shù)據(jù)需求較大。就經(jīng)驗(yàn)來(lái)說(shuō)，我更愿意認(rèn)為支持向量機(jī)在存在較少極值的小數(shù)據(jù)集上具有優(yōu)勢(shì)。隨機(jī)森林則需要更多數(shù)據(jù)但一般可以得到非常好的且具有魯棒性的模型。
1.5 隨機(jī)森林與深度學(xué)習(xí)的比較
深度學(xué)習(xí)需要比隨機(jī)森林更大的模型來(lái)擬合模型，往往，深度學(xué)習(xí)算法需要耗時(shí)更大，相比于諸如隨機(jī)森林和支持向量機(jī)那樣的現(xiàn)成分類(lèi)器，安裝配置好一個(gè)神經(jīng)網(wǎng)絡(luò)模型來(lái)使用深度學(xué)習(xí)算法的過(guò)程則更為乏味。
但不可否認(rèn)，深度學(xué)習(xí)在更為復(fù)雜問(wèn)題上，如圖片分類(lèi)，自然語(yǔ)言處理，語(yǔ)音識(shí)別方面更具優(yōu)勢(shì)。
另外一個(gè)優(yōu)勢(shì)為你不需要太關(guān)注特征工程相關(guān)工作。實(shí)際上，至于如何選擇分類(lèi)器取決于你的數(shù)據(jù)量和問(wèn)題的一般復(fù)雜性（和你要求的效果）。這也是你作為機(jī)器學(xué)習(xí)從業(yè)者逐步會(huì)獲得的經(jīng)驗(yàn)。
可參考論文《An Empirical Comparison of Supervised Learning Algorithms》。
1.6 隨機(jī)森林與決策樹(shù)之間的區(qū)別
模型克服了單棵決策樹(shù)易過(guò)擬合的缺點(diǎn)，模型效果在準(zhǔn)確性和穩(wěn)定性方面都有顯著提升。
決策樹(shù)+bagging=隨機(jī)森林
1.7 隨機(jī)森林不會(huì)發(fā)生過(guò)擬合的原因
在建立每一棵決策樹(shù)的過(guò)程中，有兩點(diǎn)需要注意-采樣與完全分裂。首先是兩個(gè)隨機(jī)采樣的過(guò)程，random forest對(duì)輸入的數(shù)據(jù)要進(jìn)行行、列的采樣。對(duì)于行采樣，采用有放回的方式，也就是在采樣得到的樣本集合中，可能有重復(fù)的樣本。
假設(shè)輸入樣本為N個(gè)，那么采樣的樣本也為N個(gè)。這樣使得在訓(xùn)練的時(shí)候，每一棵樹(shù)的輸入樣本都不是全部的樣本，使得相對(duì)不容易出現(xiàn)over-fitting。
然后進(jìn)行列采樣，從M個(gè)feature中，選擇m個(gè)(m << M)。之后就是對(duì)采樣之后的數(shù)據(jù)使用完全分裂的方式建立出決策樹(shù)，這樣決策樹(shù)的某一個(gè)葉子節(jié)點(diǎn)要么是無(wú)法繼續(xù)分裂的，要么里面的所有樣本的都是指向的同一個(gè)分類(lèi)。一般很多的決策樹(shù)算法都一個(gè)重要的步驟-剪枝，但是這里不這樣干，由于之前的兩個(gè)隨機(jī)采樣的過(guò)程保證了隨機(jī)性，所以就算不剪枝，也不會(huì)出現(xiàn)over-fitting。 按這種算法得到的隨機(jī)森林中的每一棵都是很弱的，但是大家組合起來(lái)就很厲害了。
可以這樣比喻隨機(jī)森林算法：每一棵決策樹(shù)就是一個(gè)精通于某一個(gè)窄領(lǐng)域的專(zhuān)家（因?yàn)槲覀儚腗個(gè)feature中選擇m讓每一棵決策樹(shù)進(jìn)行學(xué)習(xí)），這樣在隨機(jī)森林中就有了很多個(gè)精通不同領(lǐng)域的專(zhuān)家，對(duì)一個(gè)新的問(wèn)題（新的輸入數(shù)據(jù)），可以用不同的角度去看待它，最終由各個(gè)專(zhuān)家，投票得到結(jié)果。
1.8 隨機(jī)森林與梯度提升樹(shù)（GBDT）區(qū)
隨機(jī)森林：決策樹(shù)+bagging=隨機(jī)森林
梯度提升樹(shù)：決策樹(shù)Boosting=GBDT
兩者區(qū)別在于bagging boosting之間的區(qū)別，可見(jiàn):

1.9 決策樹(shù)的特征選擇
本部分參考：隨機(jī)森林簡(jiǎn)易教程
特征選擇目前比較流行的方法是信息增益、增益率、基尼系數(shù)和卡方檢驗(yàn)。這里主要介紹基于基尼系數(shù)（GINI）的特征選擇，因?yàn)?a href='/map/suijisenlin/' style='color:#000;font-size:inherit;'>隨機(jī)森林采用的CART決策樹(shù)就是基于基尼系數(shù)選擇特征的。
基尼系數(shù)的選擇的標(biāo)準(zhǔn)就是每個(gè)子節(jié)點(diǎn)達(dá)到最高的純度，即落在子節(jié)點(diǎn)中的所有觀察都屬于同一個(gè)分類(lèi)，此時(shí)基尼系數(shù)最小，純度最高，不確定度最小。
決策樹(shù)中最常用的四種算法：
基尼系數(shù)（Gini Index）
基尼系數(shù)指出：我們從總體中隨機(jī)挑選兩個(gè)樣本，如果總體是純的，那么這兩個(gè)樣本是同類(lèi)別的概率為1。
    用于處理分類(lèi)型目標(biāo)變量“Success”或者“Failure”。
    它只作用于二進(jìn)制分裂。
    基尼系數(shù)越大，純度越高。
    CART（分類(lèi)和回歸樹(shù)）使用Gini方法創(chuàng)建二進(jìn)制分裂。
卡方（Chi-Square）
它可以用來(lái)衡量子節(jié)點(diǎn)和父節(jié)點(diǎn)之間是否存在顯著性差異。我們用目標(biāo)變量的觀測(cè)頻率和期望頻率之間的標(biāo)準(zhǔn)離差的平方和來(lái)計(jì)算卡方值。
    它用于處理分類(lèi)型目標(biāo)變量“Success”或“Failure”。
    它可以計(jì)算兩個(gè)或多個(gè)分裂。
    卡方越高，子節(jié)點(diǎn)與父節(jié)點(diǎn)之間的差異越顯著。
    Chi-square = ((Actual – Expected)^2 / Expected)^1/2
    它生成的樹(shù)稱(chēng)為：CHAID (Chi-square Automatic Interaction Detector)
如何計(jì)算一個(gè)分裂的卡方：
    通過(guò)計(jì)算Success和Failure的偏差來(lái)計(jì)算單個(gè)節(jié)點(diǎn)的卡方。
    通過(guò)計(jì)算每個(gè)節(jié)點(diǎn)的Success和Failure的所有卡方總和計(jì)算一個(gè)分裂的卡方。
信息增益（Information Gain）
觀察下面的圖像，想一下哪個(gè)節(jié)點(diǎn)描述起來(lái)更加容易。答案一定是C，因?yàn)镃圖中的所有的值都是相似的，需要較少的信息去解釋。相比較，B和A需要更多的信息去描述。用純度描述，就是：Pure(C) > Pure(B) > Pure(A)。


純度越高的節(jié)點(diǎn)，就會(huì)需要更少的信息去描述它；相反，不純度越高，就會(huì)需要更多的信息。信息論用熵來(lái)定義系統(tǒng)的混亂程度。如果樣本中的個(gè)體是完全相同類(lèi)別的，那么系統(tǒng)的熵為0；如果樣本是等劃分的（50%-50%），那么系統(tǒng)的熵為1。
方差削減（Reduction in Variance）
至此，我們已經(jīng)討論了很多關(guān)于分類(lèi)型目標(biāo)變量的算法。方差削減是用于連續(xù)型目標(biāo)變量的算法（回歸問(wèn)題）。它使用方差公式去挑選最優(yōu)分裂。方差最小的分裂將會(huì)作為分割總體的準(zhǔn)則。

如何計(jì)算方差？
    計(jì)算每一個(gè)節(jié)點(diǎn)的方差。
    計(jì)算每一個(gè)節(jié)點(diǎn)方差的加權(quán)平均，作為一個(gè)分裂的方差。
二、隨機(jī)森林重要性度量指標(biāo)——重要性評(píng)分、Gini指數(shù)
（1）重要性評(píng)分
定義為袋外數(shù)據(jù)自變量值發(fā)生輕微擾動(dòng)后的分類(lèi)正確率與擾動(dòng)前分類(lèi)正確率的平均減少量。
（1）：對(duì)于每棵決策樹(shù)，利用袋外數(shù)據(jù)進(jìn)行預(yù)測(cè)，將袋外數(shù)據(jù)的預(yù)測(cè)誤差將記錄下來(lái)。其每棵樹(shù)的誤差是：vote1，vote2····，voteb；
（2）：隨機(jī)變換每個(gè)預(yù)測(cè)變量，從而形成新的袋外數(shù)據(jù)，再利用袋外數(shù)據(jù)進(jìn)行驗(yàn)證，其每個(gè)變量的誤差是：vote11，vote12，···，vote1b。

（3）：對(duì)于某預(yù)測(cè)變量來(lái)說(shuō)，計(jì)算其重要性是變換后的預(yù)測(cè)誤差與原來(lái)相比的差的均值。
r語(yǔ)言中代碼：
[plain] view plain copy

    rf <- randomForest(Species ~ ., data=a, ntree=100, proximity=TRUE,importance=TRUE)  

（2）gini指數(shù)
gini指數(shù)表示節(jié)點(diǎn)的純度，gini指數(shù)越大純度越低。gini值平均降低量表示所有樹(shù)的變量分割節(jié)點(diǎn)平均減小的不純度。對(duì)于變量重要度衡量，步驟如同前面介紹，將變量數(shù)據(jù)打亂，gini指數(shù)變化的均值作為變量的重要程度度量。


（3）重要性繪圖函數(shù)——varImpPlot(rf)函數(shù)

三、隨機(jī)森林模型R語(yǔ)言實(shí)踐
3.1 隨機(jī)森林模型幾點(diǎn)注意
模型中關(guān)于分類(lèi)任務(wù)以及回歸預(yù)測(cè)任務(wù)的區(qū)別：
隨機(jī)森林模型，分類(lèi)和回歸預(yù)測(cè)的操作不同之處在于判斷因變量的類(lèi)型，如果因變量是因子則執(zhí)行分類(lèi)任務(wù)，如果因變量是連續(xù)性變量，則執(zhí)行回歸預(yù)測(cè)任務(wù)。
模型中關(guān)于數(shù)據(jù)結(jié)構(gòu)的要求：
`randomForest`函數(shù)要求為數(shù)據(jù)框或者矩陣，需要原來(lái)的數(shù)據(jù)框調(diào)整為以每個(gè)詞作為列名稱(chēng)（變量）的數(shù)據(jù)框。在文本挖掘的過(guò)程中，需要把詞頻（橫向，long型數(shù)據(jù)）轉(zhuǎn)化為變量（wide型縱向數(shù)據(jù)），可以用reshape2、data.table包來(lái)中dcast來(lái)實(shí)現(xiàn)。
隨機(jī)森林的兩個(gè)參數(shù):
候選特征數(shù)K
K越大，單棵樹(shù)的效果會(huì)提升，但樹(shù)之間相關(guān)性也會(huì)增強(qiáng)
決策樹(shù)數(shù)量M
M越大，模型效果會(huì)有提升，但計(jì)算量會(huì)變大
R中與決策樹(shù)有關(guān)的Package:
單棵決策樹(shù)：rpart/tree/C50
隨機(jī)森林：randomforest/ranger
梯度提升樹(shù)：gbm/xgboost
樹(shù)的可視化：rpart.plot
3.2 模型擬合
本文以R語(yǔ)言中自帶的數(shù)據(jù)集iris為例，以setosa為因變量，其他作為自變量進(jìn)行模型擬合，由于setosa本身就是因子型，所以不用轉(zhuǎn)換形式。
[plain] view plain copy

    > data <- iris  
    > library(randomForest)  
    > system.time(Randommodel <- randomForest(Species ~ ., data=data,importance = TRUE, proximity = FALSE, ntree = 100))  
    用戶(hù) 系統(tǒng) 流逝   
       0    0    0   
    > print(Randommodel)  
      
    Call:  
     randomForest(formula = Species ~ ., data = data, importance = TRUE,      proximity = FALSE, ntree = 100)   
                   Type of random forest: classification  
                         Number of trees: 100  
    No. of variables tried at each split: 2  
      
            OOB estimate of  error rate: 3.33%  
    Confusion matrix:  
               setosa versicolor virginica class.error  
    setosa         50          0         0        0.00  
    versicolor      0         47         3        0.06  
    virginica       0          2        48        0.04 
代碼解讀：randomForset，執(zhí)行建模，x參數(shù)設(shè)定自變量數(shù)據(jù)集，y參數(shù)設(shè)定因變量數(shù)據(jù)列，importance設(shè)定是否輸出因變量在模型中的重要性，如果移除某個(gè)變量，模型方差增加的比例是它判斷變量重要性的標(biāo)準(zhǔn)之一，proximity參數(shù)用于設(shè)定是否計(jì)算模型的臨近矩陣，ntree用于設(shè)定隨機(jī)森林的樹(shù)數(shù)（后面單獨(dú)討論），最后一句輸出模型在訓(xùn)練集上的效果。
prInt輸出模型在訓(xùn)練集上的效果，可以看出錯(cuò)誤率為3.33%，維持在比較低的水平。
3.3 隨機(jī)森林模型重要性檢
[plain] view plain copy

    > importance(Randommodel,type=1)  #重要性評(píng)分  
                 MeanDecreaseAccuracy  
    Sepal.Length             4.720094  
    Sepal.Width              1.405924  
    Petal.Length            16.222059  
    Petal.Width             13.895115  
    > importance(Randommodel,type=2)  #Gini指數(shù)  
                 MeanDecreaseGini  
    Sepal.Length         9.484106  
    Sepal.Width          1.930289  
    Petal.Length        45.873386  
    Petal.Width         41.894352  
    > varImpPlot(Randommodel)         #可視化  

利用iris數(shù)據(jù)，可以看到這四個(gè)變量的重要性排序是一樣的。
3.4 模型的預(yù)測(cè)功能
predict中有多種參數(shù)，比如Nodes，Proximity，predict.all。
[plain] view plain copy

    predict(object, newdata, type="response",  
            norm.votes=TRUE, predict.all=FALSE, proximity=FALSE, nodes=FALSE,  
            cutoff, ...)  
    #Nodes判斷是否是終點(diǎn)。Proximity判斷是否需要進(jìn)行近鄰測(cè)量。predict.all判斷是否保留所有的預(yù)測(cè)器。 
舉例，以前面的隨機(jī)森林模型進(jìn)行建模。
predict.all會(huì)輸出一個(gè)150*150的字符矩陣，代表每一顆樹(shù)的150個(gè)預(yù)測(cè)值（前面預(yù)設(shè)了ntree=100）；
Nodes輸出100顆樹(shù)的節(jié)點(diǎn)情況。
[plain] view plain copy

    prediction <- predict(Randommodel, data[,1:5],type="class")  #還有response回歸類(lèi)型  
      
    table(observed =data$Species,predicted=prediction)  
table輸出混淆矩陣，注意table并不是需要把預(yù)測(cè)值以及實(shí)際值放在一個(gè)表格之中，只要順序?qū)ι?，用observed以及predicted直接調(diào)用也可以。
3.5 補(bǔ)充——隨機(jī)森林包（party包）
與randomForest包不同之處在于，party可以處理缺失值，而這個(gè)包可以。
[html] view plain copy

    library(party)  
       #與randomForest包不同之處在于，party可以處理缺失值，而這個(gè)包可以  
    set.seed(42)  
    crf<-cforest(y~.,control = cforest_unbiased(mtry = 2, ntree = 50), data=step2_1)  
    varimpt<-data.frame(varimp(crf)) 
party包中的隨機(jī)森林建模函數(shù)為cforest函數(shù)，
mtry代表在每一棵樹(shù)的每個(gè)節(jié)點(diǎn)處隨機(jī)抽取mtry 個(gè)特征，通過(guò)計(jì)算每個(gè)特征蘊(yùn)含的信息量，特征中選擇一個(gè)最具有分類(lèi)能力的特征進(jìn)行節(jié)點(diǎn)分裂。