決策樹系列(二)——剪枝

什麼是剪枝?spa

      剪枝是指將一顆子樹的子節點所有刪掉,根節點做爲葉子節點,如下圖爲例:3d

 

 

爲甚麼要剪枝?blog

      決策樹是充分考慮了全部的數據點而生成的複雜樹,有可能出現過擬合的狀況,決策樹越複雜,過擬合的程度會越高。方法

      考慮極端的狀況,若是咱們令全部的葉子節點都只含有一個數據點,那麼咱們可以保證全部的訓練數據都能準確分類,可是頗有可能獲得高的預測偏差,緣由是將訓練數據中全部的噪聲數據都」準確劃分」了,強化了噪聲數據的做用。im

      剪枝修剪分裂先後分類偏差相差不大的子樹,可以下降決策樹的複雜度,下降過擬合出現的機率。d3

 

怎樣剪枝?數據

兩種方案:先剪枝和後剪枝margin

      先剪枝說白了就是提早結束決策樹的增加,跟上述決策樹中止生長的方法同樣。db

      後剪枝是指在決策樹生長完成以後再進行剪枝的過程。這裏介紹三種後剪枝方案:img

(1)REP—錯誤率下降剪枝        

      顧名思義,該剪枝方法是根據錯誤率進行剪枝,若是一棵子樹修剪先後錯誤率沒有降低,就能夠認爲該子樹是能夠修剪的。

      REP剪枝須要用新的數據集,緣由是若是用舊的數據集,不可能出現分裂後的錯誤率比分裂前錯誤率要高的狀況。因爲使用新的數據集沒有參與決策樹的構建,可以下降訓練數據的影響,下降過擬合的程度,提升預測的準確率。

(2)PEP—悲觀剪枝

      悲觀剪枝認爲若是決策樹的精度在剪枝先後沒有影響的話,則進行剪枝。怎樣纔算是沒有影響?若是剪枝後的偏差小於剪枝前經度的上限,則說明剪枝後的效果與剪枝前的效果一致,此時要進行剪枝。

      進行剪枝必須知足的條件:

其中:

    表示剪枝前子樹的偏差;

   表示剪枝後節點的偏差;

二者的計算公式以下:

                                   

      令子樹偏差的經度知足二項分佈,根據二項分佈的性質, ,其中 ,N爲子樹的數據量;一樣,葉子節點的偏差

      上述公式中,0.5表示修正因子。因爲子節點是父節點進行分裂的結果,從理論上講,子節點的分類效果總比父節點好,分類的偏差更小,若是單純經過比較子節點和父節點的偏差進行剪枝就徹底沒有意義了,所以對節點的偏差計算方法進行修正。修正的方法是給每個節點都加上偏差修正因子0.5,在計算偏差的時候,子節點因爲加上了偏差修正因子,就沒法保證總偏差低於父節點。

算例:

 

  

    

      因爲 ,因此應該進行剪枝。

(3)CCP—代價複雜度剪枝

      代價複雜度選擇節點表面偏差率增益值最小的非葉子節點,刪除該非葉子節點的左右子節點,如有多個非葉子節點的表面偏差率增益值相同小,則選擇非葉子節點中子節點數最多的非葉子節點進行剪枝。

可描述以下:

      令決策樹的非葉子節點爲

      a) 計算全部非葉子節點的表面偏差率增益值  

      b)選擇表面偏差率增益值最小的非葉子節點(若多個非葉子節點具備相同小的表面偏差率增益值,選擇節點數最多的非葉子節點)。

      c)對選中的非葉子節點進行剪枝

表面偏差率增益值的計算公式:

 

其中:

表示葉子節點的偏差代價, , 爲節點的錯誤率, 爲節點數據量的佔比;

表示子樹的偏差代價, 爲子節點i的錯誤率,  表示節點i的數據節點佔比;

表示子樹節點個數。

算例:

下圖是決策樹A的其中一顆子樹,決策樹的總數據量爲40。

 

該子樹的表面偏差率增益值能夠計算以下:

 

求出該子樹的表面錯誤覆蓋率爲 1/40,只要求出其餘子樹的表面偏差率增益值就能夠對決策樹進行剪枝.

相關文章
相關標籤/搜索