【机器学习】- 极简系列 - 决策树

前置知识：

1、熵、条件熵、信息增益
熵与条件熵的定义为：

熵能表示随即变量的不确定性。根据等价无穷小的有：logx->x-1,xlogx->x(x-1)。基于此来验证下面的公式可以看出，当p为0或者1的时候，熵最下=0。这符合我们对不确定性的理解。实际上，对于一个二分类问题有：

2、基尼指数

第一部分：决策树

1.1 特征选择

ID3：最大化的信息增益。
C4.5：最大化信息增益比。

1.2 决策树的生成

递归的进行特征选择

1.3 剪枝

第二部分 CART

CART算法假设决策树是二叉树。

2.1 回归树

算法理解：
遍历所有的切分变量与切分点，每一次确定一种划分后：根据公式计算响应的平方差的和，最小值对应的切分变量与切分点就是最佳值。继续在子集上进项相同的操作，知道满足停止条件。

2.2 分类树

算法理解：类似于会归属，需要选择最佳的切分变量与切分点，区别在于回归树用最小二乘法选择，而分类树用基尼指数选择。

小结：决策树算法考量不同特征划分数据集带来的信息增益，不会考虑切分点，所以假如特征有M个候选值，那么就会有M叉，但是CART算法考虑切分变量+切分点的最佳组合，所以生成的是二叉树。

例题：

ID3决策树
CART回归树
CART决策树

参考：《统计学习方法》