分类树

发表于 更新于
Classification trees

之前课程中讨论的分类方法，例如 LDA 和 SVM，将数据视为实值和离散值数字的特征向量，并且向量之间存在自然的距离度量。

然而，在某些应用中，分类问题涉及名义数据，其定义为用于命名或标记变量的数据，没有任何定量值。例如，对于变量“交通方式”，它可以采用“火车”、“汽车”、“航空”、“海运”等值。在这种情况下，传统的基于距离度量的分类器可能无法很好地工作。为了解决涉及名义数据的模式分类问题，我们可以使用非度量方法，例如分类树。

什么是分类树？

如上所示，分类树是一种具有树结构的流程图。它通过一系列问题对模式进行分类。

此类问题序列在节点处提出，按照惯例，根节点位于顶部，通过连续（定向）链接或分支连接到其他节点，直到我们到达终端或叶节点，这些节点没有进一步的链接，并带有类标签。

在每个节点处提出的问题涉及样本的特定属性（即特征或属性）。所有问题都以“是/否”或“真/假”或“值（属性）是一组值的一个元素”的形式提出。

分类树的好处

简单的分类树说明了树的好处：可解释性。这种可解释性有两种表现形式：

  1. 我们可以轻松地将任何测试数据的决策解释为沿其对应叶节点的路径的决策的结合。 例如，如果属性是{口味，颜色，形状，大小}，则数据x = {甜，黄色，薄，中等}将被归类为香蕉，因为它是（颜色=黄色）和（形状=薄）。
  2. 分类树提供了一种自然的方式来整合来自人类专家的先验知识

如何构建分类树？

现在我们来讨论关键问题：如何使用训练数据来创建分类树？

我们假设我们有一组标记的训练数据D，并且我们知道可以用来区分模式的属性集，但我们不知道如何将它们组织成树。

要构建分类树，基本上我们需要回答以下问题：

  1. 属性（即特性/特征）是否应限制为二值或允许多值？即每个节点有多少个分割？
  2. 节点应使用哪个属性？
  3. 何时应将节点声明为叶节点？
  4. 如果树变得“太大”，如何使其更小更简单，即修剪？
  5. 如果叶节点不纯，应如何分配类别标签？

每个节点的分裂次数

每个节点都会提出一个或多个问题，这些问题会分割训练数据的一个子集。根节点会分割整个训练集；每个后续节点会分割数据的一个子集。

节点的分割数与问题1密切相关，指定在节点上进行哪种特定分割。一般来说，分割数由设计者设置，并且可能在整个树中有所不同。

从节点向下延伸的链接数有时称为节点的分支因子或分支比。

查询选择和节点不纯度

设计树的大部分工作是决定在每个节点上应该测试哪个属性（即特征）查询。树创建的基本原则是简单性：我们更喜欢那些导致简单、紧凑且节点较少的决策。换句话说，解释数据的最简单的模型是首选。

为此，我们在每个节点 N 上寻找一个属性测试 T，使到达直接后代节点的数据尽可能“纯净”。在形式化这个概念时，定义节点的不纯度比纯度更方便。

可以使用几种不同的不纯度测量方法。接下来我们介绍一些最流行的方法。

令\(i(N)\)表示节点\(N\)的不纯度。在所有情况下，如果到达节点的所有样本都具有相同的类别标签，我们希望\(i(N)\)为\(0\)；如果类别的表示方式相同，我们希望\(i(N)\)较大

  1. 熵不纯度 最流行的度量是熵不纯度（或偶尔称为信息不纯度），其定义如下： \[i_{\mathrm E}(N)=-\sum_jP(\omega_j)\log_2P(\omega_j)\] 其中\(P(\omega_j)\)是节点\(N\)中属于\(\omega_j\)类别的样本比例。 如果所有样本都属于同一类别，则不纯度为\(0\)；否则为正，当不同类别的可能性相等时，不纯度值最大。
  2. 方差和基尼不纯度 方差不纯度在二分类情况下特别有用。当节点仅表示单个类别的模式时，希望不纯度为零，最简单的形式是： \[i_\mathrm{Var}(N)=P(\omega_1)P(\omega_2)\] 方差不纯度的概括，适用于两个或多个类别，是基尼不纯度： \[i_\mathrm{Gini}(N)=\sum_{j\ne k}P(\omega_j)P(\omega_k)=\frac12\left[1-\sum_jP^2(\omega_j)\right]\]
  3. 误分类不纯度 该不纯度衡量了训练样本在节点\(N\)处被错误分类的最小概率： \[i_\mathrm{MC}(N)=1-\max_jP(\omega_j)\]

