攀登树木系列 1：什么是 Decision Tree？

发布时间：2025年1月7日

这是关于机器学习中 Decision Tree 系列文章的第一篇。目标是提供对 Decision Tree 的基础理解并实现它们。

攀登树木系列

Decision Tree 本身并不是令人惊叹的算法。它们具有局限性，可能导致次优甚至奇怪的预测。然而，它们已经变得非常流行。有些人甚至会说它们是许多机器学习领域 实际上的 首选算法。这归功于 bagging 和 boosting 技术，这些技术将表现不佳的 Decision Tree 变成了最先进的算法。我们将在未来探索它们。

首先，我们将建立对什么是 Decision Tree 的直觉，并对其进行数学定义。然后，我们将探讨如何构建 Decision Tree。这将使我们能够掌握它们的主要特征、优点和缺点。我将尝试逐步引入复杂性，但我假设您对数学符号、统计和基本机器学习概念有所了解。

如果事情变得太复杂，请尝试阅读提供的参考文献。我借鉴了各种资料来理解 Decision Tree，包括书籍、文档、文章、博客文章和讲座。即使您理解了一切，也请查看参考文献：那里有很多很棒的内容。

什么是 Decision Tree？

想象一下，您正试图决定出门时是否带雨伞。您可能会问这样的问题：“有云吗？”。如果是，您可能会问 “湿度是多少？”。每个问题都有助于您缩小决策范围。这就是 Decision Tree 的工作方式。

让我们模拟这个天气示例：

湿度和云量散点图，显示多云和潮湿时更有可能下雨

可以将 Decision Tree 视为通过询问一系列关于我们数据的问题来做出连续的决策。每个内部树_节点_使用某个特征（在我们的示例中，云量或湿度）使用一个分割值将其区域分成两部分。每个新区域可以进一步分成两部分。将其区域分成两部分的节点称为_内部节点_。

_叶（或终端）节点_不再提出任何问题，而是为其区域提供预测。在我们的示例中，它可能会说 “下雨” 或 “不下雨”。更准确地说，它为每个结果分配一个概率。

让我们看一下适合我们天气示例的 Decision Tree：

决策树分割图

这个 Decision Tree 被有意地保持得很小。从上到下，该图表示我们简单树的所有决策边界。每个内部节点产生两个_分支_，即可以遵循的两条路径。这些分支递归地划分特征空间，使得具有相同标签或相似目标值的样本被分组在一起。例如，我们预测如果湿度高于 59% 且云量高于 45% (图中最右边的路径)，就会下雨，因为该区域中的大多数点 (实例) 属于“下雨”类。

显示的类别仅与叶节点相关，即最底行中的那些节点。value 属性显示每个区域中每个类别的样本数量。纯节点_在其区域中仅包含一个类的实例。由于所有节点都包含至少一个类的实例（即“下雨”和“不下雨”），因此所有节点都是_不纯的。训练期间的目标是尽可能地_减少不纯度_。如果所有节点都是纯的，则该树在训练数据集上具有_零误差_。这就是 Decision Tree 学习的方式。

树的可视化非常容易解释。我们可以遵循每条路径并清楚地看到为什么做出预测，即该模型很容易_解释_（与_黑盒_模型相反）。这是 Decision Tree 受欢迎的原因之一。简单的 Decision Tree 甚至可以应用于某些实际设置（例如，医学），而无需机器辅助。

我们还可以通过将决策边界叠加到数据的散点图上来可视化树的决策边界：

湿度和云量散点图，显示来自决策树的预测区域

我们可以看到区域之间的直线边界。更正式地说，Decision Tree 是一种分层结构，可将我们的特征递归划分为_长方体区域_。由于在我们的示例中我们有 2 个特征（2 个维度），因此长方体区域是正方形。

树的类型

广义地说，Decision Tree 有两种类型：_分类_树和_回归_树。虽然它们共享相同的基本结构和分割方法，但它们的输出以及进行预测的方式有所不同。

