统计学习方法第五章决策树

决策树（decision tree）是一种基本的分类与回归方法。其主要优点是模型具有可读性，分类速度快。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。

5.1 决策树模型与学习

5.1.1 决策树模型

定义 5.1 （决策树）分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）和叶节点（leaf node）。内部节点表示一个特征或属性，叶节点表示一个类。

5.1.2 决策树学习

假设给定训练数据集

$$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$$

其中输入实例（向量）为

$$x_i=\left(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)}\right)$$

$n$ 为特征个数。类标记为

$$y_i\in\{c_1,c_2,\cdots,c_K\}$$

其中 $i\in\{1,2,\cdots,N\}$，$N$ 为样本容量。

学习的目的是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练集不相矛盾的决策树可能有多个也可能一个也没有，我们需要的是一个与训练集矛盾较小的决策树，同时具有很好的泛化能力。

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

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

5.2 特征选择

5.2.1 特征选择的问题

特征选择在于选取对训练数据具有分类能力的特征。这样就可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选取的准则是信息增益或信息增益比。

5.2.2 信息增益

为了便于说明，首先给出熵与条件熵的定义。

熵（entropy）是表示随机变量不确定性的度量。

设 $X$ 是一个离散随机变量，其概率分布为

$$P(X=x_i)=p_i,i=1,2,\cdots,n$$

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

$$H(X)=-\sum_{i=1}^np_i\log p_i$$

若 $p_i=0$，定义 $0\log0=0$。通常，上式中对数的底为 2 或自然对数 e，这时熵的单位分别为比特（bit）或纳特（nat）。

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

$$P(X=x_i,Y=y_j)=p_{ij},i=1,2,\cdots,n;j=1,2,\cdots,m$$

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

$$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$$

这里 $p_i=P(X=x_i),i=1,2,\cdots,n$

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。

信息增益（information gain）表示得知特征 $X$ 的信息而使类 $Y$ 的信息的不确定度减少的程度。

定义 5.2 （信息增益）特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A）$之差

$$g(D,A)=H(D)-H(D|A)$$

一般的，熵与条件熵之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类和特征的互信息。

根据信息增益准则的特征选择方法是：对训练数据集（或子集）$D$，计算其每个特征的信息增益，选择信息增益最大的特征。

设训练数据集为 $D$，$|D|$ 表示其样本容量。设有 $K$ 个类 $C_k$，$k=1,2\cdots,K$，$|C_k|$ 为属于类 $C_k$ 的样本个数。设特征 $A$ 有 $n$ 个不同的取值，根据特征 $A$ 的取值将 $D$ 划分为 $n$ 个子集，$|D_i|$ 为 $D_i$ 的样本个数。记子集 $D_i$ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$，$|D_{ik}|$ 为 $D_{ik}$ 的样本个数，于是信息增益的算法如下

算法 5.1 （信息增益的算法）
输入：训练数据集 $D$ 和特征 $A$
输出：特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$
(1) 计算数据集 $D$ 的经验熵 $H(D)$

$$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}$$

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

$$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}$$
(3) 计算信息增益
$$g(D,A)=H(D)-H(D|A)$$

5.2.3 信息增益比

以信息增益作为划分训练集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。这是特征选择的另一准则。

首先说明下为何信息增益会偏向选择取值较多的特性：假设特征 $A$ 有 $N$ 个不同取值（意味着每一个样本的特征 $A$ 都有一个不同的值），则易知 $H(D|A)=0$，故一定会选取这个特性，但是这个特性（例如仅仅是不同训练数据的标号）可能对分类无用。

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

$$g_R(D,A)=\frac{g(D,A)}{H_A{(D)}}$$

其中
$$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}$$
$n$ 是特征 $A$ 取值的个数。

5.3 决策树的生成

5.3.1 ID3 算法

ID3 算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归的构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止。

算法 5.2 （ID3 算法）
输入：训练数据集 $D$，特征集 $A$，阈值 $\epsilon$
输出：决策树 $T$
(1) 若 $D$ 中所有实例属于同一类 $C_k$，则 $T$ 为单节点树，并将类 $C_k$ 作为该节点的类标记，返回 $T$
(2) 若 $A=\varnothing$，则 $T$ 为单节点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该节点的类标记，返回 $T$
(3) 否则，按算法 5.1 计算 $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$

