来自周志华《机器学习》一书，包含自己的理解。
有任何的书写错误、排版错误、概念错误等，希望大家包含指正。

决策树

1 基本流程

我们要去买西瓜，如何判断西瓜的好坏？

首先我们观察其色泽，如果是青绿色，再看它的纹理，如果纹理清晰，我们还会敲一敲瓜，如果声音清脆，那么我们就断定它是个好瓜。

按照这个逻辑，可以简单地构建一棵决策树：

我们是如何得到这棵决策树的？

瓜农们种瓜无数，阅瓜无数，凭借着他们遇到各种各样的好瓜与坏瓜的经验，总结出来一套我们用于生成决策树规律。

机器也是类似的，我们将大量的西瓜数据和学习方法提供给机器，让机器从西瓜数据中学习判断瓜好坏的方法，它在学习过程中会生成一棵完整决策树，最终我们可以利用“学有所成”的机器判断其他瓜的好坏。

---

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略，如算法 $1$ 所示。

输入:  训练集  D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } ;                                    属性值  A = { a 1 , a 2 , . . . , a d } 过程:  函数  T r e e G e n e r a t e ( D , A ) 输出:  以  n o d e  为根结点的一棵决策树

输入:过程:输出:​ 训练集 D={(xx1​,y1​),(xx2​,y2​),...,(xxm​,ym​)};                                  属性值 A={a1​,a2​,...,ad​} 函数 TreeGenerate(D,A) 以 node 为根结点的一棵决策树​

1 : 生成结点  n o d e ; 2 : if    D  中样本全属于同一类别  C    then 3 :     将  n o d e  标记为  C  类叶结点 ; return 4 : end   if 5 : if    A ≠ ∅    OR    D  中样本在  A  上取值相同  then 6 :     将  n o d e  标记为叶结点，其类别标记为  D  中样本数最多的类 ; return 7 : end   if 8 : 从  A  中选择最优划分属性  a ∗ ; 9 : for    a ∗  的每一个值  a ∗ v   do 10 :     为  n o d e  生成一个分支 ;  令  D v  表示  D  中在  a ∗  上取值为  a ∗ v  的样本子集 ; 11 :      if   D v  为空  then 12 :         将分支结点标记为叶结点 ,  其类别标记为  D  中样本数最多的类 ; return 13 :      else 14 :         以  T r e e G e n e r a t e ( D v , A   \   { a ∗ } )  为分支结点 15 :      end   if 16 : end   for

1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:​生成结点 node;if  D 中样本全属于同一类别 C  then    将 node 标记为 C 类叶结点;returnend ifif  A=∅  OR  D 中样本在 A 上取值相同 then    将 node 标记为叶结点，其类别标记为 D 中样本数最多的类;returnend if从 A 中选择最优划分属性 a∗​;for  a∗​ 的每一个值 a∗v​ do    为 node 生成一个分支; 令 Dv​ 表示 D 中在 a∗​ 上取值为 a∗v​ 的样本子集;    if Dv​ 为空 then        将分支结点标记为叶结点, 其类别标记为 D 中样本数最多的类;return    else        以 TreeGenerate(Dv​,A \ {a∗​}) 为分支结点    end ifend for​

算法 1    决策树学习基本算法

算法 $1$ 的语言描述如下。

最初决策树为空；生成一个不包含任何信息的根结点，按照一定的算法选择最佳的属性用以分支，将根结点标记为该属性，每个分支是该属性的不同取值；对于每个分支，继续创建不包含任何信息的结点，按照相同的方式继续进行分支，但是祖先结点的属性将不会出现在后代结点中，后代结点中允许出现重复的属性；另外，在分支的过程中，每个样本会根据分支代表的不同属性值被划分到不同结点。显然，决策树的生成是一个递归的过程。在决策树基本算法中，有三种情形会导致递归返回：

1. 在对某个不包含任何信息的结点选择最佳属性前，需要先判断该空结点中的样本是否完全属于同一类别，即标签是否相同，如果相同，则不为该结点选择属性，即不再继续分支，而是直接标记为样本的类别并返回。对应算法 $1$ 的第 $3$ 行；
2. 在对某个不包含任何信息的结点选择最佳属性前，如果已经没有剩余属性，或者该结点中的任意一个样本在任意一个剩余属性上的取值均相同，则不再继续分支，而是直接标记为样本数最多的类；对应算法 $1$ 的第 $6$ 行；
3. 在分支的过程中，如果划分到某个属性值下的样本集合为空，显然空样本集合对应的分支结点无法继续分支，因此，将分支结点的类别标记为其父结点（分支汇聚结点）中样本数最多的类。对应算法 $1$ 的第 $12$ 行。

2 划分选择

决策树学习的关键在于如何选择最佳的属性进行划分。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的”纯度“（purity）越来越高。

2.1 信息熵

信息熵（information entropy）是信息论中用于度量信息量的一个概念。一个系统越是有序，信息熵就越低，即系统包含的信息量越少；反之，一个系统越是混乱，信息熵就越高，即系统包含的信息量越多。因此，信息熵是度量样本集合纯度的一种指标。

通过我们常规思考来分析，我们可以理解为信息的大小跟随机事件的概率有关。越小概率的事情发生了产生的信息量越大，如”六月飞雪“是一种非常少见的情况，因此蕴含着非常多的信息；越大概率的事情发生了产生的信息量越小，如”太阳东升西落“蕴含的信息量就非常少，因为这是常识。

虽然信息熵是度量样本集合纯度的一种指标，但是其本质上描述的是样本集合的混乱程度，即信息熵越大，混乱程度越大。也就是说，信息熵既是度量纯度的指标，也是度量混乱程度的指标，但其直接描述的还是混乱程度。这点无需特意区分，仅仅为了方便理解。

2.1.1 信息熵的性质

信息论之父克劳德·香农给出的信息熵的三个性质：

1. 单调性，发生概率越高的事件，其携带的信息量越低；
2. 非负性，信息熵可以看作为一种广度量，非负性是一种合理的必然；
3. 累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和，这也是广度量的一种体现。

2.1.2 信息熵的定义

根据上面这三条性质，可以定义随机事件中一个样本点的信息熵如下：
h ( x ) = − l o g 2 p ( x )

h(x)=−log2​p(x)​(1)​
其中，$p(x)$ 代表随机事件中样本点 $x$ 发生的概率。

显然，$h(x)$ 满足单调性和非负性，样本点 $x$ 发生的概率越大，信息熵 $h(x)$ 就越小；因为 $0<p(x)\le 1$，所以 $h(x)\ge 1$；

$h(x)$ 满足累加性，$h(x)+h(y)=-lo{g}_{2}p(x)-lo{g}_{2}p(y)=-log(p(x)\cdot p(y))$；当随机事件中的两个样本点 $x$ 和 $y$ 相互独立时，$p(x)\cdot p(y)=p(x,y)$，其中 $p(x,y)$ 表示样本点 $x$ 和 $y$ 同时发生的概率。

有关随机事件的相关定义如下。

随机试验中的每一个可能出现的试验结果称为这个试验的一个样本点，记作 ${\omega }_i$。全体样本点组成的集合称为这个试验的样本空间，记作 $\Omega$ 。即 Ω = { ω 1 , ω 2 , … , ω n , … } Ω=\{ω_1,ω_2,…,ω_n,…\} Ω={ω1​,ω2​,…,ωn​,…} 。仅含一个样本点的随机事件称为基本事件，含有多个样本点的随机事件称为复合事件。

