决策树

1. 历史背景

关于树形结构的历史可以追溯到古巴比伦，在这里就不过多阐述。

1963：最早的发表在文献中的回归树算法是Automatic Interaction Detection(AID, Morgan & Sonquist)。AID 从根节点开始递归的将数据拆分为两个子节点，选择划分特征的依据是通过类似于方差的公式 $\sum (X-\overline{X})^2$ ，称为不纯函数，计算划分子节点的误差平方和使其越小说明划分效果越好，因为 $\sum (X-\overline{X})^2=\sum X^2-N\overline{X}^2$，所以最终只要计算划分后 $\sum N_i\overline{X_i}^2$ 即可，选择最大的特征进行划分。当划分后的误差平方减少值小于 $0.02(\sum X^2-N\overline{X}^2)$ 则结束算法（亦或0.006，CART书中所写）。

1972：THeta Automatic Interaction Detection (THAID, Messenger & Mandell) 将上述思想应用到分类问题中，提出了第一个分类树，并用熵函数和基尼指数代替上述不纯函数。

1980：CHi-squared Automatic Interaction Detector (CHAID) 由 Kass 创建，通过 $\mathcal{X}^2$ 拟合优度检验来找到主要特征，假设有两个类别，默认分布概率都是 $1/2$，计算 $\mathcal{X}^2=\sum\sqrt{(n_i-np_i)/(np_i)}$，选取最大的特征进行分割。卡方拟合优度越大意味着观察频数与默认均匀分布的区别越大，也就是越趋于有序，当同一特征将样本均归于同一类时，卡方拟合优度达到最大，当两个类别各有一半时，卡方拟合优度则为0。

1984：Classification And Regression Trees (CART) 伯克利的统计学教授 Leo Breiman 和 Charles Stone 以及斯坦福的 Jerome Friedman 和 Richard Olshen 共同建立。它同样使用 AID 的贪婪搜索方法，但增加了新颖的改进。CART 不再使用停止规则，而是生成一颗大树，通过最低交叉验证对树结构进行剪枝。这解决了 AID 和 THAID 的欠拟合和过拟合问题。

1986：John Ross Quinlan 提出了一个新概念有多个答案的树，而CART 和所有其他算法对每个问题只有两个答案（称为二叉树）。Quinlan 使用称为增益比的杂质标准发明了 Iterative Dichotomiser 3（ID3）。

1993：C4.5 是 ID3 算法的扩展，C4.5 解决了其前身的缺点，在数据挖掘杰出论文的 Top 10 算法中排名第一（Springer LNCS，2008）。

2.决策树结构

决策树模型是一种对实例进行分类或回归的树形结构。树结构的每个节点均代表输入特征空间的部分子区域，对于不再分割的节点称为终端节点（terminal node）也叫叶节点（leaf node），在图中由矩形框表示；除了叶节点以外的称为内部节点（internal node），在图中用圆形表示。

构建决策树的时候，从根节点开始，通过一定规则选定分割的特征维度和特征值，然后构建下一层的多个节点。特别地，如果每一个节点只通过一个特征的一个值分割为两部分，该决策树则称为二叉决策树。

对于决策树中的每一个节点的后代节点都是不相交的，也就是它们之间互斥，同时一个节点所有后代子集的并集即为该节点。例如图1中所示，$X_2$ 与 $X_3$ 互斥且 $X=X_2\bigcup X_3$。决策树中的每一层中的节点的并集构成整体输入特征空间。

终端节点是输入空间的一个子区域，所有终端节点互斥且完备，即所有终端节点的并集构成整体输入空间。在分类问题中，每个终端节点由一个类标签指定，可能有多个终端节点有相同的类标签。分类器最终分类划分是将同一类对应的所有终端子集放在一起得到的。例如，上图的划分结果为

$\begin{aligned} A_1&=X_{15} \\ A_2&=X_{10}\bigcup X_{16}\\ A_3&=X_{11}\bigcup X_{14}\\ A_4&=X_{6}\bigcup X_{17}\\ A_5&=X_8 \\ A_6&=X_{12} \\ \end{aligned}$

综上所述，可以发现构建决策树需要解决三个问题：

在每个中间节点选择拆分的方法
终止条件
每个终端叶子节点的输出结果

进一步地，如果想要决策树模型不仅对训练数据有很好的拟合效果，同时对未知数据有很好的预测，也就是避免过拟合现象的发生，我们还可能需要对已生成的决策树进行自下而上的剪枝，使树结构变得更简单，从而使它具有更好的泛化能力，也就是

决策树的剪枝

有关第一个问题，在这里先定义一个通用的方法和标准。

