【正文】 fier N a m e G i v e B i r t h C a n F l y L i v e i n W a t e r H a v e L e g s C l a s sh u m a n y e s no no y e s m a m m a l sp y t h o n no no no no n o n m a m m a l ss a l m o n no no y e s no n o n m a m m a l sw h a l e y e s no y e s no m a m m a l sf r o g no no s o m e t i m e s y e s n o n m a m m a l sk o m o d o no no no y e s n o n m a m m a l sb a t y e s y e s no y e s m a m m a l sp i g e o n no y e s no y e s n o n m a m m a l sc a t y e s no no y e s m a m m a l sl e o p a r d s h a r k y e s no y e s no n o n m a m m a l st u r t l e no no s o m e t i m e s y e s n o n m a m m a l sp e n g u i n no no s o m e t i m e s y e s n o n m a m m a l sp o r c u p i n e y e s no no y e s m a m m a l seel no no y e s no n o n m a m m a l ss a l a m a n d e r no no s o m e t i m e s y e s n o n m a m m a l sg i l a m o n s t e r no no no y e s n o n m a m m a l sp l a t y p u s no no no y e s m a m m a l so w l no y e s no y e s n o n m a m m a l sd o l p h i n y e s no y e s no m a m m a l se a g l e no y e s no y e s n o n m a m m a l sG i v e B i r t h C a n Fl y Li v e i n W a t e r H a v e Legs C l a s sy e s no y e s no ?2013)()|(207)()|(1341331310131)|(72727676)|(????????????????NPNAPMPMAPNAPMAPA: attributes M: mammals N: nonmammals P(A|M)P(M) P(A|N)P(N) = Mammals Na239。 ? 當(dāng)樹(shù)的規(guī)模變得太大時(shí)，即使訓(xùn)練誤差還在繼續(xù)降低，但是檢驗(yàn)誤差開(kāi)始增大，導(dǎo)致 模型過(guò)分?jǐn)M合 模型模型過(guò)分?jǐn)M合和擬合不足 過(guò)分?jǐn)M合 導(dǎo)致過(guò)分?jǐn)M合的原因 導(dǎo)致過(guò)分?jǐn)M合的原因 ? 噪聲導(dǎo)致的過(guò)分?jǐn)M合 – 例子：哺乳動(dòng)物的分類問(wèn)題 – 十個(gè)訓(xùn)練記錄中有兩個(gè)被錯(cuò)誤標(biāo)記：蝙蝠和鯨 – 如果完全擬合訓(xùn)練數(shù)據(jù)，決策樹(shù) 1的訓(xùn)練誤差為 0，但它在檢驗(yàn)數(shù)據(jù)上的誤差達(dá) 30%.人和海豚，針鼴誤分為非哺乳動(dòng)物 – 相反，一個(gè)更簡(jiǎn)單的決策樹(shù) 2，具有較低的檢驗(yàn)誤差（10%），盡管它的訓(xùn)練誤差較高，為 20% – 決策樹(shù) 1過(guò)分?jǐn)M合了訓(xùn)練數(shù)據(jù)。 ? 多重比較過(guò)程與模型過(guò)分?jǐn)M合有什么關(guān)系？ – 在決策樹(shù)增長(zhǎng)過(guò)程中，可以進(jìn)行多種測(cè)試，以確定哪個(gè)屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。因此，分類模型評(píng)估應(yīng)把模型復(fù)雜度考慮進(jìn)去 ? 方法：悲觀誤差估計(jì)、最小描述長(zhǎng)度原則（ MDL） 悲觀誤差評(píng)估 ? 悲觀誤差估計(jì)公式： ? Q(ti)為每個(gè)結(jié)點(diǎn) ti的罰分， e(T)為訓(xùn)練樣本集的錯(cuò)分樣本數(shù)， Nt為訓(xùn)練樣本總數(shù)， k為葉結(jié)點(diǎn)數(shù)。 – 然而，對(duì)于后剪枝，當(dāng)子樹(shù)被剪掉后，生長(zhǎng)完全決策樹(shù)的額外開(kāi)銷(xiāo)就被浪費(fèi)了。 ? ROC 曲線上有幾個(gè)關(guān)鍵點(diǎn)，它們有公認(rèn)的解釋： – （ TPR=0， FPR=0）：把每個(gè)實(shí)例都預(yù)測(cè)為負(fù)類的模型 – （ TPR=1， FPR=1）：把每個(gè)實(shí)例都預(yù)測(cè)為正類的模型 – （ TPR=1， FPR=0）：理想模型 使用 ROC曲線比較模型 ? 沒(méi)有哪個(gè)模型能夠壓倒對(duì)方 ? FRR,M1 較好 ? FRR, M2較好 ? ROC曲線下方的面積 ? 理想情況 : ? 面積 = 1 ? 隨機(jī)猜測(cè) : ? 面積 = 怎樣產(chǎn)生 ROC曲線 Class + + + + + P TP 5 4 4 3 3 3 3 2 2 1 0 FP 5 5 4 4 3 2 1 1 0 0 0 TN 0 0 1 1 2 3 4 4 5 5 5 FN 0 1 1 2 2 2 2 3 3 4 5 TPR 1 0 FPR 1 1 0 .4 0 0 0 Threshold = ROC 曲線 : 。 – 修剪有兩種做法 : ? 用新的葉結(jié)點(diǎn)替換子樹(shù)，該葉結(jié)點(diǎn)的類標(biāo)號(hào)由子樹(shù)下記錄中的多數(shù)類確定 ?用子樹(shù)中最常用的分支代替子樹(shù) 處理決策樹(shù)中的過(guò)分?jǐn)M合 … – 與先剪枝相比，后剪枝技術(shù)傾向于產(chǎn)生更好的結(jié)果。用訓(xùn)練誤差提供對(duì)泛化誤差的樂(lè)觀估計(jì) – 結(jié)合模型復(fù)雜度 – 估計(jì)統(tǒng)計(jì)上界 – 使用確定集 結(jié)合模型復(fù)雜度 ? 奧卡姆剃刀 （ Occam39。 過(guò)分?jǐn)M合與多重比較 ? 模型的過(guò)分?jǐn)M合可能出現(xiàn)在使用多重比較過(guò)程的算法中 ? 多重比較的例子：考慮未來(lái)十個(gè)交易日股市是升還是降 – 一個(gè)人十次猜測(cè)至少正確預(yù)測(cè)八次的概率是： – 假設(shè)從 50個(gè)股票分析家中選擇一個(gè)投資顧問(wèn)，策略是選擇在未來(lái)的十個(gè)交易日做出最多正確預(yù)測(cè)的分析家。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí)結(jié)構(gòu)。ve Bayes Classifier P(Re fun d=Ye s| No ) = 3/7P(Re fun d=No | No ) = 4/7P(Re fun d=Ye s| Ye s) = 0P(Re fun d=No | Ye s) = 1P(Mari tal Status=Sin gl e| No ) = 2/7P(Mari tal Status=Di vorce d| No )=1/7P(Mari tal Status=Marri ed | No ) = 4/7P(Mari tal Status=Sin gl e| Ye s) = 2/7P(Mari tal Status=Di vorce d| Ye s)=1/7P(Mari tal Status=Marri ed | Ye s) = 0For t ax ab le inco me:If class=No : samp le mea n=11 0samp le varia nce =297 5If class=Yes: samp le mea n=90samp le varia nce =25nai ve Bayes Cl assifie r:120K)IneMarr ied,No,Refund( ???X? P(X|Class=No) = P(Refund=No|Class=No) ? P(Married| Class=No) ? P(Ine=120K| Class=No) = 4/7 ? 4/7 ? = ? P(X|Class=Yes) = P(Refund=No| Class=Yes) ? P(Married| Class=Yes) ? P(Ine=120K| Class=Yes) = 1 ? 0 ? ? 109 = 0 Since P(X|No)P(No) P(X|Yes)P(Yes) Therefore P(No|X) P(Yes|X) = Class = No Given a Test Record: Na239。當(dāng)其發(fā)生時(shí)所攜信息量就少。 c )。 ?一個(gè)具體樣本的形式可為 :( v1, v2, ..., vn。反過(guò)來(lái)， 值越小，需要較少信息量就能確定 的發(fā)生，即事件 隨機(jī)性較小。ve Bayes Classifier ? Assume independence among attributes Ai when class is given: – P(A1, A2, …, An | Cj ) = P(A1| Cj) P(A2| Cj)… P(An| Cj) – Can estimate P(Ai| Cj) for all Ai and Cj. – New point is classified to Cj if P(Cj) ? j P(Ai| Cj)= P(Cj) P(A1| Cj) P(A2| Cj)… P(An| Cj) is maximal. How to Estimate Probabilities from Data? ? Class: P(C) = Nc/N – ., P(No) = 7/10, P(Yes) = 3/10 ? For discrete attributes: P(Ai | Ck) = |Aik|/ Nc – where |Aik| is number of instances having attribute Ai and belongs to class Ck – Examples: P(Status=Married|No) = 4/7 P(Refund=Yes|Yes)=0 k T i d R e f u n d M a r i t a l S t a t u s T a x a b l e I n c o m e E v a d e 1 Y e s S i n g l e 125K No 2 No M a r r i e d 100K No 3 No S i n g l e 70K No 4 Y e s M a r r i e d 120K No 5 No D i v o r c e d 95K Y e s 6 No M a r r i e d 60K No 7 Y e s D i v o r c e d 220K No 8 No S i n g l e 85K Y e s 9 No M a r r i e d 75K No 10 No S i n g l e 90K Y e s 10 categori calcategori calconti nuouscl assHow to Estimate Probabilities from Data? ? For continuous attributes: – Discretize the range into bins ? one ordinal attribute per bin ? violates independence assumption – Twoway split: (A v) or (A v) ? choose only one of