分类树旨在预测分类结果——它们将输入数据分配给预定义的类别或分类。在每个叶节点上，该树会预测到达该节点的训练样本中最常见的类别。我们的天气示例涉及分类树，叶子会预测是否会下雨。通过计算叶节点上每个类的训练样本的比例并选择多数类来进行预测。可以将其视为树询问一系列关于输入特征的是/否问题，直到它可以对输入属于哪个类别做出有根据的猜测。

另一方面，回归树预测连续的数值，而不是类别。回归树通常不是在每个叶节点上预测一个类别，而是输出所有到达该节点的训练样本的平均值。例如，回归树可能会根据面积、卧室数量和位置等特征预测房屋的价格。树中的每次分割都试图将相似的数值分组在一起。当有新的示例进入时，该树可以将其引导到包含具有相似目标值的训练示例的叶节点，并使用它们的平均值作为预测。

Decision Tree 算法

Decision Tree 已经得到了广泛的探索，并且存在各种不同的 Decision Tree 算法。最具影响力的算法是 ID3 (Iterative Dichotomiser 3)、C4.5 和 CART (Classification and Regression Trees)。

ID3 是最早的 Decision Tree 算法之一，仅支持具有分类特征的分类。根据每个特征的分类级别的数量，节点可以分为两个以上。

C4.5 扩展了 ID3 算法以支持数值特征和缺失值。CART 类似于 C4.5，但也增加了对回归的支持。

与 ID3 和 C4.5 相比，CART 方法仅执行二元分割，从而导致更高的树。尽管此处讨论的原则适用于大多数 Decision Tree 算法，但我专注于 CART——这也是我们将要实现的算法。

数学定义

从数学上讲，Decision Tree 可以描述为：

f(x)=∑m=1McmI(x∈Rm)f(x) = \sum_{m=1}^{M} c_m \mathbb{I}(x \in R_m)f(x)=m=1∑M​cm​I(x∈Rm​)

其中 xxx 是输入特征，RmR_mRm​ 是第 mmm 个区域，cmc_mcm​ 是该区域的值。I(x∈Rm)\mathbb{I}(x \in R_m)I(x∈Rm​) 如果 xxx 包含在第 mmm 个区域中，则为 1，否则为 0。这些值 (ccc) 通常是常数（回归）或概率向量（分类）。区域和值的组合定义了 Decision Tree。

但是，这些区域不能采用任意边界。它们始终与某个轴_平行_，并且只能划分先前的区域。这可能是一种限制，但它大大降低了构建 Decision Tree 的计算复杂度。在我们的天气示例中，使用其他方法很容易找到以下决策边界（我使用了 Logistic Regression）：

具有对角决策边界的天气散点图

但是，轴平行分割（单个特征）比倾斜分割（多个特征）更容易计算。找到单个特征的最佳分割涉及对数据进行排序和评估分割。由于后者与排序相比可以忽略不计，因此此操作的时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)，其中 nnn 是数据点的数量。但是，要找到结合两个特征的最佳倾斜分割，我们首先必须考虑由点对形成的所有可能的 O(n2)O(n^2)O(n2) 线。对于每条线，您都需要评估每个点落在哪一侧：O(n)O(n)O(n)。这总共需要 O(n3)O(n^3)O(n3) 的时间复杂度。更一般地，倾斜分割的时间复杂度为 O(nd+1)O(n^{d+1})O(nd+1)，其中 ddd 是特征的数量。因此，我们妥协于仅使用轴平行分割，这些分割定义了长方体区域。

每个区域 RmR_mRm​ 由从根到树的第 mmm 个叶子的路径定义。例如，考虑定义区域 R={(Humidity,Cloud)∣Humidity>59 and Cloud>45}R = \{(Humidity,\ Cloud)\ |\ Humidity > 59\ \text{and}\ Cloud > 45\}R={(Humidity,Cloud)∣Humidity>59andCloud>45} 的路径。

