决策树的生成算法

虽然我们之前已经用了许多文字来描述决策树、但可能还是显得过于抽象。为了能有直观的认知，在此援引维基百科上一张很好的图来进行说明：

这张图基本蕴含了决策树中所有的关键结构，下面我们分开来分析它们

决策树的相关术语

首先是之前分析过的、“划分标准”这个概念。在上图中，被菱形橙色方框框起来的就是作为划分标准的特征，被长方形橙色方框框起来的就是对应特征的各个取值

然后是“节点”（Node）的概念。如果读者有学过数据结构，那么想必在提起“树”（Tree）的同时会自然而然地联想到 Node。考虑到可能有读者没有学过相关知识，这里就简要说一些相关的定义。决策树，顾名思义，确实是一个 Tree 模型。在上图中，我们可以直观地把整张图想象成一棵 Tree、把被黑色边框框起来的部分理解为一个 Node，这些 Node 是 Tree 的组成部分、Tree 本身可以协助 Node 之间的数据传输和参数调用。最上方的 Node 酷似整棵树的根，我们一般称其为“根节点”（Root）；用黑色方框（亦即四个角是直角而不是圆弧）框起来的 Node 是整棵树“生长的终点”、酷似树的叶子，我们一般称其为“叶节点”（Leaf）。比如，第三排的所有 Node 都是叶节点

通常来说，我们还会称一个非叶节点有一些“下属的叶节点”。比如，所有的叶节点都是根节点下属的叶节点，第三排左数第一、第二个叶节点是第二排左数第一个 Node 下属的叶节点

决策树中的叶节点还有一个有趣的特性：每个叶节点都对应着原样本空间的一个子空间，这些叶节点对应的子空间彼此不会相交、且并起来的话就会恰好构成完整的样本空间。换句话说、决策树的行为可以概括为如下两步：

• 将样本空间划分为若干个互不相交的子空间
• 给每个子空间贴一个类别标签

此外、我们在上图中还可以看到许多箭头，这些箭头代表着树的“生长方向”。我们一般习惯称箭头的起点是终点的“父节点”（parent）、终点是起点的“子节点”（child）；而当子节点只有两个时，通常把他们称作“左子节点”和“右子节点”。比如说，根节点是第二排所有 Node 的父节点，第二排所有 Node 都是根节点的子节点；第三排左数第一、第二个 Node 是第二排左数第一个 Node 的左、右子节点

对决策树有一个直观认知后，我们关心的就是怎样去生成这么一个结构了

决策树的生成算法

决策树的生成算法发展至今已经有许多变种，想要全面介绍它们不是短短一篇文章所能做到的。本文拟介绍其中三个上一节有所提及的、相对而言比较基本的算法：ID3、C4.5 和 CART。它们本身存在着某种递进关系：

• ID3 算法可说是“最朴素”的决策树算法，它给出了对离散型数据分类的解决方案
• C4.5 算法在其上进一步发展、给出了对混合型数据分类的解决方案
• CART 算法则更进一步、给出了对数据回归的解决方案

虽说它们的功能越来越强大，但正如前文所言、它们的核心思想都是一致的：算法通过不断划分数据集来生成决策树，其中每一步的划分能够使当前的信息增益达到最大

值得一提的是，该核心思想的背后其实也有着机器学习的一些普适性的思想。我们可以这样来看待决策树：模型的损失就是数据集的不确定性，模型的算法就是最小化该不确定性；同时，和许多其它模型一样，想要从整个参数空间中选出模型的最优参数是个 NP 完全问题，所以我们（和许多其它算法一样）采用启发式的方法、近似求解这个最优化问题。具体而言，我们每次会选取一个局部最优解（每次选取一个特征对数据集进行划分使得信息增益最大化）、并把这些局部解合成最终解（合成一个划分规则的序列）

可以这样直观地去想一个决策树的生成过程：

• 向根节点输入数据
• 根据信息增益的度量、选择数据的某个特征来把数据划分成（互不相交的）好几份并分别喂给一个新 Node
• 如果分完数据后发现：
  • 某份数据的不确定较小、亦即其中某一类别的样本已经占了大多数，此时就不再对这份数据继续进行划分、将对应的 Node 转化为叶节点
  • 某份数据的不确定性仍然较大，那么这份数据就要继续分割下去（转第 2 步）

注意：虽然划分的规则是根据数据定出的，但是划分本身其实是针对整个输入空间进行划分的

