決策樹分析及SPSS實(shí)現(xiàn)

第九章決策樹分析DecisionTreeAnalysis1精選ppt決策樹分析簡(jiǎn)介決策樹基本觀念三種研究方法其他決策樹的變化決策樹的優(yōu)、缺點(diǎn)2精選ppt決策樹是功能強(qiáng)大且相當(dāng)受歡迎的分類和預(yù)測(cè)工具。這項(xiàng)以樹狀圖為基礎(chǔ)的方法，其吸引人之處在於決策樹具有規(guī)則，和類神經(jīng)網(wǎng)路不同。規(guī)則可以用文字來(lái)表達(dá)，讓人類了解，或是轉(zhuǎn)化為SQL之類的資料庫(kù)語(yǔ)言，讓落在特定類別的資料紀(jì)錄可以被搜尋。在本章中，我們先介紹決策樹運(yùn)作的方式及其如何應(yīng)用在分類和預(yù)測(cè)問題。隨後我們進(jìn)一步介紹如何以CART、C4.5和CHAID演算法建構(gòu)決策樹。

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

決策樹基本觀念5精選ppt一筆資料從根部的節(jié)點(diǎn)進(jìn)入決策樹。在根部，應(yīng)用一項(xiàng)測(cè)驗(yàn)來(lái)決定這筆資料該進(jìn)入下一層的哪一個(gè)子節(jié)點(diǎn)（childnode）。選擇一開始的測(cè)驗(yàn)有不同的演算法，但目的都是一樣的：這個(gè)過程一再重複，直到資料到達(dá)葉部節(jié)點(diǎn)（leafnode）。從根部到每一個(gè)葉部都有一套獨(dú)特的路徑，這個(gè)路徑就是用來(lái)分類資料規(guī)則的一種表達(dá)方式。決策樹基本觀念6精選ppt決策樹的多種形式:

決策樹基本觀念7精選ppt某些規(guī)則比其他規(guī)則好:我們將一個(gè)決策樹應(yīng)用在一個(gè)前所未有的資料集合上，並觀察其分類正確的比率，來(lái)衡量這個(gè)決策樹的有效程度。

對(duì)決策樹的每一個(gè)節(jié)點(diǎn)，我們可以如此衡量：●進(jìn)入這個(gè)節(jié)點(diǎn)的資料數(shù)目?！袢绻且粋€(gè)葉部節(jié)點(diǎn)，可觀察資料分類的方式。●這個(gè)節(jié)點(diǎn)將資料正確分類的比率。決策樹基本觀念8精選ppt

藉由將資料分到正確類別的情況，我們可以驗(yàn)證出建構(gòu)決策樹的最佳演算法。第四章中的電影迷資料庫(kù)。受測(cè)者被要求回答他們的年齡，性別，最?？吹碾娪?，以及最近看過的電影片名。然後我們使用決策樹程式來(lái)創(chuàng)造規(guī)則，以受測(cè)者在問卷中其他問題的答案來(lái)找出該名受測(cè)者的性別。

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

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

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

分類與迴歸樹（ClassificationAndRegressionTree，CART）CART演算法是建構(gòu)決策樹時(shí)最常用的演算法之一。自從１９８４年布里曼（L.Brieman）與其同僚發(fā)表這種方法以來(lái)，就一直機(jī)械學(xué)習(xí)實(shí)驗(yàn)的要素。20精選ppt分類與迴歸樹（CART）21精選ppt分類與迴歸樹（CART）numbers22精選ppt分類與迴歸樹（CART）找出起始的分隔:在過程中的一開始，我們有一個(gè)預(yù)先分類好的訓(xùn)練和資料。預(yù)先分類意味輸出變數(shù)，或稱依變數(shù)，具備一個(gè)己知的類別。CART藉著一個(gè)單一輸入變數(shù)函數(shù)，在每一個(gè)節(jié)點(diǎn)分隔資料，以建構(gòu)一個(gè)二分式?jīng)Q策樹。因此，第一的任務(wù)是決定哪一個(gè)自變數(shù)可以成最好的分隔變數(shù)。最好分隔的定義是能夠?qū)①Y料最完善的分配到一個(gè)單一類別支配的群體。23精選ppt分類與迴歸樹（CART）找出起始的分隔:用來(lái)評(píng)估一個(gè)分隔數(shù)的衡量標(biāo)準(zhǔn)是分散度（diversity）。對(duì)於一組資料的『分散度指標(biāo)』（indexofdiversity）有多種計(jì)算方式。不論哪一種，分散度指標(biāo)很高，表示這個(gè)組合中包含平均分配到多個(gè)類別，而分散度指標(biāo)很低則表示一個(gè)單一類別的成員居優(yōu)勢(shì)。24精選ppt分類與迴歸樹（CART）找出起始的分隔:最好的分隔變數(shù)是能夠降低一個(gè)資料組的分散度，而且降得最多。換言之，我們希望以下這個(gè)式子最大化：

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

