决策树

• 决策树是一个树形结构，每个非叶节点表示一个特征属性的测试（也就是条件），每个分支代表这个特征属性在某个值域上的输出（也就是满足某条件的下一步），每个叶节点存放一个类别。对于待预测数据，从根节点开始根据节点的条件选择不同的分支直到到达叶子节点，得到其预测类别。

  由上述对决策树的定义我们可以直到决策树也是一个用于分类的监督学习模型，当然我们依然可以使用决策树进行回归，此时称为回归决策树，叶子节点上输出数值而不是类别标签。

  决策树和kNN算法一样，理解起来非常直观易懂，例如下面是一个现实生活中决策树的例子

• 我们会发现所谓决策，就是对数据进一步提纯，将其分裂成两个不同的集合，不断进行这个过程直到得出最终结果。

  显然样本最终属于什么类别取决于节点中的各个分支，我们当然可以人为的构建决策树，但是如何让模型从数据特征空间中构建出决策树，才是机器学习要干的事。

ID3

• ML中的决策树最早是由Quinlan提出的ID3（Iterative Dichotomiser 3）算法，后续演变为C4.5和C5.0算法（C代表Classifier）。

  对于ID3算法，其使用信息增益做贪心算法来进行划分，总是挑选信息增益最大的特征划分数据，使得数据更加有序。

信息增益

• 什么是数据的信息增益呢，我们首先要了解信息熵的定义，信息熵是信息的期望值，用来表示信息的混乱、无序程度。

  信息熵定义如下

  $$H(D) = -\sum_{i=1}^m{p_i\log_2(p_i)}$$

  其中$p_i$表示第$i$个类别在训练集$D$中出现的概率，也就是这个类别样本数量占总量的比率。

  信息增益就是熵减小的值，也就是划分前后的熵值差，也就是评估数据变有序多少的指标，例如对于数据集$D$属性$A$进行划分，其取值可能包含$v$种，$D_j$代表$A=j$的样本子集，则选择属性$A$进行划分得到信息增益为

  $$\mathrm{Gain}(A) = H(D) - \sum_{i=1}^v{\frac{|D_j|}{|D|}H(D_j)}$$

数据集划分

• 有了信息增益的计算方法之后，我们便可以尝试使用每一个特征划分数据集，计算对于的信息增益，再选择收益最大的那一个特征来划分数据。

  注意划分并不一定得到两个子集，也可能会有多个子集，也就是说决策树并不一定是一颗二叉树。

  最终我们不断递归的划分数据集，直到最底层的子数据集中只有一个类别，此时我们便完成了决策树的构建。

提示

• 在统计学领域，还有CART算法，其思想和ID3类似，也是采用贪心策略，不过CART采用的是基尼系数作为指标进行划分

C4.5

• ID3算法虽然简洁易用但也存在一些缺点，其基于贪心算法每次选取取值较多的特征可能并不是全局最优解，且ID3算法容易产生过拟合问题。

  我们来看一些ID3的改进算法，C4.5算法，在这个算法中增加了分裂信息$SI$的定义

  $$SI(A) = -\sum_{i=1}^v{\frac{|D_j|}{D}}\log_2\left(\frac{|D_j|}{D}\right)$$

  C4.5将使用信息增益和分裂信息的比值计算出信息增益率

  $$\mathrm{GainRatio}(A) = \frac{Gain(A)}{SI(A)}$$

  随后C4.5将选择信息增益率最大的属性进行划分而不是直接选择最大的信息增益属性，这样的好处是惩罚取值较多的属性，显然我们可以看到$SI$的值取决于$D_j$的数量，$D_j$越大，$SI$越大从而信息收益率越小，克服了ID3算法倾向于选择取值较多的属性的缺点。

后剪枝算法

