REGRESSION AND CLASSIFICATION TREES 迴歸與分類樹

簡介 傳統的複迴歸分析，假設誤差項服從常態分配，所 以複迴歸分析是一種有母數 (parametric) 方法。 本章將介紹一種常用的無母數 (non-parametric) 的 迴歸方法，此法稱為決策樹 (decision tree) ，此方 法由於需要很強的電腦的密集計算，因此在近年來 才隨著電腦科技的進步而逐漸被廣泛地使用。

例題 π 1 : heart-attack prone 有心臟病傾向 π 2 : not heart-attack prone 沒有心臟病傾向 R 1 : over 45, overweight, no regular exercise

區別分析與決策樹

當一筆資料有多種非常不同的方法使其成為目標類 別的一部份時，使用單一線條來找出類別間界線的 統計方法效力會很弱。 例如，在信用卡產業，很多種持卡人都讓發卡銀行 有利可圖。某些持卡人每次繳款的金額不高，但他 們欠繳金額很高時，卻又不會超過額度 ; 還有一種 持卡人每月都繳清帳款，但他們交易金額很高，因 此發卡銀行還是可以賺到錢。這兩種非常不同的持 卡人可能為發卡銀行帶來同樣多的收益。 在下圖中，我們將顯示在這種分類問題上，決策樹 超越純粹統計方法的優點。 5

區別分析與決策樹 6

例題 小王是一家著名高爾夫俱樂部的經理。但是他被雇員數量 問題搞得心情十分不好。某些天好像所有人都來玩高爾夫， 以至於所有員工都忙的團團轉還是應付不過來，而有些天 不知道什麼原因卻一個人也不來，俱樂部為雇員數量浪費 了不少資金。 小王的目的是通過下周天氣預報尋找什麼時候人們會打高 爾夫，以適時調整雇員數量。因此首先他必須了解人們決 定是否打球的原因。在 2 周 (14 天 ) 時間內我們得到以下記錄： 天氣狀況有晴，雲和雨；氣溫用華氏溫度表示；相對濕度 用百分比；還有有無風。當然還有顧客是不是在這些日子 光顧俱樂部。最終他得到了 14 行 5 列的數據表格。 tw/%E5%86%B3%E7%AD%96%E6%A0% 91

例題 tw/%E5%86%B3%E7%AD%96%E6%A0% 91

例題 tw/%E5%86%B3%E7%AD%96%E6%A0%91 決策樹模型就被建起來用於解決問題。

例題 決策樹是一個有向無環圖。根結點代表所有數據。分類樹算法可 以通過變數 outlook ，找出最好地解釋非獨立變數 play （打高爾 夫的人）的方法。變數 outlook 的範疇被劃分為以下三個組： 晴天，多雲天和雨天。 我們得出第一個結論：如果天氣是多雲，人們總是選擇玩高爾夫， 而只有少數很著迷的甚至在雨天也會玩。 接下來我們把晴天組的分為兩部分，我們發現顧客不喜歡濕度高 於 70% 的天氣。最終我們還發現，如果雨天還有風的話，就不會 有人打了。 這就通過分類樹給出了一個解決方案。小王（老闆）在晴天，潮 濕的天氣或者颳風的雨天解僱了大部分員工，因為這種天氣不會 有人打高爾夫。而其他的天氣會有很多人打高爾夫，因此可以雇 用一些臨時員工來工作。 tw/%E5%86%B3%E7%AD%96%E6%A0%91

例題 『二十個問題』（ Twenty Questions ）這個遊戲， 一定可以輕易了解決策樹將資料分類的方式。在遊 戲中，一個玩家先想好所有參加者都有知道的一個 特定地點，人物或事物，其他玩家藉著提出一堆 『是或不是』的問題，來找出答案。一個決策樹代 表一系列這類問題。 在遊戲中，第一個問題的答案決定了下一個問題。 如果謹慎選擇問題，只要短短幾次詢問就可以將後 來的資料正確分類。

例題 用來將樂器分類的二分式決策樹

決策樹的應用 決策樹模式建立 (Tree-based modeling) 是一種探 究資料結構的方法，此法逐漸增加地應用在： 摘要大型多變量資料庫中的資訊 篩選變數 評價線性模式的適當性 發明可快速及重覆計算使用的預測法則

決策樹的建立 剛開始，所有物體 (Objects) 都是一組，然後根據 最有區別能力的變數 (Variable) 將物體分為 (Split) 兩組，變數的值高的屬於一組，變數的值低的屬於 另一組。 這兩組再分別根據分組後最有區別能力的變數再各 自分為兩組，如此一直分下去，直到到達適當的停 止點 (stopping point) 才停止。

