【正文】 ： 0 +： 1 ： 4 +： 5 ： 2 決策樹 T1 決策樹 T2 考慮上圖的二叉決策樹。如果罰項(xiàng)等于 ，左邊的決策樹的悲觀誤差估計為： 312 )( 1 ?????Te g右邊的決策樹的悲觀誤差估計為： )( 2 ?????Te g此時，左邊的決策樹比右邊的決策樹具有更好的悲觀誤差估計。 最小描述長度原則（ minimum description length, MDL） 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 ?標(biāo)記的 未標(biāo)記的 Cost 是傳輸總代價。目標(biāo)：最小化 Cost值。 其中 Cost(Data|Model) 是誤分類記錄編碼的開銷。 Cost(Model) 是模 型編碼的開銷 。 另一種可能是， A決定建立一個分類模型，概括 X和 y點(diǎn)之間的關(guān)系。 Cost(Model, Data) = Cost(Data|Model) + Cost(Model) 估計統(tǒng)計上界 泛化誤差也可以用訓(xùn)練誤差的統(tǒng)計修正來估計。因?yàn)榉夯`差傾向于比訓(xùn)練誤差大，所以統(tǒng)計修正通常是計算訓(xùn)練誤差的上界。 使用確認(rèn)集 在該方法中，不是用訓(xùn)練集估計泛化誤差，而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個較小的子集，一個子集用于訓(xùn)練，而另一個稱為確認(rèn)集，用于估計泛化誤差。 2/3訓(xùn)練集 1/3訓(xùn)練集 該方法通常用于通過參數(shù)控制獲得具有不同復(fù)雜度模型的分類技術(shù)。通過調(diào)整學(xué)習(xí)算法中的參數(shù)，直到學(xué)習(xí)算法產(chǎn)生的模型在確認(rèn)集上達(dá)到最低的錯誤率，可以估計最佳模型的復(fù)雜度。 處理決策樹歸納中的過分?jǐn)M合 先剪枝 (提前終止規(guī)則 ) 樹增長算法在產(chǎn)生完全擬合整個訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長 為了做到這一點(diǎn)，需要采用更具限制性的結(jié)束條件 : 當(dāng)結(jié)點(diǎn)的記錄數(shù)少于一定閾值，則停止生長 當(dāng)不純性度量的增益低于某個確定的閾值時，則停止生長 (., information gain). 缺點(diǎn)：很難為提前終止選取正確的閾值 : （ 1）閾值太高，導(dǎo)致擬合不足 （ 2）閾值太低，導(dǎo)致不能充分解決過分?jǐn)M合的問題。 后剪枝 在該方法中，初始決策樹按照最大規(guī)模生長，然后進(jìn)行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。 修剪有兩種做法 : （ 1）用新的葉結(jié)點(diǎn)替換子樹，該葉結(jié)點(diǎn)的類標(biāo)號由子樹下記錄中的多數(shù)類定（ 2）用子樹中最常用的分支代替子樹 一、保持（ Holdout）方法 將被標(biāo)記的原始數(shù)據(jù)劃分成兩個不相交的集合，分別成為訓(xùn)練集和檢驗(yàn)集。在訓(xùn)練集上歸納分類模型，在檢驗(yàn)集上評估模型的性能。 局限性： 用于訓(xùn)練的被標(biāo)記樣本較少。 模型可能高度依賴于訓(xùn)練集和檢驗(yàn)集的構(gòu)成。 二、隨機(jī)二次抽樣（ random subsampling） 隨機(jī)二次抽樣可以多次重復(fù)保持方法來改進(jìn)分類器性能的估計。 ??? ki isu b kaccacc 1 /由于它沒有控制每個記錄用于訓(xùn)練和檢驗(yàn)的次數(shù)，因此，有些用于訓(xùn)練的記錄使用的頻率可能比其他記錄高得多。 三、交叉驗(yàn)證（ crossvalidation） 在該方法中，每個記錄用于訓(xùn)練的次數(shù)相同，并且恰好檢驗(yàn)一次。 例：假設(shè)把數(shù)據(jù)分為相同大小的兩個子集，首先，我們選擇一個子集作訓(xùn)練集，而另一個作檢驗(yàn)集，然后交換兩個集合的角色，原先作訓(xùn)練集的現(xiàn)在作檢驗(yàn)集，反之亦然，這種方法叫做二折交叉驗(yàn)證。 四、自助（ bootstrap）法 在自助法中，訓(xùn)練記錄采用有放回抽樣使得它等幾率地被重新抽取。如果原始數(shù)據(jù)有 N個記錄，可以證明，平均來說，大小為 N的自助樣本大約包含原始數(shù)據(jù)的 %的記錄。 NN )11(1 ??至少一個記錄被自助樣本抽取的概率 )11(1lim ??????? eN NN它通過組合每個自助樣本的準(zhǔn)確率 和由包含所有標(biāo)記樣本的訓(xùn)練集計算的準(zhǔn)確率 計算總準(zhǔn)確率 ： )(i?)( sacc )( bootacc ?? ????bi sib ootaccbacc1)(1 ?考慮一對分類模型 Model A和 model B， 假設(shè) model A在包含 30個記錄的檢驗(yàn)集上的準(zhǔn)確率達(dá)到 85%，而 model B在包含 5000個記錄的不同檢驗(yàn)集上達(dá)到 75%的準(zhǔn)確率。 估計準(zhǔn)確度的置信區(qū)間 vNvvN ppCvXP ???? )1()( 是 N次試驗(yàn)觀察到的成功次數(shù)。檢驗(yàn)集的記錄個數(shù)為 N，準(zhǔn)確率 XNXacc? NpXE ?)( )1()( pNpXVar ??期望： 方差： （拋硬幣試驗(yàn)） 21 ??z2?z1－ α 2?2? ???????? 1))1( 212 aa ZNpppaccZP （比較兩個模型的性能 考慮一對模型 M1和 M2，它們在兩個獨(dú)立的檢驗(yàn)集 D1和 D2上進(jìn)行評估，令 n1是D1中的記錄數(shù)， n2是 D2中的記錄數(shù)。另外，假設(shè) M1在 D1上的錯誤率為 e1， M2在 D2上的錯誤率為 e2。假設(shè) n1和 n2都充分大， e1和 e2可以使用正態(tài)分布來近似。如果用 d=e1e2表示錯誤率的觀察差，則 d服從均值為 （其實(shí)際差）、方差為 的正態(tài)分布。 D的方差為： 2d?22211122 )1()1(? n een eedd ????? ??td其中 和 是錯誤率的方差。在置信水平 下 的置信區(qū)間為： 111 )1(nee ?222 )1(n ee ???td dt zdd ?? ?2/??例：模型 M1在 N1=30個檢驗(yàn)記錄上的錯誤率 e1=。 M2在 N2=5000個檢驗(yàn)記錄上的錯誤率 e2= d=||=。使用雙側(cè)檢驗(yàn)來檢查 還是 。錯誤率觀察差的估計方差計算如下： 0?td 0?td 004 0 )( )( 2 ?????d? ?d?或 ?????td結(jié)論：區(qū)間跨越 0，可以斷言在 95%的置信水平下，該觀察差不是統(tǒng)計顯著的。 比較兩種分類法的性能 令 表示分類技術(shù) 在第 j 次迭代產(chǎn)生的模型，每對模型 和 在相同的劃分 j 上進(jìn)行檢驗(yàn)。用 e1j和 e2j分別表示它們的錯誤率，它們在第 j折上的錯誤率之差可以記作 。如果 k充分大，則 服從于均值為 、方差為 的正態(tài)分布。觀察差的總方差可以用下式進(jìn)行估計： ijMiL jM1 j2 jjj eed 21 ??jd cvtd cv? )1()(? 122?????kkddkjjd cv?其中， 是平均差。用 t分布計算 的置信區(qū)間為： d cvtd cvdkcvt tdd ?? ?1),1( ????例：假設(shè)兩個分類技術(shù)產(chǎn)生的模型的準(zhǔn)確率估計差的均值等于 ，標(biāo)準(zhǔn)差等于 。如果使用 30折交叉驗(yàn)證方法估計準(zhǔn)確率，則在 95%置信水平下，真實(shí)準(zhǔn)確率為： ???cvtd統(tǒng)計顯著 查詢 t分布表