决策树

决策树是一种基本的分类与回归方法，这里讨论的分类决策树是基于特征对实例进行分类的树形结构。可以看做一组if-then规则的集合。学习步骤：特征选择、生成决策树、剪枝。

决策树的结点有两种：内部结点表示一个特征或属性；叶结点表示一个类。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。上述过程只能对已有的训练数据有较好的分类能力，但可能发生过拟合，可以对生成的树进行自下而上的剪枝，提高泛化能力。

剪枝就是去掉过于细分的叶子结点，使其回退到父结点，然后将其改为新的叶结点。

决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。换言之，决策树的生成只考虑局部最优，而决策树的剪枝则考虑全局最优。

特征选择

特征选择是决定用哪个特征来划分特征空间，ID3算法使用信息增益作为准则，而C4.5算法使用信息增益比作为准则。

信息增益

定义一个概率分布为

的离散随机变量的$X$的熵为

熵只依赖于随机变量的分布，而与其取值无关。

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

随机变量$X$给定的条件下随机变量$Y$的条件熵$H(Y|X)$定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望

这里

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

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

决策树学习中的信息增益等价于训练数据集中类与特征的互信息

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

信息增益的算法

设训练数据集为$D$，$|D|$表示其样本容量。设有$K$个类$C_k$，$k=1,2,\cdots,K$，$|C_k|$为属于类$C_k$的样本个数，$\sum^K_{k=1}|C_k|=|D|$。设特征$A$有$n$个不同的取值${a_1,a_2,\cdots,a_n}$，根据特征$A$的取值将$D$划分为$n$个子集$D_1,D_2\cdots,D_n$，$|D_i|$为$D_i$的样本个数，$\sum^n_{i=1}|D_i|=|D|$。记子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$，即$D_{ik}=D_i\cap C_k$，$|D_{ik}|$为$D_{ik}$的样本个数

输入：训练数据集$D$和特征$A$；

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

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

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

  3. 计算信息增益

    例题

image-20240202135625759

以此数据集为例介绍计算过程：

  1. 计算整个数据集$D$的经验熵$H(D)$：

    其中$|D|$表示该数据集的样本容量，即$15$，$C_k$表示被划分成多少个类别，根据最后一列可以知道划分成了两个类：是与否。因此$|C_k|=2,k=1,2$，并且可知数据集中$9$个样本为 是​，$6$个样本为 否

    故

  2. 计算各个特征对数据集$D$的信息增益，由表知共有四个特征，分别以$A_1,A_2,A_3,A_4$​表示年龄、有工作、有自己的房子和信贷情况四个特征。其中每个特征的每个取值将数据集划分成$|A_i|$个子集，如$A_1$有青年、中年、老年三个取值，将数据集划分为三部分$D_1,D_2,D_3$，每个子集都有类别的 是 与 否 两个取值，由此可以计算经验条件熵

    以$A_1$为例：一共有青年、中年、老年三个取值，将数据集划分为三个子集，每个取值都对应五个样本，故

    对于值取青年的子集$D_1$，其五个元素所属类别取值有$2$个取值为 是，$3$个取值为 否

下同

计算个特征对数据集$D$的信息增益：

其他特征计算略，最后发现特征$A_3$（有自己的房子）信息增益最大，所以选择$A_3$作为最优特征。

信息增益比

信息增益准则更倾向于选择取值较多的特征，使用信息增益比可以矫正这个问题

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

其中

$n$是特征$A$​取值的个数。

生成决策树

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$。

例题

依旧是这个训练集

image-20240202135625759

由之前的计算知特征$A_3$的信息增益最大，所以选择特征 “有自己的房子” 作为根结点的特征。根据$A_3$取值的是与否将数据集$D$划分为两个子集$D_1$、$D_2$。$D_1$中只有同一类的样本点（类别取值全为”是”），故称为叶结点，类标记为”是”。