定义训练集的输入实例数为 $N$，每个类别的数量为 $N_j$，则每个节点 $t$ 中的某一类别的数量为 $N_j(t)$，落入节点的概率为 $p(t) = N(t)/N$，条件概率$p(t\,|\,j)=N_j(t)/N_j$，属于 $j$ 类且落入节点 $t$ 两事件同时发生的概率为 $p(j,t)=p(t\,|\,j)p(j)$，在这里我们先假设先验概率 $p(j)$ 就是训练集中的类别概率 $p(j)=N_j/N$。因此，根据贝叶斯公式我们可以得到后验概率

$\begin{aligned} P(j\,|\,t)&=\frac{p(t\,|\,j)p(j)}{p(t)}\\ &=\frac{(N_j(t)/N_j) \ast (N_j/N)}{N(t)/N}\\ &=\frac{N_j(t)}{N(t)} \end{aligned}$

忙活半天，得到了一个很显而易见的结果 -_-! 但这个显而易见的比例实际上是条件概率。

通常情况下先验概率 $p(j)$ 被视为训练集中的比例 $N_j/N$。但学习样本中的比例无法反映到现实中实际的比例，就例如评价道路的好坏，实际上得到的训练集都是通过 bad case 中的路线，实际上，可能差路线存在的比例会更低。

因此，我们由其他途径的得到先验概率 $\pi(j)$ 取代训练集中的概率 $p(j)$，联合概率即为

$p(j,t)=\pi(j)N_j(t)/N_j$

同时任何案例落入节点 $t$ 的概率重新带入估计

$p(t)=\sum_jp(j,t)$

最后再去计算条件概率 $p(j\,|\,t)$，可以发现，替换后的条件概率依旧满足

$\sum_jp(j\,|\,t)=1$

决策树划分的目的就是希望能通过特征将实例的类别进行区分出来。决策树的每个内部节点将分割为更多的子区域，每个子区域的条件是一样的，而所希望的就是某一类的条件概率 $P(j\,|\,t)$ 尽可能的大。换句话说，希望每个后代节点中的数据比父节点中的数据更“纯”（purer）。

例如，假设有个六分类问题，根节点的条件概率 $(p_1,p_2,p_3,p_4,p_5,p_6)$ 为 $\displaystyle(\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6})$，一个好的划分结果就是两个子节点的条件概率也就是类别比例为 $\displaystyle(\frac{1}{3},\frac{1}{3},\frac{1}{3},0,0,0)$ 和 $\displaystyle(0,0,0,\frac{1}{3},\frac{1}{3},\frac{1}{3})$ 。

因此我们需要寻找一个测度去衡量一个节点中子集的不纯度（impurity），定义一个非负函数，要求当所有类均匀混合在一起时它的不纯度最大，当节点中只包含一个类时，该值最小，现将这个函数定义为 $i(t)$。

对于任何中间节点 $t$，假设有一个节点的候选切分 $s$ 将节点分割为 $t_L$ 和 $t_R$，这样 $t$ 中的事件（case）分别进入 $t_L$ 和 $t_R$ 的比例为 $p_L$ 和 $p_R$，那么最终切分点 $s$ 的好坏定义为不纯度的好坏的减少

$\triangle i(s,t)=i(t)-p_Li(t_L)-p_Ri(t_R)$

对于不是二叉树而是多切分节点的算法只需将上公式扩展为多个即可，但始终 $p_1+p_2+\cdots+p_n=1$。

我们对 $i(t)$ 函数的要求进行总结：

当每个类别概率相等时，$i(t)$ 值最大。
当只有一个类别时，$i(t)$ 值最小
$i(t)$ 是轴对称函数

至此，我们得到一个通用的标准去衡量切分的好坏程度，在不同的算法中以及回归和分类树中，所不同的只是不纯度函数 $i(t)$ 的不同。

3. CART 算法

CART 算法由 Breiman 等人在 1984 年提出。CART 同样由特征选择、树的生成以及剪枝组成，既可用于分类也可以用于回归。

CART 是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART 是二叉树，递归的二分每个特征，分为“是”或“否”，将输入空间即特征空间划分为有限个单元，并在每个单元上确定预测的概率分布。

CART回归树实际是基于AID的决策树方法，但增加了最优切分点的寻找以及剪枝的过程。CART分类树使用到的基尼指数也不是第一次出现。

3.1 CART 分类

我们从前述四个问题出发，先解决最直观的第三个问题

每个终端叶子节点的输出结果

定义1 一个决策树的所有节点的集合为 $T$，终端节点的集合为 $\widetilde{T}$，每个终端节点 $t\in \widetilde{T}$，所有分类标签的集合为 $j\in \{1,2,\cdots,J\}$，则某一节点所分配的类为 $j(t)$。

