决策树演算法课件

《决策树演算法课件》由会员分享，可在线阅读，更多相关《决策树演算法课件（49页珍藏版）》请在金锄头文库上搜索。

1、1,第五章,分類規則法,2,本章大綱,第一節 分類規則法的概念 第二節 決策樹歸納法 第三節 貝氏分類 第四節 其他分類規則法,3,第一節 分類規則法的概念,何謂分類規則法 分類規則法技術的分類,4,何謂分類規則法,分類法(Classification)是針對欲處理且未分類的資料集合，根據已知類別(Class)的物件(Instance)集合，將欲處理資料依據其屬性(Attributes)去完成分類的過程，並冀望能學習分類的規則，提供未來能自動分類之用。,5,圖5.1 建立分類規則與分類器,6,圖5.2 進行新資料的分類,7,分類規則法技術的分類,決策樹 決策樹是一種語意樹(Semantic T

2、ree)，與資料結構中的樹狀結構相仿，皆擁有根(Root)、節點(Node)以及樹葉(Leaf)等結構。 而每一節點都有一個分類的測試條件，就如IF-THEN的控制結構，利用測試結果來決定資料將分類於此節點的哪一棵子樹(Branch)，並繼續作為分類的條件和最後的決策。,。,8,分類規則法技術的分類(c2),貝氏網路分類 貝氏網路分類法可分為樸素貝氏分類與貝氏信念網路兩種。 樸素貝氏分類 又稱為天真貝氏分類。 主要是用在已知欲分類的類別以及個數的情況下，進行分類的動作。 貝氏信念網路 為一有向量的非循環圖形。 由節點 (Nodes)與連結線(Edges)所組成，而每個節點都有一組狀態機率表 (

3、Condition Probability Tables)。,9,分類規則法技術的分類(c3),其他技術 許多是屬於人工智慧技術 案例式推導 k-最鄰近分類法 模糊集合方法 倒傳遞類神經網路 遺傳演算法,10,圖5.3 分類規則法技術一覽表,11,第二節 決策樹歸納法,建構決策樹 決策樹演算法 決策樹修剪 萃取分類規則,12,決策樹的主要功能,決策樹的主要功能，是藉由分類已知的事例來建立一樹狀結構，並從中歸納出事例裡的某些規律；而產生出來的決策樹，也能利用來做樣本外的預測。,13,圖5.4 預估是否會玩網路遊戲決策樹,14,建構決策樹,決策樹的歸納演算法 將訓練樣本的原始資料放入決策樹的樹根。

4、 將原始資料分成兩組，一部份為訓練組資料，另一部份為測試組資料。 使用訓練資料來建立決策樹，而在每一個內部節點，則依據資訊理論(Information Theory)來評估選擇哪個屬性繼續做分支的依據。 使用測試資料來進行決策樹修剪，修剪到決策樹的每個分類都只有一個節點，以提升預測能力與速度。 將以上(1)-(4)步驟不斷遞迴進行，直到所有的新內部節點都是樹葉節點為止。,15,建構決策樹(c2),決策樹停止再往下衍生的特例情形 該群資料中，每一筆資料都已經歸類在同一類別下。 該群資料中，已經沒有辦法再找到新的屬性來進行節點分割。 該群資料中，已經沒有任何尚未處理的資料。,16,決策樹演算法,I

5、D3 (Iterative Dichotomizer 3) 可處理離散型資料。 兼顧高分類正確率以及降低決策樹的複雜度。 必須將連續型資料作離散化的程序。 CART (Classification and Regression Trees) 是以每個節點的動態臨界值作為條件判斷式。 CART藉由單一輸入的變數函數，在每個節點分隔資料，並建立一個二元決策樹 。 CART是使用 Gini Ratio來衡量指標，如果分散的指標程度很高，表示資料中分佈許多類別，相反的，如果指標程度越低，則代表單一類別的成員居多。,17,決策樹演算法(c2),C4.5 改良自ID3演算法。 先建構一顆完整的決策樹，再針

