决策树的剪枝
由于生成的决策树会存在过拟合的现象，需要对决策树进行简化，这个过程叫做剪枝。
剪枝可分为：预剪枝 和 后剪枝
预剪枝：基于信息增益准则，找出最佳分支结点时候通过验证集计算这个节点的验证集精度，如果该节点的划分不能提高验证集合的精度，那么这个节点将不允许被划分。预剪枝虽然降低了过拟合的风险，而且减少了训练时间和测试时间的开销，但这样也带来了欠拟合的风险。
后剪枝：对已经生成的决策树做剪枝操作。本章主要讲述后剪枝操作。
其实三种决策树（ID3、C4.5、CART）剪枝过程都相同，只是对当前树的评价标准不一样：信息增益、信息增益率、基尼指数。
CART剪枝
剪枝过程：
1.剪枝，形成一个子树序列T0，T1，T2....Tn
2.交叉验证，选最有子树
1.剪枝
决策树的剪枝往往通过极小化决策树整体的损失函数来实现。
在减持过程中指数的损失函数可以定义为。
以r为根的子树：
剪枝前的损失函数：
剪枝后的损失函数
只要令
将内部节点都算一遍，原来的树是R0，R0中剪去最小的Rt，得到R1。
同样在R1中剪去最小的Rt子树，得到R2
重新计算，一直这样剪枝下去，直到根节点
最后得到n个子树：R0，R1，R2......Rn
2.交叉验证，选取最优子树
利用验证数据集，测试各子树R0，R1，R2......Rn的平方误差和基尼指数，平方误差或者基尼指数最小的决策树被认为最优的决策树。
评价函数：
网友评论