7f2396aa创建于 1月21日历史提交

Important

参与组队学习的同学须知：

本章学习时间：3天

本章配套视频教程：https://www.bilibili.com/video/BV1Mh411e7VU?p=7

本章配套代码：https://github.com/datawhalechina/machine-learning-toy-code/blob/main/西瓜书代码实战.md

本章配套代码视频教程：https://space.bilibili.com/431850986/lists/3884942

第4章决策树

本章的决策树算法背后没有复杂的数学推导，其更符合人类日常思维方式，理解起来也更为直观，其引入的数学工具也仅是为了让该算法在计算上可行，同时"西瓜书"在本章列举了大量例子，因此本章的算法会更为通俗易懂。

4.1 基本流程

作为本章的开篇，首先要明白决策树在做什么。正如"西瓜书"中图4.1所示的决策过程，决策树就是不断根据某属性进行划分的过程（每次决策时都是在上次决策结果的基础之上进行），即"if......elif......else......"的决策过程，最终得出一套有效的判断逻辑，便是学到的模型。但是，划分到什么时候就停止划分呢？这就是图4.2中的3个"return"代表的递归返回，下面解释图4.2中的3个递归返回。

首先，应该明白决策树的基本思想是根据某种原则（即图4.2第8行）每次选择一个属性作为划分依据，然后按属性的取值将数据集中的样本进行划分，例如将所有触感为"硬滑"的西瓜的分到一起，将所有触感为"软粘"的西瓜分到一起，划分完得到若干子集，接着再对各个子集按照以上流程重新选择某个属性继续递归划分，然而在划分的过程中通常会遇到以下几种特殊情况。

（1）若递归划分过程中某个子集中已经只含有某一类的样本（例如只含好瓜），那么此时划分的目的已经达到了，无需再进行递归划分，此即为递归返回的情形(1)，最极端的情况就是初始数据集中的样本全是某一类的样本，那么此时决策树算法到此终止，建议尝试其他算法；

（2）递归划分时每次选择一个属性作为划分依据，并且该属性通常不能重复使用（仅针对离散属性），原因是划分后产生的各个子集在该属性上的取值相同。例如本次根据触感对西瓜样本进行划分，那么后面对划分出的子集（及子集的子集......）再次进行递归划分时不能再使用"触感"，图4.2第14行的 $A\{a∗}A \backslash\{a_*\}$ 表示的便是从候选属性集合 $A$ 中将当前正在使用的属性 $a_*$ 排除。由于样本的属性个数是有限的，因此划分次数通常不超过属性个数。若所有属性均已被用作过划分依据，即 $A=∅A=\varnothing$ ，此时子集中仍含有不同类样本（例如仍然同时含有好瓜和坏瓜），但是因已无属性可用作划分依据，此时只能少数服从多数，以此子集中样本数最多的类为标记。由于无法继续划分的直接原因是各个子集中的样本在各个属性上的取值都相同，所以即使 $A≠∅A\neq\varnothing$ ，但是当子集中的样本在属性集合 $A$ 上取值都相同时，等价视为 $A=∅A=\varnothing$ ，此即为递归返回的情形(2)；

（3）根据某个属性进行划分时，若该属性多个属性值中的某个属性值不包含任何样本（例如未收集到），例如对当前子集以"纹理"属性来划分，"纹理"共有3种取值：清晰、稍糊、模糊，但发现当前子集中并无样本"纹理"属性取值为模糊，此时对于取值为清晰的子集和取值为稍糊的子集继续递归，而对于取值为模糊的分支，因为无样本落入，将其标记为叶结点，其类别标记为训练集 $D$ 中样本最多的类，即把全体样本的分布作为当前结点的先验分布。其实就是一种盲猜，既然是盲猜，那么合理的做法就是根据已有数据用频率近似概率的思想假设出现频率最高的便是概率最大的。注意，此分支必须保留，因为测试时，可能会有样本落入该分支。此即为递归返回的情形(3)。

4.2 划分选择

本节介绍的三种划分选择方法，即信息增益、增益率、基尼指数分别对应著名的ID3、C4.5和CART三种决策树算法。

4.2.1 式(4.1)的解释

该式为信息论中的信息熵定义式，以下先证明 $0⩽Ent⁡(D)⩽log⁡2∣Y∣0\leqslant\operatorname{Ent}(D)\leqslant\log_{2}|\mathcal{Y}|$ ，然后解释其最大值和最小值所表示的含义。

已知集合 $D$ 的信息熵的定义为

Ent⁡(D)=−∑k=1∣Y∣pklog⁡2pk\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log_{2} p_{k}

其中， $∣Y∣|\mathcal{Y}|$ 表示样本类别总数， $p_k$ 表示第 $k$ 类样本所占的比例，有 $0⩽pk⩽1,∑k=1npk=10\leqslant p_k \leqslant 1,\sum_{k=1}^{n}p_k=1$ 。若令 $∣Y∣=n,pk=xk|\mathcal{Y}|=n,p_k=x_k$ ，那么信息熵 $Ent⁡(D)\operatorname{Ent}(D)$ 就可以看作一个 $n$ 元实值函数，即

,xn)=−∑k=1nxklog⁡2xk\operatorname{Ent}(D)=f(x_1,\cdots,x_n)=-\sum_{k=1}^{n} x_{k} \log_{2} x_{k}

