决策树
决策树（decision tree）是一种常见的机器学习方法，是一种基本的分类和回归方法。本文主要讨论用于分类的决策树。
决策树是树形的，在分类问题中，表示的是基于特征对实例进行分类的过程，可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。主要优点是可读性高、分类速度快。在学习阶段，利用训练数据，根据损失函数最小化原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。
决策树学习通常包含3个步骤：
- 特征选择
- 决策树的生成
- 决策树的修剪
决策树的思想主要来源于Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法。
本文会首先介绍决策树的基本概念，然后通过ID3和C4.5介绍特征选择、决策树的生成以及决策树的修剪，最后介绍CART算法。
决策树模型与学习
决策树模型
定义 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）和叶节点（leaf node）。内部节点表示一个特征或属性，叶节点表示一个类。
用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到子节点；这时，每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试与分类，直至达到叶节点，最后将实例分到叶节点的类中。
决策树与if-then规则
可以将决策树看成一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：由决策树的根节点到叶节点的每一条路径构建一条规则；路径上的内部节点的特征对应着规则的条件，而叶节点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合有一个重要的性质：互斥并且完备。这就是说，每个实例都能被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域。并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X是表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示为\(P=(Y \vert X)\)，X取值于给定划分下单元的集合，Y取值于类的集合。各叶节点（单元）上的条件概率往往偏向于某个类，即属于某个类的概率较大。决策树分类时将该节点的实例强行分到条件概率大的那一类去。
决策树学习
假设给定训练集
\[D = \{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}\]其中，\(x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})\)为输入实例（特征向量），n为特征个数，\(y_i \in \{1,2,...K\}\)为类标记，\(i=1,2,...,N\)，N为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型，使他能够对实例进行正确的分类。
决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即是能够对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看，决策树学习是由训练数据集估计条件概率模型，基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。
决策树学习用损失函数表示这一目标。如下所述，决策树学习的损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。
当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优的。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根节点，将所有数据都放在根节点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集基本能够被正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点中去，如果还有不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶节点上，即有了明确的类，这就生成了一颗决策树。
以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶节点，使其回退到父节点，甚至更高的节点，然后将父节点或者更高的节点改为新的叶节点。
如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。
可以看出，决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型，决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。
决策树学习常用的算法有ID3、C4.5与CART，下面结合这些算法分别叙述决策树学习的特征选择、决策树的生成和剪枝过程。
特征选择
特征选择问题
特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。
首先通过一个例子来说明特征选择问题。
下表是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的4个特征（属性）：第一个特征是年龄，有三个可能值：青年，中年，老年；第2个特征是有工作，有2个可能值：是，否；第3个特征是有自己的房子，有2个可能值：是，否；第4个特征是信贷情况，有3个可能值：非常好，好，一般。表的最后一列是类别，是否同意贷款，取2个值：是，否。
| ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别 |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。
特征选择是决定用哪个特征来划分特征空间。
下图是从表的数据学习到的两个可能的决策树，分别由两个不同特征的根节点构成。（a）所示的根节点的特征是年龄，有3个取值，对应于不同的取值有不同的子节点。（b）所示的根节点的特征是有工作，有2个取值，对应于不同的取值有不同的子节点。两个决策树都可以从此延续下去。问题是：究竟选择哪一个特征更好些？这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这个特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。
信息增益
为了便于说明，先给出熵和条件熵的定义。
在信息论和概率统计中，熵（entropy）是表示随机变量不确定性的度量，设X是一个取有限个值的离散随机变量，其概率分布为
则随机变量X的熵定义为
\[H(X)=-\sum_{i=1}^n{p_i\log p_i}\]在上式中，若\(p_i=0\)，则定义\(0\log 0=0\)，通常式中的对数以2为底或以e（自然对数）为底，这时熵的单位分别称作比特(bit)或纳特(nat)。由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可以将X的熵记作\(H(p)\)，即
\[H(p)=-\sum_{i=1}^n{p_i\log p_i}\]熵越大，随机变量的不确定性就越大，从定义可验证
\[0\leq H(p)\leq \log n\]当随机变量只取两个值，例如1,0时，即X的分布为
\[P(X=1)=p, P(X=0)=1-p, 0\leq p\leq 1\]熵为
\[H(p)=-p\log_2 p-(1-p)\log_2 (1-p)\]这时，熵\(H(p)\)随概率p变化的曲线如下图所示（单位为比特）。
当p=0或者p=1时，H(p)=0，随机变量完全没有不确定性。当p=0.5时，H(p)=1，熵取值最大，随机变量不确定性最大。
设有随机变量(X,Y)，其联合概率分布为
条件熵\(H(Y\vert X)\)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵\(H(Y\vert X)\)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望
\[H(Y\vert X)=\sum_{i=1}^n p_i H(Y\vert X=x_i)\]这里，\(p_i=P(X=x_i), i=1,2,...,n\)。
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。此时，如果有0概率，令\(0\log 0=0\)。
信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
定义 (信息增益)特征A对训练数据集D的信息增益\(g(D,A)\)，定义为集合D的经验熵\(H(D)\)与给定特征A条件下D的经验条件熵\(H(D\vert A)\)之差，即
\[g(D,A)=H(D)-H(D\vert A)\]一般地，熵\(H(D)\)和条件熵\(H(D\vert A)\)之差称为互信息(mutual information)，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
决策树学习应用信息增益准则选择特征。给定训练集D和特征A，经验熵\(H(D)\)表示对数据集D进行分类的不确定性。而经验条件熵\(H(D\vert A)\)表示在特征A给定的条件下对数据集D进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。显然，对数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
设训练数据集为D，|D|表示其样本容量，即样本个数。设有K个类Ck，k=1,2,…,K，|Ck|为属于类Ck的样本个数，\(\sum_{k=1}^K \vert C_k \vert =\vert D \vert\)，设特征A有n个不同的取值\(\{a_1,a_2,...,a_n\}\)，根据特征A的取值将D划分为n个子集\(D_1,D_2,...,D_n\)，\(\vert D_i \vert\)为\(D_i\)的样本个数，\(\sum_{i=1}^n\vert D_i\vert =\vert D\vert\)。记子集\(D_i\)中属于类\(C_k\)的样本的集合为\(D_{ik}\)，即\(D_{ik}=D_i\bigcap C_k\)，\(\vert D_{ik} \vert\)为\(D_{ik}\)的样本个数。于是信息增益的算法如下：
信息增益的算法：
- 输入：训练数据集D和特征A；
- 输出：特征A对训练数据集D的信息增益g(D,A)。
- 计算数据集D的经验熵H(D)
$$ H(D)=-\sum_{k=1}^K \frac{\vert C_k\vert}{\vert D\vert}\log_2 \frac{\vert C_k\vert}{\vert D\vert} $$ - 计算特征A对数据集D的经验条件熵H(D|A)
$$ H(D\vert A)=\sum_{i=1}^n \frac{\vert D_i\vert}{\vert D\vert}H(D_i)=-\sum_{i=1}^n \frac{\vert D_i\vert}{\vert D\vert} \sum_{k=1}^K \frac{\vert D_{ik}\vert}{\vert D_i\vert} \log_2 \frac{\vert D_{ik}\vert}{\vert D_i\vert} $$ - 计算信息增益
$$ g(D,A)=H(D)-H(D\vert A) $$
例1 根据表格给的数据，利用信息增益准则选择最优特征。
解：首先计算经验熵H(D)。 $$H(D)=-\frac{9}{15}\log_2 \frac{9}{15}-\frac{6}{15}\log_2 \frac{6}{15}=0.971$$ 然后计算各特征对数据集D的信息增益。分别以\(A_1,A_2,A_3,A_4\)表示年龄、有工作、有自己的房子和信贷情况4个特征，则
- \(D_1,D_2,D_3\)指的\(A_1\)（年龄）取值为青年、中年和老年的样本子集。
$$ \begin{align} g(D\vert A_1) & = H(D)-[\frac{5}{15}H(D_1)+\frac{5}{15}H(D_2)+\frac{5}{15}H(D_3)] \\
& = 0.971-[\frac{5}{15}(-\frac{2}{5}\log_2 \frac{2}{5}-\frac{3}{5}\log_2 \frac{3}{5}) \\
& +\frac{5}{15}(-\frac{3}{5}\log_2 \frac{3}{5}-\frac{2}{5}\log_2 \frac{2}{5}) \\
& +\frac{5}{15}(-\frac{4}{5}\log_2 \frac{4}{5}–\frac{1}{5}\log_2 \frac{1}{5}] \\
& = 0.971-0.888 \\
& = 0.083 \end{align} $$ - \(D_1,D_2\)对应有无工作的样本子集。
$$ \begin{align} g(D,A_2) & = H(D)-[\frac{5}{15}H(D_1)+\frac{10}{15}H(D_2)] \\
& = 0.971-[\frac{5}{15}\times 0+\frac{10}{15}(-\frac{4}{10}\log_2 \frac{4}{10}-\frac{6}{10}\log_2 \frac{6}{10})] \\
& = 0.324 \end{align} $$ - 同理可得
$$ \begin{align} g(D,A_3) & = 0.971-[\frac{6}{15}\times 0+\frac{9}{15}(-\frac{3}{9}\log_2 \frac{3}{9}-\frac{6}{9}\log_2 \frac{6}{9})] \\
& = 0.420 \end{align} $$ - 同理可得
$$ \begin{align} g(D,A_4) & = 0.971-0.608 \\
& = 0.363 \end{align} $$
最后比较各特征的信息增益值，由于特征\(A_3\)（有自己的房子）的信息增益值最大，所以选择特征\(A_3\)作为最优特征。
信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比(information gain ratio)可以对这一问题进行校正，这是特征选择的另一准则。
定义(信息增益比) 特征A对训练数据集的信息增益比\(g_R(D,A)\)定义为其信息增益\(g(D,A)\)与训练数据集D关于特征A的值的熵\(H_A(D)\)之比，即：
其中
\[H_A(D)=-\sum_{i=1}^{n}{\frac{\vert D_i\vert}{\vert D\vert}\log_2 \frac{\vert D_i\vert}{\vert D\vert}}\]n是特征A取值的个数。
决策树的生成
ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。
具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法。构建决策树；直到所有的特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
ID3算法
- 输入：训练数据集D，特征值A，阈值\(\epsilon\)；
- 输出：决策树T。
- 若D中所有实例属于同一类\(C_k\)，则T为单结点树，并将类\(C_k\)作为该结点的类标记，返回T；
- 若\(A=\varnothing\)，则T为单结点树，并将D中实例数最大的类\(C_k\)作为该节点的类标记，返回T；
- 否则，按照算法计算A中各特征对D的信息增益，选择信息增益最大的特征\(A_g\)；
- 如果\(A_g\)的信息增益小于阈值\(\epsilon\)，则置T为单结点树，并将D中实例数最大的类\(C_k\)作为该结点的类标记，返回T；
- 否则，对\(A_g\)的每一可能值\(a_i\)，依\(A_g=a_i\)将D分割为若干非空子集\(D_i\)，将\(D_i\)中实例数最大的类作为标记，构建子结点构成树T，返回T；
- 对第i个子结点，以\(D_i\)为训练集，以\(A-\{A_g\}\)为特征集，递归地调用步（1）~步（5），得到子树\(T_i\)，返回\(T_i\)。
例2 对上表中的训练数据集，利用ID3算法建立决策树。
解：利用例1结果，特征\(A_3\)（有自己的房子）的信息增益值最大，所以选择特征\(A_3\)作为根结点的特征。它将训练数据集D分为两个子集\(D_1\)(\(A_3\)取值为“是”)和\(D_2\)(\(A_3\)取值为“否”)。由于\(D_1\)只有同一类的样本点所以它成为一个叶结点，结点的类标记为“是”。
对\(D_2\)则需从特征\(A_1\)（年龄），\(A_2\)（有工作）和\(A_4\)（信贷情况）中选择新的特征，计算各个特征的信息增益：
$$
\begin{align}
g(D_2,A_1)&=H(D_2)-H(D_2\vert A_1)=0.918-0.667=0.251 \\
g(D_2,A_2)&=H(D_2)-H(D_2\vert A_2)=0.918 \\
g(D_2,A_4)&=H(D_2)-H(D_2\vert A_4)=0.474
\end{align}
$$
选择信息增益最大的特征\(A_2\)（有工作）作为结点的特征。由于\(A_2\)有两个可能取值，从这一结点引出两个子结点：一个对应“是”（有工作）的子结点，包含3个样本，它们属于同一类，所以这是一个叶结点，类标记为“是”；另一个对应“否”（无工作）的子结点，包含6个样本，它们也属于同一类，所以这也是一个叶结点，类标记为“否”。
生成的决策树如下图，只使用了两个特征（有两个内部结点）：
ID3算法只有树的生成，所以该算法生成的树容易过拟合。
C4.5的生成算法
C4.5算法ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。
C4.5算法
- 输入：训练数据集D，特征值A，阈值\(\epsilon\)；
- 输出：决策树T。
- 若D中所有实例属于同一类\(C_k\)，则T为单结点树，并将类\(C_k\)作为该结点的类标记，返回T；
- 若\(A=\varnothing\)，则T为单结点树，并将D中实例数最大的类\(C_k\)作为该节点的类标记，返回T；
- 否则，按照算法计算A中各特征对D的信息增益比，选择信息增益比最大的特征\(A_g\)；
- 如果\(A_g\)的信息增益比小于阈值\(\epsilon\)，则置T为单结点树，并将D中实例数最大的类\(C_k\)作为该结点的类标记，返回T；
- 否则，对\(A_g\)的每一可能值\(a_i\)，依\(A_g=a_i\)将D分割为若干非空子集\(D_i\)，将\(D_i\)中实例数最大的类作为标记，构建子结点构成树T，返回T；
- 对第i个子结点，以\(D_i\)为训练集，以\(A-\{A_g\}\)为特征集，递归地调用步（1）~步（5），得到子树\(T_i\)，返回\(T_i\)。
决策树的剪枝
决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据分类却没有那么准确，即出现过拟合现象。过拟合的原因是学习时过多考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。
在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。具体地，剪枝从已生成的树上剪掉一些子树或叶结点，并将其根节点或父结点作为新的叶结点，从而简化分类树模型。
本节介绍一种简单的决策树学习的剪枝算法。
决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有\(N_t\)个样本点，其中k类的样本点有\(N_{tk}\)个，k=1,2,…,K。\(H_t(T)\)为叶结点t上的经验熵，\(\alpha \geq 0\)为参数，则决策树学习的损失函数可以定义为：
其中经验熵为：
\[H_t(T)=-\sum_k{\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}}\]在损失函数定义中，右端的第一项记作：
$$
\begin{align}
C(T)&=\sum_{t=1}^{\vert T\vert}{N_tH_t(T)} \\
&=-\sum_{t=1}^{\vert T\vert}{\sum_{k=1}^{K}{N_{tk}\log \frac{N_{tk}}{N_t}}}
\end{align}
$$
这时有：
\[C_{\alpha}(T)=C(T)+\alpha\vert T\vert\]上式中，C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数\(\alpha \geq 0\)控制两者之间的影响。较大的\(\alpha\)促使使用较简单的模型（树），较小的\(\alpha\)促使选择较复杂的模型（树）。\(\alpha=0\)意味着只考虑模型和训练数据的拟合程度，不考虑模型的复杂度。
剪枝，就是\(\alpha\)确定时，选择损失函数最小的模型，即损失函数最小的子树。当\(\alpha\)值确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。
可以看出，决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减少模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。
损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。下面介绍剪枝算法。
下图是剪枝过程示意图：
- 输入：生成算法产生的整个树T，参数\(\alpha\)；
- 输出：修剪后的子树\(T_{\alpha}\)。
- 计算每个结点的经验熵。
- 递归地从树的叶结点向上回缩
设一组叶结点回缩到其父结点之前与之后的整体树分别为\(T_B与T_A\)其对应的损失函数值分别是\(C_{\alpha}(T_B)与C_{\alpha}(T_A)\)，如果
$$C_{\alpha}(T_A)\leq C_{\alpha}(T_B) \text {，式1}$$
则进行剪枝，即将父结点变为新的叶结点。 - 返回步骤2，直至不能继续为止，得到损失函数最小的子树\(T_{\alpha}\)
注意，式1只需考虑两个树的损失函数的差，其计算可以在局部进行。所以，决策树的剪枝算法可以由一种动态规划的算法实现。
CART算法
分类与回归树(classification and regression tree,CART)模型由Breiman等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类和回归的树统称为决策树。
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART算法由以下两步组成：
- 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
- 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
CART生成
决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
回归树的生成
假设X与Y是分别为输入和输出变量，并且Y是连续变量，给定训练数据集
\[D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}\]考虑如何生成回归树。
一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元\(R_1,R_2,...,R_M\)，并且在每个单元\(R_m\)上有一个固定的输出值\(c_m\)，于是回归树模型可表示为
当输入空间的划分确定时，可以用平方误差\(\sum_{x_i\in R_m}{(y_i-f(x_i))^2}\)来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元\(R_m\)上的\(c_m\)的最优值\(\hat c_m\)是\(R_m\)上的所有实例\(x_i\)对应的输出\(y_i\)的均值，即
\[\hat c_m=ave(y_i\vert x_i\in R_m)\]问题是怎么对输入空间进行划分，这里采用启发式的方法，选择第j个变量\(x^{(j)}\)和它取的值s，作为切分变量(splitting variable)和切分点(splitting point)，并定义两个区域：
\[R_1(j,s)=\{x\vert x^{(j)}\leq s\} 和 R_2(j,s)=\{x\vert x^{(j)}>s\}\]然后寻找最优切分变量j最优切分点s，具体地，求解
\[\min_{j,s}{[\min_{c_1}\sum_{x_i\in R_1(j,s)}{(y_i-c_1)^2}+\min_{c_2}\sum_{x_i\in R_2(j,s)}{(y_i-c_2)^2}]}\]对固定输入变量j可以找到最优切分点s。
\[\hat c_1=ave(y_i\vert x_i\in R_1(j,s))和\hat c_2=ave(y_i\vert x_i\in R_2(j,s))\]遍历所有输入变量，找到最优的切分变量j，构成一个对(j,s)，依此将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一颗回归树。这样的回归树通常称为最小二乘回归树(least squares regression tree)，现将算法叙述如下：
最小二乘回归树生成算法
- 输入：训练数据集D；
- 输出：回归树f(x)
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
- 选择最优切分变量j和切分点s，求解
$$\min_{j,s}{[\min_{c_1}\sum_{x_i\in R_1(j,s)}{(y_i-c_1)^2}+\min_{c_2}\sum_{x_i\in R_2(j,s)}{(y_i-c_2)^2}]} \text {$\quad$式2}$$
遍历变量j，对固定的切分变量j扫描切分点s，选择使式2达到最小值的对(j,s)。 - 用选定的对(j,s)划分区域，并决定相应的输出值：
$$R_1(j,s)=\{x\vert x^{(j)}\leq s\},\quad R_2(j,s)=\{x\vert x^{(j)}>s\}$$ $$\hat c_m=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}{y_i},\quad x_i\in R_m,\quad m=1,2$$ - 继续对两个子区域调用步骤1,2，直至满足停止条件。
- 将输入空间划分为M个区域\(R_1,R_2,...,R_M\)，生成决策树： $$f(x)=\sum_{m=1}^M{\hat c_mI(x\in R_m)}$$
分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
定义 （基尼指数） 分类问题中，假设有K个类，样本点属于第k类的概率为\(p_k\)，则概率分布的基尼指数定义为：
$$Gini(p)=\sum_{k=1}^{K}{p_k(1-p_k)}=1-\sum_{k=1}^{K}{p_k^2}$$
对于二分类问题，若样本点属于第一个类的概率是p，则概率分布的基尼指数为
$$Gini(p)=2p(1-p)$$
对于给定的样本集合D，其基尼指数为
$$Gini(D)=1-\sum_{k=1}^K{\left( \frac{\vert C_k\vert}{\vert D\vert}\right) ^2}$$
这里，\(C_k\)是D中属于第k类的样本子集，K是类的个数。
如果样本集合D根据特征A是否取某一可能值a被分割成\(D_1\)和\(D_2\)两部分，即
$$D_1={(x,y)\in D\vert A(x)=a},\quad D_2=D-D_1$$
则在特征A的条件下，集合D的基尼指数定义为
$$Gini(D,A)=\frac{\vert D_1\vert}{\vert D\vert}Gini(D_1)+\frac{\vert D_2\vert}{\vert D\vert}Gini(D_2)$$
基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。
下图是二类分类问题中基尼指数Gini(p)、熵（单位比特）之半\(\frac{1}{2}H(p)\)和分类误差率的关系。横坐标表示概率p，纵坐标表示损失。可以看出基尼指数和熵之半的曲线很接近，都可以近似的代替分类误差率。
CART生成算法
- 输入：训练数据集D，停止计算的条件；
- 输出：CART决策树
根据训练数据集，从根结点开始，递归地对每个结点进行一下操作，构建二叉决策树：
- 设结点的训练数据集维D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割为\(D_1\)和\(D_2\)两部分，利用基尼指数公式计算A=a时的基尼指数。
- 在所有可能的特征A以及他们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
- 对两个子结点递归地调用1,2，直至满足停止条件。
- 生成CART决策树。
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。
例3 根据表格数据，应用CART算法生成决策树
解：首先计算各特征的基尼指数，选择最优特征以及其最优切分点。仍采用例1的记号，分别以\(A_1,A_2,A_3,A_4\)表示年龄、有工作、有自己的房子和信贷情况4个特征，并以1,2,3表示年龄的值为青年、中年和老年，以1,2表示有工作和有自己的房子的值为是和否，以1,2,3表示信贷情况的值为非常好、好和一般。
求特征\(A_1\)的基尼指数
$$
\begin{align}
Gini(D,A_1=1)&=\frac{5}{15}\left(2\times \frac{2}{5}\times \left(1-\frac{2}{5}\right) \right)=0.44 \\
Gini(D,A_1=2)&=0.48 \\
Gini(D,A_1=3)&=0.44
\end{align}
$$
由于\(Gini(D,A_1=1)\)和\(Gini(D,A_1=3)\)相等，且最小，所以\(A_1=1\)和\(A_1=3\)都可以选作特征\(A_1\)的最优切分点。
求特征\(A_2\)和\(A_3\)的基尼指数：
$$
\begin{align}
Gini(D,A_2=1)&=0.32 \\
Gini(D,A_3=1)&=0.27
\end{align}
$$
由于\(A_2\)和\(A_3\)只有一个切分点，所以它们就是最优切分点。
求特征\(A_4\)的基尼指数：
$$
\begin{align}
Gini(D,A_4=1)&=0.36 \\
Gini(D,A_4=2)&=0.47 \\
Gini(D,A_4=3)&=0.32
\end{align}
$$
\(Gini(D,A_4=3)\)最小，所以\(A_4=3\)为\(A_4\)的最优切分点。
在\(A_1,A_2,A_3,A_4\)几个特征中，\(Gini(D,A_3=1)=0.27\)最小，所以选择特征\(A_3=1\)为其最优切分点。于是根结点生成两个子结点，一个是叶结点。对另一个结点继续使用以上方法在\(A_1,A_2,A_4\)中选择最优特征及其最优切分点，结果是\(A_2=1\)。依此计算得知，所得结点都是叶结点。
对于本问题，按照CART算法所产生的决策树与按照ID3算法所生成的决策树完全一致。
CART剪枝
CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小（模型变简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成：首先从生成算法产生的决策树\(T_0\)底端开始不断剪枝，直到\(T_0\)的根结点，形成一个子树序列\(\{T_0,T_1,...,T_n\}\)；然后通过交叉验证法在独立的验证数据集上子树序列进行测试，从中选择最优子树。
剪枝，形成一个子树序列
在剪枝过程中，计算子树的损失函数：
$$C_{\alpha}(T)=C(T)+\alpha \vert T\vert$$
其中T为任意子树，C(T)为对训练数据的预测误差（如基尼指数），|T|为子树的叶结点个数，\(\alpha \geq 0\)为参数，\(C_{\alpha}(T)\)为参数是\(\alpha\)时的子树T的整体损失。参数\(\alpha\)权衡训练数据的拟合度与模型的复杂度。
对固定的\(\alpha\)一定存在是损失函数\(C_{\alpha}(T)\)最小的子树，将其表示为\(T_\alpha\)，\(T_\alpha\)在损失函数\(C_{\alpha}(T)\)最小的意义下是最优的。容易验证这样的最优子树是唯一的。当\(\alpha\)大的时候，最优子树\(T_\alpha\)偏小，当\(\alpha\)小的时候，最优子树\(T_\alpha\)偏大。极端情况\(\alpha =0\)时，整体树是最优的，当\(\alpha \rightarrow \infty\)，根结点组成的单结点树是最优的。
Breiman等人证明：可以用递归的方法对树进行剪枝。将\(\alpha\)从小增大，\(0=\alpha_0<\alpha_1<\cdots\cdots\cdots<\alpha_n<+\infty\)，产生的一系列区间\([\alpha_i,\alpha_{i+1}),i=0,1,...,n\)；剪枝得到的子树序列对应着区间\(\alpha \in [\alpha_i,\alpha_{i+1}),i=0,1,...,n\)的最优子树序列\(\{T_0,T_1,...,T_n\}\)，序列中的子树是嵌套的。
具体地，从整体树\(T_0\)开始剪枝，对\(T_0\)的任意内部结点t，以t为单结点树的损失函数是
$$C_{\alpha}(T)=C(T)+\alpha$$
以t为根结点的子树\(T_t\)的损失函数是
$$C_{\alpha}(T_t)=C(T_t)+\alpha \vert T_t\vert$$
当\(\alpha=0\)及\(\alpha\)充分小时，有不等式
$$C_\alpha (T_t)<C_\alpha (t)$$
当\(\alpha\)增大时，在某一\(\alpha\)有
$$C_\alpha (T_t)=C_\alpha (t)$$
当\(\alpha\)再增大时，不等式反向。只要\(\alpha=\frac{C(t)-C(T_t)}{\vert T_t\vert -1}\)，\(T_t\)与t有相同的损失函数值，而t的结点少，因此t比\(T_t\)更可取，对\(T_t\)进行剪枝。
为此，对\(T_0\)的每一内部结点t，计算
$$g(t)=\frac{C(t)-C(T_t)}{\vert T_t\vert -1}$$
它表示剪枝后整体损失函数减少的程度。在\(T_0\)中减去g(t)最小的\(T_t\)，将得到的子树作为\(T_1\)，同时将最小的g(t)设为\(\alpha_1\)。\(T_1\)为区间\([\alpha_1,\alpha_2)\)的最优子树。
如此剪枝下去，直至得到根结点。在这一过程中，不断地增加\(\alpha\)的值，产生新的区间。
在剪枝得到的子树序列\(T_0,T_1,...,T_n\)中通过交叉验证选取最优子树\(T_\alpha\)
具体地，利用独立的验证数据集，测试子树序列\(T_0,T_1,...,T_n\)中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树\(T_0,T_1,...,T_n\)都对应于一个参数\(\alpha_1,\alpha_2,...,\alpha_n\)。所以，当最优子树\(T_k\)确定时，对应的\(\alpha_k\)也确定了，即得到最优决策树\(T_\alpha\)。
现在写出CART剪枝算法
CART剪枝算法
- 输入：CART算法生成的决策树\(T_0\)；
- 输出：最优决策树\(T_\alpha\)。
- 设\(k=0,\quad T=T_0\)。
- 设\(\alpha=+\infty\)。
- 自下而上的对各内部结点t计算\(C(T_t)\)，\(\vert T_t\vert\)以及
$$g(t)=\frac{C(t)-C(T_t)}{\vert T_t\vert -1}$$
$$\alpha=\min{(\alpha,g(t))}$$
这里，\(T_i\)表示以t为根结点的子树，\(C(T_i)\)是对训练数据的预测误差，\(\vert T_i\vert\)是\(T_i\)的叶结点个数。 - 对\(g(t)=\alpha\)的内部结点t进行剪枝，并对叶结点t以多数表决发决定其类，得到树T。
- 设\(k-k+1,\alpha_k=\alpha,T_k=T\)。
- 如果\(T_k\)不是由根结点及两个叶结点构成的树，则回到步骤2；否则，令\(T_k=T_n\)。
- 采用交叉验证法在子树序列\(T_0,T_1,...,T_n\)中选取最优子树\(T_\alpha\)。
本文概要
参考李航的《统计学习方法》
Leave a comment