决策树构建算法—ID3、C4.5、CART树

构建决策树的主要算法

ID3
C4.5
CART （Classification And Rsgression Tree）

ID3

ID3算法是决策树的一个经典的构造算法，内部使用：信息熵，信息增益，来进行构建：每次迭代选择信息最大的特征属性作为分割属性。
也就是说，在ID3算法中

节点纯度的度量我们用的是 “信息熵”
分裂特征的选择用的是信息增益度作为衡量指标

这和我们《决策树的构建三》用的思想是一样的。

信息熵越低——确定性越高——有序——数据越纯
信息增益——以A特征分割后,信息熵减少的越多，那就以为和Gain越大，说明分裂后信息的信息熵更低，数据更纯。
ID3算法用到的两个计算公式在决策树的构建中我们已经提到：
在这里插入图片描述

ID3算法具有以下特点

ID3算法只支持离散（类别型）特征属性，不支持连续特征属性
如果你有连续性属性，要用ID3算法，在没分列前，要讲连续属性进行离散化。
ID3算法构建的是多叉树

优点:

决策树构建速度快;实现简单;

缺点:

计算依赖于特征取值数目较多的特征，而属性值最多的属性并不一定最优
因为ID3构建决策树的时候固定构建的是多叉树，假如现在有X1，X2两个特征，X1有5种取值，X2有2种取值，现在将其构建成多叉树，如果以X1特征分裂会分成5个节点，每个节点只有2个，按照X2特征进行分裂的话，每个节点有5个样本，那么这个时候肯定按照X1特征进行分裂的树分裂后更纯。就意味着最终构建的决策树就依赖于属性值多的特征。
ID3算法不是递增算法
ID3算法是单变量决策树，对于特征属性之间的关系不会考虑
- 单变量（属性）决策树
  在进行分了的时候，每一次分裂只由于一个特征决定。（X1 = 是，X1=否）
- 多变量（属性）决策树
  反之，分裂时由多个特征决定（X1 = 是X2=否，X1=否X2=是）
抗噪性差
不做限制，训练集可以达到100%正确，但是，当有异常数据进来时，很容易被分错。
只适合小规模数据集,需要将数据放到内存中

C4.5

C4.5实际上是对ID3算法进行的优化算法。也是一种经典的决策树构建算法。
对比比ID3算法看一下C4.5算法

使用信息增益率来取代ID3算法中的信息增益,
在树的构造过程中会进行剪枝操作进行优化
能够自动完成对连续属性的离散化处理（可以对连续特征进行分裂）
C4.5构建的是多分支的决策树;
C4.5算法在选中分割属性的时候选择信息增益率最大的属性

涉及到的公式：
在这里插入图片描述
对于上述公式我们看个例子：

A ：分裂属性X的分布（已婚或未婚）
D：样本标签Y的分布（1或0）
H(A): 按照特征属性A进行分类样本D的信息熵（黑色为已婚，红色为未婚）
H(D):样本D中，按照标签1,0计算的信息熵
H(D|A)：按照特征属性A进行划分，划分后两个叶子结点按便签1,0计算的信息熵的和。
上边的图颜色上就是为了标注样本A属性类别，分裂的时候不是很正规，将就着看吧，将道理应该是一边全是黑色，一边全是红色。

优点：

产生的规则易于理解
准确率较高
实现简单

缺点：

对数据集需要进行多次顺序扫描和排序（，对连续特征进行分裂，实现连续特征离散化），所以效率较低
只适合小规模数据集，需要将数据放到内存中

CART

实际上现在构建决策树的时候只用到了CART算法
CART既可以做分类任务，也可以做回归任务
对比上两个构建算法：

重点：

CART使用：
- 基尼系数(分类树)，作为数据纯度的度量指标
  最后用多数投票法决定叶子节点代表的值。
- 均方差（回归树），作为数据纯度的度量指标
  最后的预测结果用节点中数据的平均值

根据公式基尼系数计算的是一个节点中标签Y的概率分布，但是如果你是一个连续值的话，这个概率就不好求了，这个时候不硬基尼系数作为纯度度量指标
回归任务们用均方差：
当叶子结点中的均方差越小——>叶子中的数据比较接近——>越纯（比如均方差为0，意味着所有样本的取值都一样，没有任何的波动，达到了最纯的条件）

使用基尼增益率作为分割属性选择的标准
选择基尼增益率最大的作为当前数据分割属性
CART允许特征多次使用
CATR构建的是二叉树

不管针对的是离散属性，还是连续属性，最后构建的都是二叉树，实际上，上一节我们用图像展示过三个度量纯度指标的效果实际上是一样的，对于我们最终构建的结果影响不大，但是构建的是多叉树还是二叉树，对最终决策的结果影响很大（多叉树分的会更细，一定能保证100%正确，反而会导致过拟合，我是这么认为的）。CART与上边两种算法最大的区别就在于左后构建的是一颗二叉树。

在这里插入图片描述