从上述过程可知，决策树的生成过程就是根据某个度量从数据集中训练出一系列的划分规则、使得这些规则能够在数据集有好的表现。事实上，上文说的3种不同算法在分类问题上的区别亦仅表现在度量信息增益和划分数据的方法的不同上

ID3（Interactive Dichotomizer-3）

ID3 可以译为“交互式二分法”，虽说这个名字里面带了个“二分”，但该方法完全适用于“多分”的情况。它选择互信息作为信息增益的度量、针对离散型数据进行划分。其算法叙述如下：

1. 输入：训练数据集$D = \{\left( x_{1},y_{1} \right),\ldots,(x_{N},y_{N})\}$
2. 过程：
   1. 将数据集$D$喂给一个 Node
   2. 若$D$中的所有样本同属于类别$c_{k}$，则该 Node 不再继续生成、并将其类别标记为$c_{k}$类
   3. 若$x_{i}$已经是 0 维向量、亦即已没有可选特征，则将此时$D$中样本个数最多的类别$c_{k}$作为该 Node 的类别
   4. 否则，按照互信息定义的信息增益： $$g\left( y,x^{\left( j \right)} \right) = H\left( y \right) - H(y|x^{\left( j \right)})$$ 来计算第 j 维特征的信息增益，然后选择使得信息增益最大的特征$x^{\left( j^{*} \right)}$作为划分标准，亦即： $$j^{*} = \arg{\max_{j}{g\left( y,x^{\left( j \right)} \right)}}$$
   5. 若$x^{\left( j^{*} \right)}$满足停止条件、则不再继续生成并则将此时$D$中样本个数最多的类别$c_{k}$作为类别标记
   6. 否则，依$x^{\left( j^{*} \right)}$的所有可能取值$\{ a_{1},\ldots,a_{m}\}$将数据集$D$划分为${\{ D}_{1},\ldots,D_{m}\}$、使得： $${(x}_{i},y_{i}) \in D_{j} \Leftrightarrow x_{i}^{\left( j^{*} \right)} = a_{j},\forall i = 1,\ldots,N$$ 同时，将$x_{1},\ldots,x_{N}$的第$j^{*}$维去掉、使它们成为$n - 1$维的特征向量
   7. 对每个$D_{j}$从 2.1 开始调用算法
3. 输出：原始数据对应的 Node（亦即根节点）

其中算法第 2.5 步的“停止条件”（也可称为“预剪枝”；有关剪枝的讨论会放在决策树的剪枝算法）有许多种提法，常用的是如下两种：

• 若选择$x^{\left( j^{*} \right)}$作为特征时信息增益$g(y,x^{\left( j^{*} \right)})$仍然很小（通常会传入一个参数$\epsilon$作为阈值）、则停止
• 事先把数据集分为训练集与测试集（交叉验证的思想），若由训练集得到的$x^{\left( j^{*} \right)}$并不能使得决策树在测试集上的错误率更小、则停止

这两种停止条件的提法通用于 C4.5 和 CART，后文将不再赘述。同时，正如本章一开始有所提及的、决策树会在许多地方应用到递归的思想，上述算法中的第 2.6 步正是经典的递归

我们可以对气球数据集 1.0 过一遍 ID3 算法以加深理解。由算法可知，因为每个 Node 的信息熵是确定的、所以选择互信息最大的特征等价于选择条件熵最小的特征，是故我们只需要在每个 Node 上计算各个可选特征的条件熵。易知在根节点上：

$$\begin{align} H\left( 不爆炸\middle| 颜色\right) &= - p_{11}\log p_{11} - p_{12}\log p_{12} = 1 \\ H\left( 不爆炸\middle| 大小\right) &= - p_{21}\log p_{21} - p_{22}\log p_{22} \approx 0.65 \\ H\left( 不爆炸\middle| 人员\right) &= - p_{31}\log p_{31} - p_{32}\log p_{32} \approx 0.92 \\ H\left( 不爆炸\middle| 动作\right) &= - p_{41}\log p_{41} - p_{42}\log p_{42} \approx 0.65 \end{align}$$

其中