在随机试验中，随机事件一般是由若干个基本事件组成的。样本空间 $\Omega$ 的任一子集 $A$ 称为随机事件。属于事件 $A$ 的样本点出现，则称事件 $A$ 发生。

例如，在投骰子的试验 $E$ 中，令 $A$ 表示“出现奇数点”，$A$ 就是一个随机事件，$A$ 还可以用样本点的集合形式表示，即 A = { 1 , 3 , 5 } A=\{1,3,5\} A={1,3,5}，它是样本空间 $\Omega$ 的一个子集。

本质上，也可以将”出现点 $1$ “视为一个随机事件。正如上面所述，仅含一个样本点也可以视为一个随机事件。因此，信息熵定义中所明确区分的”随机事件“与”样本点“仅仅是为了表明包含或组成的关系。

---

另外，也可以定义整个随机事件 $X$（多个样本点）的信息熵，也即平均信息量或期望信息量：
h ( X ) = − ∑ x ∈ X   p ( x )   l o g 2 p ( x )

h(X)=−x∈X∑​ p(x) log2​p(x)​(2)​
其中，$\mathcal{X}$ 表示样本空间，$x$ 表示样本空间中的样本点，并且规定 $0lo{g}_2(0)=0$。本质上，随机事件的信息熵是在计算随机事件中全部样本点的信息熵期望。

---

在决策树中，信息熵通常用于度量样本集合的纯度。假定当前样本集合 $D$ 中第 $k$ 个类（标签）样本所占的比例为 $p_k(k=1,2,...,|\mathcal{Y}|)$，则 $D$ 的信息熵定义如下：
E n t ( D ) = − ∑ k = 1 ∣ Y ∣   p k   l o g 2 p k

Ent(D)=−k=1∑∣Y∣​ pk​ log2​pk​​(3)​

$Ent(D)$ 的值越小，则 $D$ 的纯度越高。

2.2 属性选择度量

三种度量：信息增益（应用于 ID3 决策树）、增益率（应用于 C4.5 决策树）和Gini指标（应用于 CART 决策树）。

2.2.1 信息增益

假设离散属性 $a$ 有 $V$ 个可能的取值 { a 1 , a 2 , . . . , a V } \{a^1,a^2,...,a^V\} {a1,a2,...,aV}，若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ 。可以根据式 $(3)$ 计算出 $D^v$ 的信息熵，再考虑到不同分支结点所包含的样本数不同，给分支结点赋予权重 $|D^v|/|D|$，即样本数越多的分支结点的影响越大，于是可以计算出用属性 $a$ 对样本集 $D$ 进行划分所获得的“信息增益”（information gain）
G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V   D v ∣ D ∣ E n t ( D v )

Gain(D,a)=Ent(D)−v=1∑V​ ∣D∣Dv​Ent(Dv)​(4)​
从公式上来看，信息增益表示父结点的信息熵与子结点信息熵加权和之差。

一般而言，信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的“纯度提升”越大。

因为划分子结点时，父结点是相同的，即式 $(4)$ 中的 $Ent(D)$ 是相同的，如果 $\sum _{v=1}^V\frac{D^v}{|D|}Ent(D^v)$ 越小，则说明划分出的集合所包含的信息量越少，也即纯度越高，此时 $Gain(D,a)$ 就越大。

至于为什么不直接选择 $\sum _{v=1}^V\frac{D^v}{|D|}Ent(D^v)$ 最小的属性，那只能解释为 ID3决策树的发明者觉得通过信息增益来选择比直接通过前面的式子来选择更有意义、更便于理解。因为信息增益描述的是选择某个属性进行划分前后纯度的差值，如果纯度差值越大说明我们划分的越有意义，而如果直接使用 $\sum _{v=1}^V\frac{D^v}{|D|}Ent(D^v)$ 来表示，则不容易直观地理解。

因此，我们可以用信息增益来进行决策树的划分属性选择，即在决策树学习基本算法第8行选择属性 $a_{\ast }=\underset{a\in A}{argmax}Gain(D,a)$ 。著名的 ID3 决策树学习算法就是以信息增益为准则来选择划分属性。

表 1    西瓜数据集

以表 $1$ 西瓜数据集为例，该数据集包含 $17$ 个训练样例，用以学习一棵能预测没剖开的是不是好瓜的决策树。

观察标签可知 $|\mathcal{Y}|=2$。在决策树学习开始时，根结点包含 $D$ 中所有样例，其中正例占 $p_1=\frac{8}{17}$，反例占 $p_2=\frac{9}{17}$ 。于是，根据式 $(3)$ 可以计算出根结点的信息熵为
$$Ent(D)=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-\left(\frac{8}{17}lo{g}_2\frac{8}{17}+\frac{9}{17}lo{g}_2\frac{9}{17}\right)=0.998$$
然后，计算出当前属性集合 {色泽，根蒂，敲声，纹理，脐部，触感} 中每个属性的信息增益。以属性“色泽”为例，它有 $3$ 个可能的取值：{青绿，乌黑，浅白} 。若使用该属性对 $D$ 进行划分，则可以得到 $3$ 个子集，分别记为：$D^1$（色泽=青绿），$D^2$（色泽=乌黑），$D^3$（色泽=浅白）。

子集 $D^1$ 包含编号为 { 1 , 4 , 6 , 10 , 13 , 17 } \{1,4,6,10,13,17\} {1,4,6,10,13,17} 的 $6$ 个样例，其中正例占 $p_1=\frac{3}{6}$，反例占 $p_2=\frac{3}{6}$；$D^2$ 包含编号为 { 2 , 3 , 7 , 8 , 9 , 15 } \{2,3,7,8,9,15\} {2,3,7,8,9,15} 的 $6$ 个样例，其中正、反例分别占 $p_1=\frac{4}{6}$，$p_2=\frac{2}{6}$；$D^3$ 包含编号为 { 5 , 11 , 12 , 14 , 16 } \{5,11,12,14,16\} {5,11,12,14,16} 的 $5$ 个样例，其中正、反例分别占 $p_1=\frac{1}{5}$，$p_2=\frac{4}{5}$ 。根据式 $(3)$ 可以计算出用“色泽”划分之后获得的 $3$ 个分支结点的信息熵为
$$\begin{gathered} Ent(D^1)=-\left(\frac{3}{6}lo{g}_2\frac{3}{6}+\frac{3}{6}lo{g}_2\frac{3}{6}\right)=1.000, \\ Ent(D^2)=-\left(\frac{4}{6}lo{g}_2\frac{4}{6}+\frac{2}{6}lo{g}_2\frac{2}{6}\right)=0.918, \\ Ent(D^3)=-\left(\frac{1}{5}lo{g}_2\frac{1}{5}+\frac{4}{5}lo{g}_2\frac{4}{5}\right)=0.722. \end{gathered}$$
于是，根据式 $(4)$ 可以计算出属性“色泽”的信息增益为
G a i n ( D , 色泽 ) = E n t ( D ) − ∑ v = 1 3 ∣ D v ∣ ∣ D ∣ E n t ( D v ) = 0.998 − ( 6 17 × 1.000 + 6 17 × 0.918 + 5 17 × 0.722 ) = 0.109

