决策树分析及SPSS实现.ppt

1 第九章決策樹分析DecisionTreeAnalysis 2 決策樹分析 簡介決策樹基本觀念三種研究方法其他決策樹的變化決策樹的優 缺點 3 決策樹是功能強大且相當受歡迎的分類和預測工具 這項以樹狀圖為基礎的方法 其吸引人之處在於決策樹具有規則 和類神經網路不同 規則可以用文字來表達 讓人類了解 或是轉化為SQL之類的資料庫語言 讓落在特定類別的資料紀錄可以被搜尋 在本章中 我們先介紹決策樹運作的方式及其如何應用在分類和預測問題 隨後我們進一步介紹如何以CART C4 5和CHAID演算法建構決策樹 簡介 4 決策樹如何運作 二十個問題 TwentyQuestions 這個遊戲 一定可以輕易了解決策樹將資料分類的方式 在遊戲中 一個玩家先想好所有參加者都有知道的一個特定地點 人物或事物 其他玩家藉著提出一堆 是或不是 的問題 來找出答案 一個決策樹代表一系列這類問題 在遊戲中 第一個問題的答案決定了下一個問題 如果謹慎選擇問題 只要短短幾次詢問就可以將後來的資料正確分類 決策樹基本觀念 5 以 二十個問題 的方法顯示樂器的分類 決策樹基本觀念 6 一筆資料從根部的節點進入決策樹 在根部 應用一項測驗來決定這筆資料該進入下一層的哪一個子節點 childnode 選擇一開始的測驗有不同的演算法 但目的都是一樣的 這個過程一再重複 直到資料到達葉部節點 leafnode 從根部到每一個葉部都有一套獨特的路徑 這個路徑就是用來分類資料規則的一種表達方式 決策樹基本觀念 7 決策樹的多種形式 決策樹基本觀念 8 某些規則比其他規則好 我們將一個決策樹應用在一個前所未有的資料集合上 並觀察其分類正確的比率 來衡量這個決策樹的有效程度 對決策樹的每一個節點 我們可以如此衡量 進入這個節點的資料數目 如果是一個葉部節點 可觀察資料分類的方式 這個節點將資料正確分類的比率 決策樹基本觀念 9 藉由將資料分到正確類別的情況 我們可以驗證出建構決策樹的最佳演算法 第四章中的電影迷資料庫 受測者被要求回答他們的年齡 性別 最常看的電影 以及最近看過的電影片名 然後我們使用決策樹程式來創造規則 以受測者在問卷中其他問題的答案來找出該名受測者的性別 下表顯示這個節點共有11筆資料被歸類其下 其中九個是正確的 女性 還有兩個男性被誤分到這裡 換言之 這項規則的錯誤率為0 182 決策樹基本觀念 10 決策樹基本觀念 11 決策樹基本觀念 12 決策樹基本觀念 決策樹創造資料箱 雖然樹狀圖和 二十個問題 類推法有助於呈現決策樹方法的某些特質 但作者發現 在某些情況下 基於不同表現方式的箱形圖 boxdiagram 更加清楚明白 一個決策樹創造一系列盒子或箱子 我們可以將資料丟進去 任何樹狀圖的葉部節點形成一個一維式箱形圖 和決策樹根部節點有關的測試將下層分成兩個或更多部分 13 決策樹基本觀念 14 決策樹基本觀念 決策樹的根部擴大成資料箱 資料箱的寬度可以有變化 以顯示一筆資料落在特定箱中的相對可能性 這個圖形可以換成一個直條圖 histogram 每一個直條的高度顯示落在對應箱中的資料數目 這類直條圖可以使用直條的頻色或形狀來顯示對應規則的錯誤率 單一資料可以根據輸出變數的數值 用有色的球形或點狀來代表 這樣可以立即顯示這套分類系統的表現 15 決策樹基本觀念 16 決策樹基本觀念 表現多維度 當我們將資料丟進格子中 它們落到特定的層內並以此分類 一個層形圖讓我們一目了然的見到數層資料的細節 在下圖 我們可以一眼看出左下的格子清一色都是男性 仔細的看 我們可以發現某些層在分類上表現很好 或是聚集了大量資料 這和線性 邏輯性或二次差分等傳統的統計分類方法試圖在資料空間中劃上一條直線或弧線將資料分層的方式大不相同 17 決策樹基本觀念 18 決策樹基本觀念 這是一種基本上的差異 當一筆資料有多種非常不同的方法使其成為目標類別的一部份時 使用單一線條來找出類別間界線的統計方法效力會很弱 例如 在信用卡產業 很多種持卡人都讓發卡根行有利可圖 某些持卡人每次繳款的金額不高 但他們欠繳金額很高時 卻又不會超過額度 還有一種持卡人每月都繳清帳款 但他們交易金額很高 因此發卡銀行還是可以賺到錢 這兩種非常不同的持卡人可能為發卡銀行帶來同樣多的收益 在下圖中 我們將顥示在這種分類問題上 決策樹超越純粹統計方法的優點 19 決策樹基本觀念 20 分類與迴歸樹 CART 分類與迴歸樹 ClassificationAndRegressionTree CART CART演算法是建構決策樹時最常用的演算法之一 自從 年布里曼 L Brieman 與其同僚發表這種方法以來 就一直機械學習實驗的要素 21 分類與迴歸樹 CART 22 分類與迴歸樹 CART numbers 23 分類與迴歸樹 CART 找出起始的分隔 在過程中的一開始 我們有一個預先分類好的訓練和資料 預先分類意味輸出變數 或稱依變數 具備一個己知的類別 CART藉著一個單一輸入變數函數 在每一個節點分隔資料 以建構一個二分式決策樹 因此 第一的任務是決定哪一個自變數可以成最好的分隔變數 最好分隔的定義是能夠將資料最完善的分配到一個單一類別支配的群體 24 分類與迴歸樹 CART 找出起始的分隔 用來評估一個分隔數的衡量標準是分散度 diversity 對於一組資料的 分散度指標 indexofdiversity 有多種計算方式 不論哪一種 分散度指標很高 表示這個組合中包含平均分配到多個類別 而分散度指標很低則表示一個單一類別的成員居優勢 25 分類與迴歸樹 CART 找出起始的分隔 最好的分隔變數是能夠降低一個資料組的分散度 而且降得最多 換言之 我們希望以下這個式子最大化 分散度 分隔前 分散度 分隔後左邊子集合 分散度 分隔後右邊子集合 三分種分散度衡量法 min P c1 P c2 2P c1 P c2 P c1 logP c1 P c2 logP c2 26 分類與迴歸樹 CART 當各類別出現的機率相等時 以上的三個函數會出現最大值 當資料組中只包含單一類別時 函數值則為零 在完全分散和完全聚集的兩個極端之間 這些函數有些微不同的型態 為了在一個節點中選擇最佳分隔變數 我們依次考量每一個自變數 假設這個變數遇上多個數值 我們進行二分式研究 希望找出降低分散度最多的最佳分隔法 我們從每個變數中找出最能降低分散度的最佳分隔變數 勝利者就被選為根節點的分隔變數 27 分類與迴歸樹 CART 培養出整棵樹 一開始的分隔製造出兩個節點 現在我們再以分隔根節點的方法將每個節點予以分隔 再一次 我們檢視所有輸入變數 找出雀屏中選的分隔變數 如果這個變數只遇上一個數值 我們就將其排除 因為它無法被用來創造一個分隔 一個類別變數若被用來作為決策樹中較高層的分隔變數時 比較有可能很快的變成單一數值化 對每一個剩下的變數最好的分隔就確定了 當我們無法找到任何分隔可以顯著降低一個節點的分散度 我們就將其標示為葉部節點 到了最後 存在的只剩下葉部節點 而我們也完成決策樹 28 分類與迴歸樹 CART 計算每個節點的錯誤率 每一個葉部如今都分配到一個類別以及一個錯誤率 回顧前圖 圖中選取了從根部到標示為 女性 的葉部路徑 該節點是一個葉部節點 表示找不到任何分隔變數可以顯著的降低其分散性 然而 這並不表示所有祗達這個葉部的資料都屬於同一類 使用簡單機率的定義 我們可以看到11個葉部中有9個是正確分類 這告訴我們 以這個訓練組而言 抵達這個節點的資料是女性的機率為0 818 相對的 這個葉部的錯誤率1 0 818就是0 812 29 分類與迴歸樹 CART 計算整個決策樹的錯誤率 整個決策樹的錯誤率是所有葉部錯誤率的加權總數 每一個葉部的錯誤率乘上資料抵達葉部的機率 分配到資料的比例 加起來的總數就是整個決策樹的錯誤率 30 分類與迴歸樹 CART 修剪決策樹 只要能發現新的分隔 改善決策樹將訓練組資料分類的能力 決策樹就會繼續成長 如果我們試圖預測身高 而我們來到一個節點 包含一個名叫馬丁的高個子 和幾個比較矮的人 我們可以訂出一個新規則 名叫馬丁的人是高個子 來降低分散度 這個規則有助於將訓練資料分類 但如果在更寬廣的世界上 馬丁是一個很少見的名 而且這個名字和身高又沒有特別的關連 那麼這個規則比沒用還糟糕 31 分類與迴歸樹 CART 修剪決策樹 下圖顯示出會發的狀況 圖中的箱子變得很小 而且每一個都不大 只容得下訓組資料 不太可能再容納新資料 很顯的 我們需要修剪這個決策樹以便在一般性的案例中獲得更正確的預測 問題是要決定該倒推回去修剪多少 以及這些分支的決策樹中哪些表現很好 32 分類與迴歸樹 CART 33 分類與迴歸樹 CART 確認入選的分支決策樹 我們的目標是首先將提供最少額外預測能力的分支先修剪掉 為了確認這些最沒用的分支 我們引入一個決策樹的 調節錯誤率 adjusterrorrate 的觀念 這是一種衡量方法 逐一檢視每一個葉部 確認最弱勢的分支 那些無法有效降低整棵決策樹錯誤率的分支 然後將它們標示出來加以修剪 34 分類與迴歸樹 CART 35 分類與迴歸樹 CART 36 分類與迴歸樹 CART 評估分支樹 最後工作是從入選的分支樹中選出最能分類新資料的決策樹 為達到此目的 我們使用第二個預先分好的資料組 即 測試組資料 testset 測試組和訓練組來自同一群母體 但包含的資料不同 入選分支樹中每一個都被用來分類測試組資 得出最低的整體錯誤率的就是勝利者 37 分類與迴歸樹 CART 評估最佳的分支樹 最後工作是從利用第三組資料 將測試組和訓練組打散 即 評估組資料 evaluationset 入選分支樹應用在評估組所得出的錯誤率 來預期這個分支樹在未經分類的資料上使用時的錯誤率 38 分類與迴歸樹 CART 將代價列入考量 我們討論至此 只使用錯誤率作為評估一個分支樹良莠的依據 然而 在許多應用上 錯誤分類的代價依資料類別不同而有異 當然在醫療診斷上 一個錯誤的陰性診斷 negative 也許會比錯誤的陽性診斷 positive 傷害更大 在進行癌症抹片檢查時 誤診為性也許只會帶來更多的檢查 但誤診為陰性卻可能讓病情惡化 我們可以把問題列入考量 以一個使用加權方式將錯誤分類的機率加倍的代價函數 來取代錯誤率 39 C4 5 C4 5是最新出現的決策樹演算法的速成法 是澳州研究者昆蘭 J RossQuinlan 多年努力成果 與CART差異 培養決策樹 C4 5與CART之間的第一個差異是CART在每一個節點都呈現二分法 因此產生二分式決策樹 而C4 5則在每一個節點產不同數目的分支 這是因為C4 5對持續性變項的處理方式和CART相當類似 但對類別變項的處理就相當不同 40 C4 5 修剪決策樹 CART使用決策樹的分散度為度量 來標記不同的分支樹 然後以沒有見過的預先分類好的資料 測試組 來測試這些分支樹 相反的 C4 5並不參考其他資料 嘗試以只用訓練資料的情況下來修剪決策樹 因此 C4 5使用建構決策樹的相同資料來決定該如何加以修剪 41 C4 5 從決策樹到規則 我們可以在不改變分類行為的前提下藉著合併到葉部的路徑來向這個目標走出第一步 下圖的決策樹部分得出以下的規則 看球賽加上地主隊獲勝加上跟朋友出門 就會得出啤酒 看球賽加上地主隊獲勝加上待在家裡 就會得出健怡汽水 看球賽加上地主隊輸球加上跟朋友出門 就會得出啤酒 看球賽加上地主隊輸球加上待在家裡 就會得出牛奶 42 C4 5 43 CHAID CHAID是哈根 J A Hartigan 在1975年率先提出的演算法 這是本章所討論的最古老的演算法 這也是最受到廣泛使用的演算法 因為它隨著SPSS和SAS等受歡迎的統計軟體流通 CHAID是從更早的一套自動互動偵測系統AID衍生而來 後者是摩根 J A Morgan 與桑奎斯特 J N Sonquist 在1963年提出 44 CHAID CHAID與C4 5及CART的差異 CHAID和C4 5及CART兩種演算法的最大差異在於 後兩者先過度套用資料 再加以修剪 而CHAID嘗試在過度套用的情況發生之前就讓決策樹停止蔓生擴大 另一個差異是CHAID只限於類別變數使用 連續變數必須被區隔成幾個區段範圍 或是以高 中 低等類別來取代 45 CHAID 培養決策樹 如同其他兩種方法 CHAID演算利用輸入變數找出一個方法 將訓練組資料分隔成兩個或兩個以上子節點 這些子節點被選擇的方式是輸出變數遇上某個特定數值的機率隨著節點不同而有所差異 46 CHAID 選擇分隔變數 經過第一步驟之後 我們得出以下的表 47 CHAID 杏仁燒魚 鮪魚沙拉 生魚片 魚肉鵝肝醬 水牛城雞翅 碎雞肝 禽肉牛腰肉 麥香堡 罐頭牛肉 碎羊肉 紅肉 48 CHAID 重新分隔類別 第一步無法在輸出數上產生顯著統計差異的所有預測變都被合併 第二步 三個或更多的預測變數群組以二分法被重新分隔 如果這些分隔之中任何一個可以產生統計上顯著差異的結果 就就被保留 卡方分析 chi squared 這是對應於CHAID的前兩個字母縮寫 49 CHAID 評鑑入選分隔變數 一旦每一個分隔變數都被分類 在輸出變數上產生最大的類別差異 就對這項結果使用卡方分析檢驗 根據檢驗 能夠產生最大差異分類的預測變數 就被選為當前這個節點的分隔變數 50 CHAID 限制決策樹的成長 在CHAID演算法中 決策樹持續成長 直到再也沒有任何區隔能在分類上達到統計顯著性差異為止 51 其他決策樹的變化 一次使用超過一個變數 至今我們討論的三個演算法都是用在測試單一變項來形成每一個分隔 這個方法可能會有一些問題 其中之一會造成決策樹擁有超過我們所需的節點 額外的節點會造成不便 因為只有到達某一個節點的訓練組資料有能夠引發下一層的分支樹 每一個節點的案例越少 得出的分類可靠性就越低 為了簡化說明 我們假設只有三個人投票 52 其他決策樹的變化 53 其他決策樹的變化 我們將這個情形當成訓練資料 CART或其他任何可以根據單一屬性的數值來分隔建構二分法決策樹的演算法 都會建構出下圖的決策樹 這個決策樹完美的將訓練組資料分組 但需要五個內部分隔節點 若以邏輯和函數來合併特性形成結合 我們就可以獲得如下圖那樣更簡化的決策樹 這個決策樹顯示使用變數結合能獲得的另一個潛在優點 這個決策樹如今更能夠表現分類上顯示的無異議的觀念 當所有投票人意見一致 這項決策就是無異議 54 其他決策樹的變化 55 其他決策樹的變化 56 其他決策樹的變化 以機械學習研究者的行話來說 一個看一眼就能夠了解的決策樹 具有方便理解的性質 機械學習領域的一些研究者 非常強調這個觀念 但似乎只有在這些學者以一些小型的 組織完整的資料在建構他們的研究時 才能獲得這樣完美的結果 57 讓超平面傾斜 傳統的決策樹檢驗一個節點的單一變數值 只能形成方形區域 在一個二維空間 Y N這種測試形式 形成一個由與Y軸垂直且與X軸平行的直線所界定的區域 藉由選擇不同的 值 我們可以讓這條