熵不纯度由于其计算简单且基于信息论而被经常使用，尽管基尼不纯度也受到了广泛关注。通常，结果不会受到不同不纯度测量的太大影响。

现在我们来谈谈关键问题——给定一个到节点\(N\)的部分树，我们应该选择什么属性和什么值来进行属性测试？一个明显的启发式方法是选择尽可能减少不纯度的那个。不纯度的下降定义为：

\[\Delta i(N)=i(N)-[P_Li(N_L) + P_Ri(N_R)]\]

其中\(N_L\)和\(N_R\)分别为左、右后代节点，\(i(N_L)\)和\(i(N_R)\)为它们的不纯度，\(P_L\)和\(P_R\)分别为节点\(N\)处将传输至\(N_L\)和\(N_R\)的数据比例。

不纯度的最大下降量相当于后代节点的最小不纯度\([P_Li(N_L) + P_Ri(N_R)]\)

对于多重分裂，二元分裂不纯度下降的直观扩展如下：

\[\Delta i(N)=i(N)-\sum_{k=1}^BP_ki(N_k)\]

其中\(P_k\)是节点\(N\)处将通过链路发送到节点\(N_k\)的训练数据比例，\(B\)是节点\(N\)处的分支数，并且

\[\sum_{k=1}^BP_k=1\]

研究发现，无论较大的分割是否实际上代表数据中有意义的结构，该测量都有利于较大的\(B\)。

为了避免这个缺点，我们可以按如下方式调整上述措施：

