《决策树演算法比较表》由会员分享，可在线阅读，更多相关《决策树演算法比较表（69页珍藏版）》请在金锄头文库上搜索。
1、基本資料探勘技巧BasicDataMiningTechniquesPreparedby:Dr.Tsung-NanTsai,Chapter3,Datamining-951,Contents,建立決策樹之演算法有效率推論關聯法則的技巧了解關聯法則之支持度與涵蓋度K-means演算法了解如何運用基因演算法完成監督式學習與非監督式分群如何選擇資料探勘技巧以解決問題,Datamining-951,資料探勘技術,資料探勘,監督式學習模型,非監督式學習模型,屬性選擇與資料轉化,分群,樹型結構,關聯模式,規則誘發,決策樹(類別型屬性),迴歸樹(連續型屬性),C4.5/C5ID3,CART,CART,M5,CN
2、2,ITRULE,Cubist,3.1決策樹(DecisionTrees),Datamining-951,決策樹演算法,決策樹的建立只會使用資料集中最適屬性用以訓練建立決策樹。選擇資料子集訓練樣本建立決策樹完全正確分類YesStop。選擇資料子集訓練樣本建立決策樹分類錯誤加入新的樣本正確分類YesStop。,決策樹演算法,令T為訓練資料的集合於T集合中選擇一個最具區別能力的屬性.利用最具區別能力屬性建立一個節點樹自此節點開始建立子鏈結，每一個鏈結對上層所選取的屬性而言都代表一個唯一值。應用子鏈結的值以進一步將範例切割成子類別。對產生於step3之子類別而言：若子類別中範例滿足先前定義的準則，且
3、剩餘屬性集合並不符合樹的路徑，則採用新的範例以供建立新的分類。若子類別無法滿足準則且至少有一個屬性可用以切割路徑，則令T為目前子類別範例集合並回到step2.,Datamining-951,決策樹演算法,選擇適當代表屬性主要用以決定樹的大小，並減少樹的高度與節點數量。C4.5演算法：假設有n個可能結果，C4.5利用-log2(1/n)個位元來配置。Forexample:n=4,-log2(1/4)=2.可能結果為(00,01,10,11)。即兩個位元可單獨表示四個類別。若選擇屬性A，其-log2(1/2)=11個位元可表示兩個可能結果。Lift(增益值)=1C4.5獲益率C4.5應用獲益率測量
4、法決定一個最好的屬性選擇,Datamining-951,C4.5,Quinlan(1979)提出，以Shannon(1949)的資訊理論為依據。若一事件有k種結果,對應的機率為pi。則此事件發生後所得到的資訊量I(視為Entropy-增益率)為：I=-(p1log2(p1)+p2log2(p2)+pklog2(pk)Example1:設k=4p1=0.25,p2=0.25,p3=0.25,p4=0.25I=-(0.25log2(0.25)4)=2Example2:設k=2p1=0,p2=0.5,p3=0,p4=0.5I=-(0.5log2(0.5)2)=1Example3:設k=1p1=1,p
5、2=0,p3=0,p4=0I=-(1log2(1)=0,Datamining-951,決策樹演算法比較表,(Categorical),(Categorical),(Continuous),Datamining-951,範例,Datamining-951,最高節點,輸出:壽險促銷,精確度:11/15=0.73分數=0.73/4=0.183,Datamining-951,Seepage.72,精確度:9/15=0.6分數=0.6/2=0.3,Datamining-951,精確度:12/15=0.8分數=0.8/2=0.4,最佳節點,信用卡促銷資料庫,Datamining-951,C4.5,Data
6、mining-951,C4.5,Datamining-951,ID3,Datamining-951,ID3,Datamining-951,信用卡促銷,Datamining-951,信用卡促銷,Datamining-951,信用卡促銷,ARulefortheTreeinFigure3.4,Datamining-951,其他建立決策樹方法,CART:為數個商業產品應用.迴歸樹採行決策樹形式。CART與C4.5差別：CART採行二元分裂(數值與類別皆可)CART利用測試資料以幫助刪除並歸納一顆二元樹。CHAID:建立於SAS與SPSS中。限制只從事類別型屬性值。,決策樹優點,容易了解。將關係映射成一
7、些生產法則。可應用於實務問題上。資料探勘過程勿須預先假設。可處理類別型資料。,決策樹缺點,輸出屬性需為類別型.只允許一個輸出屬性.決策樹不穩定.若自數值型資料產生決策樹之過程可能非常複雜.,3.2產生關聯法則,Datamining-951,親和力分析,親和力分析(affinityanalysis)：決定事物結合一起與否的一般化過程。購物籃分析：決定顧客可能一起購買的物項。輸出為有關顧客購買行為的關聯集合。關聯法則允許多個輸出屬性Example:買牛奶也會買麵包買麵包以會買牛奶買牛奶/蛋也會買起司麵包,Datamining-951,信賴度與支撐度,法則“IfAthenB”,其信賴度為條件機率，當
8、A為真而B亦為真之條件機率。Example:假設共有10,000筆購買牛奶與麵包紀錄，買牛奶又同時買麵包有5000筆，則其信賴度為5000/10000=50%。支撐(持)度：Theminimumpercentageofinstancesinthedatabasethatcontainallitemslistedinagivenassociationrule.在交易中所佔比率。符合一條關聯法則所包含資料庫中最小範例百分比。,探勘關聯法則例子,Datamining-951,關聯法則例子,Apriori演算法:推論出項目集合(itemset)。項目及合為屬性-數值所組成。推論過程中若項目集合符合收斂
9、準則，則被捨棄。Apriori推論步驟：集合項目推論使用推論出的集合項目產出關聯法則利用表3.3進行推論，(已去除收入範圍與年齡),Datamining-951,關聯法則例子,第1步驟設定4個項目屬性值所需最小信賴度(3)。,7Y/3N,Datamining-951,關聯法則例子,Datamining-951,關聯法則例子,Datamining-951,二個項目集合規則,三個項目集合表:雜誌促銷=是且手錶促銷=否且壽險促銷=否(只有一筆,故不加入)手錶促銷=否且壽險促銷=否且信用卡=否(無),總共7筆為雜誌促銷=是其中5筆雜誌促銷與壽險促銷=是,Seepage.83and84,Datamini
10、ng-951,三個項目集合規則,第3步驟:利用二個項目集合表中屬性質推論三個項目集合。,1,手錶促銷=否且壽險促銷=否且信用卡保險=否(符合門檻值3),Datamining-951,三個項目集合規則,Datamining-951,一般考量,Weareinterestedinassociationrulesthatshowaliftinproductsaleswheretheliftistheresultoftheproductsassociationwithoneormoreotherproducts.吾輩只對具有高度增益值之關聯規則產生興趣,其增益值說明一個或以上產品之產品銷售量關連。Wea
11、realsointerestedinassociationrulesthatshowalowerthanexpectedconfidenceforaparticularassociation.吾亦對關聯規則之特定關聯信賴度低於預期信賴度。(代表品項間相互競爭或互補效應),Datamining-951,3.3k-means演算法,ChooseavalueforK(總分群數)thetotalnumberofclusters.RandomlychooseKpoints(資料點)asclustercenters(群組中心).最初群組中心Assigntheremaininginstancestothei
12、rclosestclustercenter.利用歐幾得距離分配剩餘的資料點Calculateanewclustercenterforeachcluster.計算各群集新的平均點(群組中心)Repeatsteps3-5untiltheclustercentersdonotchange.(重複3-5步驟直到群組中心未改變),Datamining-951,K-means範例,包含兩個屬性例子說明之。屬性x與y，硬設置x-y座標系統，映射圖如圖3.6所示。,Datamining-951,K-means範例(圖3.6),C2,C1,Datamining-951,K-means範例,步驟1:選擇一個K=2
13、，隨機選擇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,Datamining-951,K-means範例,C1包含範例1and2.C2包含3,4,5,6.再計算各個群集中心。C1:x=(1.0+1.0)/2=1.0y=(1.5+4.5)/2=3.0C2:x=(2.0+2.0+3.0+5.0)/4=3.0y=(1.5+3.5+2.5+6.0)/4=3.375新的群集中心C1=(1.0,3.0)andC2=(
14、3.0,3.375)重複第二步驟。Seepage.89,Datamining-951,K-means範例,Datamining-951,K-means範例,Datamining-951,K-means範例-Tanagra,Datamining-951,K-means之一般考量,無法得到最佳解需要數值型資料.吾輩必須設定群集數.只有群集大小接近時方可得到最佳分群績效.無法保證哪一個屬性之重要性較高.缺乏解釋能力.,Datamining-951,3.4基因演算法(Geneticalgorithm),基因演算法乃應用進化論方法至學習模型中，其由JohnHolland(1986)所發展出，以達爾文的物
15、競天擇原則為基。應用面包括：排程最佳化、旅行銷售員路徑排定、交換式網路的路由問題、基因演算法可用以代替監督式與非監督式的資料探勘作業。,Datamining-951,3.4基因演算法(GA),基因演算法：自n個元素中給訂初始母群P，如同細胞中之染色體般可做為未來可能的答案。直到滿足一個終止條件：使用一個適應函數評價目前每一個解答，若某一個元素符合適應函數所定義之標準，則其被保留於P中。此母群所包含m個元素(mn)，使用基因運算子來推論(n-m)個新元素，在姜新元素加到母群中。,Datamining-951,3.4基因演算法(GA),Datamining-951,GA流程圖,Datamining
16、-951,編碼,Datamining-951,3.4基因演算法,基因學習操作元選擇機制(Selection)交配機制(Crossover)突變機制(Mutation),Datamining-951,選擇,輪盤法(RouletteWheelselection)競爭法(Tournamentselection)穩態法(Steady-stateselection)排序與尺規法(Rankingandscaling)共享法(Sharing),Datamining-951,交配,GAs運算模式之核心部分：交配。其參照使用者所設定之交配率，自各母體中選擇數條染色體組中挑選兩兩交換彼此之基因內容，期產生更優秀之基因組合。算數運算交配(ArithmeticalCrossover)啟發式運算交配(HeuristicCrossover),Datamining-951,突變,為了避免落入局部最佳解中之方式。一般而言突變之目的有二開拓新的搜尋範圍，使得求解之範圍