$j(t)$ 是类分配结果同时也代表一种类分配规则

对于任何一种类分配结果 $j(t)$，如果实例落入节点 $t$，则错误分类概率的重新替换估计（resubstitution estimate）为

$\sum_{j\ne j(t)}p(j\,|\,t)$

我们需要最小化这个误分类估计的规则作为我们类分配规则 $j^\ast(t)$。

由于一个节点最终只能输出一个类别，一个直观的类分配规则就是将某一节点中占比最大的类分配给该节点，这样做的另一个原因就是使误分类的概率最小。

定义2 类分配规则 $j^\ast(t)$：如果 $\displaystyle p(j\,|\,t)=\max_i p(i\,|\,t)$，则 $j^\ast(t)=j$，如果两个或多个不同类别达到最大值，则将 $j^\ast(t)$ 任意指定为任何一个最大化类别。

第三个问题得到解决。

进一步地，我们就可以得到节点 $t$ 的误分类概率的重新带入估计 $r(t)$ 为

$\begin{aligned} r(t)&=\sum_{j\ne j^*(t)}p(j\,|\,t)\\ &=1-\max_j p(j\,|\,t) \end{aligned}$

整体决策树误分类率的重新代入估计则为

$\begin{aligned} R(T)&=\sum_{t\in \widetilde{T}}r(t)p(t)\\ &=\sum_{t\in \widetilde{T}}R(t) \end{aligned}$

$R(t)$ 的一个重要特性，以任何方式分割的越多，则 $R(T)$ 就会变得越小。一个节点 $t$ 分割成两部分 $t_L$ 和 $t_R$，则有

$R(t)\ge R(t_L)+R(t_R)$

以上公式的推导是在假定所有错误分类为 $i$ 类对象的成本或损失都是一样的，在某些问题中希望能将它们区分出来，例如某一类错误分类的代价将会更大，也就是希望尽可能减少其误分类的概率。因此，引入一组错误分类成本 $c(i\,|\,j)$ 代表将 $j$ 类对象误分类为 $i$ 类对象的代价，它应该满足
$c(i\,|\,j)={\begin{cases}C_i(C_i\ge 0)&i\ne j\\0&i=j\end{cases}}$
随机一个实例落入节点 $t$ 并被分类为类别 $i$，则估计的预期误分类代价为
$\sum_j c(i\,|\,j)p(j\,|\,t)$
一个自然地节点分配规则是选择 $i$ 来最小化这个表达式，因此，
令 $j^\ast(t)=i_0$，当 $i_0$ 最小化 $\displaystyle \sum_j c(i\,|\,j)p(j\,|\,t)$，给定节点 $t$ 定义预期错误分类成本的重新替代估计 $r(t)$ 为
$r(t)=\min_i \sum_j c(i\,|\,j)p(j\,|\,t)$
当 $c(i\,|\,j)=1,i\ne j$ 可以发现
$\sum_j c(i\,|\,j)p(j\,|\,t)=1-p(i\,|\,t)$
最小化结果与上面相同

接下来，我们解决第一个问题

在每个中间节点选择拆分的方法

在第二节，我们已经定义了一个通用的切分准则，需要确定的只是 $i(t)$ 函数是什么。事实上，CART 分类树是通过基尼指数来作为切分函数的，但基尼指数并不是凭空出现的，也不是唯一可行的。通过实验发现，构建决策树的总体误分类率对分割规则的选择并不敏感，只要在合理的规则类别内，区别是不大的，同时原作者给出了其从开始到最终基尼指数的思考过程，在这里我们从头开始追根溯源。

从误分类率 $r(t)$ 出发，我们可以发现 $r(t)$ 是可以直接作为衡量节点不纯度的标准，当节点中只有一个类别时，$r(t)$ 为 $0$，当节点中均匀分布时，$r(t)$ 最大为 $1-\frac{1}{n}$。因此最好的分割方式就是最大化

$r(t)-P_Lr(t_L)-P_Rr(t_R)$

用误分类率 $r(t)$ 作为不纯函数，存在两个严重的缺陷。

第一个缺陷，用上式对节点 $t$ 进行切分有可能所有拆分结果都为 $0$。证明如下：

$\begin{aligned} r(t)&=\sum_{j}c(j^*(t)\,|\,j)p(j\,|\,t)\\ &=\sum_{j}c(j^*(t)\,|\,j)p(j,t)p(t)\\ &=\sum_{j}c(j^*(t)\,|\,j)[p(j,t_L)+p(j,t_R)]p(t) \end{aligned}$

