【正文】 過度擬合：給定一個假設(shè)空間 H，一個假設(shè) h∈ H，如果存在其 它的假設(shè) h1 ∈ H ,使得在訓(xùn)練樣例上 h的錯誤率比 h1小，但在整個實 例發(fā)布上 h1的錯誤率比 h小，則稱假設(shè) h過度擬合訓(xùn)練數(shù)據(jù) 過度擬合產(chǎn)生的原因：噪聲，訓(xùn)練樣例太小等 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 對學(xué)習(xí)算法是否成功的真正測試是看它對于訓(xùn)練中未見到的 數(shù)據(jù)的執(zhí)行性能。 訓(xùn)練過程應(yīng)該包含訓(xùn)練樣本和驗證樣本。驗證樣本用于測試 訓(xùn)練后的性能。如果驗證結(jié)果差，則需要考慮采用不同的結(jié)構(gòu)重 新進(jìn)行訓(xùn)練，例如使用更大的樣本集，或者改變從連續(xù)值到離散 值得數(shù)據(jù)轉(zhuǎn)換等。 通常應(yīng)該建立一個驗證過程，在訓(xùn)練最終完成后用來檢測訓(xùn) 練結(jié)果的泛化能力。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 分類模型的誤差 一般可以將分類模型的誤差分為： 訓(xùn)練誤差（ Training Error）； 泛化誤差（ Generalization Error） 決策樹研究問題 關(guān)于過渡擬合 第 6章 決策樹 分類模型的誤差 訓(xùn)練誤差是在訓(xùn)練記錄上誤分類樣本比例； 泛化誤差是模型在未知記錄上的期望誤差； 一個好的模型不僅要能夠很好地擬合訓(xùn)練數(shù)據(jù)，而且對未知 樣本也要能夠準(zhǔn)確地分類。 一個好的分類模型必須具有低的訓(xùn)練誤差和泛化誤差。因為 一個具有低訓(xùn)練誤差的模型，其泛化誤差可能比具有較高訓(xùn)練誤 差的模型高。（訓(xùn)練誤差低，泛化誤差高，稱為過渡擬合） 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 模型過渡擬合的潛在因素 （ 1）噪聲導(dǎo)致的過渡擬合； 錯誤的類別值 /類標(biāo)簽，屬性值等 （ 2）缺乏代表性樣本所導(dǎo)致的過渡擬合 根據(jù)少量訓(xùn)練記錄作出的分類決策模型容易受過渡擬合的 影響。由于訓(xùn)練樣本缺乏代表性的樣本，在沒有多少訓(xùn)練 記錄的情況下，學(xué)習(xí)算法仍然繼續(xù)細(xì)化模型就會導(dǎo)致過渡 擬合。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 模型過渡擬合的潛在因素 名稱 體溫 胎生 4條腿 冬眠 哺乳動物 蠑螈 冷血 N Y Y N 虹鳉 冷血 Y N N N 鷹 恒溫 N N N N 弱夜鷹 恒溫 N N Y N 鴨嘴獸 恒溫 Y Y Y Y 哺乳動物分類的訓(xùn)練樣例 體溫 恒溫 冷血 冬眠 N Y N N 4條腿 Y N N Y 名稱 體溫 胎生 4條腿 冬眠 哺乳動物 人 恒溫 Y N N Y 大象 恒溫 Y Y N Y 鴿子 恒溫 N N N N 哺乳動物分類的訓(xùn)練樣例 按照訓(xùn)練模型。人和大象都不是 哺乳動物。決策樹作出這樣的判 斷是因為只有一個訓(xùn)練樣例具有 這些特點（鷹，恒溫，不冬眠） 被劃分為非哺乳動物。 該例清楚表明，當(dāng)決策樹的葉節(jié) 點沒有足夠的代表性時，可能會 預(yù)測錯誤。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 解決過度擬合的手段： 1 及早停止樹增長； 2 后修剪法。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 1 及早停止樹增長 由于決策樹學(xué)習(xí)要從候選集合眾選擇滿足給定標(biāo)準(zhǔn)的 最大化屬性，并且不回溯，也就是我們常說的爬山策略，其 選擇往往會是局部最優(yōu)而不是全局最優(yōu)。樹結(jié)構(gòu)越復(fù)雜，則 過渡擬合發(fā)生的可能性越大。因此，要選擇簡單的模型。 Occan法則（又稱 Occan剃刀 Occan Razor） :具有相同 泛化誤差的兩個模型，較簡單的模型比復(fù)雜的模型更可取。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法） 在訓(xùn)練過程中允許對數(shù)據(jù)的過渡擬合，然后再對樹進(jìn)行修剪 該方法稱為后剪枝法。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 A B 負(fù) C 正 正 負(fù) Y Y Y N N N 一棵通過 訓(xùn)練集合 學(xué)好的決策樹 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 A B 負(fù) C 正 正 負(fù) Y Y Y N N N 實例 A B C 類別 錯分類 1 Y Y Y + 2 Y Y Y + 3 Y Y Y + 4 Y Y Y + 5 Y Y Y + 6 Y Y N * 7 Y Y N * 8 Y Y N * 9 Y N Y + 10 Y N Y + 11 Y N Y + 12 Y N Y + 13 Y N N + * 14 Y N N + * 15 Y N N 16 Y N N 17 Y N N 18 N N N 19 N Y N 20 N Y Y 對以上的決策樹通過右側(cè)的 驗證集合進(jìn)行測試，發(fā)現(xiàn)其 有 5個錯分類。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 A B 負(fù) C 正 正 負(fù) Y Y Y N N N {18， 19， 20} {1， 2， 3， 4 5， 6， 7， 8} {9， 10， 11， 12} {13， 14， 15， 16， 17} 錯分類 5個， 6， 7， 8， 13， 14 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 第 1步 將決策樹規(guī)則化 規(guī)則 1 IF A=Y AND B=Y THEN + 規(guī)則 2 IF A=Y AND B=N AND C=Y THEN + 規(guī)則 3 IF A=Y AND B=N AND C=N THEN – 規(guī)則 4 IF A=N THEN A B 負(fù) C 正 正 負(fù) Y Y Y N N N 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 規(guī)則 1 IF A=Y AND B=Y THEN + 規(guī)則 2 IF A=Y AND B=N AND C=Y THEN + 規(guī)則 3 IF A=Y AND B=N AND C=N THEN – 規(guī)則 4 IF A=N THEN 規(guī)則 分類正確的數(shù)目 分類錯誤的數(shù)目 精度 1 5 3 5/8 2 4 0 4/4 3 3 2 3/5 4 3 0 3/3 第 2步 規(guī)則精度的計算 決策樹研究 問題 規(guī)則 2與規(guī)則 4精度為 100%，保留 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 規(guī)則 分類正確的數(shù)目 分類錯誤的數(shù)目 精度 1 5 3 5/8 2 4 0 4/4 3 3 2 3/5 4 3 0 3/3 第 3步 對規(guī)則進(jìn)行修剪 規(guī)則 去掉 A 去掉 B 去掉 C 去掉 AB 去掉 BC 去掉 AC 選擇 1 5/10 11/17 去掉 B 3 4/6 6/8 3/9 8/10 4/10 6/17 去掉 AB 決策樹研究 問題 ? 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 第 3步 對規(guī)則進(jìn)行修剪 最終規(guī)則集合為 規(guī)則 去掉 A 去掉 B 去掉 C 去掉 AB 去掉 BC 去掉 AC 選擇 1 5/10 11/17 去掉 B 3 4/6 6/8 3/9 8/10 4/10 6/17 去掉 AB 規(guī)則 1 IF A=Y AND B=Y THEN + 規(guī)則 2 IF A=Y AND B=N AND C=Y THEN + 規(guī)則 3 IF A=Y AND B=N AND C=N THEN – 規(guī)則 4 IF A=N THEN 原始規(guī)則集合 規(guī)則 1 IF A=Y THEN + 規(guī)則 2 IF A=Y AND B=N AND C=Y THEN + 規(guī)則 3 IF C=N THEN – 規(guī)則 4 IF A=N THEN 最終規(guī)則集合 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 第 4步 根據(jù)精度和泛化能力對對規(guī)則進(jìn)行排序 IF A=N THEN {18， 19， 20} IF A=Y AND B=N AND C=Y THEN + {9,10,11,12} IF C=N THEN – {6,7,8,13,14,15,16,17} IF A=Y THEN +{1,2,3,4,5} 盡管 {13， 14}仍然被錯分，但整個模型的精度提高了 決策樹研究 問題 主要內(nèi)容 決策樹基本概念 決策樹算法 決策樹研究問題 主要參考文獻(xiàn) 第 6章 決策樹 主要參考文獻(xiàn) 幾個數(shù)據(jù) 萬方數(shù)據(jù)庫中查詢涉及決策樹的學(xué)位論文； 時間跨度是 20232023； 查詢結(jié)果是 245篇（碩士論文居多） 按照以下三個領(lǐng)域分類： 1 利用決策樹解決實際問題； 2 利用決策樹與其它數(shù)據(jù)挖掘（機(jī)器學(xué)習(xí)）結(jié)合改進(jìn)； 3 有關(guān)決策樹的改進(jìn)方法。 約 150篇 約 100篇 第 6章 決策樹 主要參考文獻(xiàn) 幾個數(shù)據(jù) 萬方數(shù)據(jù)庫中查詢涉及決策樹的期刊論文 時間跨度是 20232023； 查詢結(jié)果是 982篇 按照以下三個領(lǐng)域分類： 1 利用決策樹解決實際問題； 2 利用決策樹與其它數(shù)據(jù)挖 掘（機(jī)器學(xué)習(xí)）結(jié)合改進(jìn)； 3 有關(guān)決策樹的改進(jìn)方法。 約 600篇 約 400篇 非計算機(jī)領(lǐng)域占相當(dāng)部分 計算機(jī)領(lǐng)域的主要期刊沒有 一篇 以研究與發(fā)展為例，前 100篇中有 4篇 初略估計 1000篇中有 40篇，平均每年 8篇，該期刊每年發(fā)表文章 360篇， 占比 8/360=%.研究與發(fā)展錄用率 約 810%。可以初略推算出每年收到 的關(guān)于決策樹方面的論文約 80100篇 第 6章 決策樹 主要參考文獻(xiàn) 幾個數(shù)據(jù) 以上幾個關(guān)于決策樹的數(shù)據(jù)也許能夠表明，盡管決策樹非常古老， 但目前仍然有相當(dāng)部分的研究人員和研究項目和工程項目。仍然 是碩士研究生可以加以研究的主要方向。 另外，通過對這些數(shù)據(jù)的分析，我也想告訴大家，數(shù)據(jù)是非常寶貴 的。特別是學(xué)校科研項目多數(shù)是研究項目，對海量數(shù)據(jù)集合的獲得 非常不容易。而目前數(shù)據(jù)挖掘研究和應(yīng)用往往和大數(shù)據(jù)集合有關(guān)。 像網(wǎng)絡(luò)日志、萬方數(shù)據(jù)、國外數(shù)據(jù)挖掘通用數(shù)據(jù)集合（一般都比較 ?。┑榷际俏覀兛梢岳玫臄?shù)據(jù)集合。