决策树演算法比较表

1、基本資料探勘技巧 Basic Data Mining Techniques Prepared by: Dr. Tsung-Nan Tsai,Chapter 3,Data mining-951,Contents,建立決策樹之演算法 有效率推論關聯法則的技巧 了解關聯法則之支持度與涵蓋度 K-means 演算法 了解如何運用基因演算法完成監督式學習與非監督式分群 如何選擇資料探勘技巧以解決問題,Data mining-951,資料探勘技術,資料探勘,監督式學習模型,非監督式學習模型,屬性選擇與資料轉化,分群,樹型結構,關聯模式,規則誘發,決策樹 (類別型屬性),迴歸樹 (連續型屬性),C4.5/C

2、5 ID3,CART,CART,M5,CN2,ITRULE,Cubist,3.1 決策樹 (Decision Trees),Data mining-951,決策樹演算法,決策樹的建立只會使用資料集中最適屬性用以訓練建立決策樹。 選擇資料子集訓練樣本建立決策樹完全正確分類Yes Stop。 選擇資料子集訓練樣本建立決策樹分類錯誤加入新的樣本正確分類Yes Stop。,決策樹演算法,令 T 為訓練資料的集合 於T集合中選擇一個最具區別能力的屬性. 利用最具區別能力屬性建立一個節點樹 自此節點開始建立子鏈結，每一個鏈結對上層所選取的屬性而言都代表一個唯一值。 應用子鏈結的值以進一步將範例切割成子類別

3、。 對產生於step 3之子類別而言： 若子類別中範例滿足先前定義的準則，且剩餘屬性集合並不符合樹的路徑，則採用新的範例以供建立新的分類。 若子類別無法滿足準則且至少有一個屬性可用以切割路徑，則令 T 為目前子類別範例集合並回到 step 2.,Data mining-951,決策樹演算法,選擇適當代表屬性主要用以決定樹的大小，並減少樹的高度與節點數量。 C4.5演算法： 假設有n個可能結果，C4.5利用-log2(1/n)個位元來配置。For example: n=4, -log2(1/4)=2. 可能結果為 (00, 01, 10, 11) 。即兩個位元可單獨表示四個類別。若選擇屬性A，其

