决策树

基本概念

  决策树是一种基本的分类与回归方法，决策树由节点和有向边组成，节点有 $3$ 种类型：根节点、内部节点和叶子节点。根节点和内部节点表示一个特征或属性，叶子节点表示一个类别。

决策树学习通常包括 $3$ 个步骤：

1. 特征选择。
2. 决策树生成。
3. 决策树剪枝。

原理

  决策树本质上是从训练数据集中归纳出一组分类规则，且该规则具有很好的泛化能力， 为了得到这样一棵决策树，决策树学习算法通常递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

决策树生成

1. 构建根结点：将所有训练数据放在根结点。
2. 选择一个最优特征，根据这个特征将训练数据分割成子集，使各个子集 在当前条件下有一个最好的分类。
   1. 若这些子集已能够被基本正确分类，则将该子集构成叶结点。
   2. 若某个子集不能够被基本正确分类，则对该子集选择新的最优的特征，继续对该子集进行分割，构建相应的结点。
3. 如此递归下去，直至所有训练数据子集都被基本正确分类，或者没有合适的特征为止。

递归结束条件

1. 当前结点包含的样本全部属于同一类别，无需划分；
2. 当前结点包含的样本集合为空，不能划分，把当前结点标记为叶子节点，其类别设定为其父节点所含样本最多的类别；
3. 当前属性集为空，或所有样本在所有属性上取值相同，无法划分，把当前节点标记为叶子节点，并将其类别设定为该节点所含样本最多的类别。

决策树剪枝

  使用上述方法生成的决策树可能对训练数据有很好的分类能力，但对未知的数据却未必有很好的分类能力，即可能发生过拟合现象。此时需要对生成的决策树进行剪枝操作，常用的剪枝方法有：

1. 预剪枝

   在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶子结点。

2. 后剪枝

   自底向上计算剪去每个内部节结点后决策树的泛化性能是否有所提升，若有提升则剪去该内部结点，将其标记为叶子结点。

小结

1. 决策树的生成对应着模型的局部最优，决策树的剪枝则考虑全局最优。
2. 如果学习任意大小的决策树，则可以将决策树算法视作非参数算法。但是实践中经常有大小限制（如限制树的高度、限制树的叶结点数量），从而使得决策树成为有参数模型。

特征选择

  特征选择的关键是：选取对训练数据有较强分类能力的特征。若一个特征的分类结果与随机分类的结果没有什么差别，则称这个特征是没有分类能力的。

熵

  熵（$entropy$）$H\left( X \right) $ 表示对随机变量$X$不确定性的度量，熵越大，随机变量的不确定性就越大。

  设 $X$ 是取有限个值的离散随机变量，其概率分布为：

其中，$i=1,2,\cdots ,n$，则随机变量 $X$ 的熵定义为：

条件熵

  条件熵（$condition \ entropy$）$H\left( Y | X \right) $ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。

  随机变量 $X$ 给定的条件下，随机变量 $Y$ 的条件熵 $H\left( Y | X \right) $，定义为 $X$ 给定条件下，$Y$ 的条件概率分布的熵对 $X$ 的数学期望：

这里，${ p } _ { i }=P\left( X={ x } _ { i } \right) ,i=1,2,\cdots ,n$。

小结

  当熵和条件熵由数据估计（如，极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。

信息增益

  定义数据集 $\mathbb D$ 的经验熵为：

其中：样本的类别分别为 ${ c } _ { 1 },{ c } _ { 2 },\cdots ,{ c } _ { K }$；类别 ${ c } _ { k }$ 的样本的数量为 ${ N } _ { k }$，所有样本的总数为 $N$。

  定义数据集 $\mathbb D$ 关于特征 $A$ 的经验条件熵为：

其中，特征 $A$ 的取值范围为 ${ { a } _ { 1 },{ a } _ { 2 },\cdots ,{ a } _ { { n } _ { A } } } $；属性 $A={ a } _ { i }$ 的样本的数量为 ${ N } _ { { a } _ { i } }$；属性 $A={ a } _ { i }$ 且类别为 ${ c } _ { k }$ 的样本的数量为 ${ N } _ { { a } _ { i },k }$，所有样本的总数为 $ N$。

  特征 $A$ 对训练数据集 $\mathbb D$ 的信息增益 $g\left( D | A \right) $ 定义为：集合 $\mathbb D$ 的经验熵 $H\left( D \right) $ 与关于特征$A$经验条件熵 $H\left( D | A \right) $ 之差。即：

  决策树学习可以应用信息增益来选择特征。给定训练集 $\mathbb D$ 和特征 $A$：

1. 经验熵 $H\left( D \right) $ 刻画了对数据集 $\mathbb D$ 进行分类的不确定性。
2. 经验条件熵 $H\left( D | A \right) $ 刻画了在特征 $A$ 给定条件下，对数据集 $\mathbb D$ 分类的不确定性。
3. 信息增益 $H\left( D \right) -H\left( D | A \right) $ 刻画了在特征$A$给定的条件下，数据集 $\mathbb D$ 分类的不确定性减少的程度。

  不同的特征往往具有不同的信息增益。

