Previously in this series:

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

讓我們回到Titanic資料集, 使用上一個Part學到的CART model來進行分析預測。這裡的程式範例一樣參照Trevor Stephens的文章(http://trevorstephens.com/post/72923766261/titanic-getting-started-with-r-part-3-decision ), 採用rpart這個package進行模型建置. rpart代表“Recursive Partitioning and Regression Trees”, 實現(implement)上述所闡述CART模型演算法。

library(rpart)
fit <- rpart(Survived ~ Pclass + Sex + Age + SibSp + Parch + Fare + Embarked, data=train, method="class")

除了上一篇所提到的四個變數 – Pclass, Sex, Age和Fare, Trevor Stephens另加入了三個變數進行模型訓練。3個變數的代表意義如下:

embarked        Port of Embarkation



由於CART模型演算法會自動搜尋所有的數值以決定split point, 因此我們不需要再另外產生新變數去預先決定Age或Fare的分類數值(如上一篇post 建立新變數child將Age切分為<18和>=18)。 
R內建的plot function繪圖程式過於簡單, 我們使用其他的library來繪製CART模型結果。

#R內建的plot function
plot(fit)
text(fit)
#使用其他的library來繪製CART模型結果
library(rattle)
library(rpart.plot)
library(RColorBrewer)

fancyRpartPlot(fit)

我使用左下方的節點(Node), 來解釋圖中的各項數據。

62%: 表示此節點(Node)的Sample數量共佔全部Training set數的62%. 此節點(Node)包含甚麼樣的Sample? 從它上面的節點(Node)變數邏輯能夠得知:
Sex=Male & Age >=6.5       

我們可以使用下列程式碼驗證62%的結果; 另外說明一點, 當CART模型建置時, missing data(NA數值的資料)是被忽略不處理的; 只有實際的數值才會被分析並做為split的判斷數值, 也就是說, 我們不會看到split有”是否為NA”這樣的判斷邏輯。當進行預測時, 若要預測的數據遇到split, 但此split需要的predictor預測數據不存在(NA)時, CART模型會應用surrogate splits演算法之數值取代此missing data進行預測。

nrow(dtTrain)
nrow(dtTrain[Sex=='male' & (Age>=6.5 | is.na(Age))])
nrow(dtTrain[Sex=='male' & (Age>=6.5 | is.na(Age))])/nrow(dtTrain)

891是Training set的總數, 533是左下方節點Sex=Male & Age >=6.5的數量, 因此其比率為62%. 


在62%上方有兩個數字分別為0.83和0.17, 它們表示此節點的Passengers, 17%的乘客Survived, 83% Not Survived. 

dtTrain[Survived ==1 & Sex=='male' & (Age>=6.5 | is.na(Age)),list(Name,Age,Sex,Survived)]

nrow(dtTrain[Survived==1 & Sex=='male' & (Age>=6.5 | is.na(Age)),list(Name,Age,Sex,Survived)])/nrow(dtTrain[Sex=='male' & (Age>=6.5 | is.na(Age))])

根據Majority Vote邏輯, 此節點的預測值為Not Survived. 因此可以看到節點框框的最上面的數字為0.


最後, 我們使用完成訓練的CART模型來進行預測。

Prediction <- predict(fit, test, type = "class")
submit <- data.frame(PassengerId = test$PassengerId, Survived = Prediction)
write.csv(submit, file = "myfirstdtree.csv", row.names = FALSE)

 各位可以將上述的預測結果submit至Kaggle看看預測成效如何


分析到這裡,我想使用Titanic這個Sample, review一下 Part I所提及tree-based models的優點。
第一, 當樹狀模型不會過於龐大時, 我們可以很容易從圖型化的結果理解模型的架構(the model is simple and interpretable). 雖然CART模型原理會進行大量的變數數值搜尋運算, 但你可以發現, 程式實際執行時其實沒有花費多少時間就完成模型的訓練。
第二, Tree models在模型建置時其實就隱含著進行feature selection:如果某個predictor從未被使用split, 表示此predictor對於預測結果相對地無顯著的影響能力。但要注意的是, 此項特點會隨著變數之間的相關程度增加而弱化。例如有2個predictors是很重要的預測變數, 但此兩個predictors具有高度的相關性, 當Tree models在選擇split變數遇到這2個變數時, 是以隨機方式選擇predictors之中的一個做為split變數。當有更多的predictors擁有高度相關性時, 這些predictors被選取做為split變數的次數, 可能會遠超過真正所需的頻率, 另外一方面這種現象也會影響變數重要性(variable importance values)的排名。以2個高度相關的predictors為例, 在此情況下,這兩個predictors的變數重要性就可能被削減一半。  

Tree models另外一個需要注意的點是selection bias: Tree models在決定split變數時,傾向選取擁有較多不一樣數值(distinct values)的變數。Loh and Shih 1997; Carolin et al. 2007; Loh 2010都發表過相關文章討論。節錄Loh and Shih (1997).如下 

“The danger occurs when a data set consists of a mix of informative and noise variables, and the noise variables have many more splits than the informative variables. Then there is a high probability that the noise variables will be chosen to split the top nodes of the tree. Pruning will produce either a tree wih misleading structure or no tree at all.”

因為selection bias這個特性, 如果數據中有過多的missing values, 模型訓練時要特別注意受selection bias影響而產生偏差模型。也正因為如此,實務上在模型訓練之前,都會預先給予(fill)missing values一些合理的數值. R提供許多packages支援impute missing values. 主要的packages如MICE(Multivariate Imputation via Chained Equations) - 應用regression演算法, Amelia – 應用bootstrap演算法, missForest – 應用我們將討論的random forest演算法。其他packages還有Hmisc和mi(Multiple imputation with diagnostics)等。

Over-Fitting and Tree pruning

當我們開始進行Tree models建置時, Tree models可能會長的非常的巨大; 以Titanic資料集為例子, 我們可能會建立出下列這樣的一個節點(Node)邏輯:

34 year old female in third class who paid $20.17 for a ticket from Southampton with a sister and mother aboard

這種邏輯可能不僅繁瑣, 更多可能的是此複雜的條件結果僅存在於訓練資料集(training data set)之中。我們將這種過於”嵌合”訓練資料的現象稱為Over-Fitting. 為了解決Tree models容易產生Over-Fitting的模型, Tree models演算法導入了Tree Pruning技術 – 概念上來說, 就是將樹狀模型結構進行裁剪, 讓樹狀模型的深度(depth)縮減到一個合理的大小, 此調整的目標是達到極小化模型的錯誤率。Breiman et al. (1984)提出了cost–complexity tuning方法論, 引進了參數cp (complexity parameter)作為和節點(Node)數, 作為模型Purity 標準的懲罰因子; 公式如下:

Gini index =  Gini index + cp * [# Terminal Nodes]

我們可以透過rpart package的rpart.control引數, 進行Tree Pruning. 其中兩個常用的參數為:

下列程式碼展示一個沒有進行Tree Pruning而產生的一個非常龐大的Tree Model(set cp=0, minsplit=2):

ofit <- rpart(Survived ~ Pclass + Sex + Age + SibSp + Parch + Fare + Embarked, 
  data=train, 
  method="class", 
  control=rpart.control(minsplit=2, cp=0))

fancyRpartPlot(ofit)
Prediction <- predict(ofit, test, type = "class")
submit <- data.frame(PassengerId = test$PassengerId, Survived = Prediction)
write.csv(submit, file = "overfit.csv", row.names = FALSE)

如果你將上述程式碼產生的overfit.csv上傳至Kaggle網站, 就會發現預測結果非常的糟糕,甚至比最一開始用[性別]參數建立的模型預測能力還要差! 這就是模型Over-Fitting的結果。

Advantages and Disadvantages of Trees

最後, 我節錄An Introduction to Statistical Learning一書, 第八章Tree-Based Methods的內容, 總結應用Decision tree於進行regression和classification分析預測上, 優於傳統統計方法的優勢:

然而, 單一的Decision tree模型並非完全沒有缺點; 2個明顯的模型缺陷為:


為了消減上述問題, Machine Learning的研究人員開發出了”Ensemble methods”.  Ensemble技術的核心概念是先產生眾多的Decision tree模型, 然後再將這些模型合併(combine)後, 產生一個綜合所有模型分析的預測結果。目前主要的Ensemble技術有Bagging, Random Forests,和Boosting. 在許多研究和比賽結果可以發現, 結合大數量的tree模型所創構的Model, 可以大幅度改善模型的預測績效。我們將在下一篇Post中, 介紹Bagging和Random Forests.

by J.D.