根节点和叶节点之间的路径

该区域可以在散点图上可视化：

散点图中定义的区域

与线性模型不同，Decision Tree 不会对整个数据分布进行建模。相反，每个区域都有独立的预测值。更正式地说，添加所有独立区域定义了一个分段函数，它可以近似数据中的任何模式，但可能难以正确表示平滑或连续的函数。

Bias-Variance 权衡

与所有其他机器学习算法一样，树也受到 Bias-Variance 权衡 的困扰。如果这个概念对您来说是新的，我强烈建议您先阅读它（检查参考文献），但稍后再回来。

Bias-Variance 权衡复习 总之，Bias 是指由于过度简化特征之间的关系（欠拟合）而导致模型产生的误差。Variance 衡量模型预测对训练集中小波动有多敏感。高方差意味着模型正在捕获_噪声_，而不是真实的关系（过拟合）。减少 Bias 往往会增加 Variance，反之亦然。找到最佳的 Bias-Variance 平衡对于实现良好的预测准确性至关重要。

Decision Tree 的 Variance

由于树的非线性和非平滑性质，它们很容易捕获噪声。因此，更深的树呈现出更多的 Variance。如果您完全生长一棵树，它将划分特征空间，直到误差为零1。该模型将有效地_记住_训练集（包括噪声），从而导致_过拟合_。

如果我们重建我们的示例树直到误差为 0，我们将获得以下区域：

湿度和云量散点图，显示来自深度决策树的预测区域

它具有完美的准确性，但由于噪声（高方差）而具有非常不寻常的边界。该模型不能很好地泛化，也就是说，它在新数据上的得分会很低。有多种方法可以限制树的方差，即：

填充树所需的样本数量对于树的每个附加级别（深度）都会翻倍。这些限制确保叶节点不会过于稀疏。另一种可能性是完全生长树，然后_修剪它_以平衡复杂性和准确性。

让我们在玩具数据集上构建深度增加的 Decision Tree：

Play Depth: 1 在左边，我们可以看到具有两个特征和两个类的训练集2。我们正在构建_分类_树，其决策边界叠加在左侧图上。右侧的图显示了训练和测试误差，以及 Logistic Regression 模型作为基线的测试误差。测试集是从相同的分布中采样的，但与训练集不同。使用滑块比较深度。我们可以看到最佳测试误差发生在深度为 3 的情况下。进一步增加深度会导致过拟合。

Decision Tree 的 Bias

即使在上面的示例中深度为 3，误差也大于 Logistic Regression 基线。这是一个线性模型由于数据的_加性结构_而优于 Decision Tree 的示例。Logistic Regression 在这种情况下是：

logit(p)=β0+β1x1+β2x2+εlogit(p) = \beta_{0} + \beta_{1} x_{1} + \beta_{2} x_{2} + \varepsilonlogit(p)=β0​+β1​x1​+β2​x2​+ε

其中 ppp 是结果属于 1 类的概率。忽略常数和噪声（ε\varepsilonε），概率由两个特征的线性组合决定。特征之间的关系不是_分层的_，因此 Decision Tree 需要多次，有时是冗余的分割来近似这个概念，从而导致深度或过于复杂的树。

还有其他概念属于同一类别，例如：

这些可能看起来过于具体，但它们被用作测试机器学习算法能力的基准。加性结构、XOR 和 Parity 涉及全局依赖关系，需要一起考虑多个输入。Decision Tree 一次基于一个特征分割数据，因此在捕获这些关系方面效率不高。Multiplexer 问题需要非分层的条件规则，使得树非常大，以考虑选择器-输入对的所有组合。

在更复杂的真实世界数据集中，很可能存在多个非分层概念，从而导致次优的 Bias。如果它们具有低于标准的 Variance 和 Bias，Decision Tree 似乎是一个糟糕的算法选择。实际上，它们很少单独发光，而是作为_集成_（使用 bagging 或 boosting），我们将在未来介绍。

