15.3 剪枝優化

• 規則生成本質上是一個貪心搜索的過程，需要一定的機制緩解過擬合的風險，最常見的做法是剪枝（pruning）。與決策樹相似，剪紙可以發生在規則生長過程中，即預剪枝。也可以發生在規則產生后，即后剪枝。通常是基于某種性能度量指標來評估增/刪邏輯文字前后的規則性能，或增/刪規則前后的規則集性能，從而判斷是否要進行剪枝。

• 剪枝還可以借助統計顯著性檢驗來進行，例如CN2算法在預剪枝的過程時，假設用規則集來進行預測必須顯著優于直接基于訓練樣例集后驗概率分布進行預測，為了便于計算。CN2使用了似然率統計量（LRS）。令m+，m-分別表示訓練樣例集中的正，反例數目，m^+,m-分別表示規則（集合——覆蓋的正反例數目，則有

• 這實際上是一種信息量指標，衡量了規則集覆蓋樣例的分布和訓練集經驗分布的差別：LRS越大，說明采用規則集進行預測和直接使用訓練集正，反例比率進行猜測的差別越大。LRS越小，說明規則集的效果越可能是偶然現象，在數據量比較大的現實任務中，通常設置為LRS很大（例如0.99）時，CN2算法才停止規則集生長

• 規則學習中常稱為生長集，和剪枝條。

• 后剪枝最常用的策略是減錯剪枝（REP），其基本的做法是：將樣例集合劃分為訓練集和驗證集，從訓練集上學得規則R后進行多輪剪枝，在每一輪窮舉所有可能的剪枝操作，包括刪除規則中的某個文字，刪除規則中結尾文字，刪除規則尾部多個文字，刪除整條規則等。然后用驗證集對剪枝產生的所有候選規則集進行評估，保留最好的那個規則集進行下一輪的剪枝，如此繼續，直到無法通過剪枝提高驗證集上的性能為止。

• REP剪枝通常很有效果，但是他的復雜度是 O（m^4),m為馴良樣本的數量。IREP，負責都是m （log m）^2，其做法是：在生成每條規則前，先將當前樣例集劃分為訓練集和驗證集，在訓練集上生成一條規則R，立即在驗證集上對其進行REP剪枝，得到規則 R’，將R‘覆蓋的樣例去掉，在更新后的樣例集合上重復上述的操作。顯然，REP是針對規則集進行剪枝，而IREP僅僅對于單挑規則進行剪枝，因此后者比前者更加高效

• 若將剪枝機制和其他一些后處理手段結合起來對規則集進行優化，則往往可以獲得很好的效果，以著名的規則學習算法RIPPER為例，其泛化性能超過很多決策樹算法，而且學習速度也比大多數決策樹算法更快，奧妙就在于將剪枝和后處理優化相結合

• RIPPER算法描述如下，它先使用了IREP剪枝機制生成了規則集R，IREP是IREP的改進，主要是以m+和m- 取代了IREP使用的準確率作為規則性能度量指標，在剪枝的時候刪除規則尾部的多個文字，并且在最終得到規則集之后再進行一次IREP剪枝。RIPPER中的后處理機制是為了在剪枝的基礎上進一步提升性能，對R中的每條規則Ri，RIPPER為它產生兩個變體：

• R’：基于Ri的覆蓋的樣例，用IREP*重新生成一條規則R‘，該規則稱為替換規則

• R’’：對Ri增加文字進行特化，然后再用IREP*剪枝生成一條規則Ri’’，該規則稱為修訂規則

• 接下來，將R‘i和R’‘i分別與R中除Ri之外的規則放在一起，組成了規則集R’和R’’，然后將他們和R一起進行比較，選擇最優的規則集保留下來，這就是第四行算法所作的操作

• 為什么RIPPER的優化策略有效呢？原因很簡單：最初生成R的時候，規則是按序生成的、每條規則都沒有對其后產生的規則加以考慮，這樣的貪心算法本質常常導致算法陷入局部最優。RIPPER的后處理優化過程將R中的所有規則放在一起重新加以優化，恰恰是通過全局的考慮來緩解貪心算法的局部性，從而往往能夠得到更好的效果。

總結

以上是生活随笔為你收集整理的15.3 剪枝优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。