$$p_{11} \triangleq p\left( 不爆炸\middle| 黄色\right) = \frac{1}{2},\ \ p_{12} \triangleq p\left( 不爆炸\middle| 紫色\right) = \frac{1}{2}$$ $$p_{21} \triangleq p\left( 不爆炸\middle| 小\right) = \frac{5}{6},\ \ p_{22} \triangleq p\left( 不爆炸\middle| 大\right) = \frac{1}{6}$$ $$p_{31} \triangleq p\left( 不爆炸\middle| 成人\right) = \frac{1}{3},\ \ p_{32} \triangleq p\left( 不爆炸\middle| 小孩\right) = \frac{2}{3}$$ $$p_{41} \triangleq p\left( 不爆炸\middle| 手打\right) = \frac{5}{6},\ \ p_{42} \triangleq p\left( 不爆炸\middle| 脚踩\right) = \frac{1}{6}$$

且易知

$$H\left( 不爆炸\middle| A \right) = H\left( 爆炸\middle| A \right),\ \ \forall A \in \{ 颜色, 大小, 人员, 动作\}$$

从而可知应选测试动作或者气球大小作为根节点的划分标准。不妨选择气球大小作为划分标准，此时的决策树如下图所示（图片是使用 ProcessOn 在线绘制而成的）：

图中 Node A 和 Node B 所对应的数据集分别如下面两张表所示：

颜色	测试人员	测试动作	结果
黄色	成人	用手打	不爆炸
黄色	成人	用脚踩	爆炸
黄色	小孩	用手打	不爆炸
黄色	小孩	用脚踩	不爆炸
紫色	成人	用手打	不爆炸
紫色	小孩	用手打	不爆炸

颜色	测试人员	测试动作	结果
黄色	成人	用手打	爆炸
黄色	成人	用脚踩	爆炸
黄色	小孩	用手打	不爆炸
黄色	小孩	用脚踩	爆炸
紫色	成人	用脚踩	爆炸
紫色	小孩	用脚踩	爆炸

注意此时气球大小已经不是可选特征了。我们接下来要分别对 Node A 和 Node B 调用 ID3 算法，计算过程和根节点上的计算过程大同小异。以此类推、最终我们可以得到如下图所示的决策树：

可知该决策树在气球数据集 1.0 上的正确率为 100%、且它做的决策都很符合直观

C4.5

C4.5 使用信息增益比作为信息增益的度量，从而缓解了 ID3 算法会倾向于选择 m 比较大的特征$A$作为划分依据这个问题；也正因如此，C4.5 算法可以处理 ID3 算法比较难处理的混合型数据。我们先来看看它在离散型数据上的算法（仅展示和 ID3 算法中不同的部分）：

算法 2.4 步

否则，按照信息增益比定义的信息增益：

$$g_{R}\left( y,x^{\left( j \right)} \right) = \frac{g(y,x^{\left( j \right)})}{H_{x^{\left( j \right)}}(y)}$$

来计算第 j 维特征的信息增益，然后选择使得信息增益最大的特征$x^{\left( j^{*} \right)}$作为划分标准，亦即：

$$j^{*} = \arg{\max_{j}{g_{R}\left( y,x^{\left( j \right)} \right)}}$$

注意：C4.5 算法虽然不会倾向于选择 m 比较大的特征、但有可能会倾向于选择 m 比较小的特征。针对这个问题，Quinlan 在 1993 年提出了这么一个启发式的方法：先选出互信息比平均互信息要高的特征、然后从这些特征中选出信息增益比最高的

混合型数据的处理方法大同小异，本书拟介绍一种常用且符合直观的、同时亦是 C4.5 所采用的方法：使用二类问题的解决方案处理连续型特征。具体而言，当二类问题和决策树结合起来时，在连续的情况下、我们通常可以把它转述为：

$$Y_{1} = \left\{ y:y^{A} < a_{1} \right\},Y_{2} = \{ y:y^{A} \geq a_{1}\}$$

相对应的，我们同样可以用处理二类问题的思想来处理离散型特征，此时：

$$A \in \left\{ a_{1},a_{2} \right\};\ \ Y_{1} = \left\{ y:y^{A} = a_{1} \right\},\ Y_{2} = \{ y:y^{A} = a_{2}\}$$

更进一步、我们通常会将它表示为：

$$Y_{1} = \left\{ y:y^{A} = a_{1} \right\},Y_{2} = \{ y:y^{A} \neq a_{1}\}$$

我们通常称以上各式中的$a_{1}$为“二分标准”。一般而言，如何处理连续型特征这个问题会归结于如何选择“二分标准”这个问题。一个比较容易想到的做法是：

