决策树分析及SPSS实现

第九章決策樹分析DecisionTreeAnalysis1決策樹分析簡介決策樹基本觀念三種研究方法其他決策樹的變化決策樹的優、缺點2決策樹是功能強大且相當受歡迎的分類和預測工具。這項以樹狀圖為基礎的方法，其吸引人之處在於決策樹具有規則，和類神經網路不同。規則可以用文字來表達，讓人類了解，或是轉化為SQL之類的資料庫語言，讓落在特定類別的資料紀錄可以被搜尋。在本章中，我們先介紹決策樹運作的方式及其如何應用在分類和預測問題。隨後我們進一步介紹如何以CART、C4.5和CHAID演算法建構決策樹。

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

決策樹基本觀念5一筆資料從根部的節點進入決策樹。在根部，應用一項測驗來決定這筆資料該進入下一層的哪一個子節點（childnode）。選擇一開始的測驗有不同的演算法，但目的都是一樣的：這個過程一再重複，直到資料到達葉部節點（leafnode）。從根部到每一個葉部都有一套獨特的路徑，這個路徑就是用來分類資料規則的一種表達方式。決策樹基本觀念6決策樹的多種形式:

決策樹基本觀念7某些規則比其他規則好:我們將一個決策樹應用在一個前所未有的資料集合上，並觀察其分類正確的比率，來衡量這個決策樹的有效程度。

對決策樹的每一個節點，我們可以如此衡量：●進入這個節點的資料數目。●如果是一個葉部節點，可觀察資料分類的方式。●這個節點將資料正確分類的比率。決策樹基本觀念8

藉由將資料分到正確類別的情況，我們可以驗證出建構決策樹的最佳演算法。第四章中的電影迷資料庫。受測者被要求回答他們的年齡，性別，最常看的電影，以及最近看過的電影片名。然後我們使用決策樹程式來創造規則，以受測者在問卷中其他問題的答案來找出該名受測者的性別。

下表顯示這個節點共有11筆資料被歸類其下，其中九個是正確的（女性），還有兩個男性被誤分到這裡。換言之，這項規則的錯誤率為0.182決策樹基本觀念9決策樹基本觀念10決策樹基本觀念yearplacemovielastlikesexpred.594231FF432112FF432130FF4512563MF451252FF4512526FF461262FF45232111FF493163MF4512563FF4523217FF11決策樹基本觀念決策樹創造資料箱:雖然樹狀圖和『二十個問題』類推法有助於呈現決策樹方法的某些特質，但作者發現，在某些情況下，基於不同表現方式的箱形圖（boxdiagram）更加清楚明白。一個決策樹創造一系列盒子或箱子，我們可以將資料丟進去。任何樹狀圖的葉部節點形成一個一維式箱形圖。和決策樹根部節點有關的測試將下層分成兩個或更多部分。12決策樹基本觀念13決策樹基本觀念決策樹的根部擴大成資料箱：●資料箱的寬度可以有變化，以顯示一筆資料落在特定箱中的相對可能性。●這個圖形可以換成一個直條圖（histogram），每一個直條的高度顯示落在對應箱中的資料數目。這類直條圖可以使用直條的頻色或形狀來顯示對應規則的錯誤率。●單一資料可以根據輸出變數的數值，用有色的球形或點狀來代表。這樣可以立即顯示這套分類系統的表現。14決策樹基本觀念15決策樹基本觀念表現多維度:當我們將資料丟進格子中，它們落到特定的層內並以此分類。一個層形圖讓我們一目了然的見到數層資料的細節。在下圖，我們可以一眼看出左下的格子清一色都是男性。仔細的看，我們可以發現某些層在分類上表現很好，或是聚集了大量資料。這和線性，邏輯性或二次差分等傳統的統計分類方法試圖在資料空間中劃上一條直線或弧線將資料分層的方式大不相同。16決策樹基本觀念17決策樹基本觀念

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

18決策樹基本觀念19分類與迴歸樹（CART）

分類與迴歸樹（ClassificationAndRegressionTree，CART）CART演算法是建構決策樹時最常用的演算法之一。自從１９８４年布里曼（L.Brieman）與其同僚發表這種方法以來，就一直機械學習實驗的要素。20分類與迴歸樹（CART）21分類與迴歸樹（CART）numbers22分類與迴歸樹（CART）找出起始的分隔:在過程中的一開始，我們有一個預先分類好的訓練和資料。預先分類意味輸出變數，或稱依變數，具備一個己知的類別。CART藉著一個單一輸入變數函數，在每一個節點分隔資料，以建構一個二分式決策樹。因此，第一的任務是決定哪一個自變數可以成最好的分隔變數。最好分隔的定義是能夠將資料最完善的分配到一個單一類別支配的群體。23分類與迴歸樹（CART）找出起始的分隔:用來評估一個分隔數的衡量標準是分散度（diversity）。對於一組資料的『分散度指標』（indexofdiversity）有多種計算方式。不論哪一種，分散度指標很高，表示這個組合中包含平均分配到多個類別，而分散度指標很低則表示一個單一類別的成員居優勢。24分類與迴歸樹（CART）找出起始的分隔:最好的分隔變數是能夠降低一個資料組的分散度，而且降得最多。換言之，我們希望以下這個式子最大化：

分散度（分隔前）－﹝分散度（分隔後左邊子集合）＋分散度（分隔後右邊子集合）﹞

三分種分散度衡量法：

min{P(c1),P(c2)}

2P(c1)P(c2)

〔P(c1)logP(c1)〕+〔P(c2)logP(c2)〕

