决策树与随机森林——原理篇（二）
第一篇我们主要关注了根结点及内部结点的选择
第二篇主要关注如何处理“过拟合”现象
参考
大致了解机器学习——AI 算法 归档 - 产品经理的人工智能学习库 (easyai.tech)
医学僧的科研日记之机器学习系列——决策树与随机森林（1）—— 决策树算法数学推导与实例演练 (qq.com)
问题一、什么是过拟合？
个性化与泛化是一个相互矛盾概念，就像个体化诊疗与指南的矛盾一样。
决策树对训练数据可以得到很低的错误率，但是运用到测试数据上却得到非常高的错误率，这就是“过拟合现象”。
具体解释如下：对于决策树，我们希望每个叶子节点分的都是正确的答案，所以在不加限制的情况下，决策树倾向于把每个叶子节点单纯化，那如何最单纯呢？极端情况下，就是每个叶子节点只有一个样本，那这样，这个模型在建模集的准确率就非常高了。但是，这又带来了一个问题——过拟合，这会导致该模型在建模集效果显著，但是验证集表现不佳。
这可能有以下几个原因：
1、训练集里面有噪音数据，干扰了正常数据的分支
2、训练集不具有特征性
3、特征太多
使用信息增益来种树时，为了得到最优的决策树，算法会不惜带价倾向于将熵值降为最小（可能的话甚至为0），这颗树会显得非常的冗杂。
问题二、如何避免过拟合现象？
通过限制复杂度参数（complexity parameter），抓主要矛盾，来防止模型的过拟合。具体的计算过程可以参考<医学僧的科研日记>，这里我直接引用
我们先不考虑模型的泛化能力，那么得到一棵表现最优的树可以根据所有叶结点中的预测误差来衡量，即模型与训练数据的拟合程度。设树 T 的叶结点个数为 N，n 是树 T 的一个叶结点，该叶结点有 Nt个样本，其中 k 类的样本点有 Ntk 个，K=1，2，3......K, K 为样本空间中的所属分类数量。叶结点 t 上的熵 Ht(T) 为
图片
这个代表了该叶节点 t 的混乱程度，极端来看，如果该叶节点 t 只有一个分类 kn 时，该节点的 Ht(T) 最终会等于0，那么可以说，Ht(T) 接代表了该叶节点对所属路径数据分类的彻底性。考虑到所有叶节点里面每个叶节点的样例个数不同，所以，我们得到了决策树损失函数的前体：
图片
用 C(T) 来衡量模型对训练数据的整体测量误差。
但是，问题来了，如果仅仅用 C(T) 来作为优化目标函数，如上所述，该模型就会走向过拟合的结果。因为模型会倾向将每个分支划分到最细来使每一个叶节点的 Ht(T) = 0，最终使得 C(T) 最小。
为了避免过拟合，我们需要给优化目标函数增加一个正则惩罚项，正则项应该包含模型的复杂度信息，对于决策树来说，其叶节点的数量越多就越复杂，所以损失函数如下：
图片
参数 α 控制了 C(T) 和 T 两者之间的影响程度，如果 α 越大，则倾向于形成简单的树，如果 α 越小，则倾向于形成较复杂的树。注意，剪枝的目的不是为了最小化损失函数，剪枝的目的是提高模型的泛化能力。对于决策树，如果其叶节点的数量越多，说明决策树模型对训练数据的细节反应的就越多，从而弱化了模型的泛化能力。所以，提高泛化能力需要进行剪枝。而 α 的值衡量的是损失函数中叶节点数量的权重，α 越大，在最小化损失函数时候，需要对叶节点数量考虑更多一些，α 越小，考虑叶节点数量会更少一些。α 可以看作一个系数，不同的 α 对应了不同的损失函数，而对于这些所有的损失函数来说，在训练集上进行决策树生成的步骤都一样，差别只是在判断某些节点是否进行展开的结果不一样罢了。
剪枝（pruning）则是决策树算法对付过拟合的主要手段，剪枝的策略有两种如下：
预剪枝：在构建决策树的过程中，提前停止
后剪枝：决策树构建好，才开始剪枝
一、预剪枝
定义：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，如果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
在 rpart 函数中，有个参数叫做 control，它可以控制 rpart 的各种细节参数，而预剪枝就是在这里设置的，比如我们可以规定 minsplit = 100，就是指每个内部节点中所含样本最小数最小为100；也可以设置 minbucket = 50，就是指叶节点中所含样本最小数目为50，设置树的深度 maxdepth = 3 就是最大不超过3，设置复杂度 cp = 0.2; 如果这些条件没满足，那么决策树就是停止划分下去，这就是预剪枝。
二、后剪枝
对于 rpart 生成的结果，使用 prune 函数对其进行后剪枝，一般选择最小交叉验证误差 xerror 对应的复杂度参数 cp 值，这种方法也叫做最小代价复杂度剪枝法。
总结
相比于预剪枝，后剪枝往往应用更加广泛，
后剪枝通常比预剪枝保留了更多的分支
后剪枝的欠拟合风险很小，泛化能力往往高于预剪枝决策树
后剪枝训练时间比未剪枝和预剪枝决策树要长很多