让 $p(t)=1$，因此

$\begin{aligned} r(t)&-P_Lr(t_L)-P_Rr(t_R)\\ &=\sum_{j}c(j^*(t)\,|\,j)[p(j,t_L)+p(j,t_R)]-\min_i\sum_jc(i\,|\,j)p(j\,|\,t_L)P_L-\min_i\sum_jc(i\,|\,j)p(j\,|\,t_R)P_R\\ &=\sum_{j}c(j^*(t)\,|\,j)[p(j,t_L)+p(j,t_R)]-\min_i\sum_jc(i\,|\,j)p(j,t_L)-\min_i\sum_jc(i\,|\,j)p(j,t_R)\\ &=\sum_{j}c(j^*(t)\,|\,j)p(j,t_L)-\min_i\sum_jc(i\,|\,j)p(j,t_L) + \sum_{j}c(j^*(t)\,|\,j)p(j,t_R)-\min_i\sum_jc(i\,|\,j)p(j,t_R)\\ &=\sum_{j}c(j^*(t)\,|\,j)p(j,t_L)-\sum_jc(j^*(t_L)\,|\,j)p(j,t_L) + \sum_{j}c(j^*(t)\,|\,j)p(j,t_R)-\sum_jc(j^*(t_R)\,|\,j)p(j,t_R)\\ \end{aligned}$

等号的右边是大于 $0$ 的，并且仅当 $j^\ast(t)=j^\ast(t_L)=j^\ast(t_R)$ 时等号成立。

这个式子可以这么理解，$j^\ast(t)$ 是使 $\displaystyle\sum_j c(i\,|\,j)p(j\,|\,t)$ 最小化的特征，当节点 $t$ 被切分为两部分后， $j^\ast(t_L)$ 是使 $\displaystyle\sum_j c(i\,|\,j)p(j\,|\,t_L)$ 最小化的特征，那么 $j^\ast(t)$ 无论是什么都不会使 $\displaystyle \sum_{j}c(j^\ast(t)\,|\,j)p(j,t_L)$ 比 $\displaystyle \sum_jc(j^\ast(t_L)\,|\,j)p(j,t_L)$ 更小。

从上式中可以知道，当父节点与切分后的两个节点的最大占比的类别一样时，无论怎么切分 $r(t)-P_Lr(t_L)-P_Rr(t_R)$ 均为 $0$，即不存在单个或少量的最优拆分点。

第二个缺陷是很难对决策树进行准确的评价。换句话说，降低错误分类率似乎不是整个决策树生长过程的好的目标和标准。

举一个简单的例子，父节点 $t$ 的分布为 400（类别1）和 400（类别2），一个切分方式生成两个节点，一个节点分布为 300（类别1）、100（类别2），另一个节点分布为 100（类别1）、300（类别2），其中 200 个实例被分类错误，误分类率为 0.25。另一种切分方式为200（类别1）、400（类别2）和 200（类别1）、0（类别2），误分类率同样为 0.25。

误分类率对两种切分方式评价相同，不纯度值的减少分别为 $\displaystyle \frac{1}{2}-\frac{1}{2}\ast \frac{1}{4}-\frac{1}{2}\ast \frac{1}{4}=0.25$ 和 $\displaystyle \frac{1}{2}-\frac{6}{8}\ast \frac{2}{6}-\frac{2}{8}\ast 0=0.25$。但对于决策树未来的生长来看，第二种切分方式更为可取，虽然一个节点的误分类率为 $\displaystyle\frac{2}{6}$ ，但另一个节点误分类率为 $0$，这个节点是终端，无需进一步切分。

综上所述，为了解决误分类率作为不纯度函数的缺陷，需要对不纯度函数进行改进。

从二分类问题出发，误分类率不纯度函数为

$\begin{aligned} \varphi(p_1,p_2)&=1-\max (p_1,p_2)\\ &=\min (p_1,p_2)\\ &=\min (p_1,1-p_1)\\ &={ \begin{cases} p_1&0\le p_1\le 0.5\\ 1-p_1&0.5<p_1\le 1 \end{cases} } \end{aligned}$

从上述例子可以想到，为了将两种切分方式区分出来，使第二种切分结果得到的评价更高，就要充分奖励更纯的节点。假设 $p_1>0.5$，那么 $\varphi(p_1)=1-p_1$ 是随着 $p_1$ 线性减少的，为了使纯节点的评价更好，需要使 $\varphi(p_1)$ 随着 $p_1$ 的增加而比线性下降更快。也就是当 $p’’_1>p’_1$ 时，$\varphi’(p’’_1)<\varphi’(p’_1)$，因此要求不纯度函数是严格凸函数。如果 $\varphi$ 在 $[0,1]$ 上有连续的二阶导数，则应该满足 $\varphi’’(p_1)<0,0<p_1<1$。