1. 信息增益大的特征具有更强的分类能力 。
2. 如果一个特征的信息增益为 $0$，则表示该特征没有什么分类能力。

信息增益比

  以信息增益作为特征选择的度量标准，对取值数目较多的特征有所偏好。在经验条件商：

中，当极限情况下，特征 $A$ 在每个样本上的取值都不同，即 ${ n } _ { A }=N$。此时特征 $A$ 将每一个样本都划分到不同的子结点。即：${ N } _ { { a } _ { i } }=1,i=1,2,\cdots ,{ n } _ { A }$。由于 $\sum _ { k=1 }^{ K }{ { N } _ { { a } _ { i },k } } ={ N } _ { { a } _ { i } }=1$，因此有：${ N } _ { { a } _ { i },k }\le 1,i=1,2,\cdots ,{ n } _ { A };k=1,2,\cdots ,K$。即：${ N } _ { { a } _ { i },k }$ 取值为 $0$ 或者 $1$。因此有：$\frac { { N } _ { { a } _ { i },k } }{ { N } _ { { a } _ { i } } } \log { \frac { { N } _ { { a } _ { i },k } }{ { N } _ { { a } _ { i } } } } =0$。最终使得 $H\left( D | A \right) =0$。

  条件熵的最小值为 $0$，这意味着该情况下的信息增益达到了最大值。然而很显然这个特征 $A$ 显然不是最佳选择，因为它并不具有任何分类能力。

  可以通过定义信息增益比来解决该问题。特征 $A$ 对训练集 $\mathbb D$ 的信息增益比 ${ g } _ { R }\left( D | A \right) $ 定义为：信息增益 $g\left( D | A \right) $ 与关于 特征 $A$ 的熵 ${ H } _ { A }\left( D \right) $ 之比：

其中，${ H } _ { A }\left( D \right) $ 的表达式为：

表征了特征 $A$ 对训练集 $\mathbb D$ 的拆分能力。因为 ${ H } _ { A }\left( D \right) $ 只考虑样本在特征 $A$ 上的取值，而不考虑样本的标记 $y$，所以这种拆分并不是对样本的分类。

  信息增益比本质上是对信息增益乘以一个加权系数：

1. 当特征 $A$ 的取值集合较大时，加权系数较小，表示抑制该特征。
2. 当特征 $A$ 的取值集合较小时，加权系数较大，表示鼓励该特征。

生成算法

决策树有两种常用的生成算法：

1. $ID3$ 生成算法
2. $C4.5$ 生成算法

$ID3$ 生成算法和 $C4.5$ 生成算法只有树的生成算法，生成的树容易产生过拟合：对训练集拟合得很好，但是预测测试集效果较差。

ID3 生成算法

$ID3$ 生成算法核心是在决策树的每个结点上应用信息增益准则选择特征，递归地构建决策树。

1. 从根结点开始，计算结点所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征划分出子结点。
2. 再对子结点递归地调用以上方法，构建决策树。
3. 直到所有特征的信息增益均很小或者没有特征可以选择为止，最后得到一个决策树 。

如果不设置特征信息增益的下限，则可能会使得每个叶子都只有一个样本点，从而划分得太细。

伪码

输入：

1. 训练数据集 $\mathbb D$
2. 特征集合 $\mathbb A={ { A } _ { 1 },{ A } _ { 2 },\cdots ,{ A } _ { n } } $
3. 特征信息增益阈值 $\varepsilon >0$

输出：决策树 $T$

算法步骤：

1. 若 $\mathbb D$ 中所有样本均属于同一类 ${ c } _ { k }$ ，则 $T$ 为单结点树，并将 ${ c } _ { k }$ 作为该结点的类标记，算法终止。
2. 若 $\mathbb A=\phi$，则 $T$ 为单结点树，将 $\mathbb D$ 中样本数最大的类 ${ c } _ { k }$ 作为该结点的类标记，算法终止。
3. 否则计算 $g\left( D,{ A } _ { j } \right) ,j=1,2,\cdots ,n$，选择信息增益最大的特征 ${ A } _ { g }$：
   1. 若 $g\left( D,{ A } _ { g } \right) <\varepsilon $，则置 $T$ 为单结点树，将 $\mathbb D$ 中样本数最大的类 ${ c } _ { k }$ 作为该结点的类标记，返回。
   2. 若 $g\left( D,{ A } _ { g } \right) \ge \varepsilon $，则对 ${ A } _ { g }$特征的每个可能取值${ a } _ { i },i=1,2,\cdots ,{ n } _ { g }$，根据 ${ A } _ { g }={ a } _ { i }$ 将 $\mathbb D$ 划分为若干个非空子集 $\mathbb D _ i$。
4. 对第 $i$ 个子结点，以 $\mathbb D _ i$ 为训练集，以 $\mathbb A-{A _ g}$ 为特征集，递归地调用前面的步骤来构建子树。

优点

1. 决策树易于理解和解释
2. 能够处理不相关的特征（可以同时处理标称型和数值型数据）
3. 对特征值缺失不敏感

缺点