对于$D_2$​，递归地进行信息增益的计算，选择信息增益最大的特征作为子树的根结点并根据取值进行划分，最后可以生成如下所示的决策树

ID3算法生成的树很容易产生过拟合

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$。

剪枝

上面的算法都是递归地产生决策树，往往对训练数据的分类很准确，但容易出现过拟合，且会过于复杂。对其进行简化的过程称为剪枝。往往通过极小化决策树整体的损失函数或代价函数来实现。

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

其中经验熵为

在损失函数中，记预测误差$C(T)$为

也就是损失函数的右侧第一项，这时有

参数解释：$C(T)$表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，$|T|$表示模型复杂度，参数$\alpha\ge0$控制两者之间的影响。较大的$\alpha$促使选择较简单的模型（树），相反则促使选择较复杂的模型（树）。$\alpha=0$时，意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。剪枝则是当$\alpha$​确定时，选择损失函数最小的树。

剪枝算法

输入：生成算法产生的整个树$T$，参数$\alpha$；

输出：修建后的子树$T_\alpha$。

  1. 计算每个节点的经验熵

  2. 递归地从树的叶结点向上回缩

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

    则进行剪枝，即将父结点变为新的叶结点

  4. 返回第二步，直到不能继续执行为止，得到损失函数最小的子树$T_\alpha$

CART算法

分类与回归树（Classification And Regression Tree, CART）同样由特征选择、生成决策树和剪枝三个步骤组成。这里对分类树使用基尼系数最小化准则，生成的是一个二叉树

CART生成

生成回归树

假设回归树将输入空间划分为$M$个单元$R_1,R_2,\cdots,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，于是回归树模型可表示为

使用平方误差作为回归树队训练数据的预测误差，则训练准则便是平方误差最小化求解每个单元上的最优输出值。单元$R_m$上的$c_m$的最优值$\hat{c}_m$是$R_m$上的所有输入实例$x_i$对应的输出$y_i$的均值，即

对输入空间的划分采用启发式的方法，选择第$j$各变量$x^{(j)}$和它取的值$s$作为切分变量和切分点。根据切分点划分为两个区域：

求解如下表达式寻找最优切分变量$j$和最优切分点$s$：

生成分类树

CART分类树使用基尼指数选择最优特征：

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

对于二类分类问题，若样本点属于第一个类的概率是$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决策树

例题

还是这个数据集

image-20240202135625759

对于特征$A_1$，有三个取值（青年、中年、老年），记为$A_{11},A_{12},A_{13}$，计算基尼系数

系数解释：特征”年龄”是否取值”青年”将数据集分为$D_1$（是青年，样本数为$5$）和$D_2$（不是青年，样本数为$10$），然后分别对子集求基尼系数

这里对于类标记来说，$D_1$有两个样本为”是”，概率为$\dfrac{2}{5}$代入公式即得。对于其他依次计算即可。另外需要注意的是，如果某个特征只有两个取值，则只有一个切分点，也即其两个取值的基尼指数相同。

找到所有特征的所有取值中最小基尼系数的特征作为最优特征，其取值作为最优切分点。根结点由此生成两个子结点，其中一个为叶结点。对另一个结点继续计算剩余特征的基尼系数，找出最优特征和最优切分点。

如果计算正确，本题生成的决策树和ID3算法生成的决策树相同

CART剪枝算法

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

输出：最优决策树$T_\alpha$

  1. 设$k=0$，$T=T_0$

  2. 设$\alpha=+\infty$

  3. 自下而上地对各内部结点$t$计算$C(T_t)$，$|T_t|$以及

    这里$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$不是由根结点及两个叶结点构成的树，则回到步骤2；否则令$T_k=T_n$

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

总结

ID3

信息增益的计算：

其中$H(D)$表示数据集的经验熵

$H(D|A)$表示数据集对特征A的经验条件熵

C4.5

信息增益比的计算：

其中

$n$是特征$A$​取值的个数。

CART

基尼指数计算

每个特征值都是根据是否取值将原数据集分为两类