决策树

《统计学习方法》笔记 第5章

Posted by Cheereus on January 20, 2020

第5章 决策树

5.1 决策树模型与学习

5.1.1 决策树模型

决策树(decision tree)是一种基本的分类与回归方法。本章主要讨论用于分类的决策树,其定义为:

  • 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点(node)和右向边(directed edge)组成。节点由两种类型:内部节点(internal node)和叶节点(leaf node)。内部节点表示一个特征或属性,叶节点表示一个类。

用决策树分类,从根节点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子节点;这时,每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至到达叶节点。最后将实例节点分到叶节点的类中。

5.1.2 决策树与 if-then 规则

可以将决策树看成一个 if-then 规则的集合。将决策树转换成 if-then 规则的过程如下:

由决策树的根节点到叶节点的每一条路径构建一条规则;

路径上内部节点的特征对应着规则的条件,而叶节点的类对应着规则的结论。

决策树的路径或其对应的 if-then 规则集合具有一个重要的性质:互斥并且完备。这就是说,每一个实例都被一条路径或一条规则覆盖,而且只被一条路径或一条规则所覆盖。

5.1.3 决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分(partition)上。将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路经对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

5.1.4 决策树学习

假设给定训练数据集

其中,$x_i=(x^{(1)_i},x^{(2)_i},\cdots,x^{(n)_i})^T$ 为输入实例(特征向量),$n$ 为特征个数,$y_i \in \{1,2,\cdots,K\}$ 为类标记,$i=1,2,\cdots,N$,$N$ 为样本容量。决策树学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。

决策树学习本质上是从训练数据集中归纳出一组分类规则。从另一个角度看,决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测。

决策树学习用损失函数表示这一目标。决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。

当损失函数确定以后,学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是 NP 完全问题,所以现实中决策树学习算法通常采用启发式方法,近似求解这一最优化问题。这样得到的决策树是次最优(sub-optimal)的。

决策树学习算法包含:特征选择、决策树的生成与决策树的剪枝过程。

决策树的生成只考虑局部最优,决策树的剪枝则考虑全局最优。

5.2 特征选择

5.2.1 特征选择问题

特征选择在于选取对训练数据具有分类能力的特征,这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的,经验上扔掉这样的特征对决策树学习的精度影响不打。

通常特征选择的准则是信息增益或信息增益比。

5.2.2 信息增益

在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量。设 $X$ 是一个取有限个值的离散随机变量,其概率分布为:

则随机变量 $X$ 的熵定义为:

其中,若 $p_i=0$ 则定义 $0\log 0 = 0$。通常此式中的对数以 $2$ 为底或以 $e$ 为底,这时熵的单位分别称作比特(bit)或者纳特(nat)。由定义可知,熵只依赖于 $X$ 的分布,而与 $X$ 的取值无关,所以也可将 $X$ 的熵记作 $H(p)$,即:

熵越大,随机变量的不确定性就越大。从定义可验证:

当随机变量只取两个值,例如 $1, 0$,即 $X$ 的分布为:

熵为:

当 $p=0$ 或 $p=1$ 时 $H(p)=0$,随机变量完全没有不确定性。当 $p=0.5$ 时 $H(p)=1$,熵取值最大,随机变量不确定性最大。

设有随机变量 $(X,Y)$,其联合概率分布为:

条件熵 $H(Y \vert X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。随机变量 $X$ 给定的条件下随机变量 $Y$ 的条件熵(conditional entropy) $H(Y \vert X)$,定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望:

其中 $p_i=P(X=x_i),i=1,2,\cdots,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)$ 之差,即:

一般地,熵 $H(Y)$ 与条件熵 $H(Y \vert X)$ 之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

根据信息增益准则的特征选择方法是:对训练数据集或子集 $D$,计算其每个特征的信息增益,并比较他们的大小,选择信息增益最大的特征。

设训练数据集为 $D$,$\vert D \vert$ 表示其样本容量,即样本个数。设有 $K$ 个类 $C_k,k=1,2,\cdots,K, \ \vert C_k \vert$ 为属于类 $C_k$ 的样本个数,$\displaystyle\sum_{k=1}^K \vert C_k \vert = \vert D \vert$。设特征 $A$ 有 $n$ 个不同的取值 $\{a_1,a_2,\cdots,a_n\}$,根据特征 $A$ 的取值将 $D$ 划分为 $n$ 个子集 $D_1,D_2,\cdots, D_n, \ \vert D_i \vert$ 为 $D_i$ 的样本个数,$\displaystyle\sum_{i=1}^n \vert D_i \vert = \vert D \vert$。记子集 $D_i$ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$,即 $D_{ik}=D_i \cap C_k$,$\vert D_{ik} \vert$ 为 $D_{ik}$ 的样本个数。于是信息增益的算法如下:

输入:训练数据集 $D$ 和特征 $A$;

输出:特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$。

(1) 计算数据集 $D$ 的经验熵 $H(D)$

(2) 计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D \vert A)$

(3) 计算信息增益

5.2.3 信息增益比

以信息增益作为划分训练数据集的特征,存在偏向于取值较多的特征的问题。使用信息增益比(information gain ratio)可以对这一问题进行校正。信息增益比的定义为:

特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征 $A$ 的值的熵 $H_A(D)$ 之比,即:

其中,$H_A(D)=-\displaystyle\sum \frac{\vert D_i \vert}{D} \log_2 \frac{\vert D_i \vert}{D}$,$n$ 是特征 $A$ 取值的个数。

5.3 决策树的生成

5.3.1 ID3 算法

ID3 算法的核心是在决策树各个节点上应用信息增益准则选择特征,递归地构建决策树。

输入:训练数据集 $D$,特征集 $A$ 阈值 $\epsilon$;

输出:决策树 $T$。

(1) 若 $D$ 中所有实例属于同一类 $C_k$,则 $T$ 为单节点树,并将类 $C_k$ 作为该节点的类标记,返回 $T$;

(2) 若 $A=\emptyset$,则 $T$ 为单节点树,并将 $D$ 中实例数最大的类 $C_k$ 作为该节点的类标记,返回 $T$;

(3) 否则,按信息增益算法计算 $A$ 中各特征对 $D$ 的信息增益,选择信息增益最大的特征 $A_g$;

(4) 如果 $A_g$ 的信息增益小于阈值 $\epsilon$,则置 $T$ 为单节点树,并将 $D$ 中实例数最大的类 $C_k$ 作为该节点的类标记,返回 $T$;

(5) 否则,对 $A_g$ 的每一可能值 $a_i$,依 $A_g=a_i$ 将 $D$ 分割为若干非空子集 $D_i$,将 $D_i$ 中实例数最大的类作为标记,构建子节点,由节点及其子节点构成树 $T$,返回 $T$;

(6) 对第 $i$ 个子节点,以 $D_i$ 为训练集,以 $A-\{A_g\}$ 为特征集,递归地调用步 (1)~(5),得到子树 $T_i$,返回 $T_i$。

5.3.2 C4.5 的生成算法

C4.5 算法与 ID3 算法相似,但进行了改进,在生成的过程中,用信息增益比来选择特征。

输入:训练数据集 $D$,特征集 $A$ 阈值 $\epsilon$;

输出:决策树 $T$。

(1) 如果 $D$ 中所有实例属于同一类 $C_k$,则置 $T$ 为单节点树,并将 $C_k$ 作为该节点的类,返回 $T$;

(2) 如果 $A=\emptyset$,则置 $T$ 为单节点树,并将 $D$ 中实例数最大的类 $C_k$ 作为该节点的类,返回 $T$;

(3) 否则,按信息增益比的定义计算 $A$ 中各特征对 $D$ 的信息增益比,选择信息增益比最大的特征 $A_g$;

(4) 如果 $A_g$ 的信息增益比小于阈值 $\epsilon$,则置 $T$ 为单节点树,并将 $D$ 中实例数最大的类 $C_k$ 作为该节点的类,返回 $T$;

(5) 否则,对 $A_g$ 的每一可能值 $a_i$,依 $A_g=a_i$ 将 $D$ 分割为若干非空子集 $D_i$,将 $D_i$ 中实例数最大的类作为标记,构建子节点,由节点及其子节点构成树 $T$,返回 $T$;

(6) 对第 $i$ 个子节点,以 $D_i$ 为训练集,以 $A-\{A_g\}$ 为特征集,递归地调用步 (1)~(5),得到子树 $T_i$,返回 $T_i$。

5.4 决策树的剪枝

在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning)。决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。决策树学习的损失函数可以定义为:

其中,$C(T)$ 表示模型对训练数据的预测误差,即模型与训练数据的拟合程度,$\vert T \vert$ 表示模型复杂度,参数 $\alpha \geq 0$ 控制两者之间的影响。