• 若在当前数据集中有 m 个取值，不妨假设它们为$u_1,...,u_m$；不失一般性、再不妨假设它们满足$u_1<...<u_m$（若不然，进行一次排序操作即可），那么依次选择$v_1,...,v_p$作为二分标准并决出最好的一个，其中$v_1,...,v_p$构成等差数列、且: $$v_{1} = u_{1},v_{p} = u_{m}$$ p 的选取则视情况而定，一般而言会取 p 反比于“深度”。这意味着当数据越分越细时、对特征的划分会越分越粗，从直观上来说这有益于防止过拟合

但这样可能会产生许多“冗余”的二分标准。试想如果这些取值满足：

$$u_{1} = 0,u_{2} = 100,u_{3} = 101,u_{4} = 102,\ldots$$

那么我们就会在$u_{1}$和$u_{2}$之间尝试大量的划分标准、但显然这些划分标准算出来的结果都是一样的。为了处理类似于这种不合理的情况，C4.5 采用如下做法：

• 依次选择$v_{1} = \frac{u_{1} + u_{2}}{2},\ldots,v_{m - 1} = \frac{u_{m - 1} + u_{m}}{2}$作为二分标准、计算它们的信息增益比、从而决出最好的二分标准来划分数据

在这之上还有另一种可行的做法：

• 设$u_1,...,u_m$所对应的类别是$y_1,...,y_m$，那么在$v_1,...,v_{m-1}$中只选取使得： $$y_{i} \neq y_{i + 1},\ \ (i = 1,\ldots,m - 1)$$ 的$v_i$作为二分标准、计算它们的信息增益比、从而决出最好的二分标准来划分数据

这种做法在某些情况下会表现得更好、但在某些情况下也会显得不合理。鉴于此，本书会采用更稳定的上一种做法来进行实现

注意：从以上讨论可知，我们完全可以把 ID3 算法推广成可以处理连续型特征的算法。只不过如果数据集是混合型数据集的话、ID3 就会倾向于选择离散型特征作为划分标准而已。如果数据集的所有特征都是连续型特征、那么 ID3 和 C4.5 之间孰优孰劣是难有定论的

这里需要特别指出的是、C4.5 也是有一个比较糟糕的性质的：由信息增益比的定义可知，如果是二分的话、它会倾向于把数据集分成很不均匀的两份；因为此时$H_{A}(y)$将非常小、导致$g_{R}(y,A)$很大（即使$g(y,A)$比较小）。举个例子：如果当前划分标准为连续特征、那么 C4.5 可能会倾向于直接选择$v_{1},v_{2},v_{3}$等作为二分标准

之所以说该性质比较糟糕、是因为它将直接导致如下结果：当 C4.5 进行二叉分枝时、它可能总会直接分出一个比较小的 Node 作为叶节点、然后剩下一个大的 Node 继续进行生成。这种行为会导致决策树倾向于往深处发展、从而导致很容易产生过拟合现象，这并不是我们期望的结果

CART

CART 的全称是 Classification and Regression Tree（“分类与回归树”）。顾名思义，它既可做分类亦可做回归。囿于篇幅，本书会介绍分类问题的算法和实现、对于回归问题则只叙述算法，感兴趣的观众老爷们可以尝试触类旁通地实现它

CART 算法一般会使用基尼增益作为信息增益的度量（当然也可以使用互信息和信息增益比作为度量，需要视具体场合而定），其一大特色就是它假设了最终生成的决策树为二叉树、亦即它在处理离散型特征时也会通过决出二分标准来划分数据：

算法 2.4 步

否则，不妨设$x^{\left( j \right)}$在当前数据集中有$S_{j}$个取值$u_{1}^{\left( j \right)},\ldots,u_{S_{j}}^{\left( j \right)}$且它们满足$u_{1}^{\left( j \right)} < \ldots < u_{S_{j}}^{\left( j \right)}$，则：

