构造和剪枝

我们在做决策树的时候，会经历两个阶段：构造和剪枝。

构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程。

在构造过程中，会存在三种节点：

根节点：

就是树的最顶段，最开始的那个节点。

内部结点：

就是树中间的那些节点。

叶节点：

就是树最底部的节点，也就是决策结果。

对决策树进行减枝是为了减少过多的判断，同时可以防止过拟合的发生。

一般来说，减枝可以分为预剪枝和后剪枝。

预剪枝

是在决策树构造时就进行剪枝。方法是在构造过程中对节点进行评估，如果对某个节点进行划分，在验证过程中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。

后剪枝

就是生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，对分类准确性影响不大或者有所提升，那么就可以把该子节点树进行剪枝，用此节点子树的叶节点来替代该节点，类标记为这个节点子树最频繁的那个类。

纯度和信息熵

在决策树构造的过程中还需要用到两个概念，纯度和信息熵。

纯度

可以理解为让目标变量的分歧最小。

例如，有三个不同的集合：｛1，1，1，1，1，1｝， ｛1，1，0，1，0，1｝，｛1，0，1，0，1，0｝

则按照纯度的指标来说，集合1>集合2>集合3。

信息熵

表示了信息的不确定度，其数学公式为：

其中，表示了节点t为分类i的概率。

ID3算法

此算法计算的是信息增益，信息增益指的是划分可以带来纯度的提高，信息熵的下降。

信息增益个公式可以表示为：

其中，是父节点，是子节点，中的作为节点的属性选择。 

C4.5算法

此算法基于ID3算法进行了改进：

1.采用信息增益率

ID3算法在计算的时候，倾向于选择取值多的属性。而C4.5采用信息增益率的方式来选择属性。

信息增益率=信息增益/属性熵

2.采用悲观剪枝

悲观剪枝是后剪枝技术的一种，通过递归估算每个内部结点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。

3.离散化处理连续属性

4.处理缺失值