一、决策树：分类决策树模型是一种描述实例进行分类的树形结构。

二、决策树学习

三、决策树特征选择

1、信息增益：熵

2、

3、信息增益比

四、决策树的生成

1、ID3算法

2、C4.5算法

五、剪枝

1、

2、预剪枝方法

限定决策树的深度；

设定一个阈值；

设置某个指标，比较节点划分前后的泛化能力。

3、决策树后剪枝

降低错误剪枝：

4、悲观错误剪枝（PEP）

特点：

不需要分离剪枝数据集，有利于实例较少的问题；

误差使用了连续修正值，使得适用性更强；

由于自上而下的剪枝策略，PEP效率更高；

可能会修剪掉不应剪掉的枝条。

5、最小误差剪枝（MEP）

原理：根据剪枝前后的最小分类错误概率来决定是否剪枝。自下而上剪枝，只需要训练集即可。

6、基于错误剪枝（EBP）

原理：根据剪枝前后的误判个数来决定是否剪枝。自下而上剪枝，只需要训练集即可。

7、代价-复杂度剪枝（CCP）

原理：根据剪枝前后的损失函数来决定是否剪枝。

六、CART算法

1、基尼指数

2、特征下的基尼指数

特征A条件下，样本集D的基尼指数为：

基尼指数在0~0.5之间，越小越特征确定性越高。

3、

4、回归树生成

5、剪枝