C++ 二叉决策树

二叉决策树是一种决策图表，按照顺序从根节点开始，到叶节点结束。在这里，叶节点代表我们通过决策想要实现的输出结果。它受到二叉树的直接启发。由于二叉树中每个节点最多可以有两个子节点，在每一步中，我们会选择其中一个或两个子节点来进行决策。

它是机器学习中使用的决策算法，当我们有大量数据并且希望在每一步处理后获得结果时使用。

如果没有适当的约束条件，决策树可能会一直扩展，直到每个节点只剩下一个样本或者非常少的样本。由于这种情况，模型会过度拟合，失去了准确推广的能力。可以通过使用一致的测试集、交叉验证和最大允许深度来避免这个问题。类平衡是另一个需要考虑的关键因素。当一个类占主导地位时，决策树可能产生不准确的结果，因为它们对于不平衡的类别是反应性的。可以使用一些重抽样技术或类别权重选项来缓解这个问题，例如scikit-learn提供的实现。通过避免偏见，可以相应地惩罚主导类别。

假设在一个数据集中，我们有n个数据点，每个数据点有m个特征。那么决策树可能是这个样子，其中t是阈值：

单一分裂节点

因此，在二叉决策树中，每个节点应该被选择成为能够以最佳方式分离数据的特征。如果我们选择这样的节点，它将减少步骤的数量，我们会以更少的步骤和复杂性得到目标。

在现实生活中，很难选择或找到一个能够最小化二叉决策树结构的特征。树的结构取决于我们选择的特征和阈值。

例如： 我们有一个学生班级，所有男孩都有黑色头发，女孩都有绿色头发。黑色中的学生可能有不同的长度，红色中也可能有不同的长度。如果我们的目标是获取黑色和绿色头发数据的组成，那么一个简单的二叉决策树可以如下所示：

这里 D 代表我们正在处理的完整数据集。 D left和 D right代表根据阈值切分后得到的左节点和右节点数据集。

I 代表节点的总不纯度度量。