其中 $\leqslant x_k \leqslant 1,\sum_{k=1}^{n}x_k=1$ 。

下面考虑求该多元函数的最值. 首先我们先来求最大值，如果不考虑约束 $\leqslant x_k \leqslant 1$ 而仅考虑 $∑k=1nxk=1\sum_{k=1}^{n}x_k=1$ ，则对 $,xn)f(x_1,\cdots,x_n)$ 求最大值等价于如下最小化问题：

∑k=1nxk=1\begin{array}{ll}{ \operatorname{min}} & {\sum\limits_{k=1}^{n} x_{k} \log_{2} x_{k} }\\ {\text { {\rm s.t.} }} & {\sum\limits_{k=1}^{n}x_k=1} \end{array}

显然，在 $\leqslant x_k \leqslant 1$ 时，此问题为凸优化问题。对于凸优化问题来说，使其拉格朗日函数的一阶偏导数等于0的点即最优解。根据拉格朗日乘子法可知，该优化问题的拉格朗日函数为

,xn,λ)=∑k=1nxklog⁡2xk+λ(∑k=1nxk−1)L(x_1,\cdots,x_n,\lambda)=\sum_{k=1}^{n} x_{k} \log _{2} x_{k}+ \lambda\left(\sum_{k=1}^{n}x_k-1\right)

其中， $λ\lambda$ 为拉格朗日乘子。对 $,xn,λ)L(x_1,\cdots,x_n,\lambda)$ 分别关于 $,xn,λx_1,\cdots,x_n,\lambda$ 求一阶偏导数，并令偏导数等于0可得

,xn,λ)∂x1=∂∂x1[∑k=1nxklog⁡2xk+λ(∑k=1nxk−1)]=0=log⁡2x1+x1⋅1x1ln⁡2+λ=0=log⁡2x1+1ln⁡2+λ=0⇒λ=−log⁡2x1−1ln⁡2\begin{aligned} \dfrac{\partial L(x_1,\cdots,x_n,\lambda)}{\partial x_1}&=\dfrac{\partial }{\partial x_1} \left[\sum_{k=1}^{n} x_{k} \log _{2} x_{k}+\lambda \left(\sum_{k=1}^{n}x_k-1\right)\right]=0\\ &=\log _{2} x_{1}+x_1\cdot \dfrac{1}{x_1\ln2}+\lambda=0 \\ &=\log _{2} x_{1}+\dfrac{1}{\ln2}+\lambda=0 \\ &\Rightarrow \lambda=-\log _{2} x_{1}-\dfrac{1}{\ln2}\\ \end{aligned}

,xn,λ)∂λ=∂∂λ[∑k=1nxklog⁡2xk+λ(∑k=1nxk−1)]=0⇒∑k=1nxk=1\begin{aligned} \dfrac{\partial L(x_1,\cdots,x_n,\lambda)}{\partial x_2}&=\dfrac{\partial }{\partial x_2}\left[\sum_{k=1}^{n} x_{k} \log _{2} x_{k}+\lambda\left(\sum_{k=1}^{n}x_k-1\right)\right]=0\\ &\Rightarrow \lambda=-\log _{2} x_{2}-\dfrac{1}{\ln2}\\ \cdots\\ \dfrac{\partial L(x_1,\cdots,x_n,\lambda)}{\partial x_n}&=\dfrac{\partial }{\partial x_n}\left[\sum_{k=1}^{n} x_{k} \log _{2} x_{k}+\lambda\left(\sum_{k=1}^{n}x_k-1\right)\right]=0\\ &\Rightarrow \lambda=-\log _{2} x_{n}-\dfrac{1}{\ln2};\\ \dfrac{\partial L(x_1,\cdots,x_n,\lambda)}{\partial \lambda}&=\dfrac{\partial }{\partial \lambda}\left[\sum_{k=1}^{n} x_{k} \log _{2} x_{k}+\lambda\left(\sum_{k=1}^{n}x_k-1\right)\right]=0\\ &\Rightarrow \sum_{k=1}^{n}x_k=1\\ \end{aligned}

整理一下可得

{λ=−log⁡2x1−1ln⁡2=−log⁡2x2−1ln⁡2=⋯=−log⁡2xn−1ln⁡2∑k=1nxk=1\left\{ \begin{array}{lr} \lambda=-\log _{2} x_{1}-\frac{1}{\ln2}=-\log _{2} x_{2}-\frac{1}{\ln2}=\cdots=-\log _{2} x_{n}-\frac{1}{\ln2} \\ \sum\limits_{k=1}^{n}x_k=1 \end{array}\right.

由以上两个方程可以解得

x1=x2=⋯=xn=1nx_1=x_2=\cdots=x_n=\dfrac{1}{n}

又因为 $x_k$ 还需满足约束 $\leqslant x_k \leqslant 1$ ，显然 $0⩽1n⩽10\leqslant\frac{1}{n}\leqslant 1$ ，所以 $x1=x2=⋯=xn=1nx_1=x_2=\cdots=x_n=\frac{1}{n}$ 是满足所有约束的最优解，即当前最小化问题的最小值点，同时也是 $,xn)f(x_1,\cdots,x_n)$ 的最大值点。将 $x1=x2=⋯=xn=1nx_1=x_2=\cdots=x_n=\frac{1}{n}$ 代入 $,xn)f(x_1,\cdots,x_n)$ 中可得

