本文结构:
分类与回归树,是二叉树,可以用于分类,也可以用于回归问题,最先由 Breiman 等提出。
分类树的输出是样本的类别, 回归树的输出是一个实数。
决策树生成和剪枝。
决策树生成:递归地构建二叉决策树的过程,基于训练数据集生成决策树,生成的决策树要尽量大;
自上而下从根开始建立节点,在每个节点处要选择一个最好的属性来分裂,使得子节点中的训练集尽量的纯。
不同的算法使用不同的指标来定义"最好":
分类问题,可以选择GINI,双化或有序双化; 回归问题,可以使用最小二乘偏差(LSD)或最小绝对偏差(LAD)。
决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时损失函数最小作为剪枝的标准。
这里用代价复杂度剪枝 Cost-Complexity Pruning(CCP)
回归树模型表示为:
其中,数据空间被划分成了 R1~Rm 单元,每个单元上有一个固定的输出值 cm。 这样就可以计算模型输出值与实际值的误差:
我们希望每个单元上的 cm,可以使得这个平方误差最小化,易知当 cm 为相应单元上的所有实际值的均值时,可以达到最优:
那么如何生成这些单元划分?
假设,我们选择变量 xj 为切分变量,它的取值 s 为切分点,那么就会得到两个区域:
当 j 和 s 固定时,我们要找到两个区域的代表值 c1,c2 使各自区间上的平方差最小,
前面已经知道 c1,c2 为区间上的平均,
那么对固定的 j 只需要找到最优的 s, 然后通过遍历所有的变量,我们可以找到最优的 j, 这样我们就可以得到最优对(j,s),并得到两个区间。
上述过程表示的算法步骤为:
即: (1)考虑数据集 D 上的所有特征 j,遍历每一个特征下所有可能的取值或者切分点 s,将数据集 D 划分成两部分 D1 和 D2 (2)分别计算上述两个子集的平方误差和,选择最小的平方误差对应的特征与分割点,生成两个子节点。 (3)对上述两个子节点递归调用步骤(1)(2),直到满足停止条件。
(1)对每个特征 A,对它的所有可能取值 a,将数据集分为 A=a,和 A!=a 两个子集,计算集合 D 的基尼指数:
(2)遍历所有的特征 A,计算其所有可能取值 a 的基尼指数,选择 D 的基尼指数最小值对应的特征及切分点作为最优的划分,将数据分为两个子集。 (3)对上述两个子节点递归调用步骤(1)(2), 直到满足停止条件。 (4)生成 CART 决策树。
1、是一种不等性度量; 2、是介于 0~1 之间的数,0-完全相等,1-完全不相等; 3、总体内包含的类别越杂乱,GINI指数就越大(跟熵的概念很相似)
定义: 分类问题中,假设有 K 个类,样本属于第 k 类的概率为 pk,则概率分布的基尼指数为:
样本集合 D 的基尼指数为:
其中 Ck 为数据集 D 中属于第 k 类的样本子集。
如果数据集 D 根据特征 A 在某一取值 a 上进行分割,得到 D1 ,D2 两部分后,那么在特征 A 下集合 D 的基尼指数为:
1、节点中的样本个数小于预定阈值, 2、样本集的Gini系数小于预定阈值(此时样本基本属于同一类), 3、或没有更多特征。
最后一列是我们要分类的目标。
例如,按照“体温为恒温和非恒温”进行划分,计算如下:
恒温时包含哺乳类5个、鸟类2个
非恒温时包含爬行类3个、鱼类3个、两栖类2个
得到特征‘体温’下数据集的GINI指数:
最后我们要选 GINI_Gain 最小的特征和相应的划分。
就是在完整的决策树上,剪掉一些子树,使决策树变小。
是为了减少决策树过拟合,如果每个属性都被考虑,那决策树的叶节点所覆盖的训练样本基本都是“纯”的,这时候的决策树对训练集表现很好,但是对测试集的表现就会比较差。
决策树很容易发生过拟合,可以改善的方法有: 1、通过阈值控制终止条件,避免树形结构分支过细。 2、通过对已经形成的决策树进行剪枝来避免过拟合。 3、基于Bootstrap的思想建立随机森林。
这里我们用 代价复杂度剪枝 Cost-Complexity Pruning(CCP) 方法来对 CART 进行剪枝。
从整个树 T0 开始,先剪去一棵子树,生成子树 T1, 在 T1 上再剪去一棵子树,生成子树 T2, 重复这个操作,直到最后只剩下一个根节点的子树 Tn, 得到了子树序列 T0~Tn, 利用独立的验证数据集,计算每个子树的平方误差或者基尼指数, 选择误差最小的那个子树作为最优的剪枝后的树。
那么这个子树序列是怎么剪出来的? 因为建模的时候,目标就是让损失函数达到最优,那剪枝的时候也用损失函数来评判。
损失函数是什么呢? 对任意子树 T,损失函数如下形式,cost-complexity function:
其中 CT 为误差(例如基尼指数),|T| 为 T 的叶节点个数,alpha 为非负参数,用来权衡训练数据的拟合程度和模型的复杂度。
alpha 固定时,一定可以找到一个子树 T,使得等式右边达到最小,那么这个 T 就叫做最优子树。
对固定的 alpha 找到损失函数最小的子树 T,二者之间有这样的关系:alpha 大时,T 偏小,alpha 小时,T 偏大。
那如果将 alpha 从小增大设置为一个序列,T 就可以从大到小得到相应的最优子树序列,并且还是嵌套的关系。
剪的时候,哪个树杈是可以被剪掉的呢? 很容易想到的是,如果剪掉后和没剪时的损失函数一样或者差别不大的话,那当然是剪掉好了,只留下一个点,就能代表一个树杈,这样树就被简化了。
以节点 t 为单节点树时,它的损失函数为:(后面剪枝后就可以用一个点来代替一个树杈)
以节点 t 为根节点的子树 Tt,它的损失函数为:(后面剪枝这个树杈)
那么接下来的问题就是能不能找到这样的点呢? 上面令 alpha=0,就有 Tt 和 t 的损失函数的关系为:
那么增大 alpha,当它为如下形式时:
此时,Tt 和 t 的损失函数相等,而 t 的节点少,那么保留 t 就可以了,Tt 就可以剪掉了。
那么在剪枝算法的第三步时,对每个 t,计算一下 gt,也就是能找到子树 Tt 和 t 的损失函数相等时的 alpha,
每个点 t 都可以找到符合这样条件的 alpha, 遍历所有节点 t 后,找到最小的这个 alpha,
第四步,再把这个 alpha 对应的节点 t 的子树 Tt 剪掉, 并用多数投票表决法决定 t 上的类别, 这样得到的剪枝后的树 T 记为 Tk, 这时的 alpha 记为 alpha k,
经过上面步骤,会得到: α1⩽α2⩽ ... ⩽αk⩽ ... T1⊇T2⊇ ... ⊇Tk⊇ ... ⊇{root}
下面这棵树,有三个点 t1≡root,t2,t3
α(1)=0
计算每个点的 gt:
t2,t3 时的 gt 相等,此时我们可以选择剪枝少的点,那就是 t3 剪掉。
并且 α(2)=1/8
这时剩下 t1,t2,再继续计算 gt:
t2 的小,所以剪掉 t2:
并且令 α(3)=1/8
最后剩下 t1,计算后 gt=1/4,所以 α(4)=1/4。
如此我们得到:α(0)=0,α(1)=1/8,α(2)=1/8,α(3)=1/4 并且得到了相应的子树, 接下来就可以利用独立的验证数据集,计算每个子树的平方误差或者基尼指数,
选择误差最小的那个子树作为最优的剪枝后的树。
资料: 统计学习方法 https://wizardforcel.gitbooks.io/dm-algo-top10/content/cart.html http://blog.csdn.net/baimafujinji/article/details/53269040 http://blog.csdn.net/luoshixian099/article/details/51811945 https://www.zhihu.com/question/22697086 http://mlwiki.org/index.php/Cost-Complexity_Pruning