CART决策树

分类与回归树（Classification and Regression Trees, CART）

不同于ID3, C4.5, CART本质是对特征空间进行二元划分（即CART生成的决策树是一棵二叉树, C4.5是多个分支), 并能够对标量属性（nominal attribute）与连续属性（continuous attribute）进行分裂。

标量属性分叉： = 和 !=

连续属性分叉：阈值ε取属性相邻值的平均值，找到Gini指数最大的ε值(Gini越大，说明这个临界点越有区分度)

Gini系数

流程：

• 若满足停止分裂条件（样本个数小于预定阈值，或Gini指数小于预定阈值（样本基本属于同一类，或没有特征可供分裂），则停止分裂；
• 否则，选择最小Gini指数进行分裂；
• 递归执行1-2步骤，直至停止分裂。

剪枝：

CART剪枝与C4.5的剪枝策略相似，均以极小化整体损失函数实现。同理，定义决策树T的损失函数为：

屏幕快照 2017-07-13 21.48.35.png

参考： http://www.cnblogs.com/en-heng/p/5035945.html