决策树 | 分裂算法：ID3，C4.5，CART

在决策树算法逻辑篇中，我们讲解了决策树的构建方式，下面我们来聊一聊决策树中常用的三个算法

一. ID3算法

1. 信息增益

ID3算法是构造决策树的一个经典算法

	使用信息熵以及信息增益来进行构建
	每次迭代选择信息增益最大的特征属性作为分割属性
1
2

2. ID3算法特点

1. ID3算法只支持离散的特征属性，不支持连续的特征属性
2. 若想处理连续的特征属性，要先对连续值进行离散化处理
3. ID3算法构建的是多叉树，不保证二叉树

详细过程参考决策树算法逻辑篇中的银行示例

二. C4.5算法

对于ID3算法以信息增益为划分的标准，可以发现存在这样一种极端：

当收入按照60，80，87.5，95划分为五叉树时，可以直接得到熵为0的五个叶子节点，且此时系统的信息增益最大
 
此方案进行划分时，只需一次分裂就可以建好决策树

但是，显然上述这种情况下的划分并不合理；为了解决信息增益划分时的不合理情况，我们引入信息增益率的概念

1. 信息增益率

C4.5算法

	使用信息增益率来进行构建
	每次迭代选择信息增益率最大的特征属性作为分割属性
1
2

$$Gain-ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$

$Gain(D,a)$：信息增益
$IV(a)$：属性a的固有值

$$IV(a)=-\sum _{v=1}^v\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$
例子：
房子样本4个是，6个否
$$IV(房产)=-\frac{4}{10}{\log }_2\frac{4}{10}-\frac{6}{10}{\log }_2\frac{6}{10}=3.747$$
婚姻样本4个单身，3个已婚，3个离婚
$$IV(婚姻)=-\frac{4}{10}{\log }_2\frac{4}{10}-\frac{3}{10}{\log }_2\frac{3}{10}-\frac{3}{10}{\log }_2\frac{3}{10}=4.003$$

2. C4.5算法特点

	C4.5算法以信息增益率为划分标准
		有效避免了叉越多，信息增益越大的影响
	
	结合上面的公式分析，我们可以得出：
		树分支越多，IV(a)固有属性越大，信息增益率也就相对越小
1
2
3
4
5

1. 在树的构造过程中会进行剪枝操作进行优化
2. 能够自动完成对连续属性的离散化处理
3. C4.5构建的是多分支的决策树

三. CART算法

1. Gini系数公式

CART算法

	采用Gini系数来衡量划分的有效性
1

$$Gini=\sum _{i=1}^n[p_i\ast (1-p_i)]=1-\sum _{i=1}^n{p}_i^2$$

2. CART算法特点

1. 选择gini增益最大的属性作为当前数据集的分割属性
2. 可用于分类和回归两类问题
3. CART构建是二叉树

3. CART回归树的分裂评价指标

MSE均方误差划分指标：

	样本越集中，值越小，划分越好
1

$$MSE=\frac{1}{n}\sum _{i=1}^n(y_i-{\bar{y}}_i{)}^2$$

MAE绝对误差划分指标：
$$MAE=\frac{1}{n}\sum _{i=1}^n|y_i-{\hat{y}}_i|$$

小节

• ID3，C4.5，CART三种算法适用在小规模数据集上，即内存要能装得下

• ID3，C4.5，CART采用单变量决策树

    	单变量的决策树：每次分裂时只选择了一个特征进行分裂
    		实际现实任务时每次只选择一个特征进行分裂效果并不好
    		因此我们希望一次分裂时综合考虑好几个特征，组合成一个综合条件，但此时模型会相对复杂，计算量大
  1
  2
  3

• 一般采用CART算法构造树，ID3和C4.5算法在sklearn库中没有真正实现

• 回归树中，叶子节点的预测值一般为叶子节点中所有值的均值

• 分类树中，叶子节点的预测值一般为叶子节点中概率最大的类别

注意：三种算法的主要区别在于划分指标不同
      本质区别在于是否为二叉树

	也就说，CART算法的划分指标当然也可以选用信息增益率来划分
	只要明确构建的树为二叉树，那么关于ID3存在的问题和C4.5想要解决的问题也就不存在了
1
2

---

感谢阅读