＃＃ 介绍
决策树（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$，那么即使该节点不是纯节点，我们也会停止分裂。
在训练结束时（分裂），依赖于决策树末端的每个节点被称为“叶子”，因为它不是任何子树的根。每片叶子将代表样本最多的类别的产量。
＃＃ 结论
决策树因其高效、直观的背景和简单的实现而成为最著名的机器学习算法之一。该算法可以进一步与数值自变量（高斯决策树）一起使用，并且也可以扩展到解决回归任务。