1. 容易出现过拟合
2. 容易忽略数据集中属性的相互关联
3. 信息增益准则对可取数目较多的属性有所偏好

C4.5 生成算法

  $C4.5$ 生成算法与 $ID3$ 算法相似，但是 $C4.5$ 算法在生成过程中用信息增益比来选择特征。

剪枝算法

1. 决策树生成算法生成的树往往对于训练数据拟合很准确，但是对于未知的测试数据分类却没有那么准确。即出现过拟合现象。过拟合产生得原因是决策树太复杂。

   解决的办法是：对决策树剪枝，即对生成的决策树进行简化。

2. 决策树的剪枝是从已生成的树上裁掉一些子树或者叶结点，并将根结点或者其父结点作为新的叶结点。
3. 剪枝的依据是：极小化决策树的整体损失函数或者代价函数。
4. 决策树生成是学习局部的模型，决策树剪枝是学习整体的模型。即：生成算法仅考虑局部最优，而剪枝算法考虑全局最优。

原理

  设树 $T$ 的叶结点个数为 $| { T } _ { f } | $。设 ${ T } _ { t },t=1,2,\cdots ,| { T } _ { f } | $ 为树的叶结点，该叶结点有 ${ N } _ { t }$ 个样本点，其中属于 ${ c } _ { k }$ 类的样本点有 ${ N } _ { t,k }$ 个，$k=1,2,\cdots ,K$。令 $H\left( t \right) $ 为叶结点 ${ T } _ { t }$ 上的经验熵，令 $\alpha >0$ 为参数，则决策树 $T$ 的损失函数定义为：

其中，$H\left( t \right) =-\sum _ { k=1 }^{ K }{ \frac { { N } _ { t,k } }{ { N } _ { t } } \log { \frac { { N } _ { t,k } }{ { N } _ { t } } } } $。叶结点个数越多，表示决策树越复杂，则损失函数越大；叶结点经验熵越大，表示叶结点的样本类别分布很分散，则损失函数越大；叶结点经验熵还需要加权，权重为叶结点大小，即越大的叶结点，其分类错误的影响越大。

  令 \(C\left( T \right) =\sum_{t=1}^{\| T_f \|}{N_tH\left( t \right)}=-\sum_{t=1}^{\| T_f \|}{\sum_{k=1}^K{N_{t,k}\log \frac{N_{t,k}}{N_t}}}\)

则：

其中，$\alpha | { T } _ { f } | $ 为正则化项，$C\left( T \right) $ 表示预测误差。

  $C\left( T \right) =0$ 意味着 ${ N } _ { t,k }={ N } _ { t }$，即每个结点 ${ T } _ { t }$ 内的样本都是纯的，即单一的分类。决策树划分得越细致，则 $T$ 的叶子结点越多。当叶结点的数量等于样本集的数量时，树 $T$ 的每个叶子结点只有一个样本点。此时每个叶结点内的样本都是纯的，从而 $C\left( T \right) =0$。这样的决策树其实是没有什么实用价值的，所以必须使用正则化项来约束决策树的复杂程度。

  参数 $\alpha $ 控制预测误差与模型复杂度之间的关系:

1. 较大的 $\alpha $ 会选择较简单的模型 。
2. 较小的 $\alpha $ 会选择较复杂的模型。
3. $\alpha=0 $ 只考虑对训练集的拟合，不考虑模型复杂度。

  决策树剪枝的准则是：考虑当 $\alpha $ 确定时，${ C } _ { \alpha }\left( T \right) $ 最小化。这等价于正则化的极大似然估计。

伪码

输入：

1. 生成算法产生的决策树 $T$
2. 参数 $\alpha$

输出： 修剪后的决策树 ${ T } _ { \alpha }$

算法步骤：

1. 对树 $T$ 每个结点 ${ T } _ { t },t=1,2,\cdots ,| { T } _ { f } | $，计算其经验熵 $H\left( t \right) $。

2. 递归地从树的叶结点向上回退：

   设一组叶结点回退到父结点之前与之后的整棵树分别为 $T$ 与 ${ T }^{ \prime }$，对应的损失函数值分别为 ${ C } _ { \alpha }\left( T \right) $ 与 ${ C } _ { \alpha }\left( { T }^{ \prime } \right) $。若 ${ C } _ { \alpha }\left( { T }^{ \prime } \right) \le { C } _ { \alpha }\left( T \right) $，则进行剪枝，将父结点变成新的叶结点。

3. 递归回退直到不能继续为止，得到损失函数最小的子树 ${ T } _ { \alpha }$。

CART 树

  $CART$ ($classfification \ and \ regression \ tree$)：学习在给定输入随机变量 $x$ 条件下，输出随机变量 $y$ 的条件概率分布的模型。$CART$ 同样由特征选取、树的生成、剪枝组成，既可用于分类，也可用于回归。

  $CART$ 假设决策树是二叉树，内部结点特征的取值为是与否。其中：左侧分支取是，右侧分支取否。它递归地二分每个特征，将输入空间划分为有限个单元。

  $CART$ 树与 $ID3$ 决策树和 $C4.5$ 决策树的重要区别：