• 对于过拟合问题，C4.5使用后剪枝算法和交叉验证对决策树进行剪枝处理。

  后剪枝（Post-Pruning）即先构建完整的决策树，再对每个节点进行错误估计，去掉错误估计较大的一些分支。对C4.5来说，使用的是后剪枝算法中的悲观错误剪枝法（PEP）。

  对于一个叶节点来说，它的错误率被定义为

  $$r(t) = \frac{e(t)+0.5}{n(t)}$$

  其中$e(t)$代表到达节点$t$但不属于节点$t$所标识的类别的样本数目，$n(t)$代表到达节点$t$且属于第$i$类的样本数目。也就是说错误率$r(t)$就是计算来到这里的样本有多少是不该来的。

  同时对于一个子树节点（非叶子节点），它的错误率为

  $$r(T) = \frac{\sum_{i=1}^L{e(i)+0.5L}}{\sum_{i=1}^L{n(i)}}$$

  其中$L$代表以$T$为根节点的子树中叶节点的个数，其实也就是计算到子树的所有样本中错误样本的占比。其中$0.5$是一个惩罚因子，可根据情况修改。

• 剪枝判断：

  对于每个叶节点，我们可以看成一个二分类问题（多分类也看成二分类处理），在剪枝评估时，我们将统计每个叶节点的错误率，所以错误可以看成是一个二项分布($\sum n(t)$为样本个数，正确概率为$1-r(T)$)。此时我们可以得到子树错误的标准差

  $$\begin{aligned} \mathrm{SE}(T) &= \sqrt{np(1-p)} \\ &= \sqrt{\sum_{i=1}^L(e(i)+0.5L)(1-r(T))r(T)}\\ &= \sqrt{\left(\frac{\sum_{i=1}^L{n(i)}-\sum_{i=1}^L{e(i)+0.5L}}{\sum_{i=1}^L{n(i)}}\right)\sum_{i=1}^L{e(i)+0.5L}} \end{aligned}$$

  则我们可以引出剪枝判断标准，当剪枝后错误$\le$剪枝前错误时，我们便进行剪枝，即

  $$r(t)\le r(T)+\mathrm{SE(t)}$$

  其中标准差充当判断的置信区间。

• 在剪枝时，从根节点开始自顶向下遍历，按照如下步骤进行：

  1. 删除以此节点为根的子树，使其称为叶节点；
  2. 根据多数表决法，赋予该节点关联的训练数据类别；
  3. 比较删除前后的剪枝判断条件，决定是否剪枝该节点。

为啥叫悲观剪枝

• 很明显和悲观锁类似，总是认为每个子树都应该被剪枝去计算一次错误进行剪枝判断。

交叉验证

• C4.5中使用K-Fold交叉验证算法进行性能评估，同样需要先计算出完整的决策树，设叶节点数为$n$，按照如下步骤进行K-Fold交叉验证

  1. 将数据集划分为k个大小相似的子集；
  2. 对于每个子集，如下处理：
     1. 将第i个子集作为测试集，其它子集作为训练集；
     2. 使用训练集训练C4.5决策树；
     3. 使用测试集评估模型性能并记录。
  3. 计算k次测试的平均性能指标，作为C4.5模型在K-Fold交叉验证下的性能评估。

• 当然K-Fold是一种通用的评估方案可以用于其他模型，同时你也可以使用其他交叉验证算法来评估C4.5算法的性能指标。

  交叉验证并不会提高模型的性能，只是估计模型在实际运用时的性能。

其他

1. 对连续值的处理

   每次划分都是使用离散得数据点进行计算增益信息，而不能直接处理连续的数据，所以对于连续得数据要先进行离散化处理。

   一种常用的方法是二类划分，将连续值划分到两个区间，划分点取两个临近值的均值，则对于$m$个连续值共有$m-1$个划分点，对于每个划分点依次计算它们的信息增益，选取信息增益最大的点作为离散划分点。

2. 对缺失值的处理

   当某些属性的特征值未知时，C4.5不会将其简单的丢弃掉，而是用所有可能值分配来估计含有缺失值的信息增益率，提高C4.5在处理不完整数据集的性能和算法的健壮性。

3. 停止条件

   和ID3不一样的是，C4.5不是划分到只有一个类别时才停止，这样树的节点太多了，很容易导致过拟合问题，通常是设置阈值当节点中样本数小于阈值时，用节点样本中的$\max(p(i))$作为当前叶节点的类别。

其他

• 决策树并不一定使用固定的信息收益计算方案，本质上它是一个启发式方法来搜索最优解。