决策树分类

＃＃ 介绍

决策树（DT）是一种用于分类和回归的非参数监督学习方法。目标是创建一个模型，通过学习从数据特征推断出的简单决策规则来预测目标变量的值。

熵

训练的目标是找到节点中的最佳分割，从而找到最优树。分割是使用一些标准完成的，例如：熵。

熵有许多定义，例如：

• 熵对应于信息源中包含的信息量。

• 熵也可以被视为随机性或集合中惊喜的测量。

• 熵是衡量系统中不可预测性或杂质的指标。

在决策树中，我们将熵视为节点内部纯度的度量。决策树模型的目标是减少每次分裂时节点的熵：

因此，我们希望最大化父节点的熵和子节点的熵之间的差异。这种差异称为信息增益。

集合 $X$ 的熵 $H$ 的数学公式如下：

$$H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)$$

信息增益

信息增益是父节点的熵与子节点的熵的加权和之间的差，因此可以用以下公式表示：

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

在哪里：

• $H(.)$ 是熵。

• $Y$ 是分裂之前的种群，它代表父节点。

• $X$ 是我们要用于分割的变量。

• $x$ 是 X 的唯一值。

• $Y[X==x]$ 是一个仅包含 $x$ 值的拆分列表。

让我们举一个适当的例子：

当我们使用 X 的值除父节点时，我们将计算信息增益：

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

\

首先，我们计算父节点的熵：

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

\

然后，我们将使用 X 的唯一值来计算分割后每个子节点的内部概率：

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

例如：

• $H(Y | X = Square)$ ：表示第一个子节点的熵。

• $H(Y | X = Circle)$ ：表示第二个子节点的熵。

\

我们从第一个子节点开始：

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

\

然后是第二个子节点：

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

\

最后，我们将熵代入信息增益公式中：

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

\

\

如前所述，节点分裂的目标是最大化信息增益，从而最小化结果子节点中的熵。为此，我们需要尝试使用不同的输入集 $X_1, X_2, \ldots, Xn$ 来分割节点，并且我们只保留最大化信息增益的分割：

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

何时停止分裂

决策树中的节点分裂是递归的，因此必须有一个我们可以使用的标准来停止分裂。这些是一些最常实施的标准：

• 当节点是纯节点时： H(node) = 0。进一步分裂节点是没有意义的。

• 最大深度数： 我们可以设置模型可以达到的最大深度，这意味着即使节点不纯，分裂也会停止。

• 每个节点的最小样本数： 我们还可以设置每个节点的最小样本数 $N$。如果每个节点的样本数等于 $N$，那么即使该节点不是纯节点，我们也会停止分裂。

在训练结束时（分裂），依赖于决策树末端的每个节点被称为“叶子”，因为它不是任何子树的根。每片叶子将代表样本最多的类别的产量。

＃＃ 结论

决策树因其高效、直观的背景和简单的实现而成为最著名的机器学习算法之一。该算法可以进一步与数值自变量（高斯决策树）一起使用，并且也可以扩展到解决回归任务。