,1n)=−∑k=1n1nlog⁡21n=−n⋅1nlog⁡21n=log⁡2nf\left(\dfrac{1}{n},\cdots,\dfrac{1}{n}\right) =-\sum_{k=1}^{n} \dfrac{1}{n} \log _{2} \dfrac{1}{n}=-n\cdot\dfrac{1}{n} \log _{2} \dfrac{1}{n}=\log _{2} n

所以 $,xn)f(x_1,\cdots,x_n)$ 在满足约束 $\leqslant x_k \leqslant 1,\sum_{k=1}^{n}x_k=1$ 时的最大值为 $log _{2} n$ 。

下面求最小值。如果不考虑约束 $∑k=1nxk=1\sum_{k=1}^{n}x_k=1$ 而仅考虑 $\leqslant x_k \leqslant 1$ ，则 $,xn)f(x_1,\cdots,x_n)$ 可以看作 $n$ 个互不相关的一元函数的和，即

,xn)=∑k=1ng(xk)f(x_1,\cdots,x_n)=\sum_{k=1}^{n} g(x_k)

其中， $g(xk)=−xklog⁡2xk,0⩽xk⩽1g(x_k)=-x_{k} \log _{2} x_{k},0 \leqslant x_k \leqslant 1$ 。那么当 $,g(xn)g(x_1),g(x_2),\cdots,g(x_n)$ 分别取到其最小值时， $,xn)f(x_1,\cdots,x_n)$ 也就取到了最小值，所以接下来考虑分别求 $,g(xn)g(x_1),g(x_2),\cdots,g(x_n)$ 各自的最小值。

由于 $,g(xn)g(x_1),g(x_2),\cdots,g(x_n)$ 的定义域和函数表达式均相同，所以只需求出 $g(x_1)$ 的最小值也就求出了 $,g(xn)g(x_2),\cdots,g(x_n)$ 的最小值。下面考虑求 $g(x_1)$ 的最小值，首先对 $g(x_1)$ 关于 $x_1$ 求一阶和二阶导数，有

g′(x1)=d(−x1log⁡2x1)dx1=−log⁡2x1−x1⋅1x1ln⁡2=−log⁡2x1−1ln⁡2g^{\prime}(x_1)=\dfrac{{\rm d}(-x_{1} \log _{2} x_{1})} {{\rm d} x_1}=-\log _{2} x_{1}-x_1\cdot \dfrac{1}{x_1\ln2}=-\log _{2} x_{1}-\dfrac{1}{\ln2}

g′′(x1)=d(g′(x1))dx1=d(−log⁡2x1−1ln⁡2)dx1=−1x1ln⁡2g^{\prime\prime}(x_1)=\dfrac{{\rm d}\left(g^{\prime}(x_1)\right)} {{\rm d} x_1}=\dfrac{{\rm d}\left(-\log _{2} x_{1}-\dfrac{1}{\ln2}\right)}{{\rm d} x_1}=-\dfrac{1}{x_{1}\ln2}

显然，当 $\leqslant x_k \leqslant 1$ 时 $g′′(x1)=−1x1ln⁡2g^{\prime\prime}(x_1)=-\frac{1}{x_{1}\ln2}$ 恒小于0，所以 $g(x_1)$ 是一个在其定义域范围内开口向下的凹函数，那么其最小值必然在边界取。分别取 $x_1=0$ 和 $x_1=1$ ，代入 $g(x_1)$ 可得

g(0)=-0\log _{2} 0=0

g(1)=-1\log _{2} 1=0

（计算信息熵时约定：若 $x = 0$ ，则 $x\log_2 x=0$ ） 所以， $g(x_1)$ 的最小值为0，同理可得 $,g(xn)g(x_2),\cdots,g(x_n)$ 的最小值也都为0，即 $,xn)f(x_1,\cdots, x_n)$ 的最小值为0。但是，此时仅考虑约束 $\leqslant x_k \leqslant 1$ ，而未考虑 $∑k=1nxk=1\sum_{k=1}^{n}x_k=1$ 。若考虑约束 $∑k=1nxk=1\sum_{k=1}^{n}x_k=1$ ，那么 $,xn)f(x_1,\cdots,x_n)$ 的最小值一定大于等于0。如果令某个 $x_k=1$ ，那么根据约束 $∑k=1nxk=1\sum_{k=1}^{n}x_k=1$ 可知 $x1=x2=⋯=xk−1=xk+1=⋯=xn=0x_1=x_2=\cdots=x_{k-1}=x_{k+1}=\cdots=x_n=0$ ，将其代入 $,xn)f(x_1,\cdots,x_n)$ 可得

,0)=−0log⁡20−0log⁡20−⋯−0log⁡20−1log⁡21−0log⁡20−⋯−0log⁡20=0\begin{aligned} &f(0,0,\cdots,0,1,0,\cdots,0)\\ =&-0 \log _{2}0-0 \log _{2}0-\cdots-0 \log _{2}0-1 \log _{2}1-0 \log _{2}0-\cdots-0 \log _{2}0=0 \end{aligned}