決策樹的種類 通常在迴歸及分類問題中，都只有一個反應變數 (response variable) 或目標變數 (target variable) y ，而有許多的解釋變數 (explanatory variables) x 1, x 2,…, x k 。這些解釋變數可以是類別變數 (categorical variables) ，也可以是預測變數 (predictor variables) ，換句話說解釋變數可以是 定性變數 (qualitative variables) ，也可以是定量 變數 (quantitative variables) 。 同理 y 也可以是定性或定量變數。

決策樹的種類 當 y 是定性變數時，所建立的決策樹就稱為分類樹 (classification tree) ； 當 y 是定量變數時，所建立的決策樹則稱為迴歸樹 (regression tree) 。

決策樹的 當 y 是定性變數時，所建立的決策樹就稱為分類樹 (classification tree) ； 當 y 是定量變數時，所建立的決策樹則稱為迴歸樹 (regression tree) 。

分類與迴歸樹（ CART ） 分類與迴歸樹（ Classification And Regression Tree ， CART ） CART 演算法是建構決策樹時最常 用的演算法之一。 自從 1984 年布里曼（ L. Brieman ）與其同僚發表 這種方法以來，就一直機械學習實驗的要素。

分類與迴歸樹（ CART ） CART 以反覆運算的方式，由根部開始反覆建立二 元分支樹，直到樹節點中的同質性達到某個標準， 或觸發反覆運算終止條件為止。 CART 的反應變數可以是數值型資料，也可以是類 別型資料。 R 提供 tree 和 rpart 建構 CART 決策樹 tree(Y ~ X1+X2+X3+…+Xk,data=…) rpart(Y ~X1+X2+X3+…+Xk,data=…)

C4.5 C4.5 是最新出現的決策樹演算法的速成法，是澳 州研究者昆蘭（ J. Ross Quinlan ）多年努力成果。 與 CART 差異： C4.5 與 CART 之間的主要差異是 CART 在每一個節 點都呈現二分法，因此產生二分式決策樹，而 C4.5 則在每一個節點產不同數目的分支。這是因 為 C4.5 對連續性變項的處理方式和 CART 相當類似， 但對類別變項的處理就相當不同。

C4.5 Tree

CHAID CHAID （ Chi-squared Automatic Interaction Detection ），因為此法是用我們熟悉的卡方檢定 統計量（ Chi-squared Statistics ）來找出最佳的 分離（ split ）。

CHAID 剛開始時，所有的觀察值都在根節點，首先考慮所 有的自變數，用卡方檢定找出對因變數影響最大的 自變數（也就是 Chi-squared 值最大， p-value 最 小的變數），然後開始分成兩組。 接著在每個節點再重覆上面根節點的分離方法繼續 向下一直分，樹就一直成長，直到子節點的觀察值 剩下太少（ SPSS 設定值為 50 ）或是卡方檢定不顯 著為止。

CHAID Tree

R 軟體中的決策樹函數 CART: tree package, rpart package C4.5: RWeka package CHAID: CHAID package(chaid function)

決策樹 function 通用語法 result= 函數名稱 (Y~X1+X2+…+Xk, 其他選項 ) # Y 若為類別變數, 需設為 factor 型態 pred<-predict(result, new_X_data, type=“class”) # 混淆矩陣 (confusion matrix) ctable<-table(Y 真實值, pred) # 預測正確率 sum(diag(ctable))/sum(ctable)

決策樹模式簡介 我們用下面的例子來介紹決策樹： 在這個例子中，我們的反應變數 y 是汽車的哩程數 (Mileage) ，預測變數 x 是汽車的重量 (Weight) ，我 們用迴歸樹 (regression tree) 來表示汽車的哩程數 與汽車重量的關係。一旦用資料將決策樹模式建立 好如下之後，所有人很容易可以根據此模式來預測。

例題 - 哩程數

術語 在描述決策樹模式時，下面的術語常會用到： 節點 (node) --- 分支發生處 根節點 (root) --- 樹的最頂端的節點 葉節點 (leaf) --- 樹的終端的節點 分離 (split) --- 建立新的分枝的法則 ( 例如上圖中的 Weight<2567.5, Weight<2280 等 )

迴歸樹的生長 (Growing)

R 除了印出樹狀圖以外，也提供如下的決策樹模型 的摘要及節點編號及在各節點的詳細資訊如： 分離 (split) 、樣本大小 (n) 、預測誤差平方和 (deviance) 及預測值 (yval) 。 另外在葉節點部分有 ” ＊ ” 標示。

*** Tree Model *** Regression tree: tree(formula = Mileage ~ Weight, data = car.test.frame, na.action = na.exclude, mincut = 5, minsize = 10, mindev = 0.01) Number of terminal nodes: 9 Residual mean deviance: = / 51 Distribution of residuals: Min. 1st Qu. Median Mean 3rd Qu. Max node), split, n, deviance, yval * denotes terminal node 1) root ) Weight< ) Weight< * 5) Weight> * 3) Weight> ) Weight< ) Weight< * 13) Weight> ) Weight< * 27) Weight> * 7) Weight> ) Weight< ) Weight< ) Weight< * 57) Weight> * 29) Weight> * 15) Weight> *

