当前位置:   article > 正文

决策树剪枝算法原理_评价函数其实就是求叶结点的期望熵,用nt加权,叶子结点含有的样本数越多,对分类效

评价函数其实就是求叶结点的期望熵,用nt加权,叶子结点含有的样本数越多,对分类效

算法目的:

决策树的剪枝是为了简化决策树模型,避免过拟合。

  • 同样层数的决策树,叶结点的个数越多就越复杂;同样的叶结点个数的决策树,层数越多越复杂。
  • 剪枝前相比于剪枝后,叶结点个数和层数只能更多或者其中一特征一样多,剪枝前必然更复杂。
  • 层数越多,叶结点越多,分的越细致,对训练数据分的也越深,越容易过拟合,导致对测试数据预测时反而效果差。

算法基本思路:

剪去决策树模型中的一些子树或者叶结点,并将其上层的根结点作为新的叶结点,从而减少了叶结点甚至减少了层数,降低了决策树复杂度。

模型损失函数

  1. 变量预定义: ∣ T l e a f ∣ |T_{leaf}| Tleaf表示树T的叶结点个数,记号t表示树T的某个叶结点,同时, N t N_t Nt表示该叶结点含有的样本点个数,其中属于k类的样本点有 N t k N_{tk} Ntk个,K表示类别的个数, H t ( T ) H_t(T) Ht(T)为叶结点t上的经验熵, α ≥ 0 \alpha≥0 α0为参数。
    注:显然有 N t = ∑ k = 1 K N t k N_t=\displaystyle \sum^{K}_{k=1} {N_{tk}} Nt=k=1KNtk
  2. 损失函数(经验熵损失): H t ( T ) = − ∑ k = 1 K N t k N t log ⁡ N t k N t H_t(T) = -\displaystyle \sum_{k=1}^K \frac {N_{tk}} {N_t} \log \frac {N_{tk}}{N_t} Ht(T)=k=1KNtNtklogNtNtk
    注:以经验熵为评价函数(即损失函数 L o s s ( Y , T ( x ) ) Loss(Y,T(x)) Loss(Y,T(x)))。称为经验熵,是因为它是基于样本对真实随机变量的熵的估计。
  3. 经验风险: C ( T ) = ∑ t = 1 ∣ T l e a f ∣ N t H t ( T ) C(T)=\displaystyle \sum^{|T_{leaf}|}_{t=1} {N_tH_t(T)} C(T)=t=1TleafNtHt(T)
    注:损失函数的期望称为期望风险,需要知道整个特征空间的联合概率分布求积分,通常用经验风险估计它,即用样本的损失函数的期望对它估计,与经验熵的叫法类似。
  4. 结构风险(目标函数): C a ( T ) = ∑ t = 1 ∣ T l e a f ∣ N t H t ( T ) + α ∣ T l e a f ∣ C_a(T)=\displaystyle \sum^{|T_{leaf}|}_{t=1} {N_tH_t(T)+\alpha|T_{leaf}|} Ca(T)=t=1TleafNtHt(T)+αTleaf
    注:结构风险=经验风险+正则项,正则项即是惩罚项,与模型复杂度正相关,可减轻过拟合。
    目标函数简化形式: C a ( T ) = C ( T ) + α ∣ T l e a f ∣ C_a(T)=C(T)+\alpha|T_{leaf}| Ca(T)=C(T)+αTleaf
  • 经验熵反映了一个叶结点中的分类结果的混乱程度。经验熵越大,说明该叶结点所对应的分类结果越混乱,也就是说分类结果中包含了较多的类别,表明该分支的分类效果较差。
  • 评价函数越小越好。经验熵越小越好。而以经验熵作为评价函数,其值越大,说明模型的分类效果越差,因而又称损失函数。
  • 经验风险其实是求叶结点的经验熵期望。用 N t N_t Nt给经验熵加权的依据是叶子节点含有的样本个数越多,其分类效果或混乱程度越占主导,相当于求样本期望,可以更好的描述分支前后的关系。例如设一个结点r有n个样本,其组成是第i类有 n i n_i ni个样本,在分了几个孩子结点后各个叶结点的成分仍保持原比例,记新的子树为R,可以计算得出评价函数 C ( r ) = C ( R ) C(r)=C(R) C(r)=C(R),即在随机分组后不会有任何分类效果的改进。
  • 修正项 α ∣ T l e a f ∣ \alpha|T_{leaf}| αTleaf被称为正则项或惩罚项,表示模型复杂度。加入正则项的原因有2个:a.模型过于复杂会出现过拟合现象(在训练集上表现较好而在测试集上表现较差);b.在保障效果的同时尽可能选取简单的模型(即奥卡姆剃刀原理)。如上面提到的随机分组的例子,r与R其实在评价函数评估后的得分是一样的,但是我们仍然觉得r更好,原因在于R的复杂度更高。此外,加了此正则项后, α \alpha α的值具有与现实对应的意义:当 α = 0 \alpha=0 α=0,表示未剪枝的完全树损失更小(熵更小的占主导地位);当 α − > ∞ \alpha->∞ α>,表示剪枝到只剩根结点更好(叶结点个数占主导地位)。
    正则项 α ∣ T l e a f ∣ \alpha|T_{leaf}| αTleaf可以避免过拟合的解释。正则项 α ∣ T l e a f ∣ \alpha|T_{leaf}| αTleaf考虑到了复杂度, α \alpha α值设置得好可以避免出现完全树和根结点这类的极端情况,因此可以避免过拟合。加入了正则项,目标函数将从“经验风险”变为“结构风险”,即结构风险=经验风险+正则项。
    纯结点的经验熵 H p = 0 H_p=0 Hp=0最小,即设 N t j = N t N_{tj}=N_t Ntj=Nt则有 H p = − ( 1 log ⁡ 1 + ∑ k = 1... K 且 k ≠ j 0 ) = 0 H_p=-(1\log 1+\displaystyle \sum_{k=1...K且k≠j} {0})=0 Hp=(1log1+k=1...Kk=j0)=0
    均结点的经验熵 H u = log ⁡ K H_u=\log K Hu=logK最大,即 H p = − ∑ k = 1 K 1 K log ⁡ 1 K = log ⁡ K H_p=-\displaystyle \sum^{K}_{k=1} {\frac{1}{K}\log\frac{1}{K}}=\log K Hp=k=1KK1logK1=logK