三分種分散度衡量法：

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

2P(c1)P(c2)

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

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

26精選ppt分類與迴歸樹（CART）培養(yǎng)出整棵樹:一開始的分隔製造出兩個(gè)節(jié)點(diǎn)，現(xiàn)在我們?cè)僖苑指舾?jié)點(diǎn)的方法將每個(gè)節(jié)點(diǎn)予以分隔。再一次，我們檢視所有輸入變數(shù)，找出雀屏中選的分隔變數(shù)。如果這個(gè)變數(shù)只遇上一個(gè)數(shù)值，我們就將其排除，因?yàn)樗鼰o(wú)法被用來(lái)創(chuàng)造一個(gè)分隔。一個(gè)類別變數(shù)若被用來(lái)作為決策樹中較高層的分隔變數(shù)時(shí)，比較有可能很快的變成單一數(shù)值化。對(duì)每一個(gè)剩下的變數(shù)最好的分隔就確定了。當(dāng)我們無(wú)法找到任何分隔可以顯著降低一個(gè)節(jié)點(diǎn)的分散度，我們就將其標(biāo)示為葉部節(jié)點(diǎn)。到了最後，存在的只剩下葉部節(jié)點(diǎn)，而我們也完成決策樹。27精選ppt分類與迴歸樹（CART）計(jì)算每個(gè)節(jié)點(diǎn)的錯(cuò)誤率：

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

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

只要能發(fā)現(xiàn)新的分隔，改善決策樹將訓(xùn)練組資料分類的能力，決策樹就會(huì)繼續(xù)成長(zhǎng)。如果我們?cè)噲D預(yù)測(cè)身高，而我們來(lái)到一個(gè)節(jié)點(diǎn)，包含一個(gè)名叫馬丁的高個(gè)子，和幾個(gè)比較矮的人，我們可以訂出一個(gè)新規(guī)則『名叫馬丁的人是高個(gè)子』，來(lái)降低分散度。這個(gè)規(guī)則有助於將訓(xùn)練資料分類，但如果在更寬廣的世界上，馬丁是一個(gè)很少見的名，而且這個(gè)名字和身高又沒有特別的關(guān)連，那麼這個(gè)規(guī)則比沒用還糟糕。30精選ppt分類與迴歸樹（CART）修剪決策樹:

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

31精選ppt分類與迴歸樹（CART）32精選ppt分類與迴歸樹（CART）確認(rèn)入選的分支決策樹：

我們的目標(biāo)是首先將提供最少額外預(yù)測(cè)能力的分支先修剪掉。為了確認(rèn)這些最沒用的分支，我們引入一個(gè)決策樹的『調(diào)節(jié)錯(cuò)誤率』（adjusterrorrate）的觀念。這是一種衡量方法，逐一檢視每一個(gè)葉部，確認(rèn)最弱勢(shì)的分支（那些無(wú)法有效降低整棵決策樹錯(cuò)誤率的分支），然後將它們標(biāo)示出來(lái)加以修剪33精選ppt分類與迴歸樹（CART）34精選ppt分類與迴歸樹（CART）35精選ppt分類與迴歸樹（CART）評(píng)估分支樹：

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

36精選ppt分類與迴歸樹（CART）評(píng)估最佳的分支樹：

最後工作是從利用第三組資料，將測(cè)試組和訓(xùn)練組打散，即『評(píng)估組資料』（evaluationset）。入選分支樹應(yīng)用在評(píng)估組所得出的錯(cuò)誤率，來(lái)預(yù)期這個(gè)分支樹在未經(jīng)分類的資料上使用時(shí)的錯(cuò)誤率。

37精選ppt分類與迴歸樹（CART）將代價(jià)列入考量

