• Big Data Exploration Part I
• Big Data Exploration Part II
• Decision Trees Model Part I
• Decision Trees Model Part II
• Random Forests Model Part I

Random Forests

在建立Tree-based models的流程中使用Bagging演算法的Bagging trees模型, 導入了隨機元件(random component)的架構, 大幅改善了模型建立的變異,因而提升了預測績效。然而, Bagging trees模型中每一個tree model彼此之間並非是完全獨立的(independent),因為, 每一個tree model在進行每一次split時, 所有資料的欄位變數(original predictors)都會被分析考慮。假設今天訓練資料集, 其欄位變數和response之間的關係(relationship)可以用tree model所建立, 則以此資料數據所產生的每一個bootstrap samples產生之tree model結構將會非常類似(尤其位於tree model的top nodes); 我們稱此特性為”Tree Correlation”。



Tree Correlation會讓Bagging演算法無法更進一步優化預測變異(variance) – 因為每一個bootstrap samples的tree model可能都使用相似的變數進行split, 並因此產生類似的預測數值。以Titanic 數據為例, 性別(gender)這個變數是一個強效的特徵(因為女性存活率明顯高於男性, 因此以此做為分割條件可以最有效的進行分類), 在這情況下, Bagging產生之大多數tree model都會以性別變數做為第一個split條件。顯然,降低tree models之間的相關性(correlation), 我們稱之為” de-correlating trees”, 是我們進一步優化預測績效的下一個目標。

以統計的觀點,要降低變數之間的關聯性,可以透過在tree model建構過程中, 增加隨機性(randomness)達到。依照此概念, Breiman (2001)創造一個稱之為”random forests”的演算法, 此演算法的流程架構如Algorithm 1(b)所示:

和Bagging 演算法的預測邏輯一樣, ensemble中的每一個模型都會產生各自的預測數據; 依照問題型態的不同, 分別使用兩種方式進行預測:


和Bagging相較, Random forests更進一步增加模型的隨機性(randomness) - 在每次split時隨機選取變數,因此可以有效地減低tree correlation。
Tree Model在進行split時需隨機選取多少數量的變數, 是Random forests演算法的調校參數(tuning parameter), 一般用代號k表示。Breiman (2001)依照預測類型的不同, 分別建議兩個算式如下:


若想對此參數k進行tuning, 我們建議從不直接使用上列算式取得之數字開始, 並以5為間距等量增加至所有的資料數據變數數量。例如資料數據共有210個變數, For regression, 參數k的調校數值為{70,75,80…,210}, 而後依照各k值所產生的模型預測績效, 決定參數k的最佳化數值。

回到Titanic 數據, 此資料集共有10個變數, 若不對參數k進行tuning, 依照classification的算式, 我們設定k=3(10的平方根大約為3.16)做為參數值。因此, Tree Model在每次進行split時, 僅會選取10個變數中的任意3個參數, 決定split; 在這個情況下, 性別變數就不會總是出現在每一個Tree Model的第一次split, 甚至有些Tree Model可能要到較深的node才會看到性別變數。

實務上,我們還需設定Random forests需包含建立多少數量的Tree Model; Breiman (2001)已經驗證Random forests並不會有over-fitting問題, 因此, 模型預測的績效不會因為過多的Tree Models而扭曲下降; 實際需要考量的是運算效能, 越多的Tree Model, 系統需要越多的運算時間去訓練以建構模型。一般建議以1000個Tree Models開始進行評估, 若cross-validation績效數值在1000個Tree Models仍有顯著的改善, 則可以加入更多的Tree Models直到績效改善效率平穩為止。

Random forests藉由選取” strong, complex learners” – 也就是low bias的模型組件, 來達到降低variance的目的。這種合併多個獨立且strong的learners可以改善模型的錯誤率。也由於每一個訓練模型組件(learners)是各自獨立所選取的,每一個元件選擇不會受前次的選擇結果(selected independently of all previous learners)所影響, Random forests演算法具有robust to a noisy response特性優勢。

Random forests透過使用兩項隨機元件, 其所組合完成之模型, 將包含完全各自獨特的tree models, 然後每一個tree models皆會產出完全不一樣的預測結果。由於Random forests的tree model並不會進行prune, 因此每一個tree model都可能會over-fitting, 但是每個over-fitting的結構又都是不一樣的。所有的這些”mistakes”都會在最後進行彙整預測時被”平均掉”。

與Bagging演算法相較, random forests在運算效能上表現更為優秀; 這是因為在Tree model建置過程中, 僅有部分比率的數據變數在split時進行分析。將此特性加上平行處理, random forests的運算效能遠高於另外一個有名ensemble演算法 - Boosting

由於模型合併(ensemble)的架構, 使得運用random forests模型時, 我們無法獲得/解釋predictors和response之間的關聯性, 但由於tree model仍是此Ensemble模型的基礎元件, 我們仍然可以量化各個predictor對於預測的影響程度數據。量化的方法為,以classification預測為例, 評量每一個Node的predictor, 其使用前後purity的變化(使用Gini index)。彙整整個random forests的量測數據後, 就可以獲得所有的predictors重要性數值。

Predictors重要性數據仍會有下列2個侷限:

Building Random Forests model on Titanic sample