Gain(D,色泽)​=Ent(D)−v=1∑3​∣D∣∣Dv∣​Ent(Dv)=0.998−(176​×1.000+176​×0.918+175​×0.722)=0.109​​
类似的，可以计算出其他属性的信息增益：
$$\begin{gathered} Gain(D,根蒂)=0.143; \\ Gain(D,敲声)=0.141; \\ Gain(D,纹理)=0.381; \\ Gain(D,脐部)=0.289; \\ Gain(D,触感)=\mathrm{0.006.} \end{gathered}$$
显然，属性“纹理”的信息增益最大，于是它被选为划分属性。图 $1$ 给出了基于“纹理”对根结点进行划分的结果，各分支结点所包含的样例子集显示在结点中。

图 1    基于“纹理”属性对根结点划分

然后，决策树学习算法将对每个分支结点做进一步划分，以图 $(1)$ 中第一个分支结点（“纹理 = 清晰”）为例，该结点包含的样本集合 $D^1$ 中有编号为 { 1 , 2 , 3 , 4 , 5 , 6 , 8 , 10 , 15 } \{1,2,3,4,5,6,8,10,15\} {1,2,3,4,5,6,8,10,15} 的 $9$ 个样例，可用属性集合为 {色泽，根蒂，敲声，脐部，触感}。基于 $D^1$ 计算出各属性的信息增益：
$$\begin{gathered} Gain(D^1,色泽)=0.043; \\ Gain(D^1,根蒂)=0.458; \\ Gain(D^1,敲声)=0.331; \\ Gain(D^1,脐部)=0.458; \\ Gain(D^1,触感)=\mathrm{0.458.} \end{gathered}$$
“根蒂”、“脐部”、“触感” $3$ 个属性均取得了最大的信息增益，可以任选其中之一作为划分属性。类似的，对每一个分支结点进行上述操作，最终得到决策树如图 $2$ 所示。

图 2    在西瓜数据集上基于信息增益生成的决策树

注意：

当叶结点中样例最多的类不唯一时，可以任选其中一类作为叶结点类别。对于西瓜数据集而言，我们规定如果某个叶结点处好瓜数目和坏瓜数目相同，则认为叶结点表示好瓜。

信息增益的缺点

从求解信息增益的公式中可以看出，信息增益准则对可取值数目较多的属性有所偏好，也就是说可取值数目越多，分到每一个子结点的样例数量就会越少，子结点中的样例是同一个类别的可能性也就越大，即纯度越高。从对决策树进行划分的目标（分支结点的纯度尽可能高）来看，采用信息增益确实可以保证满足该目标。但是这样的度量并不总是合适的，假设把表 $1$ 中的“编号”也作为一个候选划分属性，则根据式 $(4)$ 可以计算出它的信息增益为 $0.998$ ，远大于其他候选划分属性。这很容易理解：“编号”将产生 $17$ 个分支，每个分支结点仅包含一个样本，这些分支结点的纯度已到达最大。然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。

2.2.2 增益率

为了减少信息增益的偏好可能带来的不利影响，著名的 C4.5 决策树不直接使用信息增益，而是使用“增益率”（gain ratio）来选择最优化分属性。采用与式 $(4)$ 相同的符号表示，增益率定义为
G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a )

Gain_ratio(D,a)=IV(a)Gain(D,a)​​(5)​
其中
I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣

(6)IV(a)=−∑v=1V|Dv||D|log2|Dv||D|" role="presentation" style="position: relative;">IV(a)=−∑v=1V|Dv||D|log2|Dv||D|(6)$$\begin{array}{}\text{(6)}& IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}\end{array}$$

IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​​(6)​
称为属性 $a$ 的“固有属性”（intrinsic value）。属性 $a$ 的可能取值数目越多（即 $V$ 越大），则 $IV(a)$ 的值通常会越大。例如，对于表 $1$ 的西瓜数据集，有 $IV(触感)=0.874(V=2)$，$IV(色泽)=1.580(V=3)$， $IV(编号)=4.088(V=17)$ 。

注意：

式 $(6)$ 和式 $(3)$ 有点相似。可以将式 $(3)$ 理解为描述标签的纯度，即如果每种标签的个数都差不多则认为纯度很小（或者混乱程度大），如果大部分样例的标签都一样则认为纯度很大，这种标签的纯度是通过标签的信息熵来衡量的；而式 $(6)$ 描述的是某个属性取值的纯度，即每个属性值出现次数的分布情况，分布越均匀则纯度越大，这种属性值的纯度是通过属性的信息熵来衡量的。

总而言之，$Ent(D)$ 描述标签的纯度，$IV(a)$ 描述属性的纯度。这样一来，我们就能清晰地知道何时使用哪个概率计算信息熵了。

从公式上来看，增益率表示属性划分后样本标签的信息增益与该属性信息熵的比值。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

2.2.3 基尼指数

CART 决策树使用“基尼指数”（Gini index）来选择划分属性。采用与式 $(3)$ 相同的符号，即假定当前样本集合 $D$ 中第 $k$ 个类（标签）样本所占的比例为 $p_k$ $(k=1,2,...,|\mathcal{Y}|)$，数据集 $D$ 的纯度可用基尼值来度量：
G i n i ( D ) = ∑ k = 1 ∣ Y ∣ ∑ k ′ ≠ k p k   p k ′ = 1 − ∑ k = 1 ∣ Y ∣ p k 2

Gini(D)​=k=1∑∣Y∣​k′=k∑​pk​ pk′​=1−k=1∑∣Y∣​pk2​​(7)​

公式推导：$\sum _{i=1}^n\sum _{j\ne i}{p}_i{p}_j\Rightarrow 1-\sum _{i=1}^n{p}_i^2$
∑ i = 1 n ∑ j ≠ i p i   p j =   0   +   p 1 p 2   +   p 1 p 3   +   . . .   +   p 1 p n − 1   +   p 1 p n +   p 2 p 1   +   0   +   p 2 p 3   +   . . .   +   p 2 p n − 1   +   p 2 p n +   . . . +   p n p 1   +   p n p 2   +   p n p 3   +   . . .   +   p n p n − 1   +   0 = ( p 1 p 1   +   p 1 p 2   +   p 1 p 3   +   . . .   +   p 1 p n − 1   +   p 1 p n +    p 2 p 1   +   p 2 p 2   +   p 2 p 3   +   . . .   +   p 2 p n − 1   +   p 2 p n +    . . . +    p n p 1   +   p n p 2   +   p n p 3   +   . . .   +   p n p n − 1   +   p n p n ) − ( p 1 2   +   p 2 2   +   . . .   +   p n 2 ) = [ p 1   ( p 1   +   . . .   +   p n ) +    p 2   ( p 1   +   . . .   +   p n ) +    . . . +    p n   ( p 1   +   . . .   +   p n ) ] − ( p 1 2   +   p 2 2   +   . . .   +   p n 2 ) = [ p 1 ⋅ 1 +    p 2 ⋅ 1 +    . . . +    p n ⋅ 1 ] − ( p 1 2   +   p 2 2   +   . . .   +   p n 2 ) = 1 − ( p 1 2   +   p 2 2   +   . . .   +   p n 2 ) = 1 − ∑ i = 1 n p i 2