阶梯效应

当 Decision Tree 尝试对加性结构进行建模时，它们面临一个结构性约束，这种约束非常普遍，足以让我将其命名为_“阶梯”效应_3。这种限制在分类和回归任务中表现不同，但源于轴对齐的分割。

在分类问题中，当类之间的最佳决策边界涉及特征的线性组合（倾斜边界）时，阶梯效应变得明显。考虑一个简单的情况，其中最佳边界是二维特征空间中的对角线。因为 Decision Tree 只能进行平行于特征轴的分割，所以它们必须通过一系列矩形区域来近似这个对角线边界，从而创建一个类似阶梯的模式。

分类中阶梯效应的演示

在回归设置中，阶梯效应更加突出，因为回归树必须使用离散的、恒定值的区域来近似连续函数。当潜在关系是平滑的（无论是线性、多项式还是任何其他连续函数）时，树的预测表面具有阶梯状结构，在相邻区域之间具有突变。增加树的深度将预测表面近似于训练集，但该表面不一定会变得平滑，因为它会捕获特征噪声。

回归中阶梯效应的演示

具有阶梯效应的回归示例。只有一个特征 (xxx)，垂直轴是结果。

目标函数

我们需要定义目标函数以便在训练期间进行优化。分类树使用 Gini 不纯度或熵作为目标函数。回归树通常使用平方损失。

在所有示例中，考虑数据 D={(x1,y1),...,(xn,yn)},yi∈{1,...,c}\mathcal{D} = \{(x_1, y_1), ..., (x_n, y_n)\}, y_i \in \{1, ..., c\}D={(x1​,y1​),...,(xn​,yn​)},yi​∈{1,...,c}，其中 ccc 是类别的数量。

误分类率

MR(D)=∑i=1nI(y^i≠yi)nMR(\mathcal{D}) = \frac{\sum_{i=1}^n \mathbb{I}(\hat{y}_i \neq y_i)}{n}MR(D)=n∑i=1n​I(y^​i​=yi​)​

这是分类的一个非常直观的目标。它衡量了误分类示例的比例。预测 y^\hat{y}y^​ 是节点的多数票。我们的目标是减少叶节点的不纯度，这与误分类率函数对齐。

Gini 不纯度

集合类概率 ppp 上的 Gini 不纯度 4 定义为：

G(D)=∑k=1cpk(1−pk)=1−∑k=1cpk2G(\mathcal{D}) = \sum_{k=1}^{c} p_{k}(1 - p_{k}) = 1 - \sum_{k=1}^c p_{k}^2G(D)=k=1∑c​pk​(1−pk​)=1−k=1∑c​pk2​

它衡量了如果一个集合的随机选择的元素如果按照集合中标签的分布随机且独立地进行标记，那么该元素被错误标记的频率。当节点是纯的，一个类的概率为 1，其余为 0，因此 Gini 不纯度也为 0。当概率在类之间均匀分布时，会出现最坏的 Gini 不纯度，即具有最大 Gini 不纯度的节点并不比分类示例的掷硬币更好。可以证明，随着类别数量的增加，Gini 不纯度的上限为 1。

要评估分割 (S\mathcal{S}S) 的质量，我们计算每个子节点的 Gini 不纯度并取加权平均值。

G(D∣S)=∣DL∣∣D∣G(DL)+∣DR∣∣D∣G(DR)G(\mathcal{D}|\mathcal{S}) = \frac{|\mathcal{D}_L|}{|\mathcal{D}|} G(\mathcal{D}_L) + \frac{|\mathcal{D}_R|}{|\mathcal{D}|} G(\mathcal{D}_R)G(D∣S)=∣D∣∣DL​∣​G(DL​)+∣D∣∣DR​∣​G(DR​)

