【正文】 ROC (Receiver Operating Characteristic) ? ROC曲線是顯示分類器真正率（ TPR）和假正率（ FPR）之間折中的一種圖形化方法。 ? 召回率度量被分類器正確預(yù)測的正樣本的比例。 不平衡類問題 PREDICTED CLASS ACTUAL CLASS Class=Yes Class=No Class=Yes a (TP) b (FN) Class=No c (FP) d (TN) FNFPTNTPTNTPdcbada?????????? A c c u r a c y ）準確率（準確率的缺點 ? 考慮 2類問題 – 類 0的樣本數(shù) = 9990 – 類 1的樣本數(shù) = 10 ? 如果模型預(yù)測所有的樣本為類 0, 準確率為 9990/10000 = % – 準確率的值具有欺騙性 – 模型并沒有分對類 1的任何樣本 度量 TPT P RFPF P RFNF N RT P F NP r e c is ion ( p) R e c a l l ( r )2 2 *F 1 F m e a sur e ( F )2*T P FNTNT N RT N FPT N FPTPT P FPTPT P FNrp T Pr p T P T P FN??????????????? ? ?真正率真負率假正率假負率精度召回率度量? 精度確定在分類器斷言為正類的那部分記錄中實際為正類的記錄所占的比例。 – 因為不像先剪枝，后剪枝是根據(jù)完全增長的決策樹作出的剪枝決策，先剪枝則可能過早終止決策樹的生長。 處理決策樹中的過分擬合 … ? 后剪枝 – 在該方法中，初始決策樹按照最大規(guī)模生長，然后進行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。 ? 該方法為評估模型在未知樣本上的性能提供了較好辦法。 tkiikiiiNTQTetntQteTe)()()()]()([)(39。s Razor ）：給定兩個具有相同泛化誤差的模型，較簡單的模型比復(fù)雜的模型更可取 ? 因為復(fù)雜模型中的附加成分很大程度上是偶然的擬合。 ? 估計泛化誤差的方法 – 使用再代入估計。 泛化誤差估計 ? 過分擬合的主要原因一直是個爭辯的話題，但大家還是普遍同意模型的復(fù)雜度對模型的過分擬合有影響。 – 在這種情況下，算法實際上是使用多重比較過程來決定是否需要擴展決策樹。 – 該策略的缺點是，即使所有的分析家都用隨機猜測做出預(yù)測，至少有一個分析家做出八次正確預(yù)測的概率是：1（ ） 50=，這一結(jié)果相當高。 ? 這個例子清楚的表明，當決策樹的葉結(jié)點沒有足夠的代表性樣本時，很可能做出錯誤的預(yù)測。 ? 例子：五個訓(xùn)練記錄，所有的記錄都是正確標記的，對應(yīng)的決策樹盡管訓(xùn)練誤差為 0，但檢驗誤差高達 30% ? 人、大象和海豚被誤分類，因為決策樹把恒溫但不冬眠的動物分為非哺乳動物。因為屬性測試條件 4條腿具有欺騙性，它擬合了誤標記的訓(xùn)練紀錄，導(dǎo)致了對檢驗集中記錄的誤分類 噪聲導(dǎo)致的過分擬合（例子） 噪聲導(dǎo)致決策邊界的改變 缺乏代表性樣本導(dǎo)致的過分擬合 ? 根據(jù)少量訓(xùn)練記錄做出分類決策的模型也容易受過分擬合的影響。 ? 隨著決策樹中結(jié)點數(shù)的增加，模型的訓(xùn)練誤差和檢驗誤差都會隨之下降。 ? 當訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高，這種情況成為模型 過分擬合 模型過分擬合和擬合不足 ? 當決策樹很小時，訓(xùn)練和檢驗誤差都很大，這種情況稱為 模型擬合不足 。使決策樹過于復(fù)雜 子樹重復(fù)問題 PQ RS 0 10 1QS 00 1? Same subtree appears in multiple branches 決策邊界 y 0 . 3 3 ? : 0 : 3 : 4 : 0y 0 . 4 7 ? : 4 : 0 : 0 : 4x 0 . 4 3 ?Y e sY e sN oN o Y e s N o0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 100 . 10 . 20 . 30 . 40 . 50 . 60 . 70 . 80 . 91xy? 斜決策樹 x + y 1 Class = + Class = 模型過分擬合和擬合不足 ? 分類模型的誤差大致分為兩種： – 訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類樣本比例 – 泛化誤差：是模型在未知記錄上的期望誤差 ? 一個好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對未知樣本也要能準確分類。 決策樹 ? 特點 : – 決策樹是一種構(gòu)建分類模型的非參數(shù)方法 – 不需要昂貴的的計算代價 – 決策樹相對容易解釋 – 決策樹是學(xué)習離散值函數(shù)的典型代表 – 決策數(shù)對于噪聲的干擾具有相當好的魯棒性 – 冗余屬性不會對決策樹的準確率造成不利影響 – 數(shù)據(jù)碎片問題。 K越大 Split Info越大增益率越小 S p l i t I N F OG AI NG a i n RAT I O S p l i tsp l i t ? ???? kiiinnnnS p l i t I N F O1l o g基于 Classification Error的劃分 ? 給定結(jié)點 t的 Classification Error值計算 : ? 當類分布均衡時， error值達到最大值 (1 1/nc) ? 相反當只有一個類時， error值達到最小值 0 )|(m a x1)( tiPtE r r o r i??例子 C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Error = 1 – max (0, 1) = 1 – 1 = 0 P(C1) = 1/6 P(C2) = 5/6 Error = 1 – max (1/6, 5/6) = 1 – 5/6 = 1/6 P(C1) = 2/6 P(C2) = 4/6 Error = 1 – max (2/6, 4/6) = 1 – 4/6 = 1/3 )|(m a x1)( tiPtE r r o r i??不純性度量之間的比較 二元分類問題 : 決策樹 ? Hunt算法采用貪心策略構(gòu)建決策樹 . – 在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹 . ? 決策樹歸納的設(shè)計問題 – 如何分裂訓(xùn)練記錄 ?怎樣為不同類型的屬性指定測試條件 ? ?怎樣評估每種測試條件 ? – 如何停止分裂過程 停止分裂過程 ? 當所有的記錄屬于同一類時，停止分裂 ? 當所有的記錄都有相同的屬性時，停止分裂 ? 提前終止樹的生長 三種著名的決策樹 ? Cart：基本的決策樹算法 ? Id3：利用增益比不純性，樹采用二叉樹，停止準則為當所有的記錄屬于同一類時，停止分裂，或當所有的記錄都有相同的屬性時，停止分裂 ? ： id3的改進版本，也是最流行的分類數(shù)算法。當其發(fā)生時所攜信息量就少。 值越大說明需要越多的信息才能確定事件 的發(fā)生，其隨機性也越大，而當 發(fā)生時所攜帶的信息量也越大。然后，對于每個子結(jié)點，遞歸地調(diào)用該算法 Tid Re f und Marital Stat u s Taxable In e Che a t 1 Yes Single 125K No 2 No Marr i ed 100K No 3 No Single 70K No 4 Yes Marr i ed 120K No 5 No Divor ce d 95K Yes 6 No Marr i ed 60K No 7 Yes Divor ce d 220K No 8 No Single 85K Yes 9 No Marr i ed 75K No 10 No Singl e 90K Yes 10 Dt ? Hunt算法 Don’t Cheat Refund Don’t Cheat Don’t Cheat Yes No Refund Don’t Cheat Yes No Marital Status Don’t