剪枝,就是当 $\alpha$ 确定时,选择损失函数最小的模型,即损失函数最小的子树。

树的剪枝算法如下:

输入:生成算法产生的整个树 $T$,参数 $\alpha$;

输出:修剪后的子树 $T_\alpha$

(1) 计算每个节点的经验熵。

(2) 递归地从树的叶节点向上回缩。

设一组叶节点回缩到其父节点之前与之后的整体树分别为 $T_B$ 与 $T_A$,其对应的损失函数值分别是 $C_\alpha(T_B)$ 与 $C_\alpha(T_A)$,如果

则进行剪枝,即将父节点变为新的叶节点。

(3) 返回(2),直至不能继续位置,得到损失函数最小的子树 $T_\alpha$。

5.5 CART 算法

分类与回归树(classification and regression tree,CART)模型是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART 假设决策树是二叉树,内部节点的特征取值为“是”和“否”,左分支取值为“是”,右分支取值为“否”。这样的决策树等价于递归地二分每个特征,将输入空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布。

CART 算法由以下两步组成:

(1) 决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大;

(2) 决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准。

5.5.1 CART 生成

1. 回归树的生成 - 最小二乘回归树算法

输入:训练数据集 $D$;

输出:回归树 $f(x)$。

在训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二叉决策树:

(1) 选择最优切分变量 $j$ 与切分点 $s$,求解

遍历变量 $j$,对固定的切分变量 $j$ 扫描切分点 $s$,选择使上式达到最小值的对 $(j,s)$。

(2) 用选定的对 $(j,s)$ 划分区域并决定相应的输出值:

(3) 继续对两个子区域调用步骤(1),(2),直至满足停止条件。

(4) 将输入空间划分为 $M$ 个区域 $R_1,R_2,\cdots,R_M$,生成决策树:

2. 分类树的生成

分类树用基尼指数选择最优特征,同时决定该特征的最优二值切分点。

分类问题中,假设有 $K$ 个类,样本点属于第 $k$ 类的概率为 $p_k$,则概率分布的基尼指数定义为

对于二分类问题,若样本点属于第 1 个类的概率是 $p$,则概率分布的基尼指数为

对于给定的样本集合 $D$,其基尼指数为

这里,$C_k$ 是 $D$ 中属于第 $k$ 类的样本子集,$K$ 是类的个数。

如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分,即

则在特征 $A$ 的条件下,集合 $D$ 的基尼指数定义为

基尼指数 $\text{Gini}(D)$ 表示集合 $D$ 的不确定性,基尼指数 $\text{Gini}(D,A)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数越大,样本集合的不确定性也就越大,这一点与熵相似。

CART 生成算法

输入:训练数据集 $D$,停止计算的条件;

输出:CART 决策树。

(1) 设节点的训练数据集为 $D$,计算现有特征对该数据集的基尼指数。此时,对每一个特征 $A$,对其可能取的每个值 $a$,根据样本点对 $A=a$ 的测试为“是”或“否”将 $D$ 分割成 $D_1$ 和 $D_2$ 两部分,计算 $A=a$ 时的基尼指数。

(2) 在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点,从现节点生成两个子节点,将训练数据集依特征分配到两个子节点中去。

(3) 对两个子节点递归地调用 (1),(2) 直至满足停止条件。

(4) 生成 CART 决策树。

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

5.5.2 CART 剪枝

输入:CART 算法生成的决策树 $T_0$;

输出:最优决策树 $T_\alpha$。

(1) 设 $k=0,\ T=T_0$。

(2) 设 $\alpha = + \infty$。

(3) 自上而下地对各内部节点 $t$ 计算 $C(T_t), \ \vert T_t \vert$ 以及

这里,$T_t$ 表示以 $t$ 为根节点的子树,$C(T_t)$ 是对训练数据的预测误差, $\vert T_t \vert$ 是 $T_t$ 的叶节点个数。

(4) 对 $g(t)=\alpha$ 的内部节点 $t$ 进行剪枝,并对叶节点 $t$ 以多数表决法决定其类,得到树 $T$。

(5) 设 $k=k+1, \ \alpha_k=\alpha, \ T_k=T$。

(6) 如果 $T_k$ 不是由根节点及两个叶节点构成的树,则回到步骤 (2);否则令 $T_k=T_n$。

(7) 采用交叉验证法在子树序列 $T_0,T_1,\cdots,T_n$ 中选取最优子树 $T_\alpha$。

第5章完结