ID3 算法只有树的生成。所以该算法生成的树容易产生过拟合。

5.3.2 C4.5 的生成算法

C4.5 算法与 ID3 算法相似，C4.5 算法对 ID3 算法进行了改进，用信息增益比选择特征。其他步骤相同。

5.4 决策树的剪枝

决策树生成算法递归的产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。

过拟合产生的原因是学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。

解决这个问题的办法是对已生成的决策树进行简化——剪枝（pruning）。也就是从生成的决策树上剪掉一些子树或者叶节点。

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

设树 $T$ 的叶节点个数为 $|T|$，$t$ 是树 $T$ 的叶节点，该叶节点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个，$k=1,2,\cdots,K$，$H_t(T)$ 为叶节点 $t$ 上的经验熵， $\alpha\geq0$ 为参数，则决策树学习的损失函数可以定义为

$$C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$$

其中经验熵为

$$H_t(T)=-\sum_{k=1}^K\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t}$$

令

$$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log\frac{N_{tk}}{N_t}$$

则

$$C_\alpha(T)=C(T)+\alpha|T|$$

上式中，$C(T)$ 表示模型对训练数据的预测误差，$|T|$ 表示模型复杂度，参数 $\alpha\geq0$ 控制两者之间的影响。

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

决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

上式中定义的损失函数的极小化等价于正则化的极大似然估计。即

$$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log\frac{N_{tk}}{N_t}=-\log\prod_{t=1}^{|T|}\prod_{k=1}^{K}\left(\frac{N_{tk}}{N_t}\right)^{N_{tk}}$$

所以，利用损失函数最小原则进行剪枝就是用正则化的最大似然估计进行模型选择。

算法 5.4 （树的剪枝算法）
输入：生成算法产生的整个树 $T$，参数 $\alpha$
输出：修剪后的子树 $T_\alpha$
(1) 计算每个节点的经验熵
(2) 递归的从树的叶节点向上回缩：设一组叶节点回缩到其父节点之前与之后的整体树分别为 $T_B$ 和 $T_A$，其对应的损失函数分别是 $C_\alpha(T_B)$ 和 $C_\alpha(T_A)$，如果

$$C_\alpha(T_A)\leq C_\alpha(T_B)$$

则进行剪枝，即将父节点变为新的叶节点
(3) 返回 (2)，直至不能继续为止，得到损失函数最小的子树 $T_\alpha$

因为步骤 (2) 中只考虑两个树的损失函数的差，其计算可以在局部进行，所以可以用动态规划算法实现。

5.5 CRAT 算法

分类与回归树（classification and regression tree）模型是应用广泛的决策树学习方法，既可以用于分类也可以用于回归。

CART 是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART 假设决策树是二叉树，内部节点特征的取值为“是”和“否”。左分的取值是“是”，右分支的取值是“否”。

CRAT 算法由以下两步组成：

决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准

5.5.1 CART 生成

决策树的生成就是递归的构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。

回归树的生成

假设 $X$ 和 $Y$ 分别为输入和输出变量，并且 $Y$ 是连续变量，给定训练数据集

$$D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$$

一个回归树对应着输入空间（特征空间）的一个划分以及在划分的单元上的输出值。假设已经将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots,R_M$，并且每个单元 $R_m$ 上有一个固定的输出值 $c_m$，于是，回归树模型可表示为

$$f(x)=\sum_{m=1}^Mc_m\mathbb{I}(x\in R_m)$$

当输入空间的划分确定时，可以用平方误差

$$\sum_{x_i\in R_m}\left(y_i-f(x_i)\right)^2$$

来表示回归树对于训练数据集的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。

易知，单元 $R_m$ 上的 $c_m$ 的最优值 $\hat{c}_m$ 是 $R_m$ 上所有输入实例 $x_i$ 对于的输出 $y_i$ 的均值，即

$$\hat{c}_m=\text{ave}(y_i|x_i\in R_m)$$

问题是怎么对输入空间进行划分。

这里采用启发式的方法，选择第 $j$ 个特征 $x^{(j)}$ 和它的取值 $s$，作为切分变量（splitting variable）和切分点（splitting point），并定义两个区域