1. $CART$ 是二叉树，而后两者是 $N$ 叉树。由于是二叉树，因此 $CART$ 树的拆分不依赖于特征的取值数量。因此 $CART$ 树也就不像 $ID3$ 那样倾向于取值数量较多的特征。
2. $CART$ 树的特征可以是离散的，也可以是连续的。而后两者的特征是离散的。如果是连续的特征，则需要执行分桶来进行离散化。

  $CART$ 算法分两步：

1. 决策树生成：用训练数据生成尽可能大的决策树。
2. 决策树剪枝：用验证数据基于损失函数最小化的标准对生成的决策树剪枝。

CART 生成算法

$CART$ 生成算法有两个生成准则：

1. $CART$ 回归树：平方误差最小化准则。
2. $CART$ 分类树：基尼指数最小化准则。

CART 回归树

划分单元和划分点

  一棵 $CART$ 回归树对应着输入空间的一个划分，以及在划分单元上的输出值。设输出 $y$ 为连续变量，训练数据集 $\mathbb D={ \left( { x } _ { 1 },{ y } _ { 1 } \right) ,\left( { x } _ { 2 },{ y } _ { 2 } \right) ,\cdots ,\left( { x } _ { N },{ y } _ { N } \right) } $。假设已经将输入空间划分为 $M$ 个单元 ${ R } _ { 1 },{ R } _ { 2 },\cdots ,{ R } _ { m }$，且在每个单元 ${ R } _ { m }$ 上有一个固定的输出值 ${ c } _ { m }$。则 $CART$ 回归树模型可以表示为：

其中，$I\left( \cdot \right) $ 为示性函数。

  如果已知输入空间的单元划分，基于平方误差最小的准则，则 $CART$ 回归树在训练数据集上的损失函数为：

根据损失函数最小，则可以求解出每个单元上的最优输出值 ${ \hat { c } } _ { m }$ 为：${ R } _ { m }$ 上所有输入样本 ${ x } _ { i }$ 对应的输出 ${ y } _ { i }$ 的平均值。 即：

其中，${ N } _ { m }$ 表示单元 ${ R } _ { m }$ 中的样本数量。

  问题是输入空间的单元划分是未知的。如何对输入空间进行划分？设输入为 $n$ 维：

选择第 $j$ 维 $x _ j$ 和它的取值 $s$ 作为切分变量和切分点。定义两个区域：

然后寻求最优切分变量 $j$ 和最优切分点 $s$。即求解：

其意义为：首先假设已知切分变量 $j$，则遍历最优切分点 $s$，得到：

其中 $N _ 1$ 和 $N _ 2$ 分别代表区域 $R _ 1$ 和 $R _ 2$ 中的样本数量。

  然后遍历所有的特征维度，对每个维度找到最优切分点。从这些 (切分维度,最优切分点) 中找到使损失函数最小的那个。

  依次将输入空间划分为两个区域，然后重复对子区域划分，直到满足停止条件为止。这样的回归树称为最小二乘回归树。

伪码

1. 输入：
   1. 训练数据集 $\mathbb D$
   2. 停止条件
2. 输出：$CART$ 回归树 $f\left( x \right) $
3. 步骤：
   1. 选择最优切分维度 $j$ 和切分点 $s$。即求解： \(\left( { j }^{ \ast },{ s }^{ \ast } \right) =\min _ { j,s }{ \left[ \min _ { { c }_ { 1 } }{ \sum _ { { x }_ { i }\in { R }_ { 1 }\left( j,s \right) }{ { \left( { \tilde { y } }_ { i }-{ c }_ { 1 } \right) }^{ 2 } } } +\min _ { { c }_ { 2 } }{ \sum _ { { x }_ { i }\in { R }_ { 2 }\left( j,s \right) }{ { \left( { \tilde { y } }_ { i }-{ c }_ { 2 } \right) }^{ 2 } } } \right] }\)
   2. 用选定的$ (j,s) $划分区域并决定响应的输出值： \(\begin{matrix} { R }_ { 1 }\left( j,s \right) =\{ x \| { x }_ { j }\le s \} \\ { R }_ { 2 }\left( j,s \right) =\{ x \| { x }_ { j }>s \} \end{matrix}\) \(\begin{matrix} { \hat { c } }_ { 1 }=\frac { 1 }{ { N }_ { 1 } } \sum _ { { x }_ { i }\in { R }_ { 1 }\left( j,s \right) }{ { \tilde { y } }_ { i } } \\ { \hat { c } }_ { 2 }=\frac { 1 }{ { N }_ { 2 } } \sum _ { { x }_ { i }\in { R }_ { 2 }\left( j,s \right) }{ { \tilde { y } }_ { i } } \\ \end{matrix}\) 其中，$N_1$ 和 $N_2$ 分别代表区域 $R_1$ 和 $R_2$ 中的样本数量。
   3. 对子区域 $R_1$ 和 $R_2$ 递归地切分，直到满足停止条件。
   4. 最终将输入空间划分为 $M$ 个区域 ${ R }_ { 1 },{ R } _ { 2 },\cdots ,{ R } _ { m }$，生成决策树：$f\left( x \right) =\sum _ { m=1 }^{ M }{ { c } _ { m }I\left( x\in { R } _ { m } \right) } $。

