通过实施来理解：决策树

由柏拉图重新发布

关注： 0

通过实施理解：决策树
图片作者

许多高级机器学习模型，例如随机森林或梯度提升算法，例如 XGBoost、CatBoost 或 LightGBM（甚至自动编码器!) 依赖于一个关键的共同成分： 决策树!

如果不了解决策树，就不可能理解上述任何高级装袋或梯度提升算法，这对任何数据科学家来说都是一种耻辱！因此，让我们通过在 Python 中实现决策树来揭开决策树的内部工作原理的神秘面纱。

在本文中，您将学习

决策树为什么以及如何拆分数据，
信息增益，和
如何使用 NumPy 在 Python 中实现决策树。

你可以在上面找到代码我的Github.

为了做出预测，决策树依赖于分裂以递归方式将数据集分成更小的部分。

通过实施理解：决策树
图片作者

在上图中，您可以看到一个拆分示例——原始数据集被分成两部分。在下一步中，这两个部分将再次拆分，依此类推。这一直持续到满足某种停止标准为止，例如，

如果拆分导致部分为空
如果达到某个递归深度
如果（在之前的拆分之后）数据集仅包含少数元素，则无需进一步拆分。

我们如何找到这些分裂？为什么我们甚至关心？让我们找出来。

动机

让我们假设我们要解决一个 二进制 分类问题 我们现在创造自己：

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

二维数据如下所示：

通过实施理解：决策树
图片作者

我们可以看到有两个不同的类别——紫色占大约 75%，黄色占大约 25%。如果您将此数据提供给决策树分类，这棵树最初有以下想法：

“有两个不同的标签，这对我来说太乱了。我想通过将数据分成两部分来清理这个烂摊子——这些部分应该比之前的完整数据更干净。” ——获得意识的树

树也是如此。

通过实施理解：决策树
图片作者

树决定大致沿着 x-轴。这样的效果是数据的顶部现在是完美的 清洁， 意味着你只能找到 一个班级 （在这种情况下为紫色）那里。

但是，底部仍然是凌乱，在某种意义上甚至比以前更混乱。在完整的数据集中，类别比例过去约为 75:25，但在这个较小的部分中约为 50:50，这是尽可能混合的

请注意： 在这里，紫色和黄色在图片中很好地分开并不重要。只是 不同标签的原始数量 在两部分算。

通过实施理解：决策树
图片作者

尽管如此，作为树的第一步，这已经足够好了，因此它继续进行。虽然它不会在顶部造成另一个分裂，清洁部分不再存在，它可以在底部创建另一个拆分来清理它。

通过实施理解：决策树
图片作者

Et voilà，这三个独立的部分中的每一个都是完全干净的，因为我们只在每个部分找到一个单一的颜色（标签）。

现在做预测真的很容易：如果有新的数据点进来，你只需检查其中的哪一个 三个部分 它撒谎并给它相应的颜色。现在效果很好，因为每个部分都是清洁. 容易，对吧？

通过实施理解：决策树
图片作者

好吧，我们在谈论清洁和凌乱数据，但到目前为止，这些词只代表一些模糊的想法。为了实现任何东西，我们必须找到一种方法来定义清洁.

清洁措施

让我们假设我们有一些标签，例如

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

凭直觉 y₁ 是最干净的标签集，其次是 yXNUMX 然后 y₃. 到目前为止一切顺利，但我们如何才能对这种行为进行统计呢？也许最容易想到的是以下内容：

只需计算零的数量和一的数量。计算它们的绝对差。为了让它更好，通过除以数组的长度来规范化它。

例如， yXNUMX 总共有 8 个条目——6 个零和 2 个一。因此，我们的自定义 清洁度评分 将是 |6 – 2| / 8 = 0.5。很容易计算出清洁度得分为 y₁ 和 y₃ 分别为 1.0 和 0.0。在这里，我们可以看到通用公式：

通过实施理解：决策树
图片作者

在这里， n₀ 和 n₁ 分别是零和一的数量， n = n₀ + n₁ 是数组的长度和 p₁ = n₁ / n 是 1 个标签的份额。

这个公式的问题在于它是 专门针对两个类的情况，但我们通常对多类分类感兴趣。一个非常有效的公式是 基尼杂质度量：

通过实施理解：决策树
图片作者