:我們討論至此，只使用錯(cuò)誤率作為評(píng)估一個(gè)分支樹良莠的依據(jù)。然而，在許多應(yīng)用上，錯(cuò)誤分類的代價(jià)依資料類別不同而有異。當(dāng)然在醫(yī)療診斷上，一個(gè)錯(cuò)誤的陰性診斷（negative）也許會(huì)比錯(cuò)誤的陽(yáng)性診斷（positive）傷害更大。在進(jìn)行癌癥抹片檢查時(shí)，誤診為性也許只會(huì)帶來(lái)更多的檢查，但誤診為陰性卻可能讓病情惡化。我們可以把問題列入考量，以一個(gè)使用加權(quán)方式將錯(cuò)誤分類的機(jī)率加倍的代價(jià)函數(shù)，來(lái)取代錯(cuò)誤率。38精選pptC4.5

C4.5是最新出現(xiàn)的決策樹演算法的速成法，是澳州研究者昆蘭（J.RossQuinlan）多年努力成果。與CART差異：培養(yǎng)決策樹：C4.5與CART之間的第一個(gè)差異是CART在每一個(gè)節(jié)點(diǎn)都呈現(xiàn)二分法，因此產(chǎn)生二分式?jīng)Q策樹，而C4.5則在每一個(gè)節(jié)點(diǎn)產(chǎn)不同數(shù)目的分支。這是因?yàn)镃4.5對(duì)持續(xù)性變項(xiàng)的處理方式和CART相當(dāng)類似，但對(duì)類別變項(xiàng)的處理就相當(dāng)不同。39精選pptC4.5修剪決策樹：CART使用決策樹的分散度為度量，來(lái)標(biāo)記不同的分支樹，然後以沒有見過的預(yù)先分類好的資料（測(cè)試組）來(lái)測(cè)試這些分支樹。相反的，C4.5並不參考其他資料，嘗試以只用訓(xùn)練資料的情況下來(lái)修剪決策樹。因此，C4.5使用建構(gòu)決策樹的相同資料來(lái)決定該如何加以修剪。

40精選pptC4.5從決策樹到規(guī)則：

我們可以在不改變分類行為的前提下藉著合併到葉部的路徑來(lái)向這個(gè)目標(biāo)走出第一步。下圖的決策樹部分得出以下的規(guī)則：

看球賽加上地主隊(duì)獲勝加上跟朋友出門，就會(huì)得出啤酒。看球賽加上地主隊(duì)獲勝加上待在家裡，就會(huì)得出健怡汽水。看球賽加上地主隊(duì)輸球加上跟朋友出門，就會(huì)得出啤酒。看球賽加上地主隊(duì)輸球加上待在家裡，就會(huì)得出牛奶。41精選pptC4.542精選pptCHAIDCHAID是哈根（J.A.Hartigan）在1975年率先提出的演算法，這是本章所討論的最古老的演算法。這也是最受到廣泛使用的演算法，因?yàn)樗S著SPSS和SAS等受歡迎的統(tǒng)計(jì)軟體流通。CHAID是從更早的一套自動(dòng)互動(dòng)偵測(cè)系統(tǒng)AID衍生而來(lái)，後者是摩根（J.A.Morgan）與?？固?J.N.Sonquist)在1963年提出。43精選pptCHAIDCHAID與C4.5及CART的差異：CHAID和C4.5及CART兩種演算法的最大差異在於，後兩者先過度套用資料，再加以修剪，而CHAID嘗試在過度套用的情況發(fā)生之前就讓決策樹停止蔓生擴(kuò)大。另一個(gè)差異是CHAID只限於類別變數(shù)使用，連續(xù)變數(shù)必須被區(qū)隔成幾個(gè)區(qū)段範(fàn)圍，或是以高，中，低等類別來(lái)取代。44精選pptCHAID培養(yǎng)決策樹：如同其他兩種方法，CHAID演算利用輸入變數(shù)找出一個(gè)方法，將訓(xùn)練組資料分隔成兩個(gè)或兩個(gè)以上子節(jié)點(diǎn)。這些子節(jié)點(diǎn)被選擇的方式是輸出變數(shù)遇上某個(gè)特定數(shù)值的機(jī)率隨著節(jié)點(diǎn)不同而有所差異。45精選pptCHAID選擇分隔變數(shù)：經(jīng)過第一步驟之後，我們得出以下的表：46精選pptCHAID杏仁燒魚，鮪魚沙拉，生魚片魚肉鵝肝醬，水牛城雞翅，碎雞肝禽肉牛腰肉，麥香堡，罐頭牛肉，碎羊肉紅肉