所以 $xk=1,x1=x2=⋯=xk−1=xk+1=⋯=xn=0x_k=1,x_1=x_2=\cdots=x_{k-1}=x_{k+1}=\cdots=x_n=0$ 一定是 $,xn)f(x_1,\cdots,x_n)$ 在满足约束 $∑k=1nxk=1\sum_{k=1}^{n}x_k=1$ 和 $0⩽xk⩽10\leqslant x_k \leqslant 1$ 的条件下的最小值点，此时 $f$ 取到最小值0。

综上可知，当 $,xn)f(x_1,\cdots,x_n)$ 取到最大值时： $x1=x2=⋯=xn=1nx_1=x_2=\cdots=x_n=\frac{1}{n}$ ，此时样本集合纯度最低；当 $,xn)f(x_1,\cdots,x_n)$ 取到最小值时： $xk=1,x1=x2=⋯=xk−1=xk+1=⋯=xn=0x_k=1,x_1=x_2=\cdots=x_{k-1}=x_{k+1}=\cdots=x_n=0$ ，此时样本集合纯度最高。

4.2.2 式(4.2)的解释

此为信息增益的定义式。在信息论中信息增益也称为"互信息"，表示已知一个随机变量的信息后另一个随机变量的不确定性减少的程度。

下面给出互信息的定义，在此之前，还需要先解释一下什么是"条件熵"。条件熵表示的是在已知一个随机变量的条件下，另一个随机变量的不确定性。具体地，假设有随机变量 $X$ 和 $Y$ ，且它们服从以下联合概率分布

x_{i},Y = y_{j}) = p_{ij},\quad i = 1,2,\cdots,n,\quad j = 1,2,\cdots,m

那么在已知 $X$ 的条件下，随机变量 $Y$ 的条件熵为

Ent⁡(Y∣X)=∑i=1npiEnt⁡(Y∣X=xi)\operatorname{Ent}(Y|X) = \sum_{i=1}^np_i \operatorname{Ent}(Y|X = x_i)

其中， $,np_i = P(X = x_i) ，i =1,2,\cdots,n$ 。互信息定义为信息熵和条件熵的差，它表示的是已知一个随机变量的信息后使得另一个随机变量的不确定性减少的程度。具体地，假设有随机变量 $X$ 和 $Y$ ，那么在已知 $X$ 的信息后， $Y$ 的不确定性减少的程度为

I⁡(Y;X)=Ent⁡(Y)−Ent⁡(Y∣X)\operatorname{I}(Y;X) = \operatorname{Ent}(Y) - \operatorname{Ent}(Y|X)

此即互信息的数学定义。

所以式(4.2)可以理解为，在已知属性 $a$ 的取值后，样本类别这个随机变量的不确定性减小的程度。若根据某个属性计算得到的信息增益越大，则说明在知道其取值后样本集的不确定性减小的程度越大，即"西瓜书"上所说的"纯度提升"越大。

4.2.3 式(4.4)的解释

为了理解该式的"固有值"的概念，可以将式(4.4)与式(4.1)对比理解。式(4.1)可重写为

Ent⁡(D)=−∑k=1∣Y∣pklog⁡2pk=−∑k=1∣Y∣∣Dk∣∣D∣log⁡2∣Dk∣∣D∣\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_k \log _2 p_k=-\sum_{k=1}^{|\mathcal{Y}|} \frac{\left|D^k\right|}{|D|} \log _2 \frac{\left|D^k\right|}{|D|}

其中 $∣Dk∣∣D∣=pk\frac{\left|D^k\right|}{|D|}=p_k$ ，为第 $k$ 类样本所占的比例。与式(4.4)的表达式作一下对比

IV⁡(a)=−∑v=1V∣Dv∣∣D∣log⁡2∣Dv∣∣D∣\operatorname{IV}(a)=-\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \log _2 \frac{\left|D^v\right|}{|D|}

其中 $∣Dv∣∣D∣=pv\frac{\left|D^v\right|}{|D|}=p_v$ ，为属性 $a$ 取值为 $a^v$ 的样本所占的比例。即式(4.1)是按样本的类别标记计算的信息熵，而式(4.4)是按样本属性的取值计算的信息熵。

4.2.4 式(4.5)的推导

假设数据集 $D$ 中的样例标记种类共有三类，每类样本所占比例分别为 $p_1$ 、 $p_2$ 、 $p_3$ 。现从数据集中随机抽取两个样本，两个样本类别标记正好一致的概率为

p1p1+p2p2+p3p3=∑k=1∣Y∣=3pk2p_1 p_1+p_2 p_2+p_3 p_3=\sum_{k=1}^{|\mathcal{Y}|=3} p_k^2

两个样本类别标记不一致的概率为（即"基尼值"）

Gini⁡(D)=p1p2+p1p3+p2p1+p2p3+p3p1+p3p2=∑k=1∣Y∣=3∑k′≠kpkpk′\operatorname{Gini}(D)=p_1 p_2+p_1 p_3+p_2 p_1+p_2 p_3+p_3 p_1+p_3 p_2=\sum_{k=1}^{|\mathcal{Y}|=3} \sum_{k^{\prime} \neq k} p_k p_{k^{\prime}}

易证以上两式之和等于1，证明过程如下

