決策樹分析及實現(xiàn)演示文稿

決策樹分析及實現(xiàn)演示文稿目前一頁\總數(shù)六十頁\編于十二點(diǎn)決策樹分析及實現(xiàn)目前二頁\總數(shù)六十頁\編于十二點(diǎn)決策樹分析簡介決策樹基本觀念三種研究方法其他決策樹的變化決策樹的優(yōu)、缺點(diǎn)目前三頁\總數(shù)六十頁\編于十二點(diǎn)

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

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

以『二十個問題』的方法顯示樂器的分類。

決策樹基本觀念目前六頁\總數(shù)六十頁\編于十二點(diǎn)

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

決策樹基本觀念目前八頁\總數(shù)六十頁\編于十二點(diǎn)某些規(guī)則比其他規(guī)則好:

我們將一個決策樹應(yīng)用在一個前所未有的資料集合上，並觀察其分類正確的比率，來衡量這個決策樹的有效程度。

對決策樹的每一個節(jié)點(diǎn)，我們可以如此衡量：●進(jìn)入這個節(jié)點(diǎn)的資料數(shù)目?！袢绻且粋€葉部節(jié)點(diǎn)，可觀察資料分類的方式?！襁@個節(jié)點(diǎn)將資料正確分類的比率。決策樹基本觀念目前九頁\總數(shù)六十頁\編于十二點(diǎn)

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

下表顯示這個節(jié)點(diǎn)共有11筆資料被歸類其下，其中九個是正確的（女性），還有兩個男性被誤分到這裡。換言之，這項規(guī)則的錯誤率為0.182決策樹基本觀念目前十頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念目前十一頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念yearplacemovielastlikesexpred.594231FF432112FF432130FF4512563MF451252FF4512526FF461262FF45232111FF493163MF4512563FF4523217FF目前十二頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念決策樹創(chuàng)造資料箱:

雖然樹狀圖和『二十個問題』類推法有助於呈現(xiàn)決策樹方法的某些特質(zhì)，但作者發(fā)現(xiàn)，在某些情況下，基於不同表現(xiàn)方式的箱形圖（boxdiagram）更加清楚明白。一個決策樹創(chuàng)造一系列盒子或箱子，我們可以將資料丟進(jìn)去。任何樹狀圖的葉部節(jié)點(diǎn)形成一個一維式箱形圖。和決策樹根部節(jié)點(diǎn)有關(guān)的測試將下層分成兩個或更多部分。目前十三頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念目前十四頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念決策樹的根部擴(kuò)大成資料箱：●資料箱的寬度可以有變化，以顯示一筆資料落在特定箱中的相對可能性?！襁@個圖形可以換成一個直條圖（histogram），每一個直條的高度顯示落在對應(yīng)箱中的資料數(shù)目。這類直條圖可以使用直條的頻色或形狀來顯示對應(yīng)規(guī)則的錯誤率。●單一資料可以根據(jù)輸出變數(shù)的數(shù)值，用有色的球形或點(diǎn)狀來代表。這樣可以立即顯示這套分類系統(tǒng)的表現(xiàn)。目前十五頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念目前十六頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念表現(xiàn)多維度:

當(dāng)我們將資料丟進(jìn)格子中，它們落到特定的層內(nèi)並以此分類。一個層形圖讓我們一目了然的見到數(shù)層資料的細(xì)節(jié)。在下圖，我們可以一眼看出左下的格子清一色都是男性。仔細(xì)的看，我們可以發(fā)現(xiàn)某些層在分類上表現(xiàn)很好，或是聚集了大量資料。這和線性，邏輯性或二次差分等傳統(tǒng)的統(tǒng)計分類方法試圖在資料空間中劃上一條直線或弧線將資料分層的方式大不相同。目前十七頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念目前十八頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念

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

目前十九頁\總數(shù)六十頁\編于十二點(diǎn)決策樹基本觀念目前二十頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）

分類與迴歸樹（ClassificationAndRegressionTree，CART）CART演算法是建構(gòu)決策樹時最常用的演算法之一。自從１９８４年布里曼（L.Brieman）與其同僚發(fā)表這種方法以來，就一直機(jī)械學(xué)習(xí)實驗的要素。目前二十一頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）目前二十二頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）numbers目前二十三頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）找出起始的分隔:

在過程中的一開始，我們有一個預(yù)先分類好的訓(xùn)練和資料。預(yù)先分類意味輸出變數(shù)，或稱依變數(shù)，具備一個己知的類別。CART藉著一個單一輸入變數(shù)函數(shù)，在每一個節(jié)點(diǎn)分隔資料，以建構(gòu)一個二分式?jīng)Q策樹。因此，第一的任務(wù)是決定哪一個自變數(shù)可以成最好的分隔變數(shù)。最好分隔的定義是能夠?qū)①Y料最完善的分配到一個單一類別支配的群體。目前二十四頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）找出起始的分隔:

用來評估一個分隔數(shù)的衡量標(biāo)準(zhǔn)是分散度（diversity）。對於一組資料的『分散度指標(biāo)』（indexofdiversity）有多種計算方式。不論哪一種，分散度指標(biāo)很高，表示這個組合中包含平均分配到多個類別，而分散度指標(biāo)很低則表示一個單一類別的成員居優(yōu)勢。目前二十五頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）找出起始的分隔:

最好的分隔變數(shù)是能夠降低一個資料組的分散度，而且降得最多。換言之，我們希望以下這個式子最大化：

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

三分種分散度衡量法：

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

2P(c1)P(c2)

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

目前二十六頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）

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

目前二十七頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）培養(yǎng)出整棵樹:

一開始的分隔製造出兩個節(jié)點(diǎn)，現(xiàn)在我們再以分隔根節(jié)點(diǎn)的方法將每個節(jié)點(diǎn)予以分隔。再一次，我們檢視所有輸入變數(shù)，找出雀屏中選的分隔變數(shù)。如果這個變數(shù)只遇上一個數(shù)值，我們就將其排除，因為它無法被用來創(chuàng)造一個分隔。一個類別變數(shù)若被用來作為決策樹中較高層的分隔變數(shù)時，比較有可能很快的變成單一數(shù)值化。對每一個剩下的變數(shù)最好的分隔就確定了。當(dāng)我們無法找到任何分隔可以顯著降低一個節(jié)點(diǎn)的分散度，我們就將其標(biāo)示為葉部節(jié)點(diǎn)。到了最後，存在的只剩下葉部節(jié)點(diǎn)，而我們也完成決策樹。目前二十八頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）計算每個節(jié)點(diǎn)的錯誤率：

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

目前三十頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）修剪決策樹:

只要能發(fā)現(xiàn)新的分隔，改善決策樹將訓(xùn)練組資料分類的能力，決策樹就會繼續(xù)成長。如果我們試圖預(yù)測身高，而我們來到一個節(jié)點(diǎn)，包含一個名叫馬丁的高個子，和幾個比較矮的人，我們可以訂出一個新規(guī)則『名叫馬丁的人是高個子』，來降低分散度。這個規(guī)則有助於將訓(xùn)練資料分類，但如果在更寬廣的世界上，馬丁是一個很少見的名，而且這個名字和身高又沒有特別的關(guān)連，那麼這個規(guī)則比沒用還糟糕。目前三十一頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）修剪決策樹:

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

目前三十二頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）目前三十三頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）確認(rèn)入選的分支決策樹：

我們的目標(biāo)是首先將提供最少額外預(yù)測能力的分支先修剪掉。為了確認(rèn)這些最沒用的分支，我們引入一個決策樹的『調(diào)節(jié)錯誤率』（adjusterrorrate）的觀念。這是一種衡量方法，逐一檢視每一個葉部，確認(rèn)最弱勢的分支（那些無法有效降低整棵決策樹錯誤率的分支），然後將它們標(biāo)示出來加以修剪目前三十四頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）目前三十五頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）目前三十六頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）評估分支樹：

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

目前三十七頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）評估最佳的分支樹：

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

目前三十八頁\總數(shù)六十頁\編于十二點(diǎn)分類與迴歸樹（CART）將代價列入考量

:

我們討論至此，只使用錯誤率作為評估一個分支樹良莠的依據(jù)。然而，在許多應(yīng)用上，錯誤分類的代價依資料類別不同而有異。當(dāng)然在醫(yī)療診斷上，一個錯誤的陰性診斷（negative）也許會比錯誤的陽性診斷（positive）傷害更大。在進(jìn)行癌癥抹片檢查時，誤診為性也許只會帶來更多的檢查，但誤診為陰性卻可能讓病情惡化。我們可以把問題列入考量，以一個使用加權(quán)方式將錯誤分類的機(jī)率加倍的代價函數(shù)，來取代錯誤率。目前三十九頁\總數(shù)六十頁\編于十二點(diǎn)C4.5

C4.5是最新出現(xiàn)的決策樹演算法的速成法，是澳州研究者昆蘭（J.RossQuinlan）多年努力成果。與CART差異：培養(yǎng)決策樹：

C4.5與CART之間的第一個差異是CART在每一個節(jié)點(diǎn)都呈現(xiàn)二分法，因此產(chǎn)生二分式?jīng)Q策樹，而C4.5則在每一個節(jié)點(diǎn)產(chǎn)不同數(shù)目的分支。這是因為C4.5對持續(xù)性變項的處理方式和CART相當(dāng)類似，但對類別變項的處理就相當(dāng)不同。目前四十頁\總數(shù)六十頁\編于十二點(diǎn)C4.5修剪決策樹：

CART使用決策樹的分散度為度量，來標(biāo)記不同的分支樹，然後以沒有見過的預(yù)先分類好的資料（測試組）來測試這些分支樹。相反的，C4.5並不參考其他資料，嘗試以只用訓(xùn)練資料的情況下來修剪決策樹。因此，C4.5使用建構(gòu)決策樹的相同資料來決定該如何加以修剪。