$$\begin{eqnarray} R_1(j,s) &=& \{x|x^{(j)}\leq s\} \\ R_2(j,s) &=& \{x|x^{(j)}>s\} \end{eqnarray}$$

然后对于固定的 $j$ 可以找到最优切分的 $s$，具体的，求解

$$\min_{j,s}\left[\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\right]$$

历遍所有输入变量，找到最优的切分变量 $j$，构成一个对 $(j,s)$。依次将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这种方法生成的回归树通常称为最小二乘回归树（least squares regression tree）。

算法 5.5 （最小二乘回归树生成算法）
输入：训练数据集 $D$
输出：回归树 $f(x)$
在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域的输出值，构建二叉决策树
(1) 选择最优切分变量 $j$ 和切分点 $s$，求解

$$\min_{j,s}\left[\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\right]$$

遍历 $j$，对固定的切分变量 $j$ 扫描切分点 $s$，选择使上式最小的对 $(j,s)$
(2) 用选定的对 $(j,s)$ 划分区域并决定相应的输出值
$$\begin{eqnarray} R_1(j,s) &=& \{x|x^{(j)}\leq s\} \\ R_2(j,s) &=& \{x|x^{(j)}>s\} \end{eqnarray}\\ \hat{c}_m=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i,x\in R_m,m=1,2$$
(3) 继续对两个子区域调用步骤 (1)，(2)，直到满足停止条件
(4) 将输入空间划分为 $M$ 个区域 $R_1,R_2,\cdots,R_M$，生成决策树
$$f(x)=\sum_{m=1}^M\hat{c}_m\mathbb{I}(x\in R_m)$$

分类树的生成

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

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