优点

1. 可对复杂的和非线性的数据建模
2. 可处理连续型变量

缺点

1. 计算量大

CART 分类树

基尼指数

  $CART$ 分类树采用基尼指数选择最优特征。假设有 $K$ 个分类，样本属于第 $k$ 类的概率为 ${ p } _ { k }=p\left( y={ c } _ { k } \right) $。则概率分布的基尼指数为：

  基尼指数表示：从样本集合中，随机选中一个样本，该样本被分错的概率。基尼指数越小，表示越不容易分错。

  对于给定的样本集合 $\mathbb D$，设属于类 ${ c } _ { k } $ 的样本子集为 $\mathbb D _ k$，则样本集的基尼指数为：

其中，$N$ 为样本总数，$N_k$ 为子集 $\mathbb D_ k$ 的样本数量。

  对于最简单的二项分布，设 $p(X=1)=p,P(X=0)=1-p$，则其基尼系数与熵的图形见下图。

Entropy and Gini

可以看到基尼系数与熵一样，也是不确定性的度量。对于样本集 $\mathbb D$， $Gini(D)$ 越小，说明集合中的样本越纯净。

  若样本集 $\mathbb D$ 根据特征 $ A $ 是否小于（或等于）$a$ 而被分为两个子集，$\mathbb D _ 1$ 和 $\mathbb D_ 2$，其中：

则在特征 $A:a$ 的条件下，集合 $\mathbb D$ 的基尼指数为：

其中$N$为样本总数，$N_ 1,N_ 2$ 分别为子集 $\mathbb D_ 1,\mathbb D_ 2$ 的样本数量。它就是每个子集基尼系数的加权和，权重是每个子集的大小（以子集占整体集合大小的百分比来表示）。

划分单元和划分点

  一棵 $CART$ 分类树对应着输入空间的一个划分，以及在划分单元上的输出值。设输出 $y $ 为连续变量，训练数据集 $\mathbb D={ \left( { x } _ { 1 },{ y } _ { 1 } \right) ,\left( { x } _ { 2 },{ y } _ { 2 } \right) ,\cdots ,\left( { x } _ { N },{ y } _ { N } \right) } $。假设已经将输入空间划分为 $M$ 个单元 ${ R } _ { 1 },{ R } _ { 2 },\cdots ,{ R } _ { m }$，且在每个单元 ${ R } _ { m }$ 上有一个固定的输出值 ${ c } _ { m }$。则 $CART$ 分类树模型可以表示为：

其中，$I\left( \cdot \right) $ 为示性函数。

  如果已知输入空间的单元划分，基于分类误差最小的准则，则 $CART$ 分类树在训练数据集上的损失函数为：

根据损失函数最小，则可以求解出每个单元上的最优输出值 $\hat c _ m$ 为：$R _ m $ 上所有输入样本 ${ x } _ { i }$ 对应的输出 ${ y } _ { i }$ 的众数，即：

  问题是输入空间的单元划分是未知的。如何对输入空间进行划分？类似 $CART$ 回归树，$CART$ 分类树遍历所有可能的维度 $j$ 和该维度所有可能的取值 $s$，取使得基尼系数最小的那个维度 $j$ 和切分点 $s$。即求解：

伪码

输入：

1. 训练数据集 $\mathbb D$
2. 停止计算条件

输出：$CART$ 决策树

步骤：

1. 选择最优切分维度 $j$ 和切分点 $s$。即求解： \(\left( { j }^{ \ast },{ s }^{ \ast } \right) =\min _{ j,s }{ Gini\left( D,{ A }_{ j }:s \right) }\) 它表示：遍历所有可能的维度 $j$ 和该维度所有可能的取值 $s$ ，取使得基尼系数最小的那个维度 $j$ 和切分点 $s$。

2. 用选定的 $(j,s)$ 划分区域并决定响应的输出值： \(\begin{matrix} { R }_ { 1 }\left( j,s \right) =\{ x \| { x }_ { j }\le s \} \\ { R }_ { 2 }\left( j,s \right) =\{ x \| { x }_ { j }>s \} \end{matrix}\) \(\begin{matrix} { \hat { c } }_ { 1 }=arg\max _ { { c }_ { 1 } }{ \sum _ { { x }_ { i }\in { R }_ { 1 } }{ I\left( { c }_ { 1 }={ \tilde { y } }_ { i } \right) } } \\ { \hat { c } }_ { 2 }=arg\max _ { { c }_ { 2 } }{ \sum _ { { x }_ { i }\in { R }_ { 2 } }{ I\left( { c }_ { 2 }={ \tilde { y } }_ { i } \right) } } \end{matrix}\) 其中 $N_1$ 和 $N_2$ 分别代表区域 $R_ 1$ 和 $R_2$ 中的样本数量。

3. 对子区域 $R_1$ 和 $R_2$ 递归地切分，直到满足停止条件。
4. 最终将输入空间划分为 $M$ 个区域 ${ R } _ { 1 },{ R } _ { 2 },\cdots ,{ R } _ { m }$，生成决策树：$f\left( x \right) =\sum _ { m=1 }^{ M }{ { c } _ { m }I\left( x\in { R } _ { m } \right) } $。