\begin{align} \sum \limits_{i=1}^{n}\sum\limits_{j\ne i} p_i\space p_{j} &= \space0 \space + \space p_1p_2 \space + \space p_1p_3\space +\space ...\space + \space p_1p_{n-1}\space + \space p_1p_n \notag\\ &+ \space p_2p_1 \space + \space 0 \space + \space p_2p_3\space +\space ...\space + \space p_2p_{n-1}\space + \space p_2p_n \notag \\ &+ \space... \notag \\ &+ \space p_np_1 \space + \space p_np_2 \space + \space p_np_3\space +\space ...\space + \space p_np_{n-1}\space + \space 0 \notag \\ \notag\\ %%%%% &=(\pmb{p_1p_1} \space + \space p_1p_2 \space + \space p_1p_3\space +\space ...\space + \space p_1p_{n-1}\space + \space p_1p_n \notag \\ &+ \space\space p_2p_1 \space + \space \pmb{p_2p_2} \space + \space p_2p_3\space +\space ...\space + \space p_2p_{n-1}\space + \space p_2p_n \notag \\ &+ \space\space... \notag \\ &+ \space\space p_np_1 \space + \space p_np_2 \space + \space p_np_3\space +\space ...\space + \space p_np_{n-1}\space + \space \pmb{p_np_n}) \notag\\ &- (\pmb{p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=[p_1\space(p_1\space+\space...\space+\space p_n) \notag\\ &+\space\space p_2\space(p_1\space+\space...\space+\space p_n) \notag\\ &+\space\space ... \notag\\ &+\space\space p_n\space(p_1\space+\space...\space+\space p_n)] \notag \\ &- ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=[p_1·1 \notag\\ &+\space\space p_2·1 \notag\\ &+\space\space ... \notag\\ &+\space\space p_n·1] \notag\\ &- ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &= 1 - ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=1-\sum\limits_{i=1}^{n} p_i^2 \notag \end{align}" role="presentation" style="position: relative;">\begin{align} \sum \limits_{i=1}^{n}\sum\limits_{j\ne i} p_i\space p_{j} &= \space0 \space + \space p_1p_2 \space + \space p_1p_3\space +\space ...\space + \space p_1p_{n-1}\space + \space p_1p_n \notag\\ &+ \space p_2p_1 \space + \space 0 \space + \space p_2p_3\space +\space ...\space + \space p_2p_{n-1}\space + \space p_2p_n \notag \\ &+ \space... \notag \\ &+ \space p_np_1 \space + \space p_np_2 \space + \space p_np_3\space +\space ...\space + \space p_np_{n-1}\space + \space 0 \notag \\ \notag\\ %%%%% &=(\pmb{p_1p_1} \space + \space p_1p_2 \space + \space p_1p_3\space +\space ...\space + \space p_1p_{n-1}\space + \space p_1p_n \notag \\ &+ \space\space p_2p_1 \space + \space \pmb{p_2p_2} \space + \space p_2p_3\space +\space ...\space + \space p_2p_{n-1}\space + \space p_2p_n \notag \\ &+ \space\space... \notag \\ &+ \space\space p_np_1 \space + \space p_np_2 \space + \space p_np_3\space +\space ...\space + \space p_np_{n-1}\space + \space \pmb{p_np_n}) \notag\\ &- (\pmb{p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=[p_1\space(p_1\space+\space...\space+\space p_n) \notag\\ &+\space\space p_2\space(p_1\space+\space...\space+\space p_n) \notag\\ &+\space\space ... \notag\\ &+\space\space p_n\space(p_1\space+\space...\space+\space p_n)] \notag \\ &- ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=[p_1·1 \notag\\ &+\space\space p_2·1 \notag\\ &+\space\space ... \notag\\ &+\space\space p_n·1] \notag\\ &- ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &= 1 - ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=1-\sum\limits_{i=1}^{n} p_i^2 \notag \end{align}$$\begin{align} \sum \limits_{i=1}^{n}\sum\limits_{j\ne i} p_i\space p_{j} &= \space0 \space + \space p_1p_2 \space + \space p_1p_3\space +\space ...\space + \space p_1p_{n-1}\space + \space p_1p_n \notag\\ &+ \space p_2p_1 \space + \space 0 \space + \space p_2p_3\space +\space ...\space + \space p_2p_{n-1}\space + \space p_2p_n \notag \\ &+ \space... \notag \\ &+ \space p_np_1 \space + \space p_np_2 \space + \space p_np_3\space +\space ...\space + \space p_np_{n-1}\space + \space 0 \notag \\ \notag\\ %%%%% &=(\pmb{p_1p_1} \space + \space p_1p_2 \space + \space p_1p_3\space +\space ...\space + \space p_1p_{n-1}\space + \space p_1p_n \notag \\ &+ \space\space p_2p_1 \space + \space \pmb{p_2p_2} \space + \space p_2p_3\space +\space ...\space + \space p_2p_{n-1}\space + \space p_2p_n \notag \\ &+ \space\space... \notag \\ &+ \space\space p_np_1 \space + \space p_np_2 \space + \space p_np_3\space +\space ...\space + \space p_np_{n-1}\space + \space \pmb{p_np_n}) \notag\\ &- (\pmb{p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=[p_1\space(p_1\space+\space...\space+\space p_n) \notag\\ &+\space\space p_2\space(p_1\space+\space...\space+\space p_n) \notag\\ &+\space\space ... \notag\\ &+\space\space p_n\space(p_1\space+\space...\space+\space p_n)] \notag \\ &- ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=[p_1·1 \notag\\ &+\space\space p_2·1 \notag\\ &+\space\space ... \notag\\ &+\space\space p_n·1] \notag\\ &- ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &= 1 - ({p_1^2\space+\space p_2^2\space+\space...\space+\space p_n^2}) \notag\\ \notag\\ %%%% &=1-\sum\limits_{i=1}^{n} p_i^2 \notag \end{align}$$

i=1∑n​j=i∑​pi​ pj​​= 0 + p1​p2​ + p1​p3​ + ... + p1​pn−1​ + p1​pn​+ p2​p1​ + 0 + p2​p3​ + ... + p2​pn−1​ + p2​pn​+ ...+ pn​p1​ + pn​p2​ + pn​p3​ + ... + pn​pn−1​ + 0=(p1​p1​p1​p1​ + p1​p2​ + p1​p3​ + ... + p1​pn−1​ + p1​pn​+  p2​p1​ + p2​p2​p2​p2​ + p2​p3​ + ... + p2​pn−1​ + p2​pn​+  ...+  pn​p1​ + pn​p2​ + pn​p3​ + ... + pn​pn−1​ + pn​pn​pn​pn​)−(p12​ + p22​ + ... + pn2​p12​ + p22​ + ... + pn2​)=[p1​ (p1​ + ... + pn​)+  p2​ (p1​ + ... + pn​)+  ...+  pn​ (p1​ + ... + pn​)]−(p12​ + p22​ + ... + pn2​)=[p1​⋅1+  p2​⋅1+  ...+  pn​⋅1]−(p12​ + p22​ + ... + pn2​)=1−(p12​ + p22​ + ... + pn2​)=1−i=1∑n​pi2​​

直观来说，$Gini(D)$ 反映了从数据集 $D$ 种随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$ 越小，则数据集 $D$ 的纯度越高。

采用与式 $(4)$ 相同的符号表示，属性 $a$ 的基尼指数定义为
G i n i _ i n d e x ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣   G i n i ( D v )

Gini_index(D,a)=v=1∑V​∣D∣∣Dv∣​ Gini(Dv)​(8)​
于是，在候选属性集合 $A$ 种，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $a_{\ast }=\underset{a\in A}{argmax}Gini\_index(D,a)$

注意：

采用基尼指数与信息增益、增益率不同，要选择基尼指数最小的属性进行划分。主要原因在于基尼指数本质上描述的是混乱程度，而信息增益和增益率描述的是纯度。混乱程度越大，对应纯度越小；混乱程度越小，对应纯度越大，可见，混乱程度和纯度是两种正好相反的描述方式。

举例说明“ $Gini(D)$ 越小，则数据集 $D$ 的纯度越”：

假设存在只两类样本，对应标签分别为 $A$ 和 $B$ 。

情况 $1$：$p_A=\frac{1}{2}$，$p_B=\frac{1}{2}$，则 $Gini=1-{\frac{1}{2}}^2-{\frac{1}{2}}^2=\frac{1}{2}$

情况 $2$：$p_A=\frac{1}{100}$，$p_B=\frac{99}{100}$，则 $Gini=1-{\frac{1}{100}}^2-{\frac{99}{100}}^2\approx 0<\frac{1}{2}$

情况 $1$ 比情况 $2$ 的混乱程度大、Gini 值大、纯度小。

从公式来看，基尼指数的思想完全不同于信息增益和增益率。信息增益和增益率都是建立在信息熵的基础上，而基尼指数则另辟蹊径。

3 剪枝处理

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这是就可能因为训练样本学得“太好”了，以至于把训练集本身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（postpruning）。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

我们采用留出法来判断决策树泛化性能是否提升，即预留一部分数据用作“验证集”以进行性能评估。例如对表 $1$ 的西瓜数据集，将其随机划分为两部分，如表 $2$ 所示，编号为 { 1 , 2 , 3 , 6 , 7 , 10 , 14 , 15 , 16 , 17 } \{1,2,3,6,7,10,14,15,16,17\} {1,2,3,6,7,10,14,15,16,17} 的样例组成训练集，编号为 { 4 , 5 , 8 , 9 , 11 , 12 , 13 } \{4,5,8,9,11,12,13\} {4,5,8,9,11,12,13} 的样例组成验证集。

表 2    西瓜数据集划分出的训练集（双线上部）与验证集（双线下部）

假定采用信息增益准则来进行划分属性选择，则从表 $2$ 的训练集将会生成一棵如图 $3$ 所示的决策树。为了便于讨论，对途中的部分结点做了编号。

以根结点的属性选择来简单说明决策树的构建：

在划分之前，所有训练样本集中在根结点，好瓜和坏瓜各占一半。对于“脐部”属性，“凹陷”、“稍凹”、“平坦”样本分别占全部训练样本的 $\frac{4}{10}$、$\frac{4}{10}$、$\frac{2}{10}$；“凹陷”样本中好瓜样本和坏瓜样本分别占 $\frac{3}{4}$ 和 $\frac{1}{4}$，“稍凹”样本中好瓜样本和坏瓜样本分别占 $\frac{2}{4}$ 和 $\frac{2}{4}$，“平坦”样本中全为坏瓜。根据式 $(4)$ 计算信息增益为
G a i n ( D t r a i n , 脐部 ) = ( − 1 2 l o g 2 1 2 − 1 2 l o g 2 1 2 ) − [ 4 10 ( − 3 4 l o g 2 3 4 − 1 4 l o g 2 1 4 ) + 4 10 ( − 2 4 l o g 2 2 4 − 2 4 l o g 2 2 4 ) + 2 10 ( 0 − 1 l o g 2 1 ) ] = 1 − 0.724 = 0.276

Gain(Dtrain,脐部)=(−12log212−12log212)−[410(−34log234−14log214)+410(−24log224−24log224)+210(0−1log21)]=1−0.724=0.276" role="presentation" style="position: relative;">Gain(Dtrain,脐部)=(−12log212−12log212)−[410(−34log234−14log214)+410(−24log224−24log224)+210(0−1log21)]=1−0.724=0.276$$\begin{array}{rl}Gain(D_{train},脐部)& =\left(-\frac{1}{2}lo{g}_2\frac{1}{2}-\frac{1}{2}lo{g}_2\frac{1}{2}\right)-\left[\frac{4}{10}\left(-\frac{3}{4}lo{g}_2\frac{3}{4}-\frac{1}{4}lo{g}_2\frac{1}{4}\right)+\frac{4}{10}\left(-\frac{2}{4}lo{g}_2\frac{2}{4}-\frac{2}{4}lo{g}_2\frac{2}{4}\right)+\frac{2}{10}\left(0-1lo{g}_{2}1\right)\right]\\ & =1-0.724\\ & =0.276\end{array}$$

Gain(Dtrain​,脐部)​=(−21​log2​21​−21​log2​21​)−[104​(−43​log2​43​−41​log2​41​)+104​(−42​log2​42​−42​log2​42​)+102​(0−1log2​1)]=1−0.724=0.276​
类似的，计算出其他属性的信息增益
$$\begin{gathered} Gain(D_{train},色泽)=0.276; \\ Gain(D_{train},根蒂)=0.115; \\ Gain(D_{train},敲声)=0.082; \\ Gain(D_{train},纹理)=0.082; \\ Gain(D_{train},触感)=0.000. \end{gathered}$$
我们选择信息增益最大的“脐部”作为划分属性。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oXjvgo0G-1659164974247)(C:\Users\23343\AppData\Roaming\Typora\typora-user-images\image-20220729194826152.png)]