剪枝类型:

预剪枝、后剪枝

  • 预剪枝是在决策树生成过程中,对树进行剪枝,提前结束树的分支生长。
  • 后剪枝是在决策树生长完成之后,对树进行剪枝,得到简化版的决策树。

预剪枝依据:

  • 作为叶结点或作为根结点需要含的最少样本个数
  • 决策树的层数
  • 结点的经验熵小于某个阈值才停止

后剪枝思路:

  1. 如何由 T i T_i Ti剪枝得到 T i − 1 T_{i-1} Ti1
    如图
    R为r结点分支后的子树
  • C α ( r ) = C ( r ) + α C_\alpha(r)=C(r)+\alpha Cα(r)=C(r)+α
  • C α ( R ) = C ( R ) + N R ∗ α C_\alpha(R)=C(R)+N_R*\alpha Cα(R)=C(R)+NRα,其中 N R N_R NR为子树R的叶子结点数
  • 一般地有 C ( r ) > = C ( R ) C(r)>=C(R) C(r)>=C(R), 我们可以令 C α ( r ) = C α ( R ) C_\alpha(r)=C_\alpha(R) Cα(r)=Cα(R)求出 α = C ( r ) − C ( R ) N R − 1 \alpha=\frac{C(r)-C(R)}{N_R-1} α=NR1C(r)C(R)
  • 当我们把所有的非叶结点的 α \alpha α求出来后比较它们的 α \alpha α值,在最小的 α \alpha α所在结点处剪枝。
    为什么要在最小的 α \alpha α所在结点处剪枝:设给定一 α \alpha α来求两个结点 r 1 r_1 r1 r 2 r_2 r2处的损失函数 C α ( r 1 ) C_\alpha(r_1) Cα(r1) C α ( r 2 ) C_\alpha(r_2) Cα(r2)以判定是否适合继续分支,且使得给定的 α \alpha α介于它们自己的阈值参数 α 1 \alpha_1 α1 α 2 \alpha_2 α2之间,假设 α 1 \alpha_1 α1< α \alpha α< α 2 \alpha_2 α2。则
    对于 r 1 r_1 r1来说, α 1 \alpha_1 α1< α \alpha α α \alpha α给大了,参数占主导,剪枝能使得叶结点数(即参数的系数)变小,剪枝能使得 C α ( r 1 ) C_\alpha(r_1) Cα(r1)较小,剪枝更好;
    对于 r 2 r_2 r2来说, α \alpha α< α 2 \alpha_2 α2 α \alpha α给小了, C ( r 2 ) − C ( R 2 ) C(r_2)-C(R_2) C(r2)C(R2)的值占主导,即
    C α ( r ) − C α ( R ) C_\alpha(r)- C_\alpha(R) Cα(r)Cα(R)
    = C ( r ) + α − C ( R ) − N R ∗ α =C(r)+\alpha-C(R)-N_R*\alpha =C(r)+αC(R)NRα
    = [ C ( r 2 ) − C ( R 2 ) ] + [ 1 − N R ] ∗ α = [C(r_2)-C(R_2)]+[1-N_R]*\alpha =[C(r2)C(R2)]+[1NR]α
    不剪枝能使得叶结点数(即参数的系数)更大, C α ( r ) − C α ( R ) C_\alpha(r)- C_\alpha(R) Cα(r)Cα(R)更接近0,剪枝更好。
    我们看出参数阈值较小的 r 1 r_1 r1处剪枝更好,因此要在最小的 α \alpha α所在结点处剪枝。
  1. T i T_i Ti剪枝得到 T i − 1 T_{i-1} Ti1后,可以得出 T 0 − > T 1 − > T 2 − > . . . − > T n T_0->T_1->T_2->...->T_n T0>T1>T2>...>Tn,但不一定每次剪枝都能使得损失函数降低,可以对每一个 T i T_i Ti算出其损失函数进行比较,取损失函数值最小的那棵决策树。

注:10 决策树和随机森林实践
参考:http://blog.csdn.net/ritchiewang/article/details/50254009

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/833410
推荐阅读
相关标签
  

闽ICP备14008679号