将不纯函数需要满足的条件用公式表示

$\varphi(0)=\varphi(1)=0$
$\varphi(p_1)=\varphi(1-p_1)$
$\varphi(1/2)=\text{maximum}$
$\varphi’’(p_1)<0,0<p_1<1$

最简单的满足条件的函数就是二次多项式

$\varphi(x)=a+bx+cx^2$

由 1 可以得到 $a=0,b+c=0$，因此

$\varphi(x)=b(x-x^2)$

公式 4 要求 $b>0$，不失一般性，取 $b=1$，因此得到不纯度函数

$i(t)=p(1\,|\,t)p(2\,|\,t)$

这就是基尼指数的原型，公式简单且易于计算。一个直观的解释，假设节点 $t$ 中的所有 1 类对象被赋予数值 1，而 2 类对象被赋予数值 0，那么 $p(1\,|\,t)$ 和 $p(2\,|\,t)$ 是节点中两个类的比例，则节点中数值的样本方差就是 $p(1\,|\,t)p(2\,|\,t)$。

信息熵公式 $i(t)=-p(1\,|\,t)\log p(1\,|\,t)-p(2\,|\,t)\log p(2\,|\,t)$ 同样满足上述条件。原作者说想不出任何内在的原因为什么同样一个满足条件的函数应该优于任何其他函数，并且测试表明两个函数给出了相似的结果，因此依据简单性原则选择基尼指数。

将二分类问题扩展到多分类问题中，给定节点 $t$ 的类估计概率 $p(j\,|\,t),j=1,\cdots,J$，基尼指数定义为

$i(t)=\sum_j\sum_{i\ne j}p(j\,|\,t)p(i\,|\,t)$

同样可以写成

$i(t)=\sum_jp(j\,|\,t)(1-p(j\,|\,t))=1-\sum_jp^2(j\,|\,t)$

对于二分类问题则有

$\begin{aligned} i(t)&=2p(1\,|\,t)p(2\,|\,t)\\ &=2p(1-p)\\ \end{aligned}$

这里与上面的不纯度函数不同，具体在于多了 2，基尼指数是在误差分类率上推导出来的，按理说$\displaystyle i(t)=\min_j\sum_{i\ne j}p(j\,|\,t)p(i\,|\,t)$，但实际上是累加的，基尼指数的最大值是1，而误分类率最大值是0.5，有些不解。如果按下述所说的，那么实际难道是随机选择分类吗？

基尼指数的一种解释方法是，不是使用多数选择的规则对节点 $t$ 中的对象进行分类，而是从节点中随机选择实例将该实例的类别分配给对象，因此将以概率 $p(i\,|\,t)$ 分配为类别 $i$，则误分类的概率就是 $\displaystyle \sum_{i\ne j}p(j\,|\,t)p(i\,|\,t)=p(j\,|\,t)(1-p(j\,|\,t))$，然后再对 $j$ 求和。因此

$i(t)=\sum_j\sum_{i\ne j}p(j\,|\,t)p(i\,|\,t)$

另一种解释方法如前所说，在节点 $t$ 中，为所有 $j$ 类对象分配值 $1$，为所有其他对象分配值 $0$。那么这些值的样本方差为$p(j\,|\,t)(1-p(j\,|\,t))$。对所有 $J$ 类重复操作并求和，则结果就是

$i(t)=\sum_jp(j\,|\,t)(1-p(j\,|\,t))=1-\sum_jp^2(j\,|\,t)$

根据数据特征值是否为指定值 $a$，将节点 $t$ 分为两部分 $t_L$ 和 $t_R$，即

$t_L=\{(\mathbf{x},y)\,|\,\mathbf{x}^{(i)}=a\},t_R=t-t_L$

因此不纯值的减少即为

$\triangle i(s,t)=i(t)-p_Li(t_L)-p_Ri(t_R)$

最后一个需要解决的问题

终止条件

算法停止计算的条件是结点中的样本个数小于预定阀值，或样本集的基尼指数小于预定阔值(样本基本属于同一类)，或者没有更多特征。

CART回归树算法