图 3    基于表 2 生成的未剪枝决策树

3.1 预剪枝

基于信息增益准则，我们会选取属性“脐部”来对训练集进行划分，并产生 $3$ 个分支，如图 $4$ 所示。然而，还需要预剪枝对划分前后的泛化性能进行估计来确定是否应该进行这个划分。

图 4    基于表 2 生成的预剪枝决策树

在划分之前，所有样本集中在根结点。若不进行划分，则根据算法 $1$ 第 $6$ 行，该结点将被标记为叶结点，其类别标记为训练样例数最多的类别，假设将这个叶结点标记为“好瓜”。用表 $2$ 的验证集对这个单结点决策树进行评估，则编号为 { 4 , 5 , 8 } \{4,5,8\} {4,5,8} 的样例被分类正确，另外 $4$ 个样例分类错误，于是，验证集精度为 $\frac{3}{7}\times 100\%=42.9\%$ 。

在用属性“脐部”划分之后，图 $4$ 中的结点 $②$、$③$、$④$ 分别包含编号为 $1,2,3,14$、$6,7,15,17$、$10,16$ 的训练样例，因此这 $3$ 个结点分别被标记为叶结点“好瓜”、“好瓜”、“坏瓜”。此时，验证集中编号为 $4,5,8,11,12$ 的样例被分类正确，验证集精度为 $\frac{5}{7}\times 100\%=71.4\%>42.9\%$ 。于是，用“脐部”进行划分得以确定。

