决策树代价复杂度剪枝算法介绍
文 | 毕马威大数据挖掘
众所周知,决策树算法是数据挖掘中一种非常常用的算法,这种算法不仅可以直接对个体进行分类,还可以预测出每个观测属于某一类别的可能性,因变量可以是二分变量,也可以有多种取值,因此该方法兼备了判别分析、二元logistic模型和多元logistic模型的功能。由于这些特点,决策树算法还常被用作基分类器来进行集成学习,比如随机森林算法就是基于CART构建起来的。
决策树也可根据节点分裂规则不同而进行细分,比如CART、ID3和C4.5等。不过,本期我们不准备对决策树的算法进行全面的介绍,仅仅对应用比较广泛的CART算法中的代价复杂度剪枝进行一下理论上的探讨。
1. 为什么要剪枝?
CART(classification and regression trees)实际上包括了两部分的内容,第一部分涉及因变量是离散变量的分类模型,也就是所谓的分类树;第二部分涉及了因变量是连续变量的回归模型,即回归树。但第二部分内容在实际数据挖掘项目中应用的比较少,因此这里我们只介绍分类树的剪枝算法。
决策树建模属于有监督算法,因变量属于离散变量,而自变量可以是连续变量或离散变量。一般来讲,只要决策树充分地生长,就可以将训练样本中的所有个体进行完美的分类,即每个终节点里面个体的因变量取值都是一样的。
但是我们都知道,现实世界中的数据总会存在不同程度的噪音,比如数据的错误、偶然以及冗余信息等,如果让模型完美拟合训练数据,实际应用时我们会受到噪音的误导。因为这些噪音并不是真实的规律,将模型应用于验证数据时,模型的精度会出现大幅度的下降,即所谓的过拟合现象(overfitting)。
过拟合是很多机器学习算法中都必须考虑的问题,举一个例子,读中学的时候迫于考试压力,有的同学采取题海战术,甚至把题目背下来,但是一到考试,他就考得很差,因为考试时出现的题目与平时相比肯定经过了一些变化,他非常复杂地记住了每道题的做法,但却没有提炼出通用的、规律性的东西。
相反,背英语作文框架的同学往往会取得较高的分数,因为这些框架是通用的,是规律性的东西。我们训练决策树模型也是一个道理,不需要让模型“记住”太细节的东西,更希望它能“记住”那些规律性的东西。
解决这种问题的一个思路,就是先让决策树自由地生长,使之对训练样本有非常完美的拟合,然后再利用规则剪掉部分枝叶,达到精简决策树的目的;代价复杂度剪枝就是这种思路。下面我们来介绍这种算法的基本原理。
2. 成本复杂测量度的定义
我们不妨用Tmax来代表一颗充分生长的决策树,而T代表它的子树(subtree),用
表示该子树中叶子节点个数,即为树T的复杂度。α≥0表示复杂参数,R(T)是T的误判成本。Rα(T)表示在复杂参数为α时T的成本复杂测量度:
,现在我们希望在误判成本R(T)和复杂度之间追求一个平衡,希望得到较小的成本复杂测量度。
对于每一个α,我们都可以找到使得Ra(T)达到最小的子树T(α)。当α很小的时候,每一个叶子结点带来的复杂成本也较小,这样为了追求Rα(T)最小化,子树T(α)往往会比较“茂盛”,但是随着α的增大,惩罚因子
也比较大,子树T(α)会逐渐变得“枝叶凋零”,当α变得足够大的时候,T(α)会只剩下一个根结点。尽管α的取值可能无限多,但是Tmax的子树其实是有限的,这样就可以生成一系列子树Tmax>T1>T2>…>{t1}。{t1}就是最后剩下的那个根结点。那么,接下来的工作就是找到一种有效的算法,可以很高效地寻找到这一系列的子树。
3. 子树序列的生成
1)子树T1的生成
子树序列生成的起点是T1。由于理论上可以证明,对于任意非叶子节点t与其子树tL和tR之间存在关系:R(t)≥R(tL)+R(tR)。即:t节点的误判成本不会小于两个子树的误判成本之和。如果R(t)=R(tL)+R(tR),不分裂t节点,决策树会更加简洁,因此可以剪掉子树tL和tR。将Tmax所有满足该条件的枝干都剪掉,就得到子树T1。需要注意的是,子树T1的生成是根据误判成本来的,与成本复杂测量度无关。
2)其他子树的生成
剪枝实际上是在非叶子节点t和以t为根结点的子树之间进行选择。对于t本身而言,其成本复杂测量度:
而以t为根结点的子树的成本复杂测量度:
如果Rα(T)与Rα(Tt)相等,基于简洁性的原因,t的枝干应该被剪掉,显然此时:
理论上来讲,
,因此α是满足大于0的条件的。于是根据以下规则,产生了子树序列T2,…,{t1}:让α从0开始增加,依次将满足上式的枝干剪掉。每一个子树对应的复杂参数依次记为α2, α3, ……。
至此,我们就得到了子树序列T1>T2>…>{t1},这种方法从T1开始剪枝,初始时往往会剪掉叶子节点较多的枝干,但是随着树越来越小,被剪掉枝干的叶子节点会越来越少。不过,究竟取哪一个子树作为最终的模型,还需要利用验证数据集来进行选择。实际项目中,我们主要运用独立样本法或交叉验证的方法来进行选择,关于这个问题,下一期文章中将有详细介绍。
End.