决策树及SSS实现

第九章決策樹分析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.5C4.5是是最新出現現的決策樹樹演算法的的速成法，，是澳州研研究者昆蘭蘭（J.RossQuinlan）多年努努力成果。。與CART差異：培養決策樹樹：C4.5與與CART之間的第第一個差異異是CART在每一一個節點都都呈現二分分法，因此此產生二分分式決策樹樹，而C4.5則在在每一個節節點產不同同數目的分分支。這是是因為C4.5對持持續性變項項的處理方方式和CART相當當類似，但但對類別變變項的處理理就相當不不同。39C4.5修剪決策樹樹：CART使使用決策樹樹的分散度度為度量，，來標記不不同的分支支樹，然後後以沒有見見過的預先先分類好的的資料（測測試組）來來測試這些些分支樹。。相反的，，C4.5並不參考考其他資料料，嘗試以以只用訓練練資料的情情況下來修修剪決策樹樹。因此，，C4.5使用建構構決策樹的的相同資料料來決定該該如何加以以修剪。40C4.5從決策樹到到規則：我們可以在在不改變分分類行為的的前提下藉藉著合併到到葉部的路路徑來向這這個目標走走出第一步步。下圖的的決策樹部部分得出以以下的規則則：看球賽加上上地主隊獲獲勝加上跟跟朋友出門門，就會得得出啤酒。看球賽加上上地主隊獲獲勝加上待待在家裡，，就會得出出健怡汽水。看球賽加上上地主隊輸輸球加上跟跟朋友出門門，就會得得出啤酒。看球賽加上上地主隊輸輸球加上待待在家裡，，就會得出出牛奶。41C4.542CHAIDCHAID是是哈根（J.A.Hartigan）在1975年率先先提出的演算算法，這是本本章所討論的的最古老的演演算法。這也也是最受到廣廣泛使用的演演算法，因為為它隨著SPSS和SAS等受歡迎迎的統計軟體體流通。CHAID是從從更早的一套套自動互動偵偵測系統AID衍生而來來，後者是摩摩根（J.A.Morgan）與與桑奎斯特(J.N.Sonquist)在在1963年年提出。43CHAIDCHAID與與C4.5及及CART的的差異：CHAID和和C4.5及及CART兩兩種演算法的的最大差異在在於，後兩者者先過度套用用資料，再加加以修剪，而而CHAID嘗試在過度度套用的情況況發生之前就就讓決策樹停停止蔓生擴大大。另一個差異是是CHAID只限於類別別變數使用，，連續變數必必須被區隔成成幾個區段範範圍，或是以以高，中，低低等類別來取取代。44CHAID培養決策樹：：如同其他兩種種方法，CHAID演算算利用輸入變變數找出一個個方法，將訓訓練組資料分分隔成兩個或或兩個以上子子節點。這些些子節點被選選擇的方式是是輸出變數遇遇上某個特定定數值的機率率隨著節點不不同而有所差差異。45CHAID選擇分隔變數數：經過第一步驟驟之後，我們們得出以下的的表：46CHAID杏仁燒魚，鮪鮪魚沙拉，生生魚片魚肉鵝肝醬，水牛牛城雞翅，碎碎雞肝禽肉牛腰肉，麥香香堡，罐頭牛牛肉，碎羊肉肉紅肉47CHAID重新分隔類別別：第一步無法在在輸出數上產產生顯著統計計差異的所有有預測變都被被合併。第二二步，三個或或更多的預測測變數群組以以二分法被重重新分隔。如如果這些分隔隔之中任何一一個可以產生生統計上顯著著差異的結果果，就就被保保留。卡方分析(chi-squared)這是對對應於CHAID的前兩兩個字母縮寫寫。48CHAID評鑑入選分隔隔變數：一旦每一個分分隔變數都被被分類，在輸輸出變數上產產生最大的類類別差異，就就對這項結果果使用卡方分分析檢驗。根根據檢驗，能能夠產生最大大差異分類的的預測變數，，就被選為當當前這個節點點的分隔變數數。49CHAID限制決策樹的的成長：在CHAID演算法中，，決策樹持續續成長，直到到再也沒有任任何區隔能在在分類上達到到統計顯著性性差異為止。。50其他決策樹的的變化一次使用超過過一個變數：：至今我們討論論的三個演算算法都是用在在測試單一變變項來形成每每一個分隔。。這個方法可可能會有一些些問題。其中中之一會造成成決策樹擁有有超過我們所所需的節點。。額外的節點點會造成不便便，因為只有有到達某一個個節點的訓練練組資料有能能夠引發下一一層的分支樹樹。每一個節節點的案例越越少，得出的的分類可靠性性就越低。為為了簡化說明明，我們假設設只有三個人人投票。51其他決策樹的的變化52其他決策樹的的變化我們將這個情情形當成訓練練資料，CART或其他他任何可以根根據單一屬性性的數值來分分隔建構二分分法決策樹的的演算法，都都會建構出下下圖的決策樹樹。這個決策策樹完美的將將訓練組資料料分組，但需需要五個內部部分隔節點。。若以邏輯和函函數來合併特特性形成結合合，我們就可可以獲得如下下圖那樣更簡簡化的決策樹樹。這個決策策樹顯示使用用變數結合能能獲得的另一一個潛在優點點。這個決策策樹如今更能能夠表現分類類上顯示的無無異議的觀念念：『當所有有投票人意見見一致，這項項決策就是無無異議。』53其他決策樹的的變化54其他決策樹的的變化55其他決策樹的的變化以機械學習研研究者的行話話來說，一個個看一眼就能能夠了解的決決策樹，具有有方便理解的的性質。機械械學習領域的的一些研究者者，非常強調調這個觀念，，但似乎只有有在這些學者者以一些小型型的，組織完完整的資料在在建構他們的的研究時，才才能獲得這樣樣完美的結果果。56讓超平面傾斜斜：傳統的決策樹樹檢驗一個節節點的單一變變數值，只能能形成方形區區域。在一個個二維空間，，YN這種測試形形式，形成一一個由與Y軸軸垂直且與X軸平行的直直線所界定的的區域。藉由由選擇不同的的Ｎ值，我們們可以讓這條條直線上下移移動，但無法法改變其斜率率。同樣的，，在一個多維維的空