决策树（Decision Tree）是一类常见的机器学习方法。以二分类任务为例，从给定训练数据集学得一个模型用以对新示例进行分类，这个样本分类任务可视为对问题“当前样本是否属于正类？”的“决策”或“判定”过程。顾名思义，决策树基于树结构来进行决策，这恰是人类在面临决策问题时一种很自然的处理机制。

1 决策树基本流程

在如下图例的西瓜挑选决策树中，决策过程的每一次判定都是对某一属性的“测试”，决策最终结论则对应最终的判定结果。一般一颗决策树包含一个根结点、若干个内部结点和若干个叶结点，易知：

• 每个非叶结点表示一个特征属性测试
• 每个分支代表这个特征属性在某个值域上的输出
• 每个叶结点存放一个类别
• 每个结点包含的样本集合通过属性测试被划分到子结点中，根结点包含样本全集

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。算法的基本流程遵循简单且直观的分而治之（Divide-and-Conquer）策略，如下所示——

• 输入：训练集D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\dots,(\mathbf{x}_m,y_m)\}；属性集A=\{a_1,a_2,\dots,a_d\}
• 过程：函数\text{TreeGenerate}(D,A)
  • 生成结点\text{node}
  • if D中样本全属于同一类别C then
    • 将\text{node}标记为C类叶结点；return （终止条件1：最佳情形）
  • end if
  • if A=\empty OR D中样本在A上取值相同 then
    • 将\text{node}标记为叶结点，其类别标记为D中样本数最多的类；return （终止条件2：属性用完或无法划分，使用后验分布）
  • end if
  • 从A中选择最优划分属性a_*
  • for a_*的每个值a_*^v do （若为连续值属性，则只有“≤”和“>”两个分支）
    • 为\text{node}生成一个分支；令D_v表示D中在a_*上取值为a_*^v的样本子集
    • if D_v为空 then
      • 将分支结点标记为叶结点，其类别标记为D中样本最多的类；return （终止条件3：分支为空，使用先验分布）
    • else
      • 以\text{TreeGenerate}(D_v,A\setminus \{a_*\})为分支结点 （若为连续属性，则无需去除）
    • end if
  • end for
• 输出：以\text{node}为根结点的一棵决策树

特别地，单层决策树被称为决策树桩。显然，决策树的构造是一个递归的过程，有三种情形会导致递归返回：

1. 当前结点包含的样本全属于同一类别，此时直接将该结点标记为叶结点，并设为相应的类别
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，此时将该结点标记为叶结点，并将其类别设为该结点所含样本最多的类别
3. 当前结点包含的样本集合为空，不能划分，此时也将该结点标记为叶结点，并将其类别设为父结点中所含样本最多的类别。

---

2 划分选择

由算法基本流程可看出，决策树学习的关键是第8行，即如何选择最优划分属性。随着划分过程不断进行，一般希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度（Purity）越来越高。

2.1 ID3算法

信息熵（Information Entropy）是度量样本结合纯度的常用指标，假定当前样本集合D中第k类样本所占比例为p_k\ (k=1,2,\dots,\left | \mathcal{Y} \right |)，则D的信息熵定义为

\begin{aligned}
\text{Ent}(D)=-\sum\limits_{k=1}^{\left | \mathcal{Y} \right |} p_k\log_2 p_k
\end{aligned}

计算信息熵时约定，若p=0，则p\log_2 p=0。\text{Ent}(D)的最小值为0，最大值为\log_2 \left | \mathcal{Y} \right |。信息熵值越小，则样本集合D的纯度越高。

假定离散属性a有V个可能的取值，即候选属性集合A=\{a^1,a^2,\dots,a^V\}，若使用a来划分样本集D，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为a^v的样本，记为D^v，可根据前式计算出其信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重\dfrac{|D^v|}{|D|}，即包含样本数越多的分支结点的影响力越大。故可计算出用a划分后相比原始数据集D获得的信息增益（Information Gain），定义为

\begin{aligned}
\text{Gain}(D,a)=\text{Ent}(D)-\sum\limits_{v=1}^V \frac{|D^v|}{|D|}\text{Ent}(D^v)
\end{aligned}

信息增益越大，表示使用该属性划分样本集D的效果越好，因此ID3算法（ID：Iterative Dichotomiser，迭代二分器）在递归过程中，每次选择最大信息增益的属性a^*=\underset{a\in A}{\arg \max}\ \text{Gain}(D,a)作为当前的划分属性。

2.2 C4.5算法

ID3算法存在一个问题：偏向于取值数目较多的属性，例如若存在1个唯一标识，则样本集D将会被划分为|D|个分支，每个分支只有1个样本，导致划分后的信息熵为零，尽管十分纯净，但是对分类毫无用处。故C4.5算法使用增益率（Gain Ratio）来选择划分属性，避免该问题带来的困扰：首先使用ID3算法计算出信息增益高于平均水平的候选属性，接着C4.5计算这些候选属性的增益率。增益率定义为

