决策树演算法比较表

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