输入：训练数据集 $D$
输出：CART 分类决策树
步骤：
1. 从初始节点开始，选取特征 $A$，对该特征可取的每个值 $a$，将数据集 $D$ 分为两部分 $\{D_1\,|\,A=a\}$ 和 $\{D_2\,|\,A\ne a\}$，分别计算基尼指数，选择基尼指数最小的特征值作为该特征的最优切分点。
2. 对所有特征重复步骤 1，再在其中选取基尼指数最小的特征作为最优特征。根据最优特征及其最优切分点将数据集进行切分，把该节点分为两个子节点 $t_L$ 和 $t_R$，节点中的数据集即为 $D_1$ 和 $D_2$。
3. 对两个子节点递归地重复步骤 1 和步骤 2。
4. 当某一节点满足终止条件时，则停止切分，返回父节点，继续遍历其他节点。终止条件为节点中样本个数小于预定阈值，或节点中样本均为一个类别，或样本集的基尼指数小于预定阈值（样本基本属于同一类）。
5. 当所有节点均遍历之后，即生成 CART 分类决策树，结束算法。

3.2 CART 回归

回归树同样需要解决上面三个问题

训练数据集：

$D=\{(\mathbf x_1,y_1),(\mathbf x_2,y_2),...,(\mathbf x_N,y_N)\}$

第三个问题最直观也最好解决，假设输出值的函数为 $d$，总的均方误差为

$R(d)=\frac{1}{N}\sum_n^N(y_n-d(\mathbf x_n))^2$

对于每个叶子节点，假设输入空间为 $t$，根据最小二乘法，为了使 $R(d)$ 最小，输出值应为

$d_t(\mathbf x_n)=\overline{y}_t=\frac{1}{N_t}\sum_{\mathbf x_n\in t}y_n$

即回归树建立完后，每个叶子节点的输出值为其分配样本的均值。

进一步的，将预测值带入每个节点 $t$，并用 $R(T)$ 取代 $R(d)$

$R(T)=\frac{1}{N}\sum_{t\in \widetilde{T}}\sum_{\mathbf x_n\in t}(y_n-\overline{y}_t)^2$

定义

$R(t)=\frac{1}{N}\sum_{\mathbf x_n\in t}(y_n-\overline{y}_t)^2$

注意这里不是 $N_t$

因此，$R(T)$ 还可以写为

$R(T)=\sum_{t\in \widetilde{T}}R(t)$

对以上表达式一个简单的解释就是，对于每个节点 $t$，$\displaystyle \sum_{\mathbf x_n\in t}(y_n-\overline{y}_t)^2$ 是节点内的误差平方和，对 $t$ 求和给出所有节点的总平方和，再除以 $N$ 给出平均值。

假定分割前的均方误差为 $R(t)$，分割点为特征向量 $j$，分割值为 $s$，输入空间 $t$ 将被分为两个区域

$t_L=\{x\,|\,x^{(j)}\le s\},t_R=\{x\,|\,x^{(j)}\ge s\}$

为了使分割更为有效，将使均方误差减少的尽可能多，因此目标函数为

$\triangle R(s,t)=R(t)-R(t_L)-R(t_R)$

与 $s$ 相关的变量只有后两项，因此

$\max \triangle R(s,t)=\min [R(t_L)+R(t_R)]$

令 $p(t)=\frac{N_t}{N}$ 表示随机选择输入变量落入节点 $t$ 的概率，定义节点内方差

$s^2(t)=\frac{1}{N_t}\sum_{\mathbf x_n\in t}(y_n-\overline{y}_t)^2$

因此可得 $R(t)=s^2(t)p(t)$，并且

$R(T)=\sum_{t\in \widetilde{T}}s^2(t)p(t)$

$t$ 的最佳分割也就是使加权方差最小化

$\min[p(t_L)s^2(t_L)+p(t_R)s^2(t_R)]$

实际上概率 $p$ 可以带入进去，再乘以 $N$，就得到李航书中的公式

$\min_{j,s} \left[\sum_{x_i \in t_L} (y_i-\overline{y}_{t_L})^2+ \sum_{x_i \in t_R} (y_i-\overline{y}_{t_R})^2\right]$

依次选取切分变量 $j$，遍历空间中所有输入点确定最优切分值 $s$，找到最优切分变量和切分值使上式最小。

对每个区域依次重复上述过程，直到达到终止条件。与 AID 不同，CART 终止条件为节点中的样本个数小于特定阈值（通常为5），或者节点中样本均为一个类别，即该节点为纯节点。

至此回归的三个问题均已解决，归纳如下

CART回归算法