目前四十一頁\總數(shù)六十頁\編于十二點(diǎn)C4.5從決策樹到規(guī)則：

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

看球賽加上地主隊獲勝加上跟朋友出門，就會得出啤酒?？辞蛸惣由系刂麝牜@勝加上待在家裡，就會得出健怡汽水?？辞蛸惣由系刂麝犦斍蚣由细笥殉鲩T，就會得出啤酒?？辞蛸惣由系刂麝犦斍蚣由洗诩已e，就會得出牛奶。目前四十二頁\總數(shù)六十頁\編于十二點(diǎn)C4.5目前四十三頁\總數(shù)六十頁\編于十二點(diǎn)CHAID

CHAID是哈根（J.A.Hartigan）在1975年率先提出的演算法，這是本章所討論的最古老的演算法。這也是最受到廣泛使用的演算法，因為它隨著SPSS和SAS等受歡迎的統(tǒng)計軟體流通。CHAID是從更早的一套自動互動偵測系統(tǒng)AID衍生而來，後者是摩根（J.A.Morgan）與?？固?J.N.Sonquist)在1963年提出。目前四十四頁\總數(shù)六十頁\編于十二點(diǎn)CHAIDCHAID與C4.5及CART的差異：

CHAID和C4.5及CART兩種演算法的最大差異在於，後兩者先過度套用資料，再加以修剪，而CHAID嘗試在過度套用的情況發(fā)生之前就讓決策樹停止蔓生擴(kuò)大。另一個差異是CHAID只限於類別變數(shù)使用，連續(xù)變數(shù)必須被區(qū)隔成幾個區(qū)段範(fàn)圍，或是以高，中，低等類別來取代。目前四十五頁\總數(shù)六十頁\編于十二點(diǎn)CHAID培養(yǎng)決策樹：如同其他兩種方法，CHAID演算利用輸入變數(shù)找出一個方法，將訓(xùn)練組資料分隔成兩個或兩個以上子節(jié)點(diǎn)。這些子節(jié)點(diǎn)被選擇的方式是輸出變數(shù)遇上某個特定數(shù)值的機(jī)率隨著節(jié)點(diǎn)不同而有所差異。目前四十六頁\總數(shù)六十頁\編于十二點(diǎn)CHAID選擇分隔變數(shù)：經(jīng)過第一步驟之後，我們得出以下的表：目前四十七頁\總數(shù)六十頁\編于十二點(diǎn)CHAID杏仁燒魚，鮪魚沙拉，生魚片魚肉鵝肝醬，水牛城雞翅，碎雞肝禽肉牛腰肉，麥香堡，罐頭牛肉，碎羊肉紅肉

目前四十八頁\總數(shù)六十頁\編于十二點(diǎn)CHAID重新分隔類別：第一步無法在輸出數(shù)上產(chǎn)生顯著統(tǒng)計差異的所有預(yù)測變都被合併。第二步，三個或更多的預(yù)測變數(shù)群組以二分法被重新分隔。如果這些分隔之中任何一個可以產(chǎn)生統(tǒng)計上顯著差異的結(jié)果，就就被保留?？ǚ椒治?chi-squared)這是對應(yīng)於CHAID的前兩個字母縮寫。

目前四十九頁\總數(shù)六十頁\編于十二點(diǎn)CHAID評鑑入選分隔變數(shù)：一旦每一個分隔變數(shù)都被分類，在輸出變數(shù)上產(chǎn)生最大的類別差異，就對這項結(jié)果使用卡方分析檢驗。根據(jù)檢驗，能夠產(chǎn)生最大差異分類的預(yù)測變數(shù)，就被選為當(dāng)前這個節(jié)點(diǎn)的分隔變數(shù)。

目前五十頁\總數(shù)六十頁\編于十二點(diǎn)CHAID限制決策樹的成長：在CHAID演算法中，決策樹持續(xù)成長，直到再也沒有任何區(qū)隔能在分類上達(dá)到統(tǒng)計顯著性差異為止。

目前五十一頁\總數(shù)六十頁\編于十二點(diǎn)其他決策樹的變化一次使用超過一個變數(shù)：

至今我們討論的三個演算法都是用在測試單一變項來形成每一個分隔。這個方法可能會有一些問題。其中之一會造成決策樹擁有超過我們所需的節(jié)點(diǎn)。額外的節(jié)點(diǎn)會造成不便，因為只有到達(dá)某一個節(jié)點(diǎn)的訓(xùn)練組資料有能夠引發(fā)下一層的分支樹。每一個節(jié)點(diǎn)的案例越少，得出的分類可靠性就越低。為了簡化說明，我們假設(shè)只有三個人投票。目前五十二頁\總數(shù)六十頁\編于十二點(diǎn)其他決策樹的變化目前五十三頁\總數(shù)六十頁\編于十二點(diǎn)其他決策樹的變化

我們將這個情形當(dāng)成訓(xùn)練資料，CART或其他任何可以根據(jù)單一屬性的數(shù)值來分隔建構(gòu)二分法決策樹的演算法，都會建