其中 ∣DL∣∣D∣\frac{|\mathcal{D}_L|}{|\mathcal{D}|}∣D∣∣DL​∣​ 是左子节点中的输入比例，∣DR∣∣D∣\frac{|\mathcal{D}_R|}{|\mathcal{D}|}∣D∣∣DR​∣​ 是右子节点中的输入比例。

熵

H(D)=−∑k=1cpklog2pkH(\mathcal{D}) = - \sum_{k=1}^{c} p_{k}\ log_{2} p_{k}H(D)=−k=1∑c​pk​log2​pk​

熵标准是信息论中的一个概念（Shannon 熵）。它衡量了一组概率的平均不确定性程度。换句话说，它是描述潜在结果所需的预期信息量。当概率均匀分布时，熵最大，就像 Gini 不纯度一样。要理解信息和概率之间的联系，请考虑您有一组具有两个同样可能的类（假设是红色和蓝色）。如果您抽取一个样本，您对您抽取的颜色具有尽可能少的确定性。另一方面，如果红色的概率为 95%，您可以非常确信您将抽取的颜色 - 这具有低得多的不确定性。当概率均匀时，您需要额外的信息来准确地传达一系列抽奖的结果。

熵标准的范围从 0 到 log2(c)log_{2}(c)log2​(c)。我们还取子节点的加权平均值来评估分割的质量：

H(D∣S)=∣DL∣∣D∣H(DL)+∣DR∣∣D∣H(DR)H(\mathcal{D}|\mathcal{S}) = \frac{|\mathcal{D}_L|}{|\mathcal{D}|} H(\mathcal{D}_L) + \frac{|\mathcal{D}_R|}{|\mathcal{D}|} H(\mathcal{D}_R)H(D∣S)=∣D∣∣DL​∣​H(DL​)+∣D∣∣DR​∣​H(DR​)

也常见的是以_信息增益_来表示目标函数，信息增益是由节点分割产生的熵的减少。

IG(D)=H(D)−H(D∣S)IG(\mathcal{D}) = H(\mathcal{D}) - H(\mathcal{D}|\mathcal{S})IG(D)=H(D)−H(D∣S)

它表示给定我们的分割，我们获得的关于目标变量的信息量。就这些术语而言，目标是最大化信息增益。

比较分类目标

虽然误分类率直观且常用作模型指标，但它不用作优化目标。我们可以提出具有相同误分类率的分割 (S\mathcal{S}S)，但其中一个具有纯节点，而另一个没有。例如：

S={A:10,B:0},{A:10,B:5}\mathcal{S} = \{A: 10, B: 0\},\ \{A: 10, B: 5\}S={A:10,B:0},{A:10,B:5} S′={A:10,B:2},{A:10,B:3}\mathcal{S}' = \{A: 10, B: 2\},\ \{A: 10, B: 3\}S′={A:10,B:2},{A:10,B:3}

两个分割都错误分类了 5 个 B 类的样本（相同的误分类率），但是第一个具有纯节点。从优化的角度来看，我们应该偏爱纯节点，因为它们减少了后续分割的数量。您可以检查第二个分割的熵和 Gini 不纯度确实更高。

检查该断言是否成立 误分类率： MR(D∣S)=10250+1525515=0.2MR(\mathcal{D}|\mathcal{S}) = \frac{10}{25} 0 + \frac{15}{25} \frac{5}{15} = 0.2MR(D∣S)=2510​0+2515​155​=0.2MR(D∣S′)=1225212+1325313=0.2MR(\mathcal{D}|\mathcal{S}') = \frac{12}{25} \frac{2}{12} + \frac{13}{25} \frac{3}{13} = 0.2MR(D∣S′)=2512​122​+2513​133​=0.2MR(D∣S)=MR(D∣S′)MR(\mathcal{D}|\mathcal{S}) = MR(\mathcal{D}|\mathcal{S}')MR(D∣S)=MR(D∣S′)

