【正文】 差（10%），盡管它的訓練誤差較高，為 20% – 決策樹 1過分擬合了訓練數(shù)據(jù)。因為屬性測試條件 4條腿具有欺騙性，它擬合了誤標記的訓練紀錄，導致了對檢驗集中記錄的誤分類 噪聲導致的過分擬合（例子） 噪聲導致決策邊界的改變 缺乏代表性樣本導致的過分擬合 ? 根據(jù)少量訓練記錄做出分類決策的模型也容易受過分擬合的影響。 ? 由于訓練數(shù)據(jù)缺乏具有代表性的樣本，在沒有多少訓練記錄的情況下，學習算法仍然細化模型就會產生過分擬合。 ? 例子：五個訓練記錄，所有的記錄都是正確標記的，對應的決策樹盡管訓練誤差為 0，但檢驗誤差高達 30% ? 人、大象和海豚被誤分類，因為決策樹把恒溫但不冬眠的動物分為非哺乳動物。決策樹做出這樣的分類決策是因為只有一個訓練記錄（鷹）具有這些特征。 ? 這個例子清楚的表明，當決策樹的葉結點沒有足夠的代表性樣本時，很可能做出錯誤的預測。 過分擬合與多重比較 ? 模型的過分擬合可能出現(xiàn)在使用多重比較過程的算法中 ? 多重比較的例子：考慮未來十個交易日股市是升還是降 – 一個人十次猜測至少正確預測八次的概率是： – 假設從 50個股票分析家中選擇一個投資顧問，策略是選擇在未來的十個交易日做出最多正確預測的分析家。 – 該策略的缺點是，即使所有的分析家都用隨機猜測做出預測，至少有一個分析家做出八次正確預測的概率是：1（ ） 50=，這一結果相當高。 ? 多重比較過程與模型過分擬合有什么關系？ – 在決策樹增長過程中，可以進行多種測試，以確定哪個屬性能夠最好的劃分訓練數(shù)據(jù)。 – 在這種情況下，算法實際上是使用多重比較過程來決定是否需要擴展決策樹。 – 當候選屬性多，訓練記錄數(shù)少時，這種影響就變得更加明顯。 泛化誤差估計 ? 過分擬合的主要原因一直是個爭辯的話題，但大家還是普遍同意模型的復雜度對模型的過分擬合有影響。 ? 如何確定正確的模型復雜度？理想的復雜度是能產生最低泛化誤差的模型的復雜度。 ? 估計泛化誤差的方法 – 使用再代入估計。用訓練誤差提供對泛化誤差的樂觀估計 – 結合模型復雜度 – 估計統(tǒng)計上界 – 使用確定集 結合模型復雜度 ? 奧卡姆剃刀 （ Occam39。s Razor ）：給定兩個具有相同泛化誤差的模型，較簡單的模型比復雜的模型更可取 ? 因為復雜模型中的附加成分很大程度上是偶然的擬合。因此，分類模型評估應把模型復雜度考慮進去 ? 方法：悲觀誤差估計、最小描述長度原則（ MDL） 悲觀誤差評估 ? 悲觀誤差估計公式： ? Q(ti)為每個結點 ti的罰分， e(T)為訓練樣本集的錯分樣本數(shù)， Nt為訓練樣本總數(shù)， k為葉結點數(shù)。 tkiikiiiNTQTetntQteTe)()()()]()([)(39。11???????? ? 例子 1：如果罰分等于 ，訓練樣本集中樣本數(shù)為 24個，我們構建了 7個葉結點的決策樹，訓練樣本集的錯分樣本數(shù)為 4 ? 根據(jù)公式我們得 e’(T)=(4+7*)/24= ? 例子 2：如果罰分等于 ，訓練樣本集中樣本數(shù)為 24個，我們構建了 4個葉結點的決策樹，訓練樣本集的錯分樣本數(shù)為 6 ? 根據(jù)公式我們得 e’(T)=(6+4*)/24= ? 當罰分等于 1時，例 1， 2為 ， ? ，結點就應當擴充，因為擴展一個結點等價于總誤差增加 ，代價比犯一個訓練錯誤小 最小描述長度 (MDL) ? Cost(Model,Data) = Cost(Data|Model) + Cost(Model) – Cost 是傳輸總代價 . – 最小化 cost值 . ? Cost(Data|Model) 是誤分類記錄編碼的開銷 . ? Cost(Model) 是模型編碼的開銷 . A BA?B?C?1001Y e s NoB 1 B 2C 1 C 2X yX 1 1X 2 0X 3 0X 4 1… …X n 1X yX 1 ?X 2 ?X 3 ?X 4 ?… …X n ?使用確認集 ? 該方法中，不是用訓練集估計泛化誤差，而是把原始的訓練數(shù)據(jù)集分為兩個較小的子集，一個子集用于訓練，而另一個稱為確認集，用于估計泛化誤差。 ? 該方法為評估模型在未知樣本上的性能提供了較好辦法。 處理決策樹中的過分擬合 ? 先剪枝 (Early Stopping Rule) – 樹增長算法在產生完全擬合整個訓練數(shù)據(jù)集的之前就停止決策樹的生長 – 為了做到這一點，需要采用更具限制性的結束條件 : ? 當結點的記錄數(shù)少于一定閾值，則停止生長 ?當不純性度量的增益低于某個確定的閾值時，則停止生長 (., information gain). – 缺點：很難為提前終止選取正確的閾值 : ? 閾值太高，導致擬合不足 ?閾值太低，導致不能充分解決過分擬合的問題。 處理決策樹中的過分擬合 … ? 后剪枝 – 在該方法中，初始決策樹按照最大規(guī)模生長，然后進行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。 – 修剪有兩種做法 : ? 用新的葉結點替換子樹，該葉結點的類標號由子樹下記錄中的多數(shù)類確定 ?用子樹中最常用的分支代替子樹 處理決策樹中的過分擬合 … – 與先剪枝相比，后剪枝技術傾向于產生更好的結果。 – 因為不像先剪枝，后剪枝是根據(jù)完全增長的決策樹作出的剪枝決策，先剪枝則可能過早終止決策樹的生長。 – 然而，對于后剪枝，當子樹被剪掉后，生長完全決策樹的額外開銷就被浪費了。 不平衡類問題 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 ? 如果模型預測所有的樣本為類 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??????????????? ? ?真正率真負率假正率假負率精度召回率度量? 精度確定在分類器斷言為正類的那部分記錄中實際為正類的記錄所占的比例。精度越高，分類器的假正類錯誤率就越低。 ? 召回率度量被分類器正確預測的正樣本的比例。具有高召回率的分類器很少將正樣本誤分為負樣本。 ROC (Receiver Operating Characteristic) ? ROC曲線是顯示分類器真正率（ TPR）和假正率（ FPR）之間折中的一種圖形化方法。 ? ROC 曲線上有幾個關鍵點，它們有公認的解釋： – （ TPR=0， FPR=0）：把每個實例都預測為負類的模型 – （ TPR=1， FPR=1）：把每個實例都預測為正類的模型 – （ TPR=1， FPR=0）：理想模型 使用 ROC曲線比較模型 ? 沒有哪個模型能夠壓倒對方 ? FRR,M1 較好 ? FRR, M2較好 ? ROC曲線下方的面積 ? 理想情況 : ? 面積 = 1 ? 隨機猜測 : ? 面積 = 怎樣產生 ROC曲線 C la ss + + + + + P 0. 25 0. 43 0. 53 0. 76 0. 85 0. 85 0. 85 0. 87 0. 93 0. 95 1. 00 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 T PR 1 0. 8 0. 8 0. 6 0. 6 0. 6 0. 6 0. 4 0. 4 0. 2 0 F PR 1 1 0. 8 0. 8 0. 6 0 .4 0. 2 0. 2 0 0 0 Threshold = ROC 曲線 :