The practical guide to Random Forests – Decision Tree Model Part I
(Using Kaggle’s Titanic Data with R code)



Previously in this series:
 
在上一篇Post的結尾, 我們建立了一個如下的預測模型邏輯:
test$Survived <- 0
test$Survived[test$Sex == 'female'] <- 1
test$Survived[test$Sex == 'female' & test$Pclass == 3 & test$Fare >= 20] <- 0

我們可以將此程式碼的邏輯結構, 整理成一段IF-then/ELSE的分析流程:

     IF 性別為”女性” THEN
           IF Pclass 為 3 THEN
                IF 船票費用 高於 $20 THEN
                     預測:生還
     ELSE
           預測:未生還

     這樣以一系列IF/ELSE邏輯判斷所組合而成的模型架構, 即是Decision Tree模型的基本概念。

The classification and regression tree (CART) model

Decision Tree模型包含了一個或一個以上的IF-THEN語法, 其根據資料集的欄位變數(predictors/variables)進行邏輯判斷, 將資料切分成一個個的區塊(partition). 在每個區塊(partition)中的訓練結果, 即為模型用以估算未知資料的預測值。Decision Tree模型可以進行資料的分類預測, 也可以進行數值預測.

一個簡單的Decision Tree模型範例如下。假設一筆資料集共有2個欄位變數A和B, 預測目標是要將資料集分成2個Class – 1和2. 經過測試資料訓練之後,產生之Decision Tree模型如下:

IF Predictor B >=30 THEN
|  IF PredictorA >=25 THEN Class =1
|  ELSE  Class =2
ELSE
|  Class =2

 我們可以將此模型之邏輯圖像化結果如下。對於Two-class 的分類問題, 2個欄位變數將資料空間切分成3個矩型區塊。在每一個區塊中, Decision Tree模型將所有落在該區塊的所有資料, 統一預測歸類為”Class 1” 或 “Class 2”. 各區塊中的預測類別決定方法, Decision Tree模型最基本的方式是以[majority vote - 多數決]的方式決定, 因此可以看到圖中右上方的正方形區塊中, 由於Class 1的數量大於Class 2, 因此對於此區塊的數據預測為Class 1。 若預測目標為進行數值預測, Decision tree模型則是使用該區塊中, 所有sample reponse的平均數, 做為該區塊中的數據預測值。
以Tree models方法論來說, 此模型進行了2個splits, 並將資料切分成3個terminal nodes 或 leaves of the tree. 針對新的數據, 模型會根據所建立的一系列IF-then邏輯方程式, 逐一檢視新的數據欄位變數, 最後確認該筆新數據是落在哪一個terminal nodes, Decision Tree模型再使用majority vote算式,決定其預測類別。
 

讓我們用Titanic訓練資料, 產生一個僅用Sex欄位變數做為predictor的Decision Tree Model:


IF Sex = female THEN
   Survived
ELSE
   Not Survived
       

這裡使用R的rpart package 產生Decision Tree模型。相關程式碼的解說將在後面文章介紹。 
library(rpart)
fit <- rpart(Survived ~ Sex, data=train, method="class")
library(rattle)
library(rpart.plot)
library(RColorBrewer)
fancyRpartPlot(fit)




延續上述例子, 增加第2個predictor – Pclass, 產生另外一個稍微複雜的Decision Tree Model:

IF Sex = female THEN
|  IF Pclass == 3 THEN Survived
|  ELSE  Not Survived
ELSE
|  Not Survived


我們可以一直增加第3個、第4個、…predictors去建立Decision Tree Model, 而隨著predictor數量的增加, 模型將會越來越龐大與複雜(bigger and deeper). 數理界有許多技術可以進行上列的推演流程以建立Tree-based model. 目前最為廣泛應用的方法論是於1984由Breiman et al.所提出的the classification and regression tree (CART)模型演算法。CART model一開始針對整個資料集(data set)進行探勘, 模型會搜尋每一個predictor的每一個可能的數值進行計算, 以取得最佳的predictor與切分(split)數值, 來將原資料集, 分割成為2個子群組區塊。在新切分出來的區塊中, 再繼續上述的搜尋與分割流程; 這些Splits會不斷地增加Decision Tree Model的深度(depth), 造成樹狀模型的壯大。切分(split)流程會不斷地進行, 一直到分割的結果碰到停止條件(stop criterion)為止。停止條件可為每一個節點區塊(Node)中應該包含的最小的資料數量(samples), 或是Tree Model的最大深度(depth). 


