模型算法基础——决策树剪枝算法(三)

在经过前两篇模型算法基础——决策树剪枝算法(一)和模型算法基础——决策树剪枝算法(二)之后,相信同学们对误差降低剪枝(REP)和悲观错误剪枝(PEP)已经有了一定的了解了,那么今天我们再来介绍一种剪枝算法——代价复杂度剪枝(Cost Complexity Pruning/CCP)

代价复杂度剪枝分为两步:

第一步:在所有非叶子节点中寻找代价复杂度参数最小的节点,其中代价复杂度参数为:

其中e(T)为错分率,p(T)为该节点所覆盖的样本量占总样本量的比例,L(T)为T节点下叶子节点的个数。

还是前两篇的那个栗子,假设总样本量为60,计算节点T4的代价复杂度参数:

第二步:循环对代价复杂度参数最小的节点进行剪枝(有多个节点同时取到最小值时取叶子节点最多的节点),直到只剩下根节点,可得到一系列的剪枝数,其中T0为原始的决策树,Tm为根节点,Ti+1为Ti剪枝后的结果。在这一系列的剪枝树中,根据实际的误差估计决定最优的决策树。

代价复杂度参数α可以理解为代价和复杂度之间的关系,剪枝后叶子节点的个数(复杂度)减少,但是错分样本个数(代价)增多了。CCP是在一系列子树中选择最优树,因此结果也较为准确。

除此之外,还有Minimum Error Pruning(MEP), CriticalValue Pruning(CVP), Optimal Pruning(OPP), Error Based Pruning(EBP)等等剪枝方法,这些方法各有优缺点和针对性,感兴趣的同学可以学习一下。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20171227G06E4F00?refer=cp_1026

扫码关注云+社区