一、例子引入
由于决策树算法很容易对训练集过拟合而导致泛化能力差,所以对于建立好的决策树需要进行剪枝处理,CART算法剪枝过程是测试集用于修正模型的最佳体现。例如,有如下的决策树模型,其中,黑色数字表示训练集上的分类情况,红色数字表示模型作用于验证集时的分类情况。
二、CART 算法利用验证集进行剪枝
(1)判断每个叶节点在验证集上的错误率。节点4的错误率 ,节点5的错误率,节点6的错误率,节点7的错误率为;
(2)计算子节点总加权平均错误率,并和父节点进行比较。加权方法就是乘以验证集中该节点样本量占父节点样本总量的百分比,例如以节点2为父节点,其错误率为,而其对应的子节点的加权平均错误率为 ,也就是说子节点的错误率更高,所以考虑剪枝。同样地,可以计算出节点6和节点7的加权平均错误率为 ,而其父节点(节点3)的错误率为,因此也考虑剪枝处理。
(3)重复上述过程,直到模型错误率不在降低。剪枝过后继续往上计算,节点2和节点3的加权平均错误率为 ,比父节点(节点1)的错误率 要小,因此保留该节点,停止剪枝。
可以看出,CART 算法剪枝过程更易于理解也更便于操作,同时可以看到,验证集不仅能够对模型的准确率做出评估,同时还能起到修正、优化模型的作用。