The Gini Index and Greedy algorithm


就分類(classification)預測而言, CART模型的目標, 是將資料集切割成一個一個的群組, 每一個群組中的資料數量要低而且同質性高。所謂的同質性(Homogeneity), 就Decision Tree Model方法論來說, 表示每次切分(split)出來新的節點(node)要更單純(pure); 換句話說, 新的節點(node)所包含的某一類別(class)的比例, 要比分割前更高, 否則此分割動作根本不需要。 
一個簡單的方法來定義分類預測的purity是最大化正確性(accuracy), 也就是極小化分類的錯誤率(misclassification error)。然而, 將正確性(accuracy)做為purity的評測標準, 稍微有點產生誤導的傾向, 因為降低分類的錯誤率(misclassification error)並不等同於能達到purity的目標, 也就是將單一的類別(class)的sample分割放置於同一個節點(node)中。


Gini Index將分類目標從正確性(accuracy)轉移至purity。針對two-class分類問題, 每一個節點(node)的Gini Index定義如下: 


p1 (1 − p1) + p2 (1 − p2)                       Eq. 1.1

其中p1和p2分別為節點(node)中Class 1與Class 2的比例(probability)。由於只有兩種類別,因此p1+p2=1, Eq. 1.1.可以簡化成為2p1p2.

以極端的數值來分析, 我們可以看出Gini Index如何達到purity的目標。若Gini Index為0, 表示p1或p2其中必定有一個為0, 因此該節點(node)只會包含一個類別(class)的sample; 此時purity最佳. 而purity最差的情況為p1=p2=0.5(Gini Index=0.5), 表示該節點(node)包含數量一樣的Class 1與Class 2;由於Decision Tree Model應用多數決(Majority Vote)方式決定預測結果, 當預測sample分類至Gini Index=0.5這樣的節點時, 模型就無法做出預測判斷。 結論: 以Gini Index做為切分(split)的評測標準時, CART模型的目標是尋求極小化每一個節點(node)的Gini Index. 


Decision Tree Model在進行切分(split)評估時, 是以當下節點(node)的最佳化進行分析; 當切分(split)完成產生新節點(node)後, 就不會再”回頭”更改之前產生的節點(node)決策。以文章開頭Titanic sample為例, Decision Tree Model先以Sex變數做為第一個節點(node)進行切分(split), 而後再用Pclass變數切分(split); 也許Sex變數再後面進行切分(split)能產生較好,更pure的模型結果? 我們不容易在數個變數組合的情況下去分辨出來, 但是Decision Tree Model在產生節點(node)之後就不會再更改或是刪除之前生出之節點(node)。Decision Tree Model應用此項概念, 稱之為Greedy algorithm, 建立樹狀模型, 因此無法保證建置出最佳化的模型(optimal solution)。簡單以下列例子說明Greedy algorithm運作方法:


假設有一組數字分別為{1, 15, 25}, 目標是從用此3個數字組建出一個總和為30的組合 
Greedy: 25 + 1 + 1 + 1 + 1 + 1 = 30, with 6 items
Optimal: 15 + 15 = 30, with 2 items 

Tree-based models是一個被廣泛應用的建模(modeling)技術, 它擁有下列幾項優勢:
  1. 此模型容易建置(implement), 且非常易於理解模型變數的邏輯架構(highly interpretable)
  2. 由於此模型建構的邏輯特性, Tree-based models能相當有效率地處理各種型態的變數/predictors (sparse, skewed, continuous, categorical, etc.), 無需預先進行變數的清理或轉換(pre-process), 或是如regression model, 需特別specify變數/predictors與response之間的關聯。 
  3. 此模型可以有效率地處理missing data(NA 數值), 且自動進行變數篩選(feature selection), 這在許多實際(real-life)建模的問題處理中, 是一個很實用且重要的功能特性。

決策樹模型 Part I 先在此做一個結束; 下一個Part會運用此演算法對Titanic 資料集進行分類預測。我們將使用的是R的rpart這個package進行model building.

by J.D.




6/26/2016 | 標籤： , , |