优点

1. 可处理连续型和离散型数据
2. 可用于多分类

缺点

1. 计算量大

其它讨论

$CART$ 分类树和 $CART$ 回归树通常的停止条件为：

1. 结点中样本个数小于预定值，这表示树已经太复杂。
2. 样本集的损失函数或者基尼指数 小于预定值，表示结点已经非常纯净。
3. 没有更多的特征可供切分。

前面讨论的 $CART$ 分类树和 $CART$ 回归树都假设特征均为 连续值。

1. 实际上 $CART$ 树的特征可以为离散值，此时切分区域定义为： \(\begin{matrix} { R }_ { 1 }\left( j,s \right) =\{ x \| { x }_ { j }=s \} \\ { R }_ { 2 }\left( j,s \right) =\{ x \| { x }_ { j }\neq s \} \end{matrix}\)
2. 连续的特征也可以通过分桶来进行离散化，然后当作离散特征来处理。

CART 剪枝

  $CART$ 树的剪枝是从完全生长的 $CART$ 树底端减去一些子树，使得 $CART$ 树变小（即模型变简单），从而使得它对未知数据有更好的预测能力。

$CART$ 剪枝算法由两步组成：

1. 从决策树 $T_ 0$ 的底端开始不断剪枝，直到 $T_ 0$的根节点，形成一个子树序列 ${ T _ 0,T _ 1,…,T _ n } $；
2. 通过交叉验证法在独立的验证集上，对子树进行测试，选出最优子树。

原理

  定义 $CART$ 树 $T$ 的损失函数为：

其中，${ C } _ { \alpha }\left( T \right) $ 为参数是 $\alpha$ 时，树 $T$ 的整体损失；$C(T)$ 为树 $T$ 对训练数据的预测误差；$| { T } _ { f } | $ 为子树的叶结点个数。

  对固定的 $\alpha$，存在使 ${ C } _ { \alpha }\left( T \right) $ 最小的子树，令其为 ${ T } _ { \alpha }^{ \ast }$，可以证明 ${ T } _ { \alpha }^{ \ast }$ 是唯一的。

1. 当 $\alpha$ 大时 ${ T } _ { \alpha }^{ \ast }$ 偏小，即叶结点偏少。
2. 当 $\alpha$ 小时，${ T } _ { \alpha }^{ \ast }$ 偏大，即叶结点偏多。
3. 当 $\alpha=0$ 时，未剪枝的生成树就是最优的，此时不需要剪枝。
4. 当 $\alpha =\infty $ 时，根结点组成的一个单结点树就是最优的。此时剪枝到极致：只剩下一个结点。

  从生成树 $T _ 0$ 开始剪枝。对 $T _ 0$ 任意非叶子结点 $t$，考虑需不需要对 $t$ 进行剪枝？以 $t$ 为单结点树，因为此时只有一个叶结点，即为 $t$ 本身，所以损失函数为：

以 $t$ 为根的子树 $T _ t$，此时的损失函数为：

可以证明：

1. 当 $\alpha=0$ 及充分小时，有 ${ C } _ { \alpha }\left( { T } _ { t } \right) <{ C } _ { \alpha }\left( t \right) $。此时倾向于选择比较复杂的 $ T _ t$，因为正则化项的系数 $\alpha$ 太小。
2. 当 $\alpha$ 增大到某个值时，有 ${ C } _ { \alpha }\left( { T } _ { t } \right) ={ C } _ { \alpha }\left( t \right) $。
3. 当 $\alpha$ 再增大时，有 ${ C } _ { \alpha }\left( { T } _ { t } \right) >{ C } _ { \alpha }\left( t \right) $。即此时倾向于选择比较简单的 $t$，因为正则化项的系数 $\alpha$ 太大。

令 $\alpha =\frac { C\left( t \right) -C\left( { T } _ { t } \right) }{ | { T } _ { t } | -1 } $，此时 $T _ t$ 与 $t$ 有相同的损失函数值，但是 $t$ 的结点更少。因此 $t$ 比 $T _ t$ 更可取，于是对 $T _ t$ 进行剪枝。

  对 $T_ 0$ 内部的每一个内部结点 $t$，计算

它表示剪枝后整体损失函数增加的程度（可以为正，可以为负）。则有：

因为$t$是个内部结点，所以 $ |T _ t |>1$，因此有：

1. $g\left( t \right) >\alpha $ 时，${ C } _ { \alpha }\left( t \right) -{ C } _ { \alpha }\left( { T } _ { t } \right) >0$，表示剪枝后，损失函数增加。
2. $g\left( t \right) =\alpha $ 时，${ C } _ { \alpha }\left( t \right) -{ C } _ { \alpha }\left( { T } _ { t } \right) =0$ ，表示剪枝后，损失函数不变。
3. $g\left( t \right) <\alpha $ 时，${ C } _ { \alpha }\left( t \right) -{ C } _ { \alpha }\left( { T } _ { t } \right) <0$ ，表示剪枝后，损失函数减少。

  对 $T _ 0$ 内部的每一个内部结点 $t$，计算最小的 $g$： \({ g }^{ \ast }=\min { g\left( t \right) ,t\in { T }_ { 0 } } and\quad t\quad is\quad not\quad a\quad leaf\)

