之前泛泛看了下了Random Forest和决策树，现在落实到一个具体决策树算法：CART(Classification and Regression Tree)。
CART是1984年由Breiman, Friedman, Olshen, Stone提出的一个决策树算法，虽然不是第一个机器学习领域的决策树，但却是第一个有着复杂的统计学和概率论理论保证的决策树(这些话太学术了，引自参考文献[2])。
CART是一个二叉决策树，亦即决策树的每个内部节点(决策节点)最多有两个分支。因为之前有 博文 介绍过ID3和C4.5算法，所以这里只从确定最佳分裂属性和剪枝两方面介绍CART。
1. 确定最佳分裂属性(和最佳分裂点)
我们这里只考虑连续值的情况。对于每个输入属性的每个可能的分裂点(分裂点即相邻两个连续值的中点)，我们计算每个划分
Gini指标
：
，然后对该分裂点的两个划分的Gini指标求加权和。我们选取Gini指标最小的那个输入属性的分裂点进行划分。
按照以上规则生成一个完全增长的决策树，不需要任何停止条件。
2. 剪枝
因为上一步生成的决策树是没有停止条件的，所以这个决策树可能会非常大，对训练数据很可能会过度拟合，所以需要对决策树进行后剪枝。
CART算法采用的是 Cost-Complexy剪枝 :
我们用
来衡量一棵子树的代价复杂度。其中R(T)代表将这个子树替换为叶子节点后所带来的误差的增加，number-of-leaves为子树T的叶子节点的个数，α不是一个常数，而是一个从0开始增大到无穷大的数。对于决策树T，我们在α不是一个常数，而是一个从0开始增大到无穷大的数。逐步增加的过程中，每次选择使Rα最小的子树，并将之替换为一个叶子节点，对替换后的树迭代执行以上步骤。
上述过程可能略显复杂，我们可以用另外一个等价的剪枝方法来得到相同的结果： Weakest-Link-Pruning ：
(1)对于所有的子树STi，我们试图用合适的叶子节点来代替STi，然后计算增加的误差E与STi的叶子节点的比值。我们选择比值最小的那个子树STj，用合适的叶子节点代替之。
(2)重复迭代以上步骤，每次都替换掉一棵子树。我们会得到从完全增长的树T0到只有根节点一个决策节点的树Tn的一系列决策树：T0,T1,.....Tn。然后我们用独立的验证集(我们可以从可用数据集中抽取三分之一作为验证集，剩下的三分之二作为训练集)来验证各个决策树的分类准确性。选取准确性最高的决策树为最终的CART决策树。
参考文献：
[1] CART算法学习及实现
[2] 机器学习十大算法：CART
[3] Complexity-Based Evaluation Of Rule-Based Expert Systems