25分類與迴歸樹（CART）當各類別出現的機率相等時，以上的三個函數會出現最大值，當資料組中只包含單一類別時，函數值則為零。在完全分散和完全聚集的兩個極端之間，這些函數有些微不同的型態。為了在一個節點中選擇最佳分隔變數，我們依次考量每一個自變數。假設這個變數遇上多個數值，我們進行二分式研究，希望找出降低分散度最多的最佳分隔法。我們從每個變數中找出最能降低分散度的最佳分隔變數，勝利者就被選為根節點的分隔變數。

26分類與迴歸樹（CART）培養出整棵樹:一開始的分隔製造出兩個節點，現在我們再以分隔根節點的方法將每個節點予以分隔。再一次，我們檢視所有輸入變數，找出雀屏中選的分隔變數。如果這個變數只遇上一個數值，我們就將其排除，因為它無法被用來創造一個分隔。一個類別變數若被用來作為決策樹中較高層的分隔變數時，比較有可能很快的變成單一數值化。對每一個剩下的變數最好的分隔就確定了。當我們無法找到任何分隔可以顯著降低一個節點的分散度，我們就將其標示為葉部節點。到了最後，存在的只剩下葉部節點，而我們也完成決策樹。27分類與迴歸樹（CART）計算每個節點的錯誤率：

每一個葉部如今都分配到一個類別以及一個錯誤率。回顧前圖，圖中選取了從根部到標示為『女性』的葉部路徑。該節點是一個葉部節點，表示找不到任何分隔變數可以顯著的降低其分散性。然而，這並不表示所有祗達這個葉部的資料都屬於同一類。使用簡單機率的定義，我們可以看到11個葉部中有9個是正確分類。這告訴我們，以這個訓練組而言，抵達這個節點的資料是女性的機率為0.818。相對的，這個葉部的錯誤率1-0.818就是0.812。28分類與迴歸樹（CART）計算整個決策樹的錯誤率：整個決策樹的錯誤率是所有葉部錯誤率的加權總數。每一個葉部的錯誤率乘上資料抵達葉部的機率(分配到資料的比例)，加起來的總數就是整個決策樹的錯誤率。

29分類與迴歸樹（CART）修剪決策樹:

只要能發現新的分隔，改善決策樹將訓練組資料分類的能力，決策樹就會繼續成長。如果我們試圖預測身高，而我們來到一個節點，包含一個名叫馬丁的高個子，和幾個比較矮的人，我們可以訂出一個新規則『名叫馬丁的人是高個子』，來降低分散度。這個規則有助於將訓練資料分類，但如果在更寬廣的世界上，馬丁是一個很少見的名，而且這個名字和身高又沒有特別的關連，那麼這個規則比沒用還糟糕。30分類與迴歸樹（CART）修剪決策樹:

下圖顯示出會發的狀況。圖中的箱子變得很小，而且每一個都不大，只容得下訓組資料，不太可能再容納新資料。很顯的。我們需要修剪這個決策樹以便在一般性的案例中獲得更正確的預測。問題是要決定該倒推回去修剪多少，以及這些分支的決策樹中哪些表現很好。

31分類與迴歸樹（CART）32分類與迴歸樹（CART）確認入選的分支決策樹：

我們的目標是首先將提供最少額外預測能力的分支先修剪掉。為了確認這些最沒用的分支，我們引入一個決策樹的『調節錯誤率』（adjusterrorrate）的觀念。這是一種衡量方法，逐一檢視每一個葉部，確認最弱勢的分支（那些無法有效降低整棵決策樹錯誤率的分支），然後將它們標示出來加以修剪33分類與迴歸樹（CART）34分類與迴歸樹（CART）35分類與迴歸樹（CART）評估分支樹：

最後工作是從入選的分支樹中選出最能分類新資料的決策樹。為達到此目的，我們使用第二個預先分好的資料組，即『測試組資料』（testset）。測試組和訓練組來自同一群母體，但包含的資料不同。入選分支樹中每一個都被用來分類測試組資，得出最低的整體錯誤率的就是勝利者。

36分類與迴歸樹（CART）評估最佳的分支樹：

最後工作是從利用第三組資料，將測試組和訓練組打散，即『評估組資料』（evaluationset）。入選分支樹應用在評估組所得出的錯誤率，來預期這個分支樹在未經分類的資料上使用時的錯誤率。

37分類與迴歸樹（CART）將代價列入考量

:我們討論至此，只使用錯誤率作為評估一個分支樹良莠的依據。然而，在許多應用上，錯誤分類的代價依資料類別不同而有異。當然在醫療診斷上，一個錯誤的陰性診斷（negative）也許會比錯誤的陽性診斷（positive）傷害更大。在進行癌症抹片檢查時，誤診為性也許只會帶來更多的檢查，但誤診為陰性卻可能讓病情惡化。我們可以把問題列入考量，以一個使用加權方式將錯誤分類的機率加倍的代價函數，來取代錯誤率。38C4.5

C4.5是最新出現的決策樹演算法的速成法，是澳州研究者昆蘭（J.RossQuinlan）多年努力成果。與CART差異：培養決策樹：C4.5與CART之間的第一個差異是CART在每一個節點都呈現二分法，因此產生二分式決策樹，而C4.5則在每一個節點產不同數目的分支。這是因為C4.5對持續性變項的處理方式和CART相當類似，但對類別變項的處理就相當不同。39C4.5修剪決策樹：CART使用決策樹的分散度為度量，來標記不同的分支樹，然後以沒有見過的預先分類好的資料（測試組）來