∑k=1∣Y∣=3pk2+∑k=1∣Y∣=3∑k′≠kpkpk′=(p1p1+p2p2+p3p3)+(p1p2+p1p3+p2p1+p2p3+p3p1+p3p2)=(p1p1+p1p2+p1p3)+(p2p1+p2p2+p2p3)+(p3p1+p3p2+p3p3)=p1(p1+p2+p3)+p2(p1+p2+p3)+p3(p1+p2+p3)=p1+p2+p3=1\begin{aligned} &\sum_{k=1}^{|\mathcal{Y}|=3} p_k^2+\sum_{k=1}^{|\mathcal{Y}|=3} \sum_{k^{\prime} \neq k} p_k p_{k^{\prime}}\\ =&\left(p_1 p_1+p_2 p_2+p_3 p_3\right)+\left(p_1 p_2+p_1 p_3+p_2 p_1+p_2 p_3+p_3 p_1+p_3 p_2\right) \\ =&\left(p_1 p_1+p_1 p_2+p_1 p_3\right)+\left(p_2 p_1+p_2 p_2+p_2 p_3\right)+\left(p_3 p_1+p_3 p_2+p_3 p_3\right) \\ =&p_1\left(p_1+p_2+p_3\right)+p_2\left(p_1+p_2+p_3\right)+p_3\left(p_1+p_2+p_3\right) \\ =&p_1+p_2+p_3=1 \end{aligned}

所以可进一步推得式(4.5)

Gini⁡(D)=∑k=1∣Y∣∑k′≠kpkpk′=1−∑k=1∣Y∣pk2\operatorname{Gini}(D)=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_k p_{k^{\prime}}=1-\sum_{k=1}^{\mid \mathcal{Y |}} p_k^2

从数据集中 $D$ 任取两个样本，类别标记一致的概率越大表示其纯度越高（即大部分样本属于同一类），类别标记不一致的概率（即基尼值）越大表示纯度越低。

4.2.5 式(4.6)的解释

此为数据集 $D$ 中属性 $a$ 的基尼指数的定义，表示在属性 $a$ 的取值已知的条件下，数据集 $D$ 按照属性 $a$ 的所有可能取值划分后的纯度。不过在构造CART决策树时并不会严格按照此式来选择最优划分属性，主要是因为CART决策树是一棵二叉树，如果用上式去选出最优划分属性，无法进一步选出最优划分属性的最优划分点。常用的CART决策树的构造算法如下[1]：

(1)考虑每个属性 $a$ 的每个可能取值 $v$ ，将数据集 $D$ 分为 $a = v$ 和 $a≠va\neq v$ 两部分来计算基尼指数，即

Gini_index⁡(D,a)=∣Da=v∣∣D∣Gini⁡(Da=v)+∣Da≠v∣∣D∣Gini⁡(Da≠v)\operatorname{Gini\_index}(D,a) = \frac{|D^{a=v}|}{|D|}\operatorname{Gini}(D^{a=v})+\frac{|D^{a\neq v}|}{|D|}\operatorname{Gini}(D^{a\neq v})

(2)选择基尼指数最小的属性及其对应取值作为最优划分属性和最优划分点；

(3)重复以上两步，直至满足停止条件。

下面以"西瓜书"中表4.2中西瓜数据集2.0为例来构造CART决策树，其中第一个最优划分属性和最优划分点的计算过程如下：以属性"色泽"为例，它有3个可能的取值： ${青绿\{\text{青绿}$ ， $乌黑\text{乌黑}$ ， $浅白}\text{浅白}\}$ ，若使用该属性的属性值是否等于"青绿"对数据集 $D$ 进行划分，则可得到2个子集，分别记为 $D1(色泽=青绿),D2(色泽≠青绿)D^1(\text{色泽}=\text{青绿}),D^2(\text{色泽}\not=\text{青绿})$ 。子集 $D^1$ 包含编号 ${1,4,6,10,13,17\}$ 共6个样例，其中正例占 $p1=36p_1=\frac{3}{6}$ ，反例占 $p2=36p_2=\frac{3}{6}$ ；子集 $D^2$ 包含编号 ${2,3,5,7,8,9,11,12,14,15,16\}$ 共11个样例，其中正例占 $p1=511p_1=\frac{5}{11}$ ，反例占 $p2=611p_2=\frac{6}{11}$ ，根据式(4.5)可计算出用"色泽=青绿"划分之后得到基尼指数为

Gini_index⁡(D,色泽=青绿)=617×(1−(36)2−(36)2)+1117×(1−(511)2−(611)2)=0.497\begin{aligned} &\operatorname{Gini\_index}(D,\text{色泽}=\text{青绿}) \\ =&\frac{6}{17}\times\left(1-\left(\frac{3}{6}\right)^2-\left(\frac{3}{6}\right)^2\right)+\frac{11}{17}\times\left(1-\left(\frac{5}{11}\right)^2-\left(\frac{6}{11}\right)^2\right) = 0.497 \end{aligned}

类似地，可以计算出不同属性取不同值的基尼指数如下：

Gini_index⁡(D,色泽=乌黑)=0.456\operatorname{Gini\_index}(D,\text{色泽}=\text{乌黑})=0.456