设 ${ g }^{ \ast }$ 对应的内部结点为 ${ t }^{ * }$，在 $T _ 0$ 内减去 ${ t }^{ * }$，得到的子树作为 $T _ 1$。令 $\alpha _ 1=g* $，对于 ${ t\neq t }^{ * }$，有：

对于 $\alpha >{ \alpha } _ { 1 }$，有：

1. 对于 $t^{*}$ 剪枝，得到的子树的损失函数一定是减少的。它也是所有内部结点剪枝结果中，减少的最多的。因此 $T _ 1$是$\alpha \in [\alpha _ 1,)$ 内的最优子树。
2. 对任意一个非 $ t^{*}$ 内部结点的剪枝，得到的子树的损失函数有可能是增加的，也可能是减少的。如果损失函数是减少的，它也没有 $T _ 1 $ 减少的多。

  如此剪枝下去，直到根结点被剪枝。此过程中不断产生 $\alpha _ i$ 的值，产生新区间 $[\alpha _ 1,\alpha _ 2),[\alpha _ 2,\alpha _ 3),\cdots$；此过程中不断产生 最优子树 $T _ 1,T _ 2,\cdots$；其中 $T _ 1$ 是由 $T _ 0$ 产生的 $\alpha \in [\alpha _ 1,\alpha _ 2)$ 内的最优子树；$T _ 2$ 是由 $T _ 1$ 产生的 $\alpha \in [\alpha _ 2,\alpha _ 3)$ 内的最优子树；…

  上述剪枝的思想就是用递归的方法对树进行剪枝：计算出一个序列 $0=\alpha _ 0 \lt \alpha _ 1\lt\cdots\lt \alpha _ n \lt \infty$，同时剪枝得到一系列最优子树序列 ${T _ 0,T _ 1,\cdots,T _ n}$。 其中 $T _ i$ 是 $\alpha \in[\alpha _ i,\alpha _ i+1)$ 时的最优子树。

  上述剪枝的结果只是对于训练集的损失函数较小。需要用交叉验证的方法在验证集上对子树序列进行测试，挑选出最优子树。交叉验证的本质就是为了挑选超参数$ \alpha$。验证过程：用独立的验证数据集来测试子树序列 ${T _ 0,T _ 1,\cdots,T _ n}$ 中各子树的平方误差或者基尼指数。由于 ${T _ 1,\cdots,T _ n}$ 对应于一个参数序列 ${\alpha _ 1,\alpha _ 2,\cdots,\alpha _ n}$，因此当最优子树 $T _ k$ 确定时，对应的区间 $[\alpha _ k,\alpha _ {k+1)}$ 也确定了。

算法

输入：$CART$ 算法生成的决策树 $T _ 0$

输出： 最优决策树 ${ T }^{ \ast }$

算法步骤：

1. 初始化：$k=0,T=T _ 0,\alpha=\infty$
2. 自下而上的对各内部结点 $t$ 计算 $C\left( { T } _ { t } \right) $，$| { T } _ { t } | $，$g\left( t \right) =\frac { C\left( t \right) -C\left( { T } _ { t } \right) }{ | { T } _ { t } | -1 } $，$\alpha =\min { \left( \alpha ,g\left( t \right) \right) } $。
3. 自下而上地访问内部结点 $t$： 若有 $g(t)=\alpha$,则进行剪枝，并确定叶结点 $t$ 的输出，得到树 $T$。
   1. 如果为分类树，则叶结点 $t$ 的输出采取多数表决法：结点 $t$ 内所有样本的标记的众数。
   2. 如果为回归树，则叶结点 $t$ 的输出为平均法：结点 $t$ 内所有样本的标记的均值。
4. 令 $k=k+1,\alpha _ k=\alpha,T _ k=T$。
5. 若 $T$ 不是由根结点单独构成的树，则继续前面的步骤。
6. 采用交叉验证法在子树序列 $T _ 0,T _ 1,\cdots,T _ n$ 中选取最优子树 $T^{*}$。

优点

$CART$ 剪枝算法的优点是：不需要显式指定正则化系数 $\alpha$。

1. $CART$ 剪枝算法自动生成了一系列良好的超参数 $\alpha _ 1,\alpha _ 2,\cdots$ ，然后利用验证集进行超参数选择。
2. 虽然传统剪枝算法也可以用验证集来进行超参数选择，但是 $CART$ 剪枝算法的效率更高。因为 $CART$ 剪枝算法只需要搜索超参数 $\alpha$ 的有限数量的区间即可，而传统剪枝算法需要搜索整个数域 $[0,\infty)$。

连续值、缺失值处理

连续值

  现实学习任务中常常会遇到连续属性，此时可以使用连续属性离散化技术将连续特征转换为离散特征。最常用的离散化技术为二分法 $bi-partition$，给定样本集 $\mathbb D$ 和连续属性 $A$，假设该属性在 $\mathbb D$ 中出现了 $M$ 个不同的取值。