输入：训练数据集 $D$
输出：CART 回归决策树
步骤：
1. 从初始节点开始，选取特征 $j$，遍历数据集 $D$ 中每个实例特征 $j$ 的取值 $s$，将数据集分为两部分$t_L=\{D_1\,|\,\mathbf x^{(j)}\le s\}$ 和 $t_R=\{D_2\,|\,\mathbf x^{(j)}\ge s\}$，每部分的输出值即为该部分所有实例的平均值 $\overline{y}_t$，依次用 $\displaystyle \sum_{x_i \in t_L} (y_i-\overline{y}_{t_L})^2+ \sum_{x_i \in t_R} (y_i-\overline{y}_{t_R})^2$ 计算分类误差，误差最小的 $s$ 即为最优切分值。
2. 对所有特征重复步骤 1，再在其中选取分类误差最小的特征作为最优特征。根据最优特征及其最优切分点将数据集进行切分，把该节点分为两个子节点 $t_L$ 和 $t_R$，节点中的数据集即为 $\{D_1\,|\,\mathbf x^{(j)}\le s\}$ 和 $\{D_2\,|\,\mathbf x^{(j)}\ge s\}$
3. 对两个子节点递归地重复步骤 1 和步骤 2。
4. 当某一节点满足终止条件时，则停止切分，返回父节点，继续遍历其他节点。终止条件为节点中的样本个数小于特定阈值（通常为5），或者节点中样本均为一个类别，即该节点为纯节点。
5. 当所有节点均遍历之后，即生成 CART 回归决策树，结束算法。

3.2 CART 剪枝

随着决策树生成终端节点的增加，训练数据集的误分类率会下降，极端情况一个实例一个节点，则训练集的准确率会达到百分之百。但是，测试集的误分类率会随着决策树的变大先减少后增加，即决策树应当在一定大的时候停止分裂，这时预测效果才是最好的。产生这样的现象的原因是偏差和方差之间的权衡。

在早期决策树的停止规则是设定阈值 $\beta$，当不纯值的最大减少小于 $\beta$ 则停止分裂节点。这样做的结果通常不会令人满意，主要有两个问题，第一如果 $\beta$ 设的太小则会导致决策树过大，如前所述，导致预测准确率下降；第二，如果 $\beta$ 过大，可能有节点的不纯值减少的很小，但其两个后代节点可能有分裂，且不纯值大幅减少，例如二维空间中一三象限同类，二四象限同类，且分布均匀，第一次无论怎么分割不纯值都不会减少很多，但第二次分割就可以区分出两个类别。

最终，Breiman 等人认为寻找正确的停止规则本身就是一个错误的方式，并发现了一个更令人满意的方法：

采用修剪而不是停止。不加约束的使决策树尽可能的生长，然后以正确的方式向上修剪，直到最终修剪回根节点。
使用更准确的误分类率估计从修剪的子树中选择合适大小的树。

对于更准确误分类率估计的方法，对于大样本量就是使用独立的测试样本，而对于小样本量，则应采用交叉验证的方法。

进行修剪的前置条件是要求决策树足够的大，但两个足够大的树结构其实并没有区别，无论是从一个最大的树 $T_{max}$ 开始，还是一个较小但依然足够大的数 $T’_{max}$ 开始，如果从 $T_{max}$ 开始的剪枝过程产生的子树包含在 $T’_{max}$ 中，那么两个树结构将修剪出完全相同的子树。

如前所述，CART 终止条件为节点中的样本个数小于特定阈值（通常为5，偶尔设置为1），或者节点中样本均为一个类别，即该节点为纯节点，或仅包含相同的测量向量（应该是特征值相同，但类别不同）。这样就可以保证生成一颗足够大的决策树。

假设 CART 最终生成的决策树为 $T_{max}$，则对于任意一颗子树 $T\preceq T_{max}$ 的误分类率（或者基尼指数）重新带入估计为

$\begin{aligned} R(T)&=\sum_{t\in \widetilde{T}}r(t)p(t)\\ &=\sum_{t\in \widetilde{T}}R(t) \end{aligned}$

定义一个新的损失函数

$R_\alpha(T)=R(T)+\alpha|\widetilde{T}|$

其中，$\alpha$ 称为复杂度参数且 $\alpha\ge 0$，$|\widetilde{T}|$ 是子树 $T$ 中终端节点的个数，$R_\alpha(T)$ 是损失值。如果将 $\alpha$ 视为每个终端节点的复杂度成本，那么 $R_\alpha(T)$ 实际上就是在树的错误分类成本上增加复杂度成本惩罚形成的。$\alpha$ 的作用就是权衡训练数据的拟合程度与模型的复杂度。

现在，对任意取值的 $\alpha$，都可以找到一个子树 $T(\alpha)\preceq T_{max}$ 使损失值 $R_\alpha(T)$ 最小

$R_\alpha(T(\alpha))=\min_{T\preceq T_{max}}R_\alpha(T)$