Gini_index⁡(D,色泽=浅白)=0.426\operatorname{Gini\_index}(D,\text{色泽}=\text{浅白})=0.426

Gini_index⁡(D,根蒂=蜷缩)=0.456\operatorname{Gini\_index}(D,\text{根蒂}=\text{蜷缩})=0.456

Gini_index⁡(D,根蒂=稍蜷)=0.496\operatorname{Gini\_index}(D,\text{根蒂}=\text{稍蜷})=0.496

Gini_index⁡(D,根蒂=硬挺)=0.439\operatorname{Gini\_index}(D,\text{根蒂}=\text{硬挺})=0.439

Gini_index⁡(D,敲声=浊响)=0.450\operatorname{Gini\_index}(D,\text{敲声}=\text{浊响})=0.450

Gini_index⁡(D,敲声=沉闷)=0.494\operatorname{Gini\_index}(D,\text{敲声}=\text{沉闷})=0.494

Gini_index⁡(D,敲声=清脆)=0.439\operatorname{Gini\_index}(D,\text{敲声}=\text{清脆})=0.439

Gini_index⁡(D,纹理=清晰)=0.286\operatorname{Gini\_index}(D,\text{纹理}=\text{清晰})=0.286

Gini_index⁡(D,纹理=稍稀)=0.437\operatorname{Gini\_index}(D,\text{纹理}=\text{稍稀})=0.437

Gini_index⁡(D,纹理=模糊)=0.403\operatorname{Gini\_index}(D,\text{纹理}=\text{模糊})=0.403

Gini_index⁡(D,脐部=凹陷)=0.415\operatorname{Gini\_index}(D,\text{脐部}=\text{凹陷})=0.415

Gini_index⁡(D,脐部=稍凹)=0.497\operatorname{Gini\_index}(D,\text{脐部}=\text{稍凹})=0.497

Gini_index⁡(D,脐部=平坦)=0.362\operatorname{Gini\_index}(D,\text{脐部}=\text{平坦})=0.362

Gini_index⁡(D,触感=硬挺)=0.494\operatorname{Gini\_index}(D,\text{触感}=\text{硬挺})=0.494

Gini_index⁡(D,触感=软粘)=0.494\operatorname{Gini\_index}(D,\text{触感}=\text{软粘})=0.494

特别地，对于属性"触感"，由于它的可取值个数为2，所以其实只需计算其中一个取值的基尼指数即可。

根据上面的计算结果可知， $Gini_index⁡(D,纹理=清晰)=0.286\operatorname{Gini\_index}(D,\text{纹理}=\text{清晰}) = 0.286$ 最小，所以选择属性"纹理"为最优划分属性并生成根节点，接着以"纹理=清晰"为最优划分点生成 $D1(纹理=清晰)D^1(\text{纹理}=\text{清晰})$ 、 $D2(纹理≠清晰)D^2(\text{纹理}\not=\text{清晰})$ 两个子节点，对两个子节点分别重复上述步骤继续生成下一层子节点，直至满足停止条件。

以上便是CART决策树的构建过程，从构建过程可以看出，CART决策树最终构造出来的是一棵二叉树。CART除了决策树能处理分类问题以外，回归树还可以处理回归问题，下面给出CART回归树的构造算法。

假设给定数据集

\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\cdots,(\boldsymbol{x}_N,y_N)\}

其中 $x∈Rd\boldsymbol{x}\in \mathbb{R}^d$ 为 $d$ 维特征向量， $y∈Ry\in\mathbb{R}$ 是连续型随机变量。这是一个标准的回归问题的数据集,若把每个属性视为坐标空间中的一个坐标轴，则 $d$ 个属性就构成了一个 $d$ 维的特征空间，而每个 $d$ 维特征向量 $x\boldsymbol{x}$ 就对应了 $d$ 维的特征空间中的一个数据点。CART回归树的目标是将特征空间划分成若干个子空间，每个子空间都有一个固定的输出值，也就是凡是落在同一个子空间内的数据点 $xi\boldsymbol{x}_i$ ，它们所对应的输出值 $y_i$ 恒相等，且都为该子空间的输出值。

那么如何划分出若干个子空间呢？这里采用一种启发式的方法。

(1) 任意选择一个属性 $a$ ，遍历其所有可能取值，根据下式找出属性 $a$ 最优划分点 $v^*$ ：

v∗=arg⁡min⁡v[min⁡c1∑xi∈R1(a,v)(yi−c1)2+min⁡c2∑xi∈R2(a,v)(yi−c2)2]v^* = \arg\min_{v}\left[\min_{c_1}\sum_{\boldsymbol {x}_i\in{R_1(a,v)}}{(y_i - c_1)}^2 + \min_{c_2}\sum_{\boldsymbol {x}_i\in{R_2(a,v)}}{(y_i - c_2)}^2 \right]

其中， $R1(a,v)={x∣x∈Da⩽v},R2(a,v)={x∣x∈Da>v}R_1(a,v)=\{\boldsymbol {x}|\boldsymbol {x}\in D^{a\leqslant v}\},R_2(a,v)=\{\boldsymbol {x}|\boldsymbol {x}\in D^{a > v}\}$ ， $c_1$ 和 $c_2$ 分别为集合 $R_1(a,v)$ 和 $R_2(a,v)$ 中的样本 $xi\boldsymbol{x}_i$ 对应的输出值 $y_i$ 的均值，即