47精選pptCHAID重新分隔類別：第一步無(wú)法在輸出數(shù)上產(chǎn)生顯著統(tǒng)計(jì)差異的所有預(yù)測(cè)變都被合併。第二步，三個(gè)或更多的預(yù)測(cè)變數(shù)群組以二分法被重新分隔。如果這些分隔之中任何一個(gè)可以產(chǎn)生統(tǒng)計(jì)上顯著差異的結(jié)果，就就被保留?？ǚ椒治?chi-squared)這是對(duì)應(yīng)於CHAID的前兩個(gè)字母縮寫。

48精選pptCHAID評(píng)鑑入選分隔變數(shù)：一旦每一個(gè)分隔變數(shù)都被分類，在輸出變數(shù)上產(chǎn)生最大的類別差異，就對(duì)這項(xiàng)結(jié)果使用卡方分析檢驗(yàn)。根據(jù)檢驗(yàn)，能夠產(chǎn)生最大差異分類的預(yù)測(cè)變數(shù)，就被選為當(dāng)前這個(gè)節(jié)點(diǎn)的分隔變數(shù)。

49精選pptCHAID限制決策樹的成長(zhǎng)：在CHAID演算法中，決策樹持續(xù)成長(zhǎng)，直到再也沒有任何區(qū)隔能在分類上達(dá)到統(tǒng)計(jì)顯著性差異為止。

50精選ppt其他決策樹的變化一次使用超過一個(gè)變數(shù)：

至今我們討論的三個(gè)演算法都是用在測(cè)試單一變項(xiàng)來(lái)形成每一個(gè)分隔。這個(gè)方法可能會(huì)有一些問題。其中之一會(huì)造成決策樹擁有超過我們所需的節(jié)點(diǎn)。額外的節(jié)點(diǎn)會(huì)造成不便，因?yàn)橹挥械竭_(dá)某一個(gè)節(jié)點(diǎn)的訓(xùn)練組資料有能夠引發(fā)下一層的分支樹。每一個(gè)節(jié)點(diǎn)的案例越少，得出的分類可靠性就越低。為了簡(jiǎn)化說明，我們假設(shè)只有三個(gè)人投票。51精選ppt其他決策樹的變化52精選ppt其他決策樹的變化

我們將這個(gè)情形當(dāng)成訓(xùn)練資料，CART或其他任何可以根據(jù)單一屬性的數(shù)值來(lái)分隔建構(gòu)二分法決策樹的演算法，都會(huì)建構(gòu)出下圖的決策樹。這個(gè)決策樹完美的將訓(xùn)練組資料分組，但需要五個(gè)內(nèi)部分隔節(jié)點(diǎn)。

若以邏輯和函數(shù)來(lái)合併特性形成結(jié)合，我們就可以獲得如下圖那樣更簡(jiǎn)化的決策樹。這個(gè)決策樹顯示使用變數(shù)結(jié)合能獲得的另一個(gè)潛在優(yōu)點(diǎn)。這個(gè)決策樹如今更能夠表現(xiàn)分類上顯示的無(wú)異議的觀念：『當(dāng)所有投票人意見一致，這項(xiàng)決策就是無(wú)異議?！?3精選ppt其他決策樹的變化54精選ppt其他決策樹的變化55精選ppt其他決策樹的變化

以機(jī)械學(xué)習(xí)研究者的行話來(lái)說，一個(gè)看一眼就能夠了解的決策樹，具有方便理解的性質(zhì)。機(jī)械學(xué)習(xí)領(lǐng)域的一些研究者，非常強(qiáng)調(diào)這個(gè)觀念，但似乎只有在這些學(xué)者以一些小型的，組織完整的資料在建構(gòu)他們的研究時(shí)，才能獲得這樣完美的結(jié)果。56精選ppt讓超平面傾斜：

傳統(tǒng)的決策樹檢驗(yàn)一個(gè)節(jié)點(diǎn)的單一變數(shù)值，只能形成方形區(qū)域。在一個(gè)二維空間，YN這種測(cè)試形式，形成一個(gè)由與Y軸垂直且與X軸平