决策树分析

nullnull第九章 決策樹分析 Decision Tree Analysis決策樹分析決策樹分析簡介 決策樹基本觀念 三種研究 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 其他決策樹的變化 決策樹的優、缺點簡介簡介 決策樹是功能強大且相當受歡迎的分類和預測工具。這項以樹狀圖為基礎的方法，其吸引人之處在於決策樹具有規則，和類神經網路不同。規則可以用文字來表達，讓人類了解，或是轉化為SQL之類的資料庫語言，讓落在特定類別的資料紀錄可以被搜尋。 在本章中，我們先介紹決策樹運作的方式及其如何應用在分類和預測問題。隨後我們進一步介紹如何以CART、C4.5和CHAID演算法建構決策樹。 決策樹基本觀念決策樹基本觀念決策樹如何運作: 『二十個問題』（Twenty Questions）這個遊戲，一定可以輕易了解決策樹將資料分類的方式。在遊戲中，一個玩家先想好所有參加者都有知道的一個特定地點，人物或事物，其他玩家藉著提出一堆『是或不是』的問題，來找出 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 。一個決策樹代表一系列這類問題。 在遊戲中，第一個問題的答案決定了下一個問題。如果謹慎選擇問題，只要短短幾次詢問就可以將後來的資料正確分類。決策樹基本觀念決策樹基本觀念 以『二十個問題』的方法顯示樂器的分類。 決策樹基本觀念決策樹基本觀念 一筆資料從根部的節點進入決策樹。在根部，應用一項測驗來決定這筆資料該進入下一層的哪一個子節點（child node）。選擇一開始的測驗有不同的演算法，但目的都是一樣的：這個過程一再重複，直到資料到達葉部節點（leaf node）。 從根部到每一個葉部都有一套獨特的路徑，這個路徑就是用來分類資料規則的一種表達方式。 決策樹基本觀念決策樹基本觀念決策樹的多種形式: 決策樹基本觀念決策樹基本觀念某些規則比其他規則好: 我們將一個決策樹應用在一個前所未有的資料集合上，並觀察其分類正確的比率，來衡量這個決策樹的有效程度。  對決策樹的每一個節點，我們可以如此衡量： ●進入這個節點的資料數目。 ●如果是一個葉部節點，可觀察資料分類的方式。 ●這個節點將資料正確分類的比率。決策樹基本觀念決策樹基本觀念 藉由將資料分到正確類別的情況，我們可以驗證出建構決策樹的最佳演算法。第四章中的電影迷資料庫。受測者被要求回答他們的年齡，性別，最常看的電影，以及最近看過的電影片名。然後我們使用決策樹程式來創造規則，以受測者在問卷中其他問題的答案來找出該名受測者的性別。  下表顯示這個節點共有11筆資料被歸類其下，其中九個是正確的（女性），還有兩個男性被誤分到這裡。換言之，這項規則的錯誤率為0.182決策樹基本觀念決策樹基本觀念決策樹基本觀念決策樹基本觀念決策樹基本觀念決策樹基本觀念決策樹創造資料箱: 雖然樹狀圖和『二十個問題』類推法有助於呈現決策樹方法的某些特質，但作者發現，在某些情況下，基於不同表現方式的箱形圖（box diagram）更加清楚明白。 一個決策樹創造一系列盒子或箱子，我們可以將資料丟進去。任何樹狀圖的葉部節點形成一個一維式箱形圖。和決策樹根部節點有關的測試將下層分成兩個或更多部分。 決策樹基本觀念決策樹基本觀念決策樹基本觀念決策樹基本觀念決策樹的根部擴大成資料箱： ●資料箱的寬度可以有變化，以顯示一筆資料落 在特定箱中的相對可能性。 ●這個圖形可以換成一個直條圖（histogram）， 每一個直條的高度顯示落在對應箱中的資料數 目。這類直條圖可以使用直條的頻色或形狀來 顯示對應規則的錯誤率。 ●單一資料可以根據輸出變數的數值，用有色的 球形或點狀來代表。這樣可以立即顯示這套分 類系統的表現。 決策樹基本觀念決策樹基本觀念null決策樹基本觀念表現多維度: 當我們將資料丟進格子中，它們落到特定的層內並以此分類。一個層形圖讓我們一目了然的見到數層資料的細節。在下圖，我們可以一眼看出左下的格子清一色都是男性。仔細的看，我們可以發現某些層在分類上表現很好，或是聚集了大量資料。這和線性，邏輯性或二次差分等傳統的統計分類方法試圖在資料空間中劃上一條直線或弧線將資料分層的方式大不相同。 null決策樹基本觀念null決策樹基本觀念 這是一種基本上的差異：當一筆資料有多種非常不同的方法使其成為目標類別的一部份時，使用單一線條來找出類別間界線的統計方法效力會很弱。例如，在信用卡產業，很多種持卡人都讓發卡根行有利可圖。某些持卡人每次繳款的金額不高，但他們欠繳金額很高時，卻又不會超過額度;還有一種持卡人每月都繳清帳款，但他們交易金額很高，因此發卡銀行還是可以賺到錢。這兩種非常不同的持卡人可能為發卡銀行帶來同樣多的收益。在下圖中，我們將顥示在這種分類問題上，決策樹超越純粹統計方法的優點。 null決策樹基本觀念null分類與迴歸樹（CART） 分類與迴歸樹（Classification And Regression Tree，CART）CART演算法是建構決策樹時最常用的演算法之一。自從１９８４年布里曼（L. Brieman）與其同僚發表這種方法以來，就一直機械學習實驗的要素。 null分類與迴歸樹（CART）null分類與迴歸樹（CART）numbersnull分類與迴歸樹（CART）找出起始的分隔 : 在過程中的一開始，我們有一個預先分類好的訓練和資料。預先分類意味輸出變數，或稱依變數，具備一個己知的類別。CART藉著一個單一輸入變數函數，在每一個節點分隔資料，以建構一個二分式決策樹。因此，第一的任務是決定哪一個自變數可以成最好的分隔變數。最好分隔的定義是能夠將資料最完善的分配到一個單一類別支配的群體。 null分類與迴歸樹（CART）找出起始的分隔 : 用來評估一個分隔數的衡量標準是分散度（diversity）。對於一組資料的『分散度指標』（index of diversity）有多種計算方式。不論哪一種，分散度指標很高，表示這個組合中包含平均分配到多個類別，而分散度指標很低則表示一個單一類別的成員居優勢。 null分類與迴歸樹（CART）找出起始的分隔 : 最好的分隔變數是能夠降低一個資料組的分散度，而且降得最多。換言之，我們希望以下這個式子最大化：  分散度（分隔前）－﹝分散度（分隔後左邊子集 合）＋分散度（分隔後右邊子集合）﹞  三分種分散度衡量法：  min{P(c1), P(c2) }  2P(c1)P(c2 )  〔P(c1)logP (c1)〕+〔P(c2)logP (c2)〕 null分類與迴歸樹（CART） 當各類別出現的機率相等時，以上的三個函數會出現最大值，當資料組中只包含單一類別時，函數值則為零。在完全分散和完全聚集的兩個極端之間，這些函數有些微不同的型態。 為了在一個節點中選擇最佳分隔變數，我們依次考量每一個自變數。假設這個變數遇上多個數值，我們進行二分式研究，希望找出降低分散度最多的最佳分隔法。我們從每個變數中找出最能降低分散度的最佳分隔變數，勝利者就被選為根節點的分隔變數。 null分類與迴歸樹（CART）培養出整棵樹: 一開始的分隔製造出兩個節點，現在我們再以分隔根節點的方法將每個節點予以分隔。再一次，我們檢視所有輸入變數，找出雀屏中選的分隔變數。如果這個變數只遇上一個數值，我們就將其排除，因為它無法被用來創造一個分隔。 一個類別變數若被用來作為決策樹中較高層的分隔變數時，比較有可能很快的變成單一數值化。對每一個剩下的變數最好的分隔就確定了。當我們無法找到任何分隔可以顯著降低一個節點的分散度，我們就將其標示為葉部節點。到了最後，存在的只剩下葉部節點，而我們也完成決策樹。 null分類與迴歸樹（CART）計算每個節點的錯誤率： 每一個葉部如今都分配到一個類別以及一個錯誤率。回顧前圖，圖中選取了從根部到標示為『女性』的葉部路徑。該節點是一個葉部節點，表示找不到任何分隔變數可以顯著的降低其分散性。然而，這並不表示所有祗達這個葉部的資料都屬於同一類。使用簡單機率的定義，我們可以看到11個葉部中有9個是正確分類。這告訴我們，以這個訓練組而言，抵達這個節點的資料是女性的機率為0.818。相對的，這個葉部的錯誤率1-0.818就是0.812。 null分類與迴歸樹（CART）計算整個決策樹的錯誤率： 整個決策樹的錯誤率是所有葉部錯誤率的加權總數。每一個葉部的錯誤率乘上資料抵達葉部的機率(分配到資料的比例)，加起來的總數就是整個決策樹的錯誤率。 null分類與迴歸樹（CART）修剪決策樹 :  只要能發現新的分隔，改善決策樹將訓練組資料分類的能力，決策樹就會繼續成長。 如果我們試圖預測身高，而我們來到一個節點，包含一個名叫馬丁的高個子，和幾個比較矮的人，我們可以訂出一個新規則『名叫馬丁的人是高個子』，來降低分散度。這個規則有助於將訓練資料分類，但如果在更寬廣的世界上，馬丁是一個很少見的名，而且這個名字和身高又沒有特別的關連，那麼這個規則比沒用還糟糕。null分類與迴歸樹（CART）修剪決策樹 :  下圖顯示出會發的狀況。圖中的箱子變得很小，而且每一個都不大，只容得下訓組資料，不太可能再容納新資料。很顯的。我們需要修剪這個決策樹以便在一般性的案例中獲得更正確的預測。問題是要決定該倒推回去修剪多少，以及這些分支的決策樹中哪些表現很好。 null分類與迴歸樹（CART）null分類與迴歸樹（CART）確認入選的分支決策樹： 我們的目標是首先將提供最少額外預測能力的分支先修剪掉。為了確認這些最沒用的分支，我們引入一個決策樹的『調節錯誤率』（adjust error rate）的觀念。這是一種衡量方法，逐一檢視每一個葉部，確認最弱勢的分支（那些無法有效降低整棵決策樹錯誤率的分支），然後將它們標示出來加以修剪null分類與迴歸樹（CART）null分類與迴歸樹（CART）null分類與迴歸樹（CART）評估分支樹： 最後工作是從入選的分支樹中選出最能分類新資料的決策樹。為達到此目的，我們使用第二個預先分好的資料組，即『測試組資料』（test set）。測試組和訓練組來自同一群母體，但包含的資料不同。入選分支樹中每一個都被用來分類測試組資，得出最低的整體錯誤率的就是勝利者。 null分類與迴歸樹（CART）評估最佳的分支樹： 最後工作是從利用第三組資料，將測試組和訓練組打散，即『評估組資料』（evaluation set）。入選分支樹應用在評估組所得出的錯誤率，來預期這個分支樹在未經分類的資料上使用時的錯誤率。 null分類與迴歸樹（CART）將代價列入考量 : 我們討論至此，只使用錯誤率作為評估一個分支樹良莠的依據。然而，在許多應用上，錯誤分類的代價依資料類別不同而有異。 當然在醫療診斷上，一個錯誤的陰性診斷（negative）也許會比錯誤的陽性診斷（positive）傷害更大。在進行癌症抹片檢查時，誤診為性也許只會帶來更多的檢查，但誤診為陰性卻可能讓病情惡化。我們可以把問題列入考量，以一個使用加權方式將錯誤分類的機率加倍的代價函數，來取代錯誤率。nullC4.5 C4.5是最新出現的決策樹演算法的速成法，是澳州研究者昆蘭（J. Ross Quinlan）多年努力成果。與CART差異： 培養決策樹： C4.5與CART之間的第一個差異是CART在每一個節點都呈現二分法，因此產生二分式決策樹，而C4.5則在每一個節點產不同數目的分支。這是因為C4.5對持續性變項的處理方式和CART相當類似，但對類別變項的處理就相當不同。 nullC4.5修剪決策樹： CART使用決策樹的分散度為度量，來標記不同的分支樹，然後以沒有見過的預先分類好的資料（測試組）來測試這些分支樹。相反的，C4.5並不參考其他資料，嘗試以只用訓練資料的情況下來修剪決策樹。因此，C4.5使用建構決策樹的相同資料來決定該如何加以修剪。 nullC4.5從決策樹到規則： 我們可以在不改變分類行為的前提下藉著合併到葉部的路徑來向這個目標走出第一步。下圖的決策樹部分得出以下的規則：  看球賽加上地主隊獲勝加上跟朋友出門，就會得出啤酒。 看球賽加上地主隊獲勝加上待在家裡，就會得出健怡汽水。 看球賽加上地主隊輸球加上跟朋友出門，就會得出啤酒。 看球賽加上地主隊輸球加上待在家裡，就會得出牛奶。 nullC4.5nullCHAID CHAID是哈根（J.A. Hartigan）在1975年率先提出的演算法，這是本章所討論的最古老的演算法。這也是最受到廣泛使用的演算法，因為它隨著SPSS和SAS等受歡迎的統計軟體流通。CHAID是從更早的一套自動互動偵測系統AID衍生而來，後者是摩根（J.A. Morgan）與桑奎斯特(J.N. Sonquist)在1963年提出。nullCHAIDCHAID與C4.5及CART的差異： CHAID和C4.5及CART兩種演算法的最大差異在於，後兩者先過度套用資料，再加以修剪，而CHAID嘗試在過度套用的情況發生之前就讓決策樹停止蔓生擴大。 另一個差異是CHAID只限於類別變數使用，連續變數必須被區隔成幾個區段範圍，或是以高，中，低等類別來取代。 nullCHAID培養決策樹： 如同其他兩種方法，CHAID演算利用輸入變數找出一個方法，將訓練組資料分隔成兩個或兩個以上子節點。這些子節點被選擇的方式是輸出變數遇上某個特定數值的機率隨著節點不同而有所差異。 nullCHAID選擇分隔變數： 經過第一步驟之後，我們得出以下的表：nullCHAID杏仁燒魚，鮪魚沙拉，生魚片  魚肉 鵝肝醬，水牛城雞翅，碎雞肝  禽肉 牛腰肉，麥香堡，罐頭牛肉，碎羊肉  紅肉 nullCHAID重新分隔類別： 第一步無法在輸出數上產生顯著統計差異的所有預測變都被合併。第二步，三個或更多的預測變數群組以二分法被重新分隔。如果這些分隔之中任何一個可以產生統計上顯著差異的結果，就就被保留。 卡方分析(chi-squared )這是對應於CHAID的前兩個字母縮寫。 nullCHAID評鑑入選分隔變數： 一旦每一個分隔變數都被分類，在輸出變數上產生最大的類別差異，就對這項結果使用卡方分析檢驗。根據檢驗，能夠產生最大差異分類的預測變數，就被選為當前這個節點的分隔變數。 nullCHAID限制決策樹的成長： 在CHAID演算法中，決策樹持續成長，直到再也沒有任何區隔能在分類上達到統計顯著性差異為止。  null其他決策樹的變化一次使用超過一個變數： 至今我們討論的三個演算法都是用在測試單一變項來形成每一個分隔。這個方法可能會有一些問題。其中之一會造成決策樹擁有超過我們所需的節點。額外的節點會造成不便，因為只有到達某一個節點的訓練組資料有能夠引發下一層的分支樹。每一個節點的案例越少，得出的分類可靠性就越低。為了簡化說明，我們假設只有三個人投票。null其他決策樹的變化null其他決策樹的變化 我們將這個情形當成訓練資料，CART或其他任何可以根據單一屬性的數值來分隔建構二分法決策樹的演算法，都會建構出下圖的決策樹。這個決策樹完美的將訓練組資料分組，但需要五個內部分隔節點。  若以邏輯和函數來合併特性形成結合，我們就可以獲得如下圖那樣更簡化的決策樹。這個決策樹顯示使用變數結合能獲得的另一個潛在優點。這個決策樹如今更能夠表現分類上顯示的無異議的觀念：『當所有投票人意見一致，這項決策就是無異議。』null其他決策樹的變化null其他決策樹的變化null其他決策樹的變化 以機械學習研究者的行話來說，一個看一眼就能夠了解的決策樹，具有方便理解的性質。機械學習領域的一些研究者，非常強調這個觀念，但似乎只有在這些學者以一些小型的，組織完整的資料在建構他們的研究時，才能獲得這樣完美的結果。 null讓超平面傾斜： 傳統的決策樹檢驗一個節點的單一變數值，只能形成方形區域。在一個二維空間，Y  N這種測試形式，形成一個由與Y軸垂直且與X軸平行的直線所界定的區域。藉由選擇不同的Ｎ值，我們可以讓這條直線上下移動，但無法改變其斜率。同樣的，在一個多維的空間，根據單一變數所做的檢驗定義出一個超平面，這個平面和用來進行檢驗的這個變數所代表的軸垂直，而與其他所有軸平行。其他決策樹的變化null 問題是有些東西不適合放進方形區域裡，下圖顯示了這個問題：這兩個區域實際上是由一條對角線劃分，需要一個更深入的決策樹才能產生足夠的方形區域來約略正確的將其劃分。真正的辦法是用屬性的線性合併輕易解決問題。多個軟體工具嘗試以變數數值的加權總數來做分，讓超平面傾斜，而且有多種方法可以選擇加權方式。這些衍生變數可能是多個其他變數的函數，或者可能是對數，平方根，立方，絕對值，或其他單一變數函數。 其他決策樹的變化null其他決策樹的變化null類神經樹： 在每一個節點就多個變數進行合併性輸入的一個方法，就是將每一個節點組成一個小型的類神經網路。Torrent Systems的一套資料探礦套裝軟體其中一項工具就有使用這個方法。當我們碰到方形區域無法順利描述出讓類別真正形狀的領域，類神經可以得出更正確的分類。從使用者的觀點，這種混合技術在類神經網路領域在決策樹領域更常見，因為與類神經網路結後，決策樹將無法解釋其決策，即使如以下形式(W1X1+W2X2+W3X3+…)  N，其規則以藉由每一個節點變數的線性組合來以決策樹方法獲得，但在類神經網就很容易讓人迷惑。 其他決策樹的變化決策樹的優、缺點決策樹的優、缺點 優點： ●決策樹可以產生易於了解的規則。 ●決策樹不需要太多計算就可進行分類。 ●決策樹能夠處理連續與類別型的資料。 ●決策樹提供清楚的指引，告訴我們在進行預 測和分類時哪一個變是最重要。  缺點： ●遇上太多類別時容易犯錯。 ●對非方型區域無能為力。