1. 将这些值从小到大进行排列，记作 $a _ 1,a _ 2,\cdots,a _ M$。
2. 选取 $M-1$ 个划分点，依次为 $\frac{a1+a2}{2},\frac{a2+a3}{2},\cdots,\frac{a _ {M-1}+a _ M}{2}$。
3. 然后就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集和的划分。

这也是 $C4.5$ 算法采取的方案。

  事实上划分点的数量可以是任意正整数，划分点的位置也可以采取其它的形式。划分点的数量、划分点的位置都是超参数，需要结合验证集、具体问题来具体分析。

缺失值

  现实任务中经常会遇到不完整样本，即样本的某些属性值缺失。如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，则是对数据信息的极大浪费。这里有两个问题：

1. 如何在属性值缺失的情况下选择划分属性？
2. 给定划分属性，如果样本在该属性上的值缺失，则如何划分样本？

划分属性选择

  给定训练集 $\mathbb D$ 和属性 $A$，令 $\tilde {\mathbb D}$ 表示 $\mathbb D $ 中在属性 $A$ 上没有缺失的样本子集。则可以仅根据 $\tilde {\mathbb D}$ 来判断属性 $A$ 的优劣 。

  假定属性 $A$有 $n$ 个可能的取值 $a _ 1,a _ 2,\cdots,a _ n$。令：

1. $\tilde {\mathbb D}^{i}$ 表示：$\tilde {\mathbb D}$ 中在属性 $A$ 上取值为 $a _ i$ 的样本的子集
2. $\tilde {\mathbb D} _ k$ 表示：$\tilde {\mathbb D}$ 中属于第 $k$ 类的样本子集（一共有 $K$ 个分类）。

  为每个样本 $x$ 赋予一个权重 ${ w } _ { x }$，定义： \(\begin{aligned} \rho &=\frac { \sum _{ x\in \tilde { D } }{ { w }_{ x } } }{ \sum _{ x\in D }{ { w }_{ x } } } \\ { \tilde { p } }_{ k }&=\frac { \sum _{ x\in { \tilde { D } }_{ k } }{ { w }_{ x } } }{ \sum _{ x\in \tilde { D } }{ { w }_{ x } } } \\ { \tilde { r } }_{ i }&=\frac { \sum _{ x\in { \tilde { D } }^{ i } }{ { w }_{ x } } }{ \sum _{ x\in \tilde { D } }{ { w }_{ x } } } \\ k&=1,2,\cdots ,K \\ i&=1,2,\cdots ,n \end{aligned}\)

其物理意义为：

1. $\rho$ 表示：无缺失值样本占总体样本的比例。
2. $\tilde p _ k $ 表示：无缺失值样本中，第$k$类所占的比例。
3. $\tilde r _ i$ 表示：无缺失值样本中，在属性$A$上取值为 $a _ i$ 的样本所占的比例。

  将信息增益的计算公式推广为：

其中：$H\left( \tilde { D } \right) =-\sum _ { k=1 }^{ K }{ { \tilde { p } } _ { k } } \log { { \tilde { p } } _ { k } } $。

样本划分

基于权重的样本划分：

1. 如果样本 $x$ 在划分属性 $ A $ 上的取值已知，则：
   1. 将 $x$ 划入与其对应的子结点。
   2. $x$ 的权值在子结点中保持为 ${ w } _ { x }$。
2. 如果样本 $x$ 在划分属性 $ A $ 上的取值未知，则：
   1. 将 $x$ 同时划入所有的子结点。
   2. $x$ 的权值在所有子结点中进行调整：在属性值为 $ a _ i$ 对应的子结点中，该样本的权值调整为 ${ \tilde { r } } _ { i }\times { w } _ { x }$。

直观地看，基于权重的样本划分就是让同一个样本以不同的概率分散到不同的子结点中去。

1. 这一做法依赖于：每个样本拥有一个权重，然后权重在子结点中重新分配。
2. $C4.5$使用了该方案。

多变量决策树

  由于决策树使用平行于坐标轴的拆分，使得它对于一些很简单的问题很费力。比如：当 $x _ 2\gt x _ 1$ 时为正类；否则为反类。这种拆分边界并不平行于坐标轴，使得决策树会用许多层的拆分来逼近这个边界。

  解决方案是：多变量决策树 ($multivariate \ decision \ tree$)。传统的单变量决策树的分类边界每一段是与坐标轴平行的，每一段划分都直接对应了某个属性的取值；多变量决策树的分类边界可以为斜线，它可以大大简化了决策树的模型。

  多变量决策树中，内部结点不再是针对某个属性，而是对属性的线性组合。即：每个内部结点是一个 $\sum _ { i=1 }^{ d }{ { w } _ { i }{ x } _ { i }=t } $ 的线性分类器。其中，$w _ i$ 是属性 $x _ i$ 的权重；$d$ 为变量的数量；$t$ 表示这些变量的约束。

  与传统的单变量决策树不同，在多变量决策树的学习过程中，不是为每内部结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。