决策树演算法

1第五章資料分類法2第五章資料分類法簡介以決策樹為基礎之分類法非決策樹為基礎之分類法3何謂分類根據已知資料及其分類屬性值，建立資料的分類模型，接著利用此分類模型預測新資料的類別範例：顧客是否會購買筆記型電腦的分類模型婚姻年齡收入否是否否是單身已婚30=30低中高4分類法的特性與分類演算法分類法特性屬於機器學習(machinelearning)一種監督式的學習法(supervisedlearning)常用的分類演算法以決策樹為基礎的分類法包括ID3,PRISM,以及Gini索引非決策樹為基礎的分類法貝氏分類法、記憶基礎推論法、類神經分類法5分類的目的與應用分類目的分析影響資料歸類的因素預測資料所屬的類別(classlabel)分類應用信用額度核准(creditapproval)例如：根據預測的信用等級決定核卡額度目標行銷(targetmarketing)例如：找出會購買筆記型電腦的顧客屬性醫療診斷(medicaldiagnosis)例如：依病人的症狀判斷是否罹患SARS．．．6分類所需的資料前置處理資料一般化將連續性資料離散化，資料的數值分布精簡化避免分類的品質不佳特徵屬性選取(featureselection)找出具有關鍵影響的屬性，將無關屬性去除提高分類的精準度注意每筆建立分類模型的資料樣本，一定要有已知的分類標記(classlabel)，包含這個已知分類標記的屬性稱之為標記屬性是否購買筆記型電腦標記屬性7分類的程序建立模型利用現有資料找出分類模型模型的表示方式有：分類規則(classificationrules)決策樹(decisiontrees)數學公式(mathematicalformulas)評估模型將資料分成訓練樣本(trainingsamples)及測試樣本(testingsamples)第一階段利用訓練樣本來建立模型第二階段測試樣本評估準確性使用模型找出資料分類的原因預測新進資料類型8分類程序的範例(1)步驟1：建立模型訓練樣本姓名年齡婚姻收入購買筆記型電腦王大銘30單身高否陳倩茹30單身中否張明雄=30已婚高是田信程=30單身低是何偉業=30已婚高是林葳婷=30已婚低否分類模型婚姻年齡收入否是否否是單身已婚30=30低中高訓練樣本姓名年齡婚姻收入購買筆記型電腦王大銘30單身高否陳倩茹30單身中否張明雄=30已婚高是田信程=30單身低是何偉業=30已婚高是林葳婷=30已婚低否分類模型婚姻年齡收入否是否否是單身已婚30=30低中高婚姻年齡收入否是否否是單身已婚30=30低中高9分類程序的範例(2)步驟2：評估模型購買筆記型電腦?姓名年齡婚姻收入購買筆記型電腦黃欣怡=30單身中是胡志銘30單身中否劉志強30單身低否鄧喬賢=30已婚高否測試樣本否分類模型是胡志銘鄧喬賢婚姻年齡收入否是否否是單身已婚30=30低中高購買筆記型電腦?姓名年齡婚姻收入購買筆記型電腦黃欣怡=30單身中是胡志銘30單身中否劉志強30單身低否鄧喬賢=30已婚高否測試樣本否分類模型是是胡志銘鄧喬賢婚姻年齡收入否是否否是單身已婚30=30低中高婚姻年齡收入否是否否是單身已婚30=30低中高10分類程序的範例(3)步驟3：使用模型假設有一位新會員陳建成前來註冊，其基本資料為35歲，單身，低收入依分類模型所預測的結果為“是”，也就是此會員有可能會購買筆記型電腦該線上購物商店可對此會員進行一連串筆記型電腦的廣告行銷活動，例如寄送電子報，以促使顧客下單購買筆記型電腦11分類法的準確性訓練測試法(training-and-testing)資料樣本分為訓練和測試資料集，訓練資料集建立分類模型，利用測試資料集測試準確性適合用在樣本空間非常大的情況交互驗證法(cross-validation)資料樣本分成k個子樣本，輪流將k-1個子樣本當作訓練樣本，剩下一個子樣本當作測試樣本，重複做k次建立模型的工作之後，找出準確度最高的分類模型，也稱作k疊交互驗證法(k-foldcrossvalidation)適合用在樣本空間不多的情況自助法(bootstrapmethod)只留一筆資料當做測試樣本，其他全部拿來當訓練樣本，這是交互驗證法的特例適合用在樣本空間非常小的情況12分類演算法的評估(1)準確度速度建立分類模型的速度使用分類模型預測的速度品質藉由事後修剪(postpruning)降低分類模型複雜度可詮釋性(interpretability)能不能從建立出來的分類模型去歸納、解釋分類的原因13分類演算法的評估(2)其他的評估觀點健全性(robustness)考量分類法對於雜訊以及遺缺值(missingvalue)的處理能力擴展性(scalability)，考量分類法在資料樣本規模擴大時是否仍能在可容忍的時間內求得探勘的結果14第五章資料分類法簡介以決策樹為基礎之分類法非決策樹為基礎之分類法15何謂決策樹決策樹(Decisiontree)類似流程的樹狀結構。樹的中間節點(non-leafnodes)代表測試的條件樹的分支(branches)代表條件測試的結果樹的葉節點(leafnodes)代表分類後所得到的分類標記，也就是表示分類的結果16決策樹的產生程序與用途決策樹的產生程序步驟1:建立樹狀結構開始時，所有的訓練樣本都在根節點依據選取的屬性，重複地將樣本分隔開來步驟2:修剪樹狀結構辨識並且移除導致雜訊或特例的分支決策樹的用途：分類未知的樣本靠著決策樹測試樣本的屬性值17決策樹推論演算法(1)基本演算法(貪婪演算法，greedyalgorithm)樹結構是以由上而下，遞迴(recursive)各個擊破(divide-and-conquer)方式建立無法處理連續性的數值，數值屬性必須先轉換運作方式一開始，所有的訓練樣本都在根節點。屬性都是類別型態（若是連續型數值，事先做離散化）依據選取的屬性，反複地將樣本分隔開來。測試各屬性是不是以嘗試性或統計性測量（例如資訊獲利informationgain）為基礎，而挑選出來的18決策樹推論演算法(2)停止分支的條件當某分支子集合內的所有樣本都屬於同一個類別時可能所有的屬性都用完了，用多數投票法以樣本數較多的類別來代表此葉節點選取屬性之後產生某分支完全沒有測試樣本的情況19屬性選取量測法資訊獲利(Informationgain)ID3/C4.5/PRISM假設所有的屬性都是類別型態(categorical)可修改用在連續型數值的屬性Gini索引(Giniindex,IBMIntelligentMiner)假設所有的屬性都是連續型數值型態假設每個屬性都存在數個可能的切割值適用於連續性的數值型態屬性可能需要其他工具(例如分群)，來得到可能的分群值可修改用在類別型態的屬性20由決策樹採掘分類規則從根節點到葉節點的每一條路徑，便代表一條分類規則範例(圖5-1的決策樹為例)從根節點到最左邊的葉節點，所得之分類規則為IF婚姻狀態＝單身AND年齡＜30歲THEN購買筆記型電腦＝否完整規則IF婚姻狀態=單身AND年齡30歲THEN購買筆記型電腦=否IF婚姻狀態=單身AND年齡=30歲THEN購買筆記型電腦=是IF婚姻狀態=已婚AND收入=低THEN購買筆記型電腦=否IF婚姻狀態=已婚AND收入=中THEN購買筆記型電腦=否IF婚姻狀態=已婚AND收入=高THEN購買筆記型電腦=是21分類結果過度遷就過度遷就(over-fitting)問題有時會出現決策樹只對某一訓練資料集有效，更換另一組訓練資料集，預測結果產生錯誤雜訊或特例所造成的，分支太多必須適當修剪預先修剪(prepruning)：分支過程中進行品質量測事後修剪：先讓決策樹自由發展，再將多餘分支修剪22應用分類法的資料樣本範例年齡婚姻收入購買筆記型電腦24單身80k否28單身45k否35單身25k是32已婚40k否40已婚20k否42已婚22k否38已婚35k否29單身60k否22已婚18k否33已婚38k否25已婚55k是50已婚42k否35單身36k是45已婚28k否37單身44k是18單身25k否表5-123經前置處理之分類法資料樣本範例年齡婚姻收入購買筆記型電腦30單身高否30單身中否=30單身低是=30已婚中否=30已婚低否=30已婚低否=30已婚中否30單身高否30已婚低否=30已婚中否30已婚高是=30已婚中否=30單身中是=30已婚低否=30單身中是30單身低否表5-224決策樹演算法-ID3昆蘭(Quinlan)1979年所提出的決策樹演算法使用雪南(Shannon)於1949年所提出的資訊理論作為選擇測試屬性的依據25資訊理論(informationtheory)假設一個事件有n種結果，發生的機率分別為P(v1),…,P(vｎ)，這些機率都是已知的，則定義這個事件發生後所得到的資訊量為：各種結果發生機率愈平均，所求資訊量也愈大資訊量可以當作亂度(Entropy)的指標，資訊量愈大，表示亂度愈大解決屬性選擇的問題niiinvvvvPPPPI121)()())(,),((log26資訊獲利(1)假設分類結果為P(正例，positiveinstance)和N(反例，negativeinstance)A代表某一個屬性X代表屬性測試前的樣本集合X1,…,Xv代表屬性測試後的樣本子集合p代表Ｘ中正例的個數n代表反例的個數pi代表Ｘi中正例的個數ni代表Ｘi中反例的個數27資訊獲利(2)根據屬性A的值將X分為X1,…,Xv所得到的資訊獲利為：其中，當p,n皆不為0，當p或n任一為0)(),()(AEnpIAGainnpnnpnnppnppnpI22loglog,0),(npIiiviiinpInpnpAE,128利用資訊獲利做屬性選取資訊獲利即“測試前的資訊量”減“測試後的資訊量”分類的目的將訓練樣本分成亂度最小的子集合也就是所有樣本都屬於同一分類標記的子集合ID3中以測試後資訊量最小的屬性為優先選取，也就是選擇資訊獲利最大的屬性。29利用資訊獲利做屬性選取之範例(1)假設：P會購買筆記型電腦；N不會購買筆記型電腦以表5-2為例，16筆顧客資料中，曾購買NB有4筆，未曾買NB有12筆I(p,n)=I(4,12)=0.8113依照年齡將16位顧客分成兩群組：小於30歲：曾買NB有1筆，未買NB有5筆大於或等於30歲：曾買NB有3筆，未買NB有7筆)(),()(AEnpIAGain7946.0)7,3(1610)5,1(166)(IIageE0167.07946.08113.0)(年齡Gain30利用資訊獲利做屬性選取之範例(2)同理Gain(婚姻)=I(4,12)–(I(3,4)+I(1,8))=0.0972Gain(收入)=I(4,12)–(I(1,5)+I(2,5)+I(1,2))=0.0177三個屬性的資訊獲利都計算出來之後，發現婚姻屬性的資訊獲利最大，因此選擇婚姻作為第一個分類的依據。接下來根據婚姻的屬性值將資料樣本分成單身以及已婚兩個子集合分別考慮。用同樣的方法來分別決定左右分支下一個要選取的屬性。31決策樹演算法-PRISM(1987)以屬性值配對做為分類的依據非如ID3般單純以屬性做為分類的依據決策樹中間節點代表一種屬性與值的配對例如：婚姻＝單身，性別＝男，年齡30等定義A=x的資訊獲利公式，當p(A=x｜P)0PRISM_Gain(A=x)=0，當p(A=x｜P)=0適用於屬性較少的分類問題))()|((log_2xApPxApxAGainPRISM32