\[\Delta i'(N)=\frac{i(N)}{-\sum_{k=1}^BP_k\log_2P_k}\]

最佳测试值是最大化二元分割的\(\Delta i(N)\)或多重分割的\(\Delta i'(N)\)的选择。上述度量也称为增益比。

何时停止分裂

现在考虑在二叉树训练期间决定何时停止分裂的问题。如果我们继续完全生长树，直到每个叶节点对应于最低不纯度，那么数据通常已经过度拟合。

  1. 在极端但罕见的情况下，每个叶子对应一个训练数据，而整棵树仅仅是查找表的方便实现；因此不能指望它能很好地概括。
  2. 相反，如果过早停止分裂，那么训练数据上的错误就不够低，因此性能可能会受到影响。

一种传统方法是使用交叉验证。也就是说，使用数据子集训练树，其余部分作为验证集。我们继续在连续的层中分割节点，直到验证数据的误差最小化。

另一种方法是设置一个（小的）不纯度减少阈值。如果节点上的最佳候选分割使不纯度减少的量小于预设量，则停止分割。这种方法有两个主要好处。首先，与交叉验证不同，树是直接使用所有训练数据进行训练的。其次，叶节点可以位于树的不同级别，当数据的复杂性在整个输入范围内变化时，这是可取的。

当节点的点数少于某个阈值（例如 10）或总训练集的某个固定百分比时，我们也可以停止分裂。

也可以使用权衡标准：

\[J=\alpha\times\mathrm{size}+\sum_{N\in\text{leaf node}}i(N)\]

这里\(\mathrm{size}\)可以是节点或链接的数量，\(\alpha\)是某个正常数。树的大小是分类器复杂度的度量，而不纯度的总和是分类器在训练数据上的性能的度量。这个权衡标准旨在在树复杂度和树性能之间取得平衡。

剪枝

顾名思义，剪枝就是修建树。树建好后，可能会过度拟合。

在修剪过程中，所有相邻的叶节点对（即链接到上一级的公共先行节点的节点）都将被考虑删除。任何删除后不纯度含量会令人满意地（小幅）增加的节点对都会被删除，而公共先行节点则被宣布为叶节点（反过来，这个先行节点本身也可以被修剪）。

显然，这两个叶节点的合并或连接是分裂的逆过程

叶节点标签的分配

为叶节点分配类别标签是树构建中最简单的步骤。如果连续节点被尽可能地分割，并且每个叶节点对应于单个类别中的模式（零不纯度），那么当然会将此类别标签分配给叶节点。

然而，极小的不纯度并不一定是可取的，因为它可能表明树过度拟合训练数据。

在更典型的情况下，无论是使用停止分裂还是剪枝，叶节点的不纯度都是正的。因此，每个叶节点都应该用样本最多的类别进行标记。

一些典型的分类树

几乎所有基于树的分类技术都采用了上述基本技术。以下是一些典型的分类树：

  1. CART（分类和回归树）。事实上，上面讨论的技术是 CART 的核心思想。
  2. ID3。ID3代表迭代二分法3，之所以这样命名，是因为该算法在每个步骤中迭代（重复）将特征二分（划分）为两个或多个组。它仅适用于名义（无序）输入。如果问题涉及实值变量，则首先将它们分成区间，每个区间被视为无序名义属性。
  3. C4.5。C4.5算法是ID3的继承者和改进，是一系列“分类”树方法中最受欢迎的算法。在算法中，实值变量的处理方式与CART相同。使用多个（B>2）分割对名义数据进行分割，就像ID3中一样，使用增益比杂质。该算法使用基于分割统计显著性的启发式方法进行剪枝。
  4. 随机森林。顾名思义，随机森林由许多决策树组成，这些决策树在完整训练数据的不同子集上进行训练。随机森林是一种集成学习方法。随机森林中的每棵树都会产生一个类预测，得票最多的类将成为模型的预测。接下来将介绍详细信息。

随机森林

动机

分类（或决策）树由贪婪算法构建：优化手头的节点分割，而不是考虑该分割对整个树的影响。由贪婪算法训练的模型容易出现过度拟合和高方差。

为了解决上述问题，我们可以使用随机森林，它是基于Bagging（Bootstrap Aggregation的缩写）的集成技术开发的。

Bagging的Bootstrapping部分是指重采样方法，其中从数据集中抽取多个随机样本并替换。因此，Bootstrapping会从同一分布中创建多个较小的随机数据集。

每个引导数据集都用于训练分类树。对于测试样本，多个分类树的输出将通过从所有树中挑选最常见的结果（即多数投票）聚合成一个最终结果。

这实际上如何帮助减少方差？

每棵树都在不同的数据集上进行训练。因此，不可避免地，每棵树都会犯不同的错误，并具有不同的误差和方差。在聚合步骤中，误差和方差都会减少。

建立随机森林的步骤

假设训练数据集由具有\(d\)特征的\(N\)个样本组成。

  1. 通过bootstrapping创建\(n\)个数据子集：子集\(1\)，\(\cdots\)，子集\(n\)。注意：\(n\lt N\)。
  2. 对于每个数据子集，从原始\(d\)个特征中随机选择\(m\)个特征，并使用这\(m\)个特征构建分类树。注意：\(m\lt d\)
  3. 重复步骤2，直到所有\(n\)个子集都已使用。

使用随机森林进行分类的步骤

给定具有未知类别标签的测试样本

  1. 将测试样本通过每棵\(n\)分类树运行，从每棵分类树中获得预测类。
  2. 计算每个预测类的投票数。
  3. 输出投票数最高的预测类作为最终的类预测

随机森林的特点

  1. 多样性：在创建一棵树时，并非所有属性/变量/特征都会被考虑；每棵树都是不同的。
  2. 不受维数灾难的影响：由于每棵树都不会考虑所有特征，因此特征空间会减少。
  3. 并行化：每棵树都是由不同的数据和属性独立创建的。
  4. 训练-测试分割：在随机森林中，我们不必分割数据进行训练和测试，因为决策树总会有看不见的数据。
  5. 稳定性：稳定性的产生是因为结果基于多数投票/平均。