天天看點

決策樹剪枝政策執行個體分析

預剪枝:是在決策樹的生成過程中,對每個結點在劃分前先進行估計,若目前結點的劃分不能帶來決策樹泛化性能提升,則停止劃分即結束樹的建構并将目前節點标記為葉結點;

後剪枝:是先從訓練集生成一棵完整的決策樹,然後自底向上地對葉結點進行考察,若将該結點對應的子樹替換為葉結點能帶來決策樹泛化為性能提升,則将該子樹替換為葉結點。泛化性能的提升可以使用交叉驗證資料來檢查修剪的效果,通過使用交叉驗證資料,測試擴充節點是否會帶來改進。如果顯示會帶來改進,那麼我們可以繼續擴充該節點。但是,如果精度降低,則不應該擴充,節點應該轉換為葉節點。

1. 預剪枝

         下表為西瓜資料集

決策樹剪枝政策執行個體分析

以資訊增益準則來進行屬性選擇,從上表資料可以得到一棵決策樹,如下圖1所示:

決策樹剪枝政策執行個體分析

這是未剪枝的決策樹,以屬性“臍部”來對訓練集進行劃分時,産生3個分支凹陷、稍凹,平坦,然而是否應該進行這個劃分呢?預剪枝要對劃分前後的泛化性能進行評估。

         劃分前,所有樣例集中在根結點,若不進行劃分,該結點被标記為葉結點,其類别标記為訓練樣例數最多的類别,若将該結點标記為“好瓜”。用上表中的驗證集對這個單結點決策樹進行評估,樣例(4,5,8)被正确分類,另外的4個樣例(9,11,12,13)分類錯誤,可得驗證集上的精度為

決策樹剪枝政策執行個體分析
決策樹剪枝政策執行個體分析

         若用屬性“臍部”劃分之後,三個結點分别包含訓練樣例(1,2,3,14)、(6,7,15,17)、(10,16)

三個結點分别被标記為葉結點“好瓜”、“好瓜”、“壞瓜”,此時驗證集中的樣例(4,5,8,9,13)被分類正确,驗證精度,于是應該用“臍部”進行劃分。

決策樹剪枝政策執行個體分析

         然後,決策樹算法應該對藍色結點進行劃分,基于資訊增益準則以“色澤”作為劃分屬性。使用色澤劃分後,編号為9的驗證集樣本分類結果由正确轉為錯誤,驗證集下降為57.1%,故預剪枝測量将禁止藍色結點2的被劃分。

         對于結點3,最優劃分屬性為“根蒂”,劃分後驗證集精度仍為71.4%。這個劃分不能提升驗證集精度,故預剪枝測量将禁止結點3的被劃分。

         對于結點4, 其所含訓練樣例已屬于同一類,不再進行劃分。

預剪枝使得很多決策樹的很多分支沒有展開,降低了過拟合的風險,同時顯著減少了決策樹的訓練時間開銷和預測時間開銷。但是,另一方面,有些分支的目前劃分雖不能提升泛化性能、甚至可能導緻泛化性能暫時下降,但是在其基礎上進行的後續劃分卻有可能帶來性能顯著提升。預剪枝 是一種“貪心”政策,這給預剪枝帶來了欠拟合的風險。、

2. 後剪枝

         後剪枝先生成一顆完整的決策樹,由圖1可知,該決策樹的驗證精度為42.9%。現在自底向上地對葉結點進行考察,先看結點6,若将該分支剪去,則6變為葉結點,替換後葉結點包含編号(7,15)訓練樣本,該葉結點被标記為好瓜,此時決策樹的驗證精度提高至57.1%,于是後剪枝決定剪枝,剪枝後如下圖2所示:

決策樹剪枝政策執行個體分析

         然後考察5,将其變為葉結點後包含編号為(6,7,15)的樣例,葉結點标記為“好瓜”,此時決策樹精度仍為57.1%。可以不進行剪枝。

         對于結點2,将其子樹換為葉結點,該葉結點包含編号為(1,2,3,14)的樣例,标記為“好瓜”,此時決策樹的驗證集精度提高至71.4%,做剪枝處理。

       對于結點3和1,将其對應子樹替換為葉結點,所得決策樹的驗證集精度分别為71.4%和42.9%,均未得到提高,被保留。最終,基于後剪枝政策生成的決策樹如圖2所示,其驗證精度為71.4%。

3. 兩種政策的比較

         後剪枝政策通常比預剪枝保留了更多的分支。一般情況下,後剪枝決策樹的欠你和風險很小,泛化性能往往優于預剪枝決策樹。但後剪枝過程在生成完全決策樹之後才能進行,并且要自底向上對樹中的所有非葉子結點逐一計算,是以訓練時間開銷比未剪枝決策樹和預剪枝決策樹的開銷大得多。