\begin{aligned}
\text{Gain\_ratio}(D,a)=\frac{\text{Gain}(D,a)}{\text{IV}(a)}
\end{aligned}

其中

\begin{aligned}
\text{IV}(a)=-\sum\limits_{v=1}^V\frac{|D^v|}{|D|}\log_2 \frac{|D^v|}{|D|}
\end{aligned}

称为属性a的固有值（Intrinsic Value）。属性a的可能取值数量V越大，则\text{IV}(a)通常会越大。综上，C4.5算法每次选择最大增益率的属性a^*=\underset{a\in A}{\arg \max}\ \text{Gain\_ratio}(D,a)作为当前的划分属性。

2.3 CART算法

CART决策树使用基尼指数（Gini Index）来选择划分属性。基尼指数\text{Gini}(D)表示从数据集D中随机抽取两个样本，其类别标记不一致的概率（即不确定性），定义如下：

\begin{aligned}
\text{Gini}(D) &= \sum\limits_{k=1}^{\left | \mathcal{Y} \right |}\sum\limits_{k'\ne k}p_{k}p_{k'}\\
 &= 1-\sum\limits_{k=1}^{\left | \mathcal{Y} \right |}p_k^2
\end{aligned}

可见，\text{Gini}(D)越小，数据集D的纯度越高。属性a的基尼指数\text{Gini\_index}(D,a)表示经过划分后数据集的不确定性，定义如下：

\begin{aligned}
\text{Gini\_index}(D,a)=\sum\limits_{v=1}^V \frac{|D^v|}{|D|} \text{Gini}(D^v)
\end{aligned}

故在候选属性集合A中，选择使得划分后基尼指数最小的属性a^*=\underset{a\in A}{\arg \min}\ \text{Gini\_index}(D,a)作为最优划分属性。

---

3 剪枝

在决策树的学习中，容易遇到过拟合问题：为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，此时就可能因训练样本学得“太好”了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。剪枝（Pruning）是决策树算法对付过拟合的主要手段，有以下两种策略：

• 预剪枝（Prepruning）：在构造的过程中先评估，再考虑是否分支。
• 后剪枝（Postpruning）：在构造好一颗完整的决策树后，自底向上，评估分支的必要性。

其中评估指的是性能度量，即决策树的泛化性能。本节假定采用留出法，并从训练集中预留一部分数据作为验证集，使用验证集作为学习器泛化性能的近似。

【例】首先根据下表给出一棵未剪枝过的决策树：

预剪枝在构造树的过程中，对一个结点考虑是否分支时，首先计算决策树不分支时在验证集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。采用预剪枝的决策树如下所示

后剪枝则在构造好一颗完整的决策树后，从最下方的结点开始，考虑该结点分支对模型的性能是否有提升，若无则剪枝，即将该结点标记为叶结点，类别标记为其包含样本最多的类别。采用后剪枝的决策树如下所示

预剪枝处理使得决策树的很多分支被剪去，因此大大降低了训练时间开销，同时降低了过拟合的风险，但另一方面由于剪枝同时剪去了当前结点后续子结点的分支，因此预剪枝“贪心”的本质阻止了分支的展开，在一定程度上带来了欠拟合的风险；而后剪枝则通常保留了更多的分支，因此采用后剪枝策略的决策树性能往往优于预剪枝，但其自底向上遍历所有结点并计算性能，训练时间开销相比预剪枝大大提升。

---

4 连续值处理

上一节中的决策树均基于离散值生成，但现实中常会遇到连续值的属性。对于连续属性，若每个取值作为一个分支则显然不可行，因此需进行离散化处理，常用的方法为二分法（Bi-partition），即C4.5算法中采用的机制。基本思想：给定样本集D与连续属性a，将a在D上的n个不同的取值从小到大进行排序，记为\{a^1,a^2,\dots,a^n\}；二分法试图找到一个划分点t将D分为子集D_t^-,D_t^+，其分别表示那些在属性a上取值不大于t与大于t的样本；显然，对相邻的属性取值a^i,a^{i+1}而言，t在区间\left [ a^i, a^{i+1} \right )中取任意值所产生的划分结果相同。因此，对于连续属性a，可考察将区间\left [ a^i, a^{i+1} \right )的中位点\dfrac{a^i+a^{i+1}}{2}作为候选划分点、包含n-1个元素的候选划分点集合，即

\begin{aligned}
T_a=\left \{ \dfrac{a^i+a^{i+1}}{2}  \mid 1 \le i \le n-1  \right \} 
\end{aligned}

之后即可像离散属性值一样考察这些划分点，选取最优的划分点进行样本集合的划分。例如推广到连续属性的信息增益计算式为

\begin{aligned}
\text{Gain}(D,a) &=\max\limits_{t\in T_a} \text{Gain}(D,a,t)\\
 &= \max\limits_{t\in T_a} \text{Ent}(D)-\sum\limits_{\lambda\in \{-,+\}} \frac{|D^\lambda_t|}{|D|}\text{Ent}(D_t^\lambda)