Gini 不纯度： G(D∣S)=10250+15250.444=0.266G(\mathcal{D}|\mathcal{S}) = \frac{10}{25} 0 + \frac{15}{25} 0.444 = 0.266G(D∣S)=2510​0+2515​0.444=0.266G(D∣S′)=12250.277+13250.355=0.318G(\mathcal{D}|\mathcal{S}') = \frac{12}{25} 0.277 + \frac{13}{25} 0.355 = 0.318G(D∣S′)=2512​0.277+2513​0.355=0.318G(D∣S)<G(D∣S′)G(\mathcal{D}|\mathcal{S}) < G(\mathcal{D}|\mathcal{S}')G(D∣S)<G(D∣S′)

出于同样的原因，当没有分割可以最小化误分类率时，树可能会“卡住”。Gini 不纯度和熵考虑概率，而误分类率仅考虑多数票，因此不够敏感。

更正式地说，Gini 不纯度和熵都是严格的凹函数。如果您在严格凹函数的曲线上取两个点并在它们之间画一条线，则该线将_始终低于_曲线。

熵函数图，曲线下方有一条线段

具有两个类的概率 ppp 上的熵 H(p)H(p)H(p) 图。第二个类的概率为 (1−p)(1 - p)(1−p)。

我们从 数据处理不等式 得知，分割后平均熵不能增加。分割要么减少两个子节点的熵（这导致与父节点相比更低的平均熵），要么一个子节点具有比父节点更高的熵，而另一个子节点具有更低的熵。两个子节点都不能具有比父节点更高的熵，因为这意味着分割_创建_了新的信息（不确定性），从而违反了数据处理不等式。因此，我们只需要表明当一个子节点具有更高的熵，而另一个子节点具有比父节点更低的熵时，平均熵会减少。熵函数的严格凹性足以确保这一点。

概率图上的熵显示标记的节点点

平均子节点熵位于曲线上两个子节点点之间的某条线上。平均概率必须与父节点的概率相同，因此平均子节点熵始终位于父节点熵的正下方。因此，~~几乎~~ 5 _始终_存在导致较低的子节点平均熵的分割。

误分类率不是严格凹的。当两个子节点位于函数的同一侧时，子节点的平均误分类率等于父节点的平均误分类率，从而停止了优化过程。

显示线上线段上的误分类率函数图

平方损失

L(D)=1N∑i=1N(yi−yˉ)2L(\mathcal{D}) = \frac{1}{N} \sum_{i=1}^N (y_{i} - \bar{y})^2L(D)=N1​i=1∑N​(yi​−yˉ​)2

平方损失函数是_回归_树的主要优化标准。在此等式中，yˉ\bar{y}yˉ​ 表示特定节点中目标变量 yyy 的平均值。该值成为落入该节点的所有观察值的预测值 (ccc)，遵循 Decision Tree 的 数学定义。

虽然此公式类似于许多统计应用程序中使用的传统均方误差 (MSE)，但存在一个重要的区别。在标准回归模型中，MSE 通常衡量预测值 (y^\hat{y}y^​) 和实际值之间的差异，其中 y^\hat{y}y^​ 可以通过模型参数直接优化。但是，在 Decision Tree 的上下文中，此平方损失函数实际上量化了目标变量的_节点内方差_。

这种方差解释导致对树构建过程的直观理解：该算法寻求最大化父节点及其子节点之间方差减少的分割。这种方法通常称为方差减少，有效地将数据划分为相对于目标变量越来越同质的子组。最佳分割是创建具有最小平均方差的子节点的分割，从而提高树的预测准确性。

构建 Decision Tree

足够大的树每个节点将具有一个训练样本，从而有效地记住训练集。这样的树实现了 0 训练误差，但它是一种病态优化情况。我们的目标是构建实现 0 训练误差的_尽可能小的_树。如果强制执行最大深度等限制，我们应该找到在尊重此类限制的同时_最小化_目标的树。