6、對每一個內部節點，依使用者定義的預估錯誤率(Predicted Error Rate)來作決策樹修剪的動作。 不同的節點，特徵值離散化結果是不相同的。 CHAID (Chi-Square Automatic Interaction Detector) 利用卡方分析(Chi-Square Test)預測二個變數是否需要合併，如能夠產生最大的類別差異的預測變數，將成為節點的分隔變數。 計算節點中類別的 P值 (P-Value)，以P值大小來決定決策樹是否繼續生長，所以不需像C4.5或CART要再做決策樹修剪的動作。,18,表5.1 決策樹演算法之比較,19,決策樹修剪,當原始訓練資料呈現不完整、稀

7、疏或是含有雜訊時，則容易造成決策樹超適(Overfitting)的問題，以致於所產生的決策樹太過於複雜，因此必須再做適當的修剪。 發生超適的主要原因有兩個： 屬性太多：演算法剛好選擇到和類別不相關的屬性。 偏差(Bias) ：每個演算法都有屬性選擇的偏好順序，因此可能發生演算法偏好的屬性，卻和類別毫不相關。,20,圖5.5 決策樹修剪過程,21,避免超適的方法,事前修剪(Pre-Pruning) 運用統計門檻值加以衡量，譬如卡方值或資訊獲得值等技術，評估是否該繼續分割某內部節點成數個子分支或是應該立刻停止。 事後修剪(Post-Pruning) 允許決策樹超適情形的合理存在，當完成決策樹的建立

8、之後，再來進行修剪的程序。,22,萃取分類規則,將決策樹中的每一個樹葉節點，依其樹狀路徑往上到達根節點的過程，由每個內部節點的分類標準建立出一條IF-THEN的規則。,23,第三節 貝氏分類,貝氏定理 樸素貝氏分類 貝氏信念網路 貝氏分類實際應用,24,貝氏定理,假設 是樣本空間( sample space) 的分割，且有一事件 ，則有兩定理存在： 總機率法則(Law of Total Probability ) 貝氏定理( Bayes Rule) 其中 ：事前機率( Prior Probability) ：樣本機率( Sample Probability) ：事後機率( Posterior

9、Probability),25,樸素貝氏分類,Naive Bayesian Classification 樸素貝氏分類，主要的運作原理，是透過訓練樣本，學習記憶分類根據所使用屬性的關係，產生這些訓練樣本的中心概念，再用學習後的中心概念對未歸類的資料物件，進行類別預測，以得到受測試資料物件的目標值。,26,貝氏信念網路,Bayesian Belief Network 貝氏信念網路採取使用聯合條件機率分配，但允許變數的子集有條件獨立，一個因果關係的圖形模型，使學習可以在此模型上操作，預測結果傳回一個類別的機率分配，而不是單一的類別標籤,27,圖5.8 貝氏信念網路與機率表概念圖,28,貝氏分類實際

10、應用,實際應用 彰化銀行希望能提升辨理信用卡的人次，假設目前考量辦卡的相關屬性有性別、年齡、學生身分、收入 四種。 分類目標 辦卡。 類別 會與不會。 結果 女性，年齡介於3145之間，不具學生身份，收入中等 會辦卡,29,表5.3 樸素貝氏分類器的應用實例,30,第四節 其他分類規則法,案例式推導 k-最鄰近分類法 模糊集合方法 倒傳遞類神經網路 遺傳演算法,31,案例式推導,案例式知識通常是用來描述屬於經驗的知識，而利用案例式知識來進行推論，稱為案例式推論（Case-based Reasoning；CBR）。 CBR是屬於人工智慧的問題解決方式，利用過去的案例和經驗去找出一個合適的解答來解

11、決目前所遇到的問題。,32,圖5.10 案例推論循環,33,k-最鄰近分類法,k-Nearest Neighbor Classifiers；K-NN Classifiers k-最鄰近分類法，又稱為最近鄰居決定法則，研究方法的概念是緣由統計的圖形辨識（Pattern Recognition）方法，用最直覺的方式來決定每一資料點所屬的類別，就是找出距離最近的點來判定資料點屬於哪一類。,34,圖5.11 K-NN (K = 4) 示意圖,T：目標案例 S：案例庫案例 i：屬性(向量值) f：案例庫案例中，目標案例第i個屬性的相似度函數 W i：第i個屬性的重要性權重,35,模糊集合方法,模糊理論是