在 $\alpha$ 固定的情况下，$T(\alpha)$ 在损失值 $R_\alpha(T)$ 最小的意义下是最优的，且是唯一的。当 $\alpha$ 较小时，具有大量终端节点的惩罚较小，最优子树 $T(\alpha)$ 较大。极端情况下，$\alpha=0$ ，那么 $T_{max}$ 就是最优的，无需进行剪枝。随着 $\alpha$ 的增大，最优子树 $T(\alpha)$ 将具有更少的终端节点。最后，对于足够大的 $\alpha$，最优子树 $T(\alpha)$ 将仅包含根节点 $\{t_1\}$。

在这里，子树 $T(\alpha)$ 与 $T_{max}$ 是具有相同根节点的树。

尽管 $\alpha$ 是连续取值的，但 $T_{max}$ 的子树的数量是有限的。那么随着 $\alpha$ 增加，剪枝过程会产生一个有限序列的子树 $T_1,T_2,T_3,\dots,\{t_1\}$ 终端节点不断减少。每个子树对应着 $\alpha$ 的一个区间，即在一定区间内，该子树都是最优子树。

现在的问题在于，如何找到这些最优子树，如果确定 $\alpha$ 去找最优子树，那么 $\alpha$ 的增长步长是难以决定的，太大了容易跳过某些子树，太小则搜索效率太低，毕竟对应一个 $\alpha$ 值，每个子树都需要遍历一遍。同时，在理论上，一个 $\alpha$ 值对应的最优子树是否是唯一的，以及 $T_1,T_2,T_3,\dots$ 序列中，每个子树是否都是前一个子树修剪而成的，即嵌套 $T_1\succ T_2\succ T_3\dots\succ \{t_1\}$ 是否成立。

Breiman 等人给出了如下的解决办法。

从 $T_0 = T_{max}$ 开始，对任意节点 $t \in T_0$，以该单节点 $\{t\}$ 为子树的损失函数为

$R_\alpha(\{t\})=R(t)+\alpha$

以 $t$ 为根节点的子树 $T_t$ 的损失函数为

$R_\alpha(T_t)=R(T_t)+\alpha|\widetilde{T}_t|$

当 $\alpha$ 较小时，子树 $T_t$ 的成本复杂度比单个节点 $\{t\}$ 要小

$R_\alpha(T_t)<R_\alpha(\{t\})$

但当 $\alpha$ 达到某个临界值时，两个成本复杂度会变得相等，此时，单节点 $\{t\}$ 比 $T_t$ 的终端节点更少，因此 $\{t\}$ 比 $T_t$ 更可取。求解

$R_\alpha(T_t)=R_\alpha(\{t\})$

可以得到 $\alpha$ 的值

$\alpha = \frac{R(t)-R(T_t)}{|\widetilde{T}_t|-1}$

定义一个函数 $g(t)$，对 $T_0$ 中的每个点带入计算

${\displaystyle g(t)={ \begin{cases} \displaystyle\frac{R(t)-R(T_t)}{|\widetilde{T}_t|-1}&t\notin \widetilde{T}_t\\ +\infty&t\in \widetilde{T}_t \end{cases} } }$

找到 $t_{min}$ 最小化该函数

$g(t_{min})=\min g(t)$

就可以得到剪枝之后的树

$T_1=T_0-T_{t_{min}}$

剪枝方法是保留 $t_{min}$ 节点，剔除其所有后代节点。

同时，将 $g(t_{min})$ 设为 $\alpha_1$。至此，我们就得到了区间 $[\alpha_1,\alpha_2)$ 的最优子树 $T_1$。（区间 $[\alpha_0,\alpha_1)$ 的最优子树就是 $T_0$，也就是 $T_{max}$）

进一步地，再在 $T_1$ 的基础上得到 $T_2$，直到得到根节点 $\{t_0 \}$。最终我们得到一连串的子树序列 $T_0,T_1,T_2,T_3,\dots,\{t_1\}$ ，且它们之间满足嵌套关系 $T_0\succ T_1\succ T_2\succ T_3\dots\succ \{t_1\}$ 。

最后，通过独立验证数据集，在$T_0,T_1,T_2,T_3,\dots,\{t_1\}$ 中选取平方误差或基尼指数最小的子树作为最优的子树。

https://holypython.com/dt/decision-tree-history/
https://www.explorium.ai/blog/the-complete-guide-to-decision-trees/
https://en.wikipedia.org/wiki/C4.5_algorithm
https://www.analyticsvidhya.com/blog/2021/05/implement-of-decision-tree-using-chaid/
https://www.cnblogs.com/fushengweixie/p/8039991.html

Machine Learning

2021-12-22