例題 - 割草機 上面的例子是迴歸樹，接下來再看一個分類樹的例 子，在這個例子中反應變數 y 為是否擁有割草機 (y=1 代表有割草機， y=2 代表沒有割草機 ) ，而預測 變數有兩個， x 1 代表家庭收入 (income) ， x 2 代表草 地大小 (lot size) ，我們用分類樹 (classification tree) 來表示家庭收入與草地大小與擁有割草機的 機率的關係。一旦用資料將決策樹模式建立好後， 可以根據家庭收入與草地大小來預測此家庭是否擁 有割草機。

例題 - 割草機

*** Tree Model *** Classification tree: tree(formula = mower ~ income + size, data = mower, na.action = na.exclude, mincut = 5, minsize = 10, mindev = 0.01) mincut The minimum number of observations to include in either child node. This is a weighted quantity; the observational weights are used to compute the ‘number’. The default is 5. minsize The smallest allowed node size: a weighted quantity. The default is 10. mindev The within-node deviance must be at least this times that of the root node for the node to be split. Number of terminal nodes: 4 Residual mean deviance: = 14.4 / 20 Misclassification error rate: = 3 / 24 node), split, n, deviance, yval, (yprob) * denotes terminal node 1) root owner ( ) 2) income< nonowner ( ) 4) size< nonowner ( ) 8) income< nonowner ( ) * 9) income> nonowner ( ) * 5) size> owner ( ) * 3) income> owner ( ) *

分類樹的生長 (Growing) 剛開始所有的觀察值都在根節點，首先由草地大小 及家庭收入選出一個對 y 影響最大的變數，此變數 為家庭收入，然後考慮所有家庭收入可能的 ” 分離 ” ， 然後選出最佳的分離是 income<84.75 ，因為這個 分離使得兩組的錯誤分類的機率最小。另外亦將計 算 deviance ，也就是在此節點的預測誤差平方和。 接著在每個節點再選出影響最大的變數再重覆上面 的分離方法繼續向下分，直到節點的 deviance 除 以根節點的 deviance 的比例夠小 (R 設定值為 ≤.) 或是節點的觀察值剩下太少 (R 設定值為 ≤) 。

迴歸樹的樹狀圖在葉節點處會印出反應變數 y 的預 測值，但分類樹的樹狀圖在葉節點則只印出所屬類 別。 另外在決策樹模型的摘要部分，分類樹除了 Residual mean deviance 外，還會印出錯誤分類 率 (Misclassification error rate) ，在割草機的例 子中，樹狀圖的錯誤分類率為 。

至於在各節點的資訊部分，分類樹會印出節點編號 (node) 、分離 (split) 、樣本大小 (n) 、預測誤差平方 和 (deviance) 、預測類別 (yval) 及估計各類別的機 率 (yprob) 。

在割草機例子中 yprob 會列出 ( 估計有割草機機率 估計沒有割草機機率 ) ，例如在葉節點 5 時， yprob ， 表示當家庭收入 19.8 時，估計 有割草機的機率為 0.75 ，沒有割草機的機率為 0.25 ， 因為有割草機的機率大於沒有割草機的機率，所以 我們預測此家庭是有割草機的。

決策樹的修剪 (Pruning) 由於在決策樹的生長過程中，並沒有限制樹的大小， 因此一棵決策樹可能比描述資料所需的樹要更複雜， 決策樹過於複雜會使得決策樹的解釋更加困難，所 以有必要使用修剪樹的功能以減少樹狀圖中的節點， 也就是將最不重要的分枝剪掉。

決策樹的修剪 (Pruning) 接下來的問題是如何測量分枝樹 (subtree) 的重要 性，下面我們定義一個成本複雜性量數 (cost- complexity measure) ：

決策樹的修剪 (Pruning)

建構 CART 決策樹 R 提供 tree 和 rpart 建構 CART 決策樹 tree(Y ~ X1+X2+X3+…+Xk,data=…) rpart(Y ~X1+X2+X3+…+Xk,data=…)

CART Modeling via rpart 1. Grow the Tree rpart(formula, data=, method=,control=)

CART Modeling via rpart 2. Examine the results

CART Modeling via rpart 3. prune tree-to avoid overfitting the data. Typically, you will want to select a tree size that minimizes the cross-validated error, the xerror column printed by printcp( ). Prune the tree to the desired size using prune(fit, cp= ) Specifically, use printcp( ) to examine the cross-validated error results, select the complexity parameter associated with minimum error, and place it into the prune( ) function.

CART Modeling via rpart 3. prune tree-to avoid overfitting the data. Alternatively, you can use the code fragment fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"] to automatically select the complexity parameter associated with the smallest cross- validated error

付出最多的人，也是收穫最 多的人 ~ 共勉之 ~