R環境下的Random Forest演算法有一些限制, 必須在模型建置前先行處理。最主要的一項是, R的Random Forest模型訓練資料集中, 不可以有missing values (也就是NA)。在上一篇文章中, 我們提到R有許多package支援我們處理資料集中的NA數值, 這裡參照Trevor Stephens的做法, 使用我們學過的rpart這個package, 來處理資料集中的missing value。在rpart模型訓練中遇到NA數值時, rpart運用surrogate variables方式填補missing value資料, R的Random Forest package並沒有預設或內建NA數值的處理模式, 因此必須先行處理資料集中的missing value。

首先, 我們先check上一個小節所產生的combi data set中,有哪些欄位有NA value:

summary(combi)

可以發現:Age, Fare,和Embarked這三個欄位有missing values。

我們使用上一個post所學會的Decision Tree model, 來填補Age欄位的NA value;由於這次的預測對象是continuous variable, 所以改變參數method="anova",接著使用is.na()這個方式, 選取出資料集中有NA value的資料行, 將預測值與以取代NA數值

Agefit <- rpart(Age ~ Pclass + Sex + SibSp + Parch + Fare + Embarked + Title + FamilySize,
                data=combi[!is.na(combi$Age),], 
  method="anova")

combi$Age[is.na(combi$Age)] <- predict(Agefit, combi[is.na(combi$Age),])
summary(combi$Age)

再次檢視Age欄位, NA’s已經沒有了







Embarked欄位和Age不太一樣, 首先,它是blank value, 再者,僅有2筆資料是blank value. 由於資料數很小不至於影響到model的建立, 因此我們直接將此兩筆資料用最多的Embarked値 – S取代

combi$Embarked[which(combi$Embarked == '')] <- "S"
combi$Embarked <- factor(combi$Embarked)

最後, Fare欄位僅有一筆資料為NA value, 我們使用median數値取代

which(is.na(combi$Fare))
[1] 1044
combi$Fare[1044] <- are="" code="" combi="" median="" na.rm="TRUE)">

R的Random Forest演算法第2個限制是: 模型訓練資料集中的factor欄位, 最多只能到32個levels。檢視combi data set, FamilyID這個變數共有61個levels

我們有兩個方式來處理這一個問題:

這裡, 我們採用第2個方式。我們找出FamilySize <= 3的數據, 然後將FamilyID改指定為“Small”

combi$FamilyID2 <- combi$FamilyID
combi$FamilyID2 <- as.character(combi$FamilyID2)
combi$FamilyID2[combi$FamilySize <= 3] <- 'Small'
combi$FamilyID2 <- factor(combi$FamilyID2)

快速說明一下程式碼。首先複製FamilyID欄位成為FamilyID2; 第二步, 移除factor, 將欄位轉換回文字型態; 最後, 找出需給定‘Small’數值的資料, 取代完成後, 再轉換回factor。檢視資料, levels成功降低至22

OK, 現在我們可以開始建立Random Forest模型了

install.packages('randomForest')
library(randomForest)

train <- combi[1:891,]
test <- combi[892:1309,]

set.seed(415)
rffit <- randomForest(as.factor(Survived) ~ Pclass + Sex + Age + SibSp + Parch + Fare + Embarked + Title + FamilySize +FamilyID2, 
  data=train, 
  importance=TRUE, 
  ntree=2000)

由於建立之模型用以進行分類預測, 我們使用as.factor() function, 將預測之目標變數轉換成2個levels的factor; randomForest package提供許多參數供我們進行模型調校, 這裡整理幾個重要的參數進行說明:

varImpPlot(rffit)

varImpPlot() function產生2種importance measures:

我們使用predict()方法產生test data set的預測數值。呼叫predict方法時,加上參數type=prob, 可以取得類別機率(class probabilities)數值, 而不是預測結果; 有了類別機率數值, 我們可以另外自行決定, 當類別機率高於多少時, 才選定該類別; 例如class probabilities > 70%, 才認定該人員Survived。

Prediction <- predict(rffit, test)
submit <- data.frame(PassengerId = test$PassengerId, Survived = Prediction)
write.csv(submit, file = "randomforest.csv", row.names = FALSE)

n   The result works out exactly the same as Kaggle’s Python random forest tutorial.

上述之Random Forest演算法使用CART模型做為base learner, 我們另外嘗試以conditional inference trees模型做為base learner, 來進行Titanic Data Set的預測。Conditional inference trees模型的基本架構與一般Tree-based模型類似, 唯一一個差異在於模型的決策衡量, 並非以purity做為目標, 而是使用statistical test進行評估。R implement的package為party, 此package並沒有randomForest package的factor 32 level限制; 另外, party的mtry預設參數為5, 由於Titanic Data Set的變數量不多, 因此調整為3。

install.packages('party')
library(party)

set.seed(415)
cffit <- cforest(as.factor(Survived) ~ Pclass + Sex + Age + SibSp + Parch + Fare + Embarked + Title + FamilySize + FamilyID,
               data = train, controls=cforest_unbiased(ntree=2000, mtry=3))

Prediction <- predict(cffit, test, OOB=TRUE, type = "response")
write.csv(submit, file = "conditionforest.csv", row.names = FALSE)

Random Forests模型系列到此告一段落, 希望這6篇文章有幫助各位了解Random Forests演算法, 並能運用R進行實作分類預測。