c1=ave⁡(yi∣x∈R1(a,v))=1∣R1(a,v)∣∑xi∈R1(a,v)yic_1=\operatorname{ave}(y_i | \boldsymbol{x}\in R_1(a,v))=\frac{1}{|R_1(a,v)|}\sum_{\boldsymbol {x}_i\in{R_1(a,v)}}y_i

c2=ave⁡(yi∣x∈R2(a,v))=1∣R2(a,v)∣∑xi∈R2(a,v)yic_2=\operatorname{ave}(y_i | \boldsymbol {x}\in R_2(a,v))=\frac{1}{|R_2(a,v)|}\sum_{\boldsymbol {x}_i\in{R_2(a,v)}}y_i

(2) 遍历所有属性，找到最优划分属性 $a^*$ ，然后根据 $a^*$ 的最优划分点 $v^*$ 将特征空间划分为两个子空间，接着对每个子空间重复上述步骤，直至满足停止条件.这样就生成了一棵CART回归树，假设最终将特征空间划分为 $M$ 个子空间 $,RMR_1,R_2,\cdots,R_M$ ，那么CART回归树的模型式可以表示为

f(x)=∑m=1McmI(x∈Rm)f(\boldsymbol {x}) = \sum_{m=1}^{M}c_m\mathbb{I}(\boldsymbol {x}\in{R_m})

同理，其中的 $c_m$ 表示的也是集合 $R_m$ 中的样本 $xi\boldsymbol{x}_i$ 对应的输出值 $y_i$ 的均值。此式直观上的理解就是，对于一个给定的样本 $xi\boldsymbol{x}_i$ ，首先判断其属于哪个子空间，然后将其所属的子空间对应的输出值作为该样本的预测值 $y_i$ 。

4.3 剪枝处理

本节内容通俗易懂，跟着"西瓜书"中的例子动手演算即可，无需做过多解释。以下仅结合图4.5继续讨论一下图4.2中的递归返回条件。图4.5与图4.4均是基于信息增益生成的决策树，不同在于图4.4基于表4.1，而图4.5基于表4.2的训练集。

结点包含训练集"脐部"为稍凹的样本（编号6、7、15、17），当根据"根蒂"再次进行划分时不含有"根蒂"为硬挺的样本（递归返回情形(3)），而恰巧四个样本（编号6、7、15、17）含两个好瓜和两个坏瓜，因此叶结点硬挺的类别随机从类别好瓜和坏瓜中选择其一。

结点包含训练集"脐部"为稍凹且"根蒂"为稍蜷的样本（编号6、7、15），当根据"色泽"再次进行划分时不含有"色泽"为浅白的样本（递归返回情形(3)），因此叶结点浅白类别标记为好瓜（编号6、7、15样本中，前两个为好瓜，最后一个为坏瓜）。

结点包含训练集"脐部"为稍凹、"根蒂"为稍蜷、"色泽"为乌黑的样本（编号7、15），当根据"纹理"再次进行划分时不含有"纹理"为模糊的样本（递归返回情形(3)），而恰巧两个样本（编号7、15）含好瓜和坏瓜各一个，因此叶结点模糊的类别随机从类别好瓜和坏瓜中选择其一。

图4.5两次随机选择均选为好瓜，实际上表示了一种归纳偏好（参见第1章1.4节）。

4.4 连续与缺失值

连续与缺失值的预处理均属于特征工程的范畴。

有些分类器只能使用离散属性，当遇到连续属性时则需要特殊处理，有兴趣可以通过关键词"连续属性离散化"或者"Discretization"查阅更多处理方法。结合第11章11.2节至11.4节分别介绍的"过滤式"算法、"包裹式"算法、"嵌入式"算法的概念，若先使用某个离散化算法对连续属性离散化后再调用C4.5决策树生成算法，则是一种过滤式算法，若如4.4.1节所述，则应该属于嵌入式算法，因为并没有以学习器的预测结果准确率为评价标准，而是与决策树生成过程融为一体，因此不应该划入包裹式算法。

类似地，有些分类器不能使用含有缺失值的样本，需要进行预处理。常用的缺失值填充方法是：对于连续属性，采用该属性的均值进行填充；对于离散属性，采用属性值个数最多的样本进行填充。这实际上假设了数据集中的样本是基于独立同分布采样得到的。特别地，一般缺失值仅指样本的属性值有缺失，若类别标记有缺失，一般会直接抛弃该样本。当然，也可以尝试根据第11章11.6节的式(11.24)，在低秩假设下对数据集缺失值进行填充。

4.4.1 式(4.7)的解释

此式所表达的思想很简单，就是以每两个相邻取值的中点作为划分点。下面以"西瓜书"中表4.3中西瓜数据集3.0为例来说明此式的用法。对于"密度"这个连续属性，已观测到的可能取值为 ${0.243,0.245,0.343,0.360,0.403,0.437,0.481,0.556,0.593,0.608,0.634,0.639,0.657,0.666,0.697,0.719,0.774\}$ 共17个值，根据式(4.7)可知，此时 $i$ 依次取1到16，那么"密度"这个属性的候选划分点集合为