• 若$x^{\left( j \right)}$是离散型的，则依次选取$u_{1}^{\left( j \right)},\ldots,u_{S_{j}}^{\left( j \right)}$作为二分标准$a_{p}$，此时： $$A_{jp} = \{ x^{\left( j \right)} = a_{p},x^{\left( j \right)} \neq a_{p}\}$$
• 若$x^{\left( j \right)}$是连续型的，则依次选取$\frac{u_{1}^{\left( j \right)} + u_{2}^{\left( j \right)}}{2},\ldots,\frac{u_{S_{j} - 1}^{\left( j \right)} + u_{S_{j}}^{\left( j \right)}}{2}$作为二分标准$a_{p}$，此时： $$A_{jp} = \{ x^{\left( j \right)} < a_{p},x^{\left( j \right)} \geq a_{p}\}$$ 按照基尼系数定义的信息增益： $$g_{\text{Gini}}\left( y,A_{jp} \right) = \text{Gini}\left( y \right) - \text{Gini}(y|A_{jp})$$ 来计算第 j 维特征在这些二分标准下的信息增益，然后选择使得信息增益最大的特征$x^{\left( j^{*} \right)}$和相应的二分标准$u_{p^{*}}^{\left( j^{*} \right)}$作为划分标准，亦即： $${(j}^{*},p^{*}) = \arg{\max_{j,p}{g_{\text{Gini}}\left( y,A_{jp} \right)}}$$

从分类问题到回归问题不是一个不平凡的问题，它们的区别仅在于：回归问题除了特征是连续型的以外、“类别”也是连续型的，此时我们一般把“类别向量”改称为“输出向量”。正如前文所提及，决策树可以转化为最小化损失的问题。我们之前讨论的分类问题中的损失都是数据的不确定性，而在回归问题中、一种常见的做法就是将损失定义为平方损失：

$$L(D) = \sum_{i = 1}^{N}{I\left( y_{i} \neq f\left( x_{i} \right) \right)\left\lbrack y_{i} - f\left( x_{i} \right) \right\rbrack^{2}}$$

这里的$I$是示性函数，$f$是我们的模型、$f(x_{i})$是$x_{i}$在我们模型下的预测输出、$y_{i}$是真实输出。平方损失其实就是我们熟悉的“（欧式）距离”（预测向量和输出向量之间的距离），我们会在许多分类、回归问题中见到它的身影。在损失为平方损失时，一般称此时生成的回归决策树为最小二乘回归树

在分类问题中决策树是一个划分规则的序列、在回归问题中也差不多。具体而言，假设该序列一共会将输入空间划分为$R_{1},\ldots,R_{M}$（这 M 个子空间彼此不相交）、那么：

• 对于分类问题，模型可表示为： $$f\left( x_{i} \right) = \sum_{m = 1}^{M}{y_{m}I(x_{i} \in R_{m})}$$
• 对于回归问题，模型可表示为： $$f\left( x_{i} \right) = \sum_{m = 1}^{M}{c_{m}I\left( x_{i} \in R_{m} \right)}$$ 这里$c_{m} = \arg{\min_{c}{L_{m}\left( c \right)}} \triangleq \arg{\min_{c}{\sum_{\left( x_{i},y_{i} \right) \in R_{m}}^{}\left( y_{i} - c \right)^{2}}}$。那么由一阶条件： $$\frac{\partial L_{m}\left( c \right)}{\partial c} = 0 \Leftrightarrow - 2\sum_{\left( x_{i},y_{i} \right) \in R_{m}}^{}\left( y_{i} - c_{m} \right) = 0$$ 可解得$c_{m} = \text{avg}\left( y_{i}|(x_{i},y_{i}) \in R_{m} \right) \triangleq \frac{1}{\left| R_{m} \right|}\sum_{\left( x_{i},y_{i} \right) \in R_{m}}^{}y_{i}$

最小二乘回归树的算法和 CART 做分类时的算法几乎完全一样，区别只在于：

• 解决分类问题时，我们会在特征和二分标准选好后，通过求解： $${(j}^{*},p^{*}) = \arg{\max_{j,p}{g_{\text{Gini}}\left( y,A_{jp} \right)}}$$ 来选取划分标准
• 解决回归问题时，我们会在特征和二分标准选好后，通过求解： $$\left( j^{*},p^{*} \right) = \arg{\min_{j,p}{\lbrack\sum_{x_{i} < p}^{}{\left( y_{i} - c_{jp}^{\left( 1 \right)} \right)^{2} + \sum_{x_{i} \geq p}^{}\left( y_{i} - c_{jp}^{\left( 2 \right)} \right)^{2}}\rbrack}}$$ 来选取划分标准，其中$c_{jp}^{\left( 1 \right)} = \text{avg}(y_{i}|x_{i} < p)$、$c_{jp}^{\left( 2 \right)} = \text{avg}(y_{i}|x_{i} \geq p)$，p（切分点）的选取则视情况而定（可以模仿分类问题中二分标准的选取方法）