或一般情况：

通过实施理解：决策树
图片作者

它工作得很好，scikit-learn 采用它作为默认措施其 DecisionTreeClassifier 类。

通过实施理解：决策树
图片作者

请注意： 基尼系数 混乱而不是清洁度。示例：如果列表仅包含一个类（=非常干净的数据！），则总和中的所有项均为零，因此总和为零。最坏的情况是如果所有类都出现了准确的次数，在这种情况下基尼系数是 1–1/C 哪里 C 是类的数量。

现在我们有了清洁/混乱的衡量标准，让我们看看如何使用它来找到好的拆分。

寻找分裂

我们有很多拆分可供选择，但哪种拆分方式好呢？让我们再次使用我们的初始数据集，以及基尼不纯度度量。

通过实施理解：决策树
图片作者

我们现在不计算点数，但让我们假设 75% 是紫色的，25% 是黄色的。使用 Gini 的定义，完整数据集的不纯度为

通过实施理解：决策树
图片作者

如果我们沿着 x-轴，如前所述：

通过实施理解：决策树
图片作者

顶部的基尼杂质为 0.0 和底部

通过实施理解：决策树
图片作者

平均而言，这两个部分的基尼不纯度为 (0.0 + 0.5) / 2 = 0.25，优于之前整个数据集的 0.375。我们也可以用所谓的 信息获取:

这种分裂的信息增益是 0.375 – 0.25 = 0.125。

就这么简单。信息增益越高（即基尼杂质越低）越好。

请注意： 另一个同样好的初始分割是沿着 y 轴。

要记住的一件重要事情是，它对 通过零件的大小衡量零件的基尼杂质. 例如，让我们假设

第 1 部分由 50 个数据点组成，基尼不纯度为 0.0 和
第 2 部分由 450 个数据点组成，基尼不纯度为 0.5，

那么平均基尼杂质不应该是 (0.0 + 0.5) / 2 = 0.25 而是 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

好的，我们如何找到最佳拆分？简单但发人深省的答案是：

只需尝试所有拆分并选择信息增益最高的拆分即可。这基本上是一种蛮力方法。

更准确地说，标准决策树使用 沿坐标轴拆分，即 xᵢ = c 对于某些功能 i 和门槛 c. 这意味着

分割数据的一部分由所有数据点组成 x xᵢ c和
所有点的另一部分 x xᵢ ≥ c.

这些简单的拆分规则已在实践中证明足够好，但您当然也可以扩展此逻辑以创建其他拆分（即对角线，如 xᵢ + 2xⱼ = 3，例如）。

太好了，这些都是我们现在需要的所有成分！

我们现在将实施决策树。由于它由节点组成，让我们定义一个 Node 先上课。

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

一个节点知道它用于分裂的特征（feature) 以及分裂值 (value). value 也作为决策树最终预测的存储。由于我们将构建一棵二叉树，因此每个节点都需要知道其左右子节点，如存储在 left 和 right .

现在，让我们进行实际的决策树实施。我正在让它与 scikit-learn 兼容，因此我使用了一些来自 sklearn.base . 如果您对此不熟悉，请查看我关于如何构建 scikit-learn 兼容模型.

让我们实施吧！

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

就是这样！你现在可以做所有你喜欢的关于 scikit-learn 的事情：

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

由于这棵树是非正则化的，它过度拟合了很多，因此得到了完美的训练分数。看不见的数据的准确性会更差。我们还可以通过以下方式检查树的外观

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

作为图片，它会是这样的：

通过实施理解：决策树
图片作者

在本文中，我们详细了解了决策树的工作原理。我们从一些模糊但直观的想法开始，并将它们转化为公式和算法。最后，我们能够从头开始实现决策树。

不过请注意：我们的决策树还不能正则化。通常，我们想指定参数，如

最大深度
叶子大小
和最小的信息增益

在许多其他人中。幸运的是，这些东西并不难实现，这对你来说是一个完美的家庭作业。例如，如果您指定 leaf_size=10 作为参数，则包含超过 10 个样本的节点不应再拆分。另外，这个实现是 效率不高. 通常，您不想将部分数据集存储在节点中，而只希望存储索引。因此，您的（可能很大的）数据集仅在内存中出现一次。

好消息是您现在可以使用此决策树模板发疯了。你可以：