然后，决策树算法应该对结点 $②$ 进行划分，基于信息增益准则将挑选出划分属性“色泽”。然而，在使用“色泽”划分后，编号为 $5$ 的验证集样本分类结果会由正确转为错误，使得验证集精度下降为 $57.1\%$。于是，预剪枝策略将禁止结点 $②$ 被划分。

对结点 $③$，最优划分属性为“根蒂”，划分后验证集精度仍为 $71.4\%$ 。这个划分不能提升验证集精度，于是，预剪枝策略禁止结点 $③$ 被划分。

对结点 $④$，根据算法 $1$ 第 $3$ 行，其所含训练样例已属于同一类，不再进行划分。

于是，基于预剪枝策略从表 $2$ 数据所生成的决策树如图 $4$ 所示，其验证集精度为 $71.4\%$ 。这是一棵仅有一层划分的决策树，亦称“决策树桩”（decision stump）。

预剪枝的优点与缺点

对比图 $3$ 和图 $4$ 可看出，预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

3.2 后剪枝

后剪枝先从训练集生从一棵完整决策树，例如基于表 $2$ 的数据集我们得到如图 $3$ 所示的决策树。易知，该决策树的验证集精度为 $42.9\%$ 。

后剪枝首先考察图 $3$ 中的结点 $⑥$。若将其领衔的分支剪除，则相当于把 $⑥$ 替换为叶结点。替换后的叶结点包含编号为 { 7 , 15 } \{7,15\} {7,15} 的训练样本，于是，该叶结点的类别标记为“好瓜”，此时决策树的验证集精度提高至 $57.1\%$ 。于是，后剪枝策略决定剪枝，如图 $5$ 灰色虚线部分所示。

然后考察结点 $⑤$，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为 $6,7,15$ 的训练样例，叶结点类别被标记为“好瓜”，此时决策树验证集精度仍为 $57.1\%$ 。根据“奥卡姆剃刀准则”，剪枝后的模型更好，于是，后剪枝策略决定剪枝。

奥卡姆剃刀定律倡导简化法则，奥卡姆剃刀定律认为保持事物的简单化是对付复杂与烦琐的事情的最有效的方式。这个原理称为“如无必要，勿增实体”，即“简单有效原理”。

对结点 $②$，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为 $1,2,3,14$ 的训练样例，叶结点标记为“好瓜”。此时决策树的验证集精度提高至 $71.4\%$ 。于是，后剪枝策略决定剪枝。

对结点 $③$ 和 $①$，若将其领衔的子树替换为叶结点，则所得决策树的验证集精度分别为 $71.4\%$ 与 $42.9\%$，均未得到提高。于是它们被保留。

最终，基于后剪枝策略从表 $2$ 数据所生成的决策树如图 $5$ 黑色实线部分所示，其验证集精度为 $71.4\%$ 。

图 5    基于表 2 生成的后剪枝决策树

后剪枝的优点与缺点

对比图 $5$ 和图 $4$ 可看出，后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

总结一下剪枝处理：

无论是预剪枝还是后剪枝，都是根据训练集标定叶结点的类别，再根据验证集计算划分或剪枝前后的精度，以验证集精度作为是否进行划分或剪枝的标准。不同之处在于两种剪枝处理策略执行时机不同，预剪枝是在生成决策树的过程中判断是否进行属性划分，而后剪枝是根据选定的属性度量标准生成完全决策树后，采用后剪枝算法用叶结点替换子树。

4 连续值处理

到目前为止我们仅讨论了基于离散属性来生成决策树。现实学习任务中常会遇到连续属性，有必要讨论如何在决策树学习中使用连续属性。

由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。此时，连续属性离散化技术可派上用场。最简单的策略是采用二分法（bi-partition）对连续属性进行处理，这正是 C4.5 决策树算法中采用的机制。

给定样本集 $D$ 和连续属性 $a$，假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，将这些值从小到大进行排序，记为 { a 1 , a 2 , . . . , a n } \{a^1 , a^2,... , a^n\} {a1,a2,...,an} 。基于划分点 $t$ 可将 $D$ 分为子集 $D_t^{-}$ 和 $D_t^{+}$，其中 $D_t^{-}$ 包含那些在属性 $a$ 上取值不大于 $t$ 的样本，而 $D_t^{+}$ 则包含那些在属性 $a$ 上取值大于 $t$ 的样本，显然，对相邻的属性取值 $a^i$ 与 $a^{i+1}$ 中来说，$t$ 在区间 $[a^i,a^{i+1})$ 中取任意值所产生的划分结果相同。因此，对连续属性 $a$，我们可考察包含 $n-1$ 个元素的候选划分点集合
T a = { a i + a i + 1 2   ∣   1 ≤ i ≤ n − 1 }

Ta​={2ai+ai+1​ ∣ 1≤i≤n−1}​(9)​
即把区间 $[a^i,a^{i+1})$ 的中位点 $\frac{a^i+a^{i+1}}{2}$ 作为候选划分点。属性的取值情况被抽象成两类，一类是大于划分点，另一类是不大于划分点。然后，我们就可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。例如，可对式 $4$ 稍加改造：
G a i n ( D , a ) = max ⁡ t ∈ T a    G a i n ( D , a , t ) = max ⁡ t ∈ T a    E n t ( D ) − ∑ λ ∈ { − , + } ∣ D t λ ∣ ∣ D ∣ E n t ( D t λ )

Gain(D,a)=maxt∈Ta  Gain(D,a,t)(10)=maxt∈Ta  Ent(D)−∑λ∈{−,+}|Dtλ||D|Ent(Dtλ)" role="presentation" style="position: relative;">Gain(D,a)=maxt∈Ta  Gain(D,a,t)=maxt∈Ta  Ent(D)−∑λ∈{−,+}|Dλt||D|Ent(Dλt)(10)$$\begin{array}{rl}Gain(D,a)& =\underset{t\in T_a}{max}Gain(D,a,t)\\ \text{(10)}& & =\underset{t\in T_a}{max}Ent(D)-\sum _{\lambda \in \{-,+\}}\frac{|D_t^{\lambda }|}{|D|}Ent(D_t^{\lambda })\end{array}$$