12、由美國加州大學柏克萊分校的拉特飛扎德(Lotfi A. Zadeh)教授在1965年所提出的。 模糊理論是依照大概的資訊對人類主觀表現的概念作大略的定量化處理。,36,模糊集合方法(c2),定義 若A 為X 的一個模糊子集，對每個xX 都指定一個數A(x)0,1，用它表示x 對A 的歸屬度，而A(x)被稱為A 的成員函數，亦即任一映射(Mapping)到A： A：X0,1，xA(x), xX 範例 分別以100、80、60、50和0分為一個測驗是否理想的集合，則其模糊子集為100/1,80/0.8,60/0.6,50/0.4,0/0 此例可以知道100分是相當令人滿意故其歸屬度為1，而0分則讓

13、人非常失望所以歸屬度給予0。,37,倒傳遞類神經網路,倒傳遞演算法的網路訓練包含兩個階段：前饋階段以及倒傳遞階段。 前饋階段：輸入向量由輸入層開始輸入，並以前饋方式經由隱藏層傳至輸出層，最後計算出網路輸出值。在此階段，網路節點之間的鍵結值都是固定的。 倒傳遞階段：網路節點之間的鍵結值則根據錯誤更正法則來進行修正，並藉由鍵結值的修正，使修正後的網路輸出值能偏向於期望的輸出值。,38,圖5.15 倒傳遞類神經網路架構,39,遺傳演算法,遺傳演算法（Genetic Algorithm；GA或稱基因演算法）最早於1975年由密西根大學John Holland教授提出。 其主要構向與概念精神主要參照達爾

14、文的進化論中物競天擇、適者生存的自然進化法則，符合物種在自然環境系統中調適與更新的現象；,40,遺傳演算法(c2),基因演算法主要的構成要素 族群（Population） 染色體（Chromosomes） 基因（Genes） 基因演算法主要運算方式 選擇（Selection） 繁殖（Reproduction） 交換（Crossover） 突變（Mutation）,41,圖5.17 遺傳演算法程序圖,42,圖5.18 遺傳演算法流程圖,43,本章摘要,分類法是針對欲處理且未分類的資料集合，根據已知類別的物件集合，將欲處理資料依據其屬性去完成分類的過程，並冀望能學習分類的規則，提供未來能自動分類之

15、用。 決策樹的主要功能，是藉由分類已知的事例來建立一樹狀結構，並從中歸納出事例裡的某些規律；而產生出來的決策樹，也能利用來做樣本外的預測。,44,本章摘要(c2),決策樹建構的主要步驟有三種程序，包括(1)由適當的演算法來處理訓練資料並建立決策樹；(2)適當的修剪決策樹；(3)從決策樹中萃取知識規則。 目前最被廣泛使用的決策樹演算法，包括 ID3、CART、C4.5、CHAID等。 發生超適的主要原因有兩個：其一是屬性太多，演算法剛好選擇到和類別不相關的屬性；其二是偏差，亦即每個演算法都有屬性選擇的偏好順序，因此可能發生演算法偏好的屬性，卻和類別毫不相關。,45,本章摘要(c3),決策樹產生知

16、識規則的方法，是將決策樹中的每一個樹葉節點，依其樹狀路徑往上到達根節點的過程，由每個內部節點的分類標準建立出一條IF-THEN規則。 貝氏定理的優點在於結合事前機率與樣本機率，因此在分析時不需太多樣本數即可得到不錯的結果。,46,本章摘要(c4),樸素貝氏分類，是透過訓練樣本，學習記憶分類根據所使用屬性的關係，產生這些訓練樣本的中心概念，再用學習後的中心概念對未歸類的資料物件，進行類別預測，以得到受測試資料物件的目標值。 貝氏信念網路是使用聯合條件機率分配，允許變數的子集有條件獨立，並建立一個因果關係的圖形模型，使學習可以在此模型上操作，預測結果傳回一個類別的機率分配，而不是單一的類別標籤。,47,本章摘要(c5),案例式知識是用來描述屬於經驗的知識，是利用過去的案例和經驗去找出一個合適的解答，來解決目前所遇到的問題。 k-最鄰近分類法是先將一群已知別的物件，分成訓集和測試集，訓集經過某種方式訓後，選擇出一組考集的測試集，這個考集是訓集的子集合，最後再用測試集檢驗考集的分正確。,48,本章摘要(c6),模糊理論是為了解決生活中普