$$\text{Gini}(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$$

对于二分类问题，若样本点属于第一个类的概率是 $p$，则概率分布的基尼指数为
$$\text{Gini}(p)=2p(1-p)$$

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

$$\text{Gini}(D)=1-\sum_{k=1}^K\left(\frac{|C_k|}{|D|}\right)^2$$

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

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

$$D_1=\{(x,y)\in D|A(x)=a\},D_2=D-D_1$$

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

$$\text{Gini}(D,A)=\frac{|D_1|}{|D|}\text{Gini}(D_1)+\frac{|D_2|}{|D|}\text{Gini}(D_2)$$

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

算法 5.6 （CART 生成算法）
输入：训练数据集 $D$，停止计算的条件
输出：CART 决策树
根据训练数据集，从根节点开始，递归的对每个节点进行以下操作，构建二叉决策树：
(1) 设节点的训练数据集为 $D$，计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$，对其可能取的每个值 $a$，根据样本点对 $A=a$ 的测试为“是”或“否”将 $D$ 分割为两部分，计算 $A=a$ 时的基尼指数
(2) 在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征和最优切分点。依最优特征和最优切分点，从现节点生成两个子节点，将训练数据集依特征分配到两个子节点去
(3) 对两个子节点递归的调用 (1)、(2)，直至满足停止条件
(4) 生成 CART 决策树

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

5.5.2 CART 剪枝

CART 剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小（模型变简单），从而能够对未知数据有更准确的预测。

CART 剪枝算法由两步组成：

从生成算法产生的决策树 $T_0$ 底部开始不断剪枝，直到 $T_0$ 的根节点，行成一个子树序列
$$\{T_0,T_1,\cdots,T_n\}$$
通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树

剪枝，形成一个子树序列

在剪枝过程中，计算子树的损失函数：

$$C_\alpha(T)=C(T)+\alpha|T|$$

其中，$T$ 为任意子树，$C(T)$ 为对训练数据的预测误差（如基尼指数），$|T|$ 为子树的叶节点个数，$\alpha\geq0$ 为参数，$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\to+\infty$ 时，根节点组成的单节点树是最优的。

Breiman 等人证明：可以用递归的方法对树进行剪枝.将 $\alpha$ 从小增大：

$$0=\alpha_0<\alpha_1<\cdots<\alpha_n<+\infty$$

产生一系列的区间：

$$[\alpha_i,\alpha_{i+1}),i=0,1,\cdots,n$$

剪枝得到的子树序列对应着区间 $\alpha\in[\alpha_i,\alpha_{i+1}),i=0,1,\cdots,n$ 的最优子树序列：

$$\{T_0,T_1,\cdots,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|T_t|$$

当 $\alpha=0$ 及 $\alpha$ 充分小时，有不等式

$$C_\alpha(T_t)<C_\alpha(t)$$

当 $\alpha$ 增大时，在某一 $\alpha$ 有

$$C_\alpha(T_t)=C_\alpha(t)$$

当 $\alpha$ 再增大时，有

$$C_\alpha(T_t)>C_\alpha(t)$$

综上所述，只要

$$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$$

则 $T_t$ 与 $t$ 有相同的损失函数值，而 $t$ 的节点少，对 $T_t$ 进行剪枝。

所以，对 $T_0$ 中每一内部节点 $t$，计算

$$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$$

它表示剪枝后整体损失函数减少的程度。在 $T_0$ 中剪去 $g(t)$ 最小的 $T_t$（这里我们是要得到一系列的 $\alpha$ 区间，所以是剪去最小的），将得到的子树作为 $T_1$，同时将最小的 $g(t)$ 设为 $\alpha_1$。$T_1$ 为区间 $[\alpha_1,\alpha_2)$ 的最优子树。

如此剪枝下去，直到得到根节点。在这一过程中，不断的增加 $\alpha$ 的值，产生新的区间。

在剪枝得到的子树序列中通过交叉验证选取最优子树 $T_\alpha$

具体的，利用独立的验证数据集，测试子树序列中各棵子树的平方误差或基尼指数。平方误差或基尼指数小的决策树被认为是最优的决策树。

算法 5.7 （CART 剪枝算法）
输入：CART 算法生成的决策树 $T_0$
输出：最优决策树 $T_\alpha$
(1) 设 $k=0,T=T_0$
(2) 设 $\alpha=+\infty$
(3) 自下而上的对各个内部节点 $t$ 计算 $C(T_t)$，$|T_t|$ 以及

$$\begin{eqnarray} g(t) &=& \frac{C(t)-C(T_t)}{|T_t|-1} \\ \alpha &=& \min(\alpha,g(t)) \end{eqnarray}$$

这里，$T_t$ 表示以 $t$ 为根节点的子树，$C(T_t)$ 是对训练数据的预测误差，$|T_t|$ 是 $T_t$ 的叶节点个数
(4) 对 $g(t)=\alpha$ 的内部节点 $t$ 进行剪枝，并对叶节点 $t$ 以多数表决法决定其类，得到树 $T$
(5) 设 $k=k+1.\alpha_k=\alpha,T_k=T$
(6) 如果 $T_k$ 不是由根节点及两个叶节点构成的树，则返回到步骤 (3)；否则，令 $T_k=T_n$
(7) 采用交叉验证法在子树序列 $T_0,T_1,\cdots,T_n$ 中选择最优子树 $T_\alpha$

统计学习方法第五章决策树

5.1 决策树模型与学习

5.1.1 决策树模型

5.1.2 决策树学习

5.2 特征选择

5.2.1 特征选择的问题

5.2.2 信息增益

5.2.3 信息增益比

5.3 决策树的生成

5.3.1 ID3 算法

5.3.2 C4.5 的生成算法

5.4 决策树的剪枝

5.5 CRAT 算法

5.5.1 CART 生成

回归树的生成

分类树的生成

5.5.2 CART 剪枝

剪枝，形成一个子树序列

在剪枝得到的子树序列中通过交叉验证选取最优子树 \(T_\alpha\)

发布日期

最后更新

分类

标签

5.1 决策树模型与学习

5.1.1 决策树模型

5.1.2 决策树学习

5.2 特征选择

5.2.1 特征选择的问题

5.2.2 信息增益

5.2.3 信息增益比

5.3 决策树的生成

5.3.1 ID3 算法

5.3.2 C4.5 的生成算法

5.4 决策树的剪枝

5.5 CRAT 算法

5.5.1 CART 生成

回归树的生成

分类树的生成

5.5.2 CART 剪枝

剪枝，形成一个子树序列

在剪枝得到的子树序列中通过交叉验证选取最优子树 \(T_\alpha\)

发布日期

最后更新

分类

标签

5.2.2 信息增益

5.3.1 ID3 算法