Gain(D,a)​=t∈Ta​max​  Gain(D,a,t)=t∈Ta​max​  Ent(D)−λ∈{−,+}∑​∣D∣∣Dtλ​∣​Ent(Dtλ​)​(10)​
其中 $Gain(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益。于是，我们就可选择使 $Gain(D,a,t)$ 最大化的划分点。

可将划分点设置为该属性在训练集中出现的不大于中位点的最大值，从而使得最终决策树使用的划分点都在训练集中出现过。

作为一个例子，我们在表 $1$ 的西瓜数据集上增加两个连续属性“密度”和“含糖率”，得到表 $3$ 所示的西瓜数据集（"密度"和“含糖率”）。下面我们用这个数据集来生成一棵决策树。

表 3    西瓜数据集（“密度”和“含糖率”）

对属性“密度”，在决策树学习开始时，根结点包含的 $17$ 个训练样本在该属性上取值均不同。根据式 $(9)$，该属性的候选划分点集合包含 $16$ 个候选值： T 密度 = { 0.244 , 0.294 , 0.351 , 0.381 , 0.420 , 0.459 , 0.518 , 0.574 , 0.600 , 0.621 , 0.636 , 0.648 , 0.661 , 0.681 , 0.708 , 0.746 } T_{密度}= \{0.244,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746\} T密度​={0.244,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746} 。枚举 $T_{密度}$ 中的每个划分点，将属性值抽象成两类，计算该划分方式下的信息增益，将全部划分方式下的信息增益的最大值作为属性的信息增益。由式 $(10)$ 可计算出属性“密度”的信息增益为 $0.262$，对应于划分点 $0.381$。

对属性“含糖率”，其候选划分点集合也包含 $16$ 个候选值： T 含糖率 = { 0.049 , 0.074 , 0.095 , 0.101 , 0.126 , 0.155 , 0.179 , 0.204 , 0.213 , 0.226 , 0.250 , 0.265 , 0.292 , 0.344 , 0.373 , 0.418 } T_{含糖率}=\{0.049,0.074,0.095,0.101,0.126,0.155,0.179,0.204,0.213,0.226,0.250,0.265,0.292,0.344,0.373,0.418\} T含糖率​={0.049,0.074,0.095,0.101,0.126,0.155,0.179,0.204,0.213,0.226,0.250,0.265,0.292,0.344,0.373,0.418} 。类似的，根据式 $(10)$ 可计算出其信息增益为 $0.349$，对应于划分点 $0.126$。

再根据式 $(4)$ 计算出表 $3$ 中各离散属性的信息增益。最终全部属性的信息增益为
G a i n ( D , 色泽 ) = 0.109 ; G a i n ( D , 根蒂 ) = 0.143 ; G a i n ( D , 敲声 ) = 0.141 ; G a i n ( D , 纹理 ) = 0.381 ; G a i n ( D , 脐部 ) = 0.289 ; G a i n ( D , 触感 ) = 0.006 ; G a i n ( D , 密度 ) = 0.262 ; G a i n ( D , 含糖率 ) = 0.349.

Gain(D,色泽)=0.109;Gain(D,敲声)=0.141;Gain(D,脐部)=0.289;Gain(D,密度)=0.262;​Gain(D,根蒂)=0.143;Gain(D,纹理)=0.381;Gain(D,触感)=0.006;Gain(D,含糖率)=0.349.​
于是，“纹理”被选作根结点划分属性，此后结点划分过程递归进行，最终生成如图 $6$ 所示的决策树。

图 6    在西瓜数据集（“密度”和“含糖率”）上基于信息增益生成的决策树

需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。例如在父结点上使用了“密度 $\le 0.381$”，不会禁止在子结点上使用“密度 $\le 0.294$”。对应于算法 $1$ 中的第 $14$ 行将执行 “$以TreeGenerate(D_v,A)为分支结点$” 。

5 缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。例如由于诊测成本、隐私保护等因素，患者的医疗数据在某些属性上的取值（如HIV测试结果）未知；尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值。如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大的浪费。例如，表 $4$ 是表 $1$ 中的西瓜数据集出现缺失值的版本，如果放弃不完整样本，则仅有编号 { 4 , 7 , 14 , 16 } \{4,7,14,16\} {4,7,14,16} 的 $4$ 个样本能被使用。显
然，有必要考虑利用有缺失属性值的训练样例来进行学习。

表 4    西瓜数据集（缺失值）

我们需解决两个问题：(1) 如何在属性值缺失的情况下进行划分属性选择？(2) 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

给定训练集 $D$ 和属性 $a$，令 $\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集。对问题 (1)，显然我们可仅根据 $\tilde{D}$ 来判断属性 $a$ 的优劣。假定属性 $a$ 有 $V$ 个可取值 { a 1 , a 2 , . . . , a V } \{a^1, a^2,... , a^V\} {a1,a2,...,aV}，令 ${\tilde{D}}^v$ 表示 $\tilde{D}$ 中在属性 $a$ 上取值为 $a^v$ 的样本子集，${\tilde{D}}_k$ 表示 $D$ 中属于第 $k$ 类 $(k=1,2,...,|\mathcal{Y}|)$ 的样本子集，则显然有$\tilde{D}={\bigcup }_{k=1}^{|\mathcal{Y}|}{\tilde{D}}_k$，$\tilde{D}={\bigcup }_{v=1}^V{\tilde{D}}^v$ 。假定我们为每个样本 $xx$ 赋予一个权重 $w_{xx}$，并定义

• 无缺失值样本所占的比例

ρ = ∑ x ∈ D ~ w x ∑ x ∈ D w x

ρ=∑xx∈D​wxx​∑xx∈D ​wxx​​​(11)​

• 无缺失值样本中第 $k$ 类所占比例

p ~ k = ∑ x ∈ D ~ k w x ∑ x ∈ D ~ w x      ( 1 ≤ k ≤ ∣ Y ∣ )

p ​k​=∑xx∈D ​wxx​∑xx∈D k​​wxx​​    (1≤k≤∣Y∣)​(12)​

• 无缺失值样本中在属性 $a$ 上取值为 $a^v$ 的样本所占比例

$${\tilde{r}}_v=\frac{{\sum }_{xx\in {\tilde{D}}^v}{w}_{xx}}{{\sum }_{xx\in \tilde{D}}{w}_{xx}}(1\le v\le V)\text{\hspace{1em}(13)}$$

显然，${\sum }_{k=1}^{|\mathcal{Y}|}{\tilde{p}}_k=1$，${\sum }_{v=1}^V{\tilde{r}}_v=1$ 。

基于上述定义，我们可将信息增益的计算式 $(4)$ 推广为
G a i n ( D , a ) = ρ   ×   G a i n ( D ~ , a ) = ρ   ×   ( E n t ( D ~ ) − ∑ v = 1 V r ~ v   E n t ( D ~ v ) )

Gain(D,a)​=ρ × Gain(D ,a)=ρ × (Ent(D )−v=1∑V​r v​ Ent(D v))​(14)​
其中由式 $(3)$，有
$$Ent(\tilde{D})=-\sum _{k=1}^{|\mathcal{Y}|}{\tilde{p}}_{k}lo{g}_2{\tilde{p}}_k$$
对问题 (2)，若样本 $xx$ 在划分属性 $a$ 上的取值已知，则将 $x$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_{xx}$ 。若样本 $x$ 在划分属性 $a$ 上的取值未知，则将 $x$ 同时划入所有子结点，且样本权值在与属性值 $a^v$ 对应的子结点中调整为 ${\tilde{r}}_v\cdot w_{xx}$ ；直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

C4.5 算法使用了上述解决方案。下面我们以表 $4$ 的数据集为例来生成一棵决策树。

在学习开始时，根结点包含样本集 $D$ 中全部 $17$ 个样例，各样例的权值均为 $1$ 。以属性“色泽”为例，该属性上无缺失值的样例子集 $\tilde{D}$ 包含编号为 { 2 , 3 , 4 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 14 , 15 , 16 , 17 } \{2,3,4,6,7,8,9,10,11,12,14,15,16,17\} {2,3,4,6,7,8,9,10,11,12,14,15,16,17} 的 $14$ 个样例。显然，$\tilde{D}$ 的信息熵为
E n t ( D ~ ) = − ∑ k = 1 2 p ~ k   l o g 2 p ~ k = − ( 6 14 l o g 2 6 14 + 8 14 l o g 2 8 14 ) = 0.985

Ent(D )​=−k=1∑2​p ​k​ log2​p ​k​=−(146​log2​146​+148​log2​148​)=0.985​
令 ${\tilde{D}}^1$，${\tilde{D}}^2$ 与 ${\tilde{D}}^3$ 分别表示在属性“色泽”上取值为“青绿”“乌黑”以及“浅白”的样本子集，有
$$\begin{gathered} Ent({\tilde{D}}^1)=-\left(\frac{2}{4}lo{g}_2\frac{2}{4}+\frac{2}{4}lo{g}_2\frac{2}{4}\right)=1.000, \\ Ent({\tilde{D}}^2)=-\left(\frac{4}{6}lo{g}_2\frac{4}{6}+\frac{2}{6}lo{g}_2\frac{2}{6}\right)=0.918, \\ Ent({\tilde{D}}^3)=-\left(\frac{0}{4}lo{g}_2\frac{0}{4}+\frac{4}{4}lo{g}_2\frac{4}{4}\right)=0.000. \end{gathered}$$
因此，样本子集 $\tilde{D}$ 上属性“色泽”的信息增益为
$$Gain(D,色泽)=\rho \times Gain(\tilde{D}，色泽)=\frac{14}{17}\times 0.306=0.252$$
类似地可计算出所有属性在 $D$ 上的信息增益：
G a i n ( D , 色泽 ) = 0.252 ; G a i n ( D , 根蒂 ) = 0.171   ; G a i n ( D , 敲声 ) = 0.145 ; G a i n ( D , 纹理 ) = 0.424   ; G a i n ( D , 脐部 ) = 0.289 ; G a i n ( D , 触感 ) = 0.006   .

Gain(D,色泽)=0.252;Gain(D,根蒂)=0.171 ;Gain(D,敲声)=0.145;Gain(D,纹理)=0.424 ;Gain(D,脐部)=0.289;Gain(D,触感)=0.006 ." role="presentation" style="position: relative;">Gain(D,色泽)=0.252;Gain(D,敲声)=0.145;Gain(D,脐部)=0.289;Gain(D,根蒂)=0.171 ;Gain(D,纹理)=0.424 ;Gain(D,触感)=0.006 .$$\begin{array}{}Gain(D,色泽)=0.252;& Gain(D,根蒂)=0.171;\\ Gain(D,敲声)=0.145;& Gain(D,纹理)=0.424;\\ Gain(D,脐部)=0.289;& Gain(D,触感)=0.006.\end{array}$$

Gain(D,色泽)=0.252;Gain(D,敲声)=0.145;Gain(D,脐部)=0.289;​Gain(D,根蒂)=0.171 ;Gain(D,纹理)=0.424 ;Gain(D,触感)=0.006 .​
“纹理”在所有属性中取得了最大的信息增益，被用于对根结点进行划分。划分结果是使编号为 { 1 , 2 , 3 , 4 , 5 , 6 , 15 } \{1,2,3,4,5,6,15\} {1,2,3,4,5,6,15} 的样本进入“纹理=清晰”分支，编号为 { 7 , 9 , 13 , 14 , 17 } \{7,9,13,14,17\} {7,9,13,14,17} 的样本进入“纹理=稍糊”分支，而编号为 { 11 , 12 , 16 } \{11,12,16\} {11,12,16} 的样本进入“纹理=模糊”分支，且样本在各子结点中的权重保持为 $1$ 。需注意的是，编号为 { 8 } \{8\} {8} 的样本在属性“纹理”上出现了缺失值，因此它将同时进入三个分支中，但权重在三个子结点中分别调整为 $\frac{7}{15}$、$\frac{5}{15}$ 和 $\frac{3}{15}$ 。编号为 { 10 } \{10\} {10} 的样本有类似划分结果。

上述结点划分过程递归执行，最终生成的决策树如图 $7$ 所示。

图 7    在西瓜数据集（缺失值）上基于信息增益生成的决策树

6 多变量决策树

仅涉及基础概念。具体相关算法可以参考论文 Multivariate Decision Tree 。如果我读完，我会尝试写相关讲解。

若我们把每个属性视为坐标空间中的一个坐标轴，则 $d$ 个属性描述的样本就对应了 $d$ 维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。

以表 $5$ 中的西瓜数据（仅含“密度”和“含糖率”）为例，将它作为训练集可学得图 $8$ 所示的决策树，这棵树所对应的分类边界如图 $9$ 所示。

表 5    西瓜数据集（仅含“密度”和“含糖率”）

图 8    在西瓜数据集（仅含“密度”和“含糖率”）上生成的决策树

图 9    图 8 决策树对应的分类边界

如图 $10$ 所示；此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

若能使用斜的划分边界，如图 $10$ 中红色线段所示，则决策树模型将大为简化。“多变量决策树”（multivariate decision tree）就是能实现这样的“斜划分”甚至更复杂划分的决策树。以实现斜划分的多变量决策树为例，在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试；换言之，每个非叶结点是一个形如 ${\sum }_{i=1}^d{w}_i{a}_i=t$ 的线性分类器，其中 $w_i$ 是属性 $a_i$ 的权重，$w_i$ 和 $t$ 可在该结点所含的样本集和属性集上学得。于是，与传统的“单变量决策树”（univariate decision tree）不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。例如对西瓜数据（仅含“密度”和“含糖率”），我们可学得图 $11$ 这样的多变量决策树，其分类边界如图 $12$ 所示。

图 10    决策树对复杂分类边界的分段近似

图 11    在西瓜数据集（仅含“密度”和“含糖率”）上生成的多变量决策树

图 12    图 11 多变量决策树对应的分类边界

7 ID3、C4.5、CART

详细介绍建议参考论文。

7.1 ID3 算法

ID3 算法中选择熵减少程度最大的特征来划分数据（贪心），也就是“最大信息熵增益”原则。ID3 算法是生成决策树最基本的算法。

7.2 C4.5 算法

C4.5 算法为了解决 ID3 算法对取值较多的属性有所偏好的问题，抛弃了“最大信息增益”原则，采用了增益率。同时，利用二分法处理连续值，即上文种“连续值处理”部分所讲内容。

7.3 CART 算法

在 ID3 算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在 C4.5 算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是 ID3 还是 C4.5 都是基于信息论的熵模型的，会涉及大量的对数运算。

CART 决策树是一棵二叉树，其算法使用基尼指数来代替信息增益率，采用二分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个子结点。

对于取值离散的属性，CART 决策树在选择划分属性时，每个属性对应的基尼指数为对该属性的取值划分为两类的全部情况对应的基尼指数的最小值。对属性取值进行二分是指枚举每个取值，根据对应属性是否为该取值对样本进行二类划分，因此，属性有多少种取值情况，就有多少种二分情况，而属性的基尼指数就是这些情况对应的最小基尼指数；对于取值连续的属性，计算方式与上文讲到的“连续值处理”中的二分法一致。

REF

[1] 机器学习 - 周志华著

[2] 随机事件 - 百度百科

[3] 信息熵及其相关概念 - CSDN博客

[4] 信息熵的简单理解 - 博客园

[5] 决策树-ID3算法和C4.5算法 - CSDN博客