4、 -log2(1/2)=1 1個位元可表示兩個可能結果。 Lift(增益值) = 1 C4.5 獲益率 C4.5 應用獲益率測量法決定一個最好的屬性選擇,Data mining-951,C4.5,Quinlan(1979)提出，以Shannon(1949)的資訊理論為依據。 若一事件有k種結果,對應的機率為pi。則此事件發生後所得到的資訊量I(視為Entropy-增益率)為： I= -(p1 log2(p1)+ p2 log2(p2)+ pklog2(pk) Example 1: 設 k=4 p1=0.25, p2=0.25, p3=0.25, p4=0.25 I=-(0.25 log2(0.

5、25) 4)=2 Example 2: 設 k=2 p1=0, p2=0.5, p3=0, p4=0.5 I=-(0.5 log2(0.5) 2)=1 Example 3: 設 k=1 p1=1, p2=0, p3=0, p4=0 I=-(1 log2(1)=0,Data mining-951,決策樹演算法比較表,(Categorical),(Categorical),(Continuous),Data mining-951,範例,Data mining-951,最高節點,輸出: 壽險促銷,精確度: 11/15=0.73 分數=0.73/4=0.183,Data mining-951,See

6、page.72,精確度: 9/15=0.6 分數=0.6/2=0.3,Data mining-951,精確度: 12/15=0.8 分數=0.8/2=0.4,最佳節點,信用卡促銷資料庫,Data mining-951,C4.5,Data mining-951,C4.5,Data mining-951,ID3,Data mining-951,ID3,Data mining-951,信用卡促銷,Data mining-951,信用卡促銷,Data mining-951,信用卡促銷,A Rule for the Tree in Figure 3.4,Data mining-951,其他建立決策樹方法

7、,CART:為數個商業產品應用. 迴歸樹採行決策樹形式。 CART與C4.5差別： CART 採行二元分裂(數值與類別皆可) CART利用測試資料以幫助刪除並歸納一顆二元樹。 CHAID: 建立於SAS與SPSS中。限制只從事類別型屬性值。,決策樹優點,容易了解。 將關係映射成一些生產法則。 可應用於實務問題上。 資料探勘過程勿須預先假設。 可處理類別型資料。,決策樹缺點,輸出屬性需為類別型. 只允許一個輸出屬性. 決策樹不穩定. 若自數值型資料產生決策樹之過程可能非常複雜.,3.2 產生關聯法則,Data mining-951,親和力分析,親和力分析(affinity analysis) ：

8、決定事物結合一起與否的一般化過程。 購物籃分析：決定顧客可能一起購買的物項。 輸出為有關顧客購買行為的關聯集合。 關聯法則允許多個輸出屬性 Example: 買牛奶也會買麵包 買麵包以會買牛奶 買牛奶/蛋 也會買 起司麵包,Data mining-951,信賴度與支撐度,法則“If A then B”, 其信賴度為條件機率，當A為真而B亦為真之條件機率。 Example: 假設共有10,000筆購買牛奶與麵包紀錄，買牛奶又同時買麵包有5000筆，則其信賴度為5000/10000=50%。 支撐(持)度：The minimum percentage of instances in the dat

9、abase that contain all items listed in a given association rule. 在交易中所佔比率。符合一條關聯法則所包含資料庫中最小範例百分比。,探勘關聯法則例子,Data mining-951,關聯法則例子,Apriori演算法: 推論出項目集合(item set) 。項目及合為屬性-數值所組成。推論過程中若項目集合符合收斂準則，則被捨棄。 Apriori 推論步驟： 集合項目推論 使用推論出的集合項目產出關聯法則 利用表3.3進行推論，(已去除收入範圍與年齡),Data mining-951,關聯法則例子,第1步驟設定4個項目屬性值所需最小

10、信賴度(3) 。,7Y/3N,Data mining-951,關聯法則例子,Data mining-951,關聯法則例子,Data mining-951,二個項目集合規則,三個項目集合表: 雜誌促銷=是 且 手錶促銷=否 且 壽險促銷=否 (只有一筆, 故不加入) 手錶促銷=否 且 壽險促銷=否 且 信用卡=否 (無),總共7筆為雜誌促銷=是 其中5筆雜誌促銷與壽險促銷=是,See page. 83 and 84,Data mining-951,三個項目集合規則,第3步驟: 利用二個項目集合表中屬性質推論三個項目集合。,1,手錶促銷=否 且 壽險促銷=否 且 信用卡保險=否 (符合門檻值 3)

11、,Data mining-951,三個項目集合規則,Data mining-951,一般考量,We are interested in association rules that show a lift in product sales where the lift is the result of the products association with one or more other products. 吾輩只對具有高度增益值之關聯規則產生興趣, 其增益值說明一個或以上產品之產品銷售量關連。 We are also interested in association rules t

12、hat show a lower than expected confidence for a particular association. 吾亦對關聯規則之特定關聯信賴度低於預期信賴度。(代表品項間相互競爭或互補效應),Data mining-951,3.3 k-means 演算法,Choose a value for K(總分群數) the total number of clusters. Randomly choose K points (資料點) as cluster centers (群組中心). 最初群組中心 Assign the remaining instances to

13、their closest cluster center.利用歐幾得距離分配剩餘的資料點 Calculate a new cluster center for each cluster. 計算各群集新的平均點(群組中心) Repeat steps 3-5 until the cluster centers do not change.(重複3-5步驟直到群組中心未改變),Data mining-951,K-means 範例,包含兩個屬性例子說明之。 屬性x與y，硬設置x-y座標系統，映射圖如圖3.6所示。,Data mining-951,K-means 範例 (圖3.6),C2,C1,Data

14、 mining-951,K-means 範例,步驟1: 選擇一個K=2，隨機選擇2個點表示最初群集中心。 假設範例1, 3為兩個群集中心。,(1-1)2+1.5-1.5)20.5=0,(2-1)2+1.5-1.5)20.5=1,(1-1)2+1.5-4.5)20.5=3,(2-1)2+1.5-4.5)20.5=3.16,Data mining-951,K-means 範例,C1包含範例1 and 2. C2包含3, 4, 5, 6. 再計算各個群集中心。 C1: x=(1.0+1.0)/2 = 1.0 y=(1.5+4.5)/2 = 3.0 C2: x=(2.0+2.0+3.0+5.0)/4=