不幸的是，计算复杂度呈组合方式增长，并且找到最佳树是 NP 完全 的。在宇宙热寂之前构建树会很好，因此我们继续使用_贪婪算法_。我们做出了一系列局部最优选择，希望它能导致某种程度上接近全局最优的解决方案。

让我们使用 Gini 不纯度标准构建一个分类树。从所有数据和第一个变量开始，我们测试_所有可能的_分割点 (N−1N - 1N−1 分割) 并选择具有最低标准的分割点。然后，我们对其余所有特征重复此过程。选择所有特征中标准最低的分割。最后，我们对左子节点和右子节点递归地重复该过程，直到所有节点中的标准为 0 或达到树大小限制为止。

Play

考虑到单个特征的优化过程的表示。我们评估所有分割点以找到最小化目标函数的分割点。必须对其他特征执行相同的过程以选择最佳分割。

这种方法虽然计算效率高，但也有很大的缺点。主要的限制在于该算法无法考虑分割决策的长期后果。在评估潜在分割时，该算法仅针对即时收益进行优化，可能会忽略可能实现更好下游决策的分割。

这种短视的优化策略引入了大量的模型不稳定性。这些局部最优但全局次优决策的累积效应使得生成的树结构对训练数据中的变化高度敏感（即，它是_方差_的另一个来源）。在极端情况下，添加或删除单个训练示例可能会通过树结构传播，从而导致截然不同的决策路径。

此外，这是要求分割节点以最小减少损失不是一个好主意的主要原因。从隔离角度来看，似乎略有好处的分割可能对于访问树结构中更深层次的有价值的划分模式至关重要。因此，来自分割的改进的即时幅度可能无法可靠地指示其对模型性能的最终贡献。

Decision Tree 的特点

假设

每个机器学习算法都对数据的结构做出假设。探索特征和结果之间所有可能关系的整个空间是不可行的，因此每个算法都以其自己的方式削减了角落。

Decision Tree 假设我们可以通过重复分割单个特征将数据分离成有意义的区域。换句话说，它们假设特征空间中的最佳决策边界是轴对齐的，因此只能通过分层结构捕获特征交互。与大多数机器学习算法一样，这些假设很少是严格正确的。但是，它们可能足够接近现实以产生良好的结果。

另一方面，Decision Tree 没有对许多机器学习算法做出其他限制性假设：它们不假设任何概率分布或任何线性结构。它们也不依赖于任何距离度量，从而部分逃避了维数灾难6。特征选择已内置到 Decision Tree 算法中，因此它们可以忽略不相关的维度。尽管如此，随着维数增长并且数据变得稀疏，在不捕获噪声的情况下找到有意义的分割变得更加困难。

优点和缺点

我们可以将 Decision Tree 的主要优点总结为：

它们也存在相同的重大缺陷，即：

外推法

Decision Tree 不进行外推。我没有将其放在_优点_或_缺点_中，因为它可能两者兼有。

关于外推的 xkcd 漫画

Decision Tree 训练程序根据示例划分特征空间。当 Decision Tree 遇到一个或多个特征超出其训练范围的数据点时，它只会分配最近叶节点的值。因此，预测在训练数据的边界之外保持不变。

此行为使模型对极端特征值具有鲁棒性，因此在某些设置中可能需要它。但是，在期望趋势扩展到我们观察到的数据范围之外的领域中，它也是一个主要限制。考虑根据建筑面积预测房屋的任务。如果训练数据仅包括高达 250 平方米的房屋，那么那是我们预测的上限，即使我们有理由期望更大的房屋更昂贵。这是 Decision Tree 固有的归纳偏差。

我们已经定义了 Decision Tree、它们的目标函数和一个通用算法。在本系列的后续文章中，我们将在 Python 中实现分类和回归树 (CART)。

参考文献