Ta={0.243+0.2452,0.245+0.3432,0.343+0.3602,0.360+0.4032,0.403+0.4372,0.437+0.4812,0.481+0.5562,0.556+0.5932,0.593+0.6082,0.608+0.6342,0.634+0.6392,0.639+0.6572,0.657+0.6662,0.666+0.6972,0.697+0.7192,0.719+0.7742}\begin{aligned} T_{a} = \{&\frac{0.243+0.245}{2},\frac{0.245+0.343}{2},\frac{0.343+0.360}{2}, \frac{0.360+0.403}{2},\frac{0.403+0.437}{2},\frac{0.437+0.481}{2},\\ &\frac{0.481+0.556}{2},\frac{0.556+0.593}{2},\frac{0.593+0.608}{2},\frac{0.608+0.634}{2},\frac{0.634+0.639}{2},\frac{0.639+0.657}{2},\\ &\frac{0.657+0.666}{2},\frac{0.666+0.697}{2}, \frac{0.697+0.719}{2},\frac{0.719+0.774}{2}\} \end{aligned}

4.4.2 式(4.8)的解释

此式是式(4.2)用于离散化后的连续属性的版本，其中 $T_a$ 由式(4.7)计算得来， $λ∈{−,+}\lambda\in\{-,+\}$ 表示属性 $a$ 的取值分别小于等于和大于候选划分点 $t$ 时的情形，即当 $λ=−\lambda=-$ 时有 $Dtλ=Dta⩽tD^{\lambda}_t=D^{a\leqslant t}_t$ ，当 $λ=+\lambda=+$ 时有 $Dtλ=Dta>tD^{\lambda}_t=D^{a> t}_t$ 。

4.4.3 式(4.12)的解释

该式括号内与式(4.2)基本一样，区别在于式(4.2)中的 $∣Dv∣∣D∣\frac{\left|D^v\right|}{|D|}$ 改为式(4.11)的 $r~v\tilde{r}_v$ ，在根据式(4.1)计算信息熵时第 $k$ 类样本所占的比例改为式(4.10)的 $p~k\tilde{p}_k$ ；所有计算结束后再乘以式(4.9)的 $ρ\rho$ 。

有关式(4.9) (4.10) (4.11)中的权重 $wxw_{\boldsymbol{x}}$ ，初始化为1。以图4.9为例，在根据"纹理"进行划分时，除编号为8、10的两个样本在此属性缺失之外，其余样本根据自身在该属性上的取值分别划入稍糊、清晰、模糊三个子集，而编号为8、10的两个样本则要按比例同时划入三个子集。具体来说，稍糊子集包含样本7、9、13、14、17共5个样本，清晰子集包含样本1、2、3、4、5、6、15共7个样本，模糊子集包含样本10、11、16共3个样本，总共15个在该属性不含缺失值的样本，而此时各样本的权重 $wxw_{\boldsymbol{x}}$ 初始化为1，因此编号为8、10的两个样本分到稍糊、清晰、模糊三个子集的权重分别为 $515\frac{5}{15}$ , $715\frac{7}{15}$ 和 $315\frac{3}{15}$ 。

4.5 多变量决策树

本节内容也通俗易懂，以下仅对部分图做进一步解释说明。

4.5.1 图(4.10)的解释

只想用该图强调一下，离散属性不可以重复使用，但连续属性是可以重复使用的。

4.5.2 图(4.11)的解释

对照"西瓜书"中图4.10的决策树，下面给出图4.11中的划分边界产出过程。

在下图4-1中，斜纹阴影部分表示已确定标记为坏瓜的样本，点状阴影部分表示已确定标记为好瓜的样本，空白部分表示需要进一步划分的样本。第一次划分条件是"含糖率 $⩽0.126?\leqslant0.126?$ "，满足此条件的样本直接被标记为坏瓜（如图4-1(a)斜纹阴影部分所示），而不满足此条件的样本还需要进一步划分（如图4-1(a)空白部分所示）。

在第一次划分的基础上对图4-1(a)空白部分继续进行划分，第二次划分条件是"密度 $⩽0.381?\leqslant0.381?$ "，满足此条件的样本直接被标记为坏瓜（如图4-1(b)新增斜纹阴影部分所示），而不满足此条件的样本还需要进一步划分（如图4-1(b)空白部分所示）。

在第二次划分的基础上对图4-1(b)空白部分继续进行划分，第三次划分条件是"含糖率 $⩽0.205?\leqslant0.205?$ "，不满足此条件的样本直接标记为好瓜（如图4-1(c)新增点状阴影部分所示），而满足此条件的样本还需进一步划分（如图4-1(c)空白部分所示）。

在第三次划分的基础上对图4-1(c)空白部分继续进行划分，第四次划分的条件是"密度 $⩽0.560?\leqslant0.560?$ "，满足此条件的样本直接标记为好瓜（如图4-1(d)新增点状阴影部分所示），而不满足此条件的样本直接标记为坏瓜（如图4-1(d)新增斜纹阴影部分所示）。

经过四次划分已无空白部分，表示决策树生成完毕，从图4-1(d)中可以清晰地看出好瓜与坏瓜的分类边界。

图4-1 图4.11中的划分边界产出过程

参考文献

[1] 李航. 统计学习方法. 清华大学出版社, 2012.

第4章 决策树