\end{aligned}

其中\text{Gain}(D,a,t)是样本集D基于划分点t二分后的信息增益。因此，可选择使得最大信息增益的划分点t^*=\underset{t\in T_a}{\arg\max}\ \text{Gain}(D,a,t)作为最优划分点。

---

5 缺失值处理

现实中常会遇到不完整的样本，即属性存在缺失值。有时若简单地进行剔除，则会造成大量的信息浪费，因此在属性值缺失的情况下需解决两个问题：

1. 如何选择划分属性？
2. 给定划分属性，若某样本在该属性上缺失值，则如何将其划分到具体的分支上？

令\tilde{D}表示训练集D中在属性a上没有缺失值的样本子集，对于问题1，显然可仅根据\tilde{D}来判断属性a的优劣：假定属性a有V个可取值\{a^1,a^2,\dots,a^V\}，令\tilde D^v表示\tilde{D}中在属性a上取值为a^v的样本子集，\tilde D_v表示\tilde{D}中属于第k类（k=1,2,\dots,\left | \mathcal{Y} \right |）的样本子集，显然，\tilde D=\bigcup\limits_{k=1}^{\left | \mathcal{Y} \right |} \tilde D_k=\bigcup\limits_{v=1}^{V} \tilde D^v；假定为每个样本\mathbf{x}赋予一个权重w_{\mathbf{x}}（在决策树学习开始阶段，根结点中各样本的权重初始化为1），并定义

\begin{aligned}
\rho &= \frac{\sum_{\mathbf{x}\in \tilde D}w_{\mathbf{x}}}{\sum_{\mathbf{x}\in D}w_{\mathbf{x}}} \\
\tilde p_k &= \frac{\sum_{\mathbf{x}\in \tilde D_k}w_{\mathbf{x}}}{\sum_{\mathbf{x}\in \tilde D}w_{\mathbf{x}}}\ (1 \le k \le \left | \mathcal{Y} \right |) \\
\tilde r_v &= \frac{\sum_{\mathbf{x}\in \tilde D^v}w_{\mathbf{x}}}{\sum_{\mathbf{x}\in \tilde D}w_{\mathbf{x}}}\ (1 \le v \le V)
\end{aligned}

直观地看，对属性a，\rho表示无缺失值样本（样本子集）所占的比例，\tilde p_k表示无缺失值样本中第k类（样本子集每个类别）所占的比例，\tilde r_v表示无缺失值样本在属性a上取值a^v的样本（每个分支所含样本）所占的比例。显然，\sum\limits_{k=1}^{\left | \mathcal{Y} \right |} \tilde p_k=\sum\limits_{v=1}^{V} \tilde r_v=1。据此，可进一步将信息增益计算式推广为

\begin{aligned}
\text{Gain}(D,a) &= \rho \times \text{Gain}(\tilde D,a)\\
 &= \rho \left ( \text{Ent}(\tilde D) -\sum\limits_{v=1}^V \tilde r_v \text{Ent}(\tilde D^v) \right )
\end{aligned}

其中\tilde D的信息熵为

\begin{aligned}
\text{Ent}(\tilde D)=-\sum\limits_{k=1}^{\left | \mathcal{Y} \right |}\tilde p_k \log_2 \tilde p_k
\end{aligned}

对于问题2，若样本\mathbf{x}在划分属性a上的取值已知，则将\mathbf{x}划入与其取值对应的子结点，且样本权值在子结点中保持为w_{\mathbf{x}}；若\mathbf{x}在a上的取值未知，则将\mathbf{x}同时划入所有子结点，且样本权值在与属性值a^v对应的子结点中调整为

\begin{aligned}
w_{\mathbf{x}} \gets \tilde r_v\cdot w_{\mathbf{x}}
\end{aligned}

直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

---

6 多变量决策树

若把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。此前所述的决策树均属于单变量决策树（Univariate Decision Tree），其所形成的分类边界有一个明显的特点：轴平行（Axis-Parallel），即其分类边界由若干个与坐标轴平行的分段组成。这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值，但在学习任务的真实分类边界较为复杂时，必须使用很多段划分才能获得较好的近似，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

若能使用斜的划分边界，则决策树模型将大为简化。多变量决策树（Multivariate Decision Tree） 记为能实现这种“斜划分”甚至更复杂划分的决策树。以实现斜划分的多变量决策树为例，在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试；换言之，每个非叶结点是一个形如\sum\limits_{i=1}^d w_ia_i=t的线性分类器，其中w_i为属性a_i的权重，w_i,t可在该结点所含的样本集和属性集上学得。与传统的单变量决策树不同，在多变量决策树的学习过程中，并非为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

【例】可将如下图左所示的单变量决策树改造为如下图右所示的多变量决策树：