1 决策树原理

1.1 决策树的基本概念

决策树的组成：

- 根节点：第一次划分数据集的地方

- 非叶节点与分支：代表中间过程的各个节点

- 叶节点：数据最终的决策结果

1.2 衡量标准

什么特征能够把数据集划分得更好，也就是哪个特征最好用，就把它放到最前面。

数据中有那么多特征，怎么分辨其能力呢？这就需要给出一个合理的评判标准，对每个特征进行评估，得到一个合适的能力值。

熵指的是物体内部的混乱程度，熵值越高，混乱程度越高。模型希望同一类别的数据放在一起，不同类别的数据分开。熵值高意味着数据没有分开，这可不是模型想要的。

熵的公式

在构建分类决策树时，不仅可以使用熵值作为衡量标准，还可以使用Gini系数，原理基本一致，公式如下：

Gini系数

1.3 信息增益

数据在没有进行划分之前，可以得到其本身的熵值，在划分成左右节点之后，照样能分别对其节点求熵值。比较数据划分前后的熵值，目标就是希望熵值能够降低，如果划分之后的熵值比之前小，就说明这次划分是有价值的。

信息增益公式

如何找到最合适的特征：

创建决策树时，基本出发点就是去遍历数据集中的所有特征，看看到底哪个特征能使熵值下降最多，信息增益最大的就是要找的根节点。接下来就要在剩下的特征中再找到使得信息增益最大的特征，以此类推，直到构建完整个树模型。

1.4 决策树构造实例

决策树的构建过程就是不断寻找当前最优特征的过程，如果不做限制，就会遍历所有特征。

1.5  连续值问题

对于身高、体重等连续型指标，不仅需要找到最合适的特征，还需要找到最合适的特征切分点。

如何选择最合适的切分点呢？需要不断进行尝试，也就是不断二分的过程。

1.6 信息增益率

ID3算法

基于信息增益的构建方法，ID3算法存在的问题：如果利用类似ID号码之类的特征计算信息增益，可能得到的结果就是它能把所有样本都分开，此时信息增益最大。但是，类似ID这样的特征却没有任何实际价值，所以需要对信息增益的计算方法进行改进，使其能够更好地应对属性值比较分散的类似ID号等特征。

C4.5算法

使用信息增益比率作为选择分支的准则去解决属性值比较分散的特征。

例如ID这样的特征，由于取值可能性太多，自身熵值已经足够大，如果将此项作为分母，将信息增益作为分子，此时，即便信息增益比较大，但由于其自身熵值更大，那么整体的信息增益率就会变得很小。

1.7 回归问题求解

决策树也可以解决回归问题，只需要将衡量标准转换成其他方法即可。

用来衡量不同样本之间差异最好的方法就是方差。在选择根节点时，分类任务要使熵值下降最多，回归任务只需要找方差最小的即可。

最终预测结果也是类似的，分类任务中，某一叶节点取众数（哪种类别多，该叶节点的最终预测类别就是多数类别的）；回归任务中，只需要取平均值作为最后的预测结果即可。

2 决策树剪枝策略

2.1 剪枝策略

通常情况下，剪枝方案有两种，分别是预剪枝和后剪枝，虽然两种方案目标相同，但做法上有所区别。

1）预剪枝是在决策树建立的过程中进行，一边构建决策树一边限制其规模

2）后剪枝是在决策树生成之后才开始，先一口气把决策树构建完成，然后再慢慢收拾它

预剪枝

在构造决策树的同时进行剪枝，目的是限制决策树的复杂程度，常用的停止条件有：树的层数、叶节点的个数、信息增益阈值等指标，这些都是决策树算法的输入参数，当决策树的构建达到停止条件之后就会自动停止。

后剪枝

决策树构建完成之后，通过一定的标准对其中的节点进行判断，可以自己定义标准，常见的衡量标准：

以上式子与正则化惩罚相似，只不过这里惩罚的是树模型中叶节点的个数。C(T)为当前的熵值，Tleaf为叶节点个数，要综合考虑熵值和叶节点个数。

- 分裂次数越多，树模型越复杂，叶节点越多，熵值也会越小；分裂次数越少，树模型越简单，叶节点个数越少，熵值越高。

- 最终的平衡点在于系数α（它的作用与正则化惩罚中的系数相同），其值的大小决定了模型的趋势倾向于哪一边。

- 对于任何一个节点，都可以通过比较其经过剪枝后Cα(T)值与未剪枝前Cα(T)值的大小，以决定是否进行剪枝操作。

现阶段在建立决策树时，预剪枝操作是必不可少的，其中涉及的参数也比较多，需要大量的实验来选择一组最合适的参数，对于后剪枝操作来说，简单了解即可。

学习资料：唐宇迪机器学习课程 第七章 决策树算法