【正文】 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?????????? Accuracy ）準(zhǔn)確率（準(zhǔn)確率的缺點(diǎn) ? 考慮 2類問題 – 類 0的樣本數(shù) = 9990 – 類 1的樣本數(shù) = 10 ? 如果模型預(yù)測所有的樣本為類 0, 準(zhǔn)確率為 9990/10000 = % – 準(zhǔn)確率的值具有欺騙性 – 模型并沒有分對類 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??????????????? ? ?真正率真負(fù)率假正率假負(fù)率精度召回率度量? 精度確定在分類器斷言為正類的那部分記錄中實(shí)際為正類的記錄所占的比例。 – 因?yàn)椴幌裣燃糁?，后剪枝是根?jù)完全增長的決策樹作出的剪枝決策，先剪枝則可能過早終止決策樹的生長。 處理決策樹中的過分?jǐn)M合 … ? 后剪枝 – 在該方法中，初始決策樹按照最大規(guī)模生長，然后進(jìn)行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。 ? 該方法為評估模型在未知樣本上的性能提供了較好辦法。 tkiikiiiNTQTetntQteTe)()()()]()([)(39。s Razor ）：給定兩個(gè)具有相同泛化誤差的模型，較簡單的模型比復(fù)雜的模型更可取 ? 因?yàn)閺?fù)雜模型中的附加成分很大程度上是偶然的擬合。 ? 估計(jì)泛化誤差的方法 – 使用再代入估計(jì)。 泛化誤差估計(jì) ? 過分?jǐn)M合的主要原因一直是個(gè)爭辯的話題，但大家還是普遍同意模型的復(fù)雜度對模型的過分?jǐn)M合有影響。 – 在這種情況下，算法實(shí)際上是使用多重比較過程來決定是否需要擴(kuò)展決策樹。 – 該策略的缺點(diǎn)是，即使所有的分析家都用隨機(jī)猜測做出預(yù)測，至少有一個(gè)分析家做出八次正確預(yù)測的概率是：1（ ） 50=，這一結(jié)果相當(dāng)高。 ? 這個(gè)例子清楚的表明，當(dāng)決策樹的葉結(jié)點(diǎn)沒有足夠的代表性樣本時(shí)，很可能做出錯(cuò)誤的預(yù)測。 ? 例子：五個(gè)訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對應(yīng)的決策樹盡管訓(xùn)練誤差為 0，但檢驗(yàn)誤差高達(dá) 30% ? 人、大象和海豚被誤分類，因?yàn)闆Q策樹把恒溫但不冬眠的動物分為非哺乳動物。因?yàn)閷傩詼y試條件 4條腿具有欺騙性，它擬合了誤標(biāo)記的訓(xùn)練紀(jì)錄，導(dǎo)致了對檢驗(yàn)集中記錄的誤分類 噪聲導(dǎo)致的過分?jǐn)M合（例子） 噪聲導(dǎo)致決策邊界的改變 缺乏代表性樣本導(dǎo)致的過分?jǐn)M合 ? 根據(jù)少量訓(xùn)練記錄做出分類決策的模型也容易受過分?jǐn)M合的影響。 ? 隨著決策樹中結(jié)點(diǎn)數(shù)的增加，模型的訓(xùn)練誤差和檢驗(yàn)誤差都會隨之下降。 ? 當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高，這種情況成為模型 過分?jǐn)M合 模型過分?jǐn)M合和擬合不足 ? 當(dāng)決策樹很小時(shí)，訓(xùn)練和檢驗(yà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 = 模型過分?jǐn)M合和擬合不足 ? 分類模型的誤差大致分為兩種： – 訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類樣本比例 – 泛化誤差：是模型在未知記錄上的期望誤差 ? 一個(gè)好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對未知樣本也要能準(zhǔn)確分類。 決策樹 ? 特點(diǎn) : – 決策樹是一種構(gòu)建分類模型的非參數(shù)方法 – 不需要昂貴的的計(jì)算代價(jià) – 決策樹相對容易解釋 – 決策樹是學(xué)習(xí)離散值函數(shù)的典型代表 – 決策數(shù)對于噪聲的干擾具有相當(dāng)好的魯棒性 – 冗余屬性不會對決策樹的準(zhǔn)確率造成不利影響 – 數(shù)據(jù)碎片問題。 K越大 Split Info越大增益率越小 SplitINFOGAINGainRATIO S plitsplit ????? kiiinnnnSplitINFO1log基于 Classification Error的劃分 ? 給定結(jié)點(diǎn) t的 Classification Error值計(jì)算 : ? 當(dāng)類分布均衡時(shí)， error值達(dá)到最大值 (1 1/nc) ? 相反當(dāng)只有一個(gè)類時(shí)， error值達(dá)到最小值 0 )|(max1)( tiPtError 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 )|(max1)( tiPtError i??不純性度量之間的比較 二元分類問題 : 決策樹 ? Hunt算法采用貪心策略構(gòu)建決策樹 . – 在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來構(gòu)造決策樹 . ? 決策樹歸納的設(shè)計(jì)問題 – 如何分裂訓(xùn)練記錄 ?怎樣為不同類型的屬性指定測試條件 ? ?怎樣評估每種測試條件 ? – 如何停止分裂過程 停止分裂過程 ? 當(dāng)所有的記錄屬于同一類時(shí)，停止分裂 ? 當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂 ? 提前終止樹的生長 三種著名的決策樹 ? Cart：基本的決策樹算法 ? Id3：利用增益比不純性，樹采用二叉樹，停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類時(shí)，停止分裂，或當(dāng)所有的記錄都有相同的屬性時(shí)，停止分裂 ? ： id3的改進(jìn)版本，也是最流行的分類數(shù)算法。當(dāng)其發(fā)生時(shí)所攜信息量就少。 值越大說明需要越多的信息才能確定事件 的發(fā)生，其隨機(jī)性也越大，而當(dāng) 發(fā)生時(shí)所攜帶的信息量也越大。然后，對于每個(gè)子結(jié)點(diǎn)，遞歸地調(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