15、3.0 y=(1.5+3.5+2.5+6.0)/4=3.375 新的群集中心 C1=(1.0, 3.0) and C2=(3.0, 3.375) 重複第二步驟。See page. 89,Data mining-951,K-means 範例,Data mining-951,K-means 範例,Data mining-951,K-means 範例 - Tanagra,Data mining-951,K-means之一般考量,無法得到最佳解 需要數值型資料. 吾輩必須設定群集數. 只有群集大小接近時方可得到最佳分群績效. 無法保證哪一個屬性之重要性較高. 缺乏解釋能力.,Data mining-9

16、51,3.4 基因演算法 (Genetic algorithm),基因演算法乃應用進化論方法至學習模型中，其由John Holland (1986)所發展出，以達爾文的物競天擇原則為基。 應用面包括：排程最佳化、旅行銷售員路徑排定、交換式網路的路由問題、 基因演算法可用以代替監督式與非監督式的資料探勘作業。,Data mining-951,3.4 基因演算法 (GA),基因演算法： 自n個元素中給訂初始母群P，如同細胞中之染色體般可做為未來可能的答案。 直到滿足一個終止條件： 使用一個適應函數評價目前每一個解答，若某一個元素符合適應函數所定義之標準，則其被保留於P中。 此母群所包含m個元素(m

17、n) ，使用基因運算子來推論(n-m)個新元素，在姜新元素加到母群中。,Data mining-951,3.4 基因演算法 (GA),Data mining-951,GA流程圖,Data mining-951,編碼,Data mining-951,3.4 基因演算法,基因學習操作元 選擇機制(Selection) 交配機制(Crossover) 突變機制(Mutation),Data mining-951,選擇,輪盤法(Roulette Wheel selection) 競爭法(Tournament selection) 穩態法(Steady-state selection) 排序與尺規法(R

18、anking and scaling) 共享法(Sharing),Data mining-951,交配,GAs運算模式之核心部分：交配。其參照使用者所設定之交配率，自各母體中選擇數條染色體組中挑選兩兩交換彼此之基因內容，期產生更優秀之基因組合。 算數運算交配(Arithmetical Crossover) 啟發式運算交配(Heuristic Crossover),Data mining-951,突變,為了避免落入局部最佳解中之方式。一般而言突變之目的有二 開拓新的搜尋範圍，使得求解之範圍有無限種可能 重新導入求解過程中不小心遺失之優秀基因，使其可以再加入運算中,基因演算法與監督式學習,Data

19、 mining-951,基因演算法與監督式學習,P,新的元素,Data mining-951,範例,使用一個促銷信用卡資料庫的子集合，建立可區分哪些接受壽險促銷或沒有接受壽險促銷之個體。,類別型,Data mining-951,範例,使用一個促銷信用卡資料庫的子集合，建立可區分哪些接受壽險促銷或沒有接受壽險促銷之個體。,Data mining-951,範例,使用一個促銷信用卡資料庫的子集合，建立可區分哪些接受壽險促銷或沒有接受壽險促銷之個體。,Data mining-951,範例,使用一個促銷信用卡資料庫的子集合，建立可區分哪些接受壽險促銷或沒有接受壽險促銷之個體。,Genetic Algor

20、ithms and Unsupervised Clustering,Data mining-951,非監督是基因分群法,Data mining-951,非監督是基因分群法,Data mining-951,GA 一般考量,Global optimization is not a guarantee. The fitness function determines the complexity of the algorithm. Explain their results provided the fitness function is understandable. Transforming the data to a form suitable for genetic learning can be a challenge.,Data mining-951,3.5 選擇資料探勘技術,Is learning supervised or unsupervised? Is explanation required? W