我将分享我在实施这类决策树方面的经验。我在 R、Weka、Python 实现中也发现了一些想法。为了简单起见，我假设您谈论的是类似 CART 的树，但我解释的内容可以简单地扩展到任何类型的决策树。

• 您不需要存储所有拆分候选。原因是您在给定的运行中始终使用相同的标准：IG、IGR、Gini、熵、误差或其他。因此，您只需要保留最佳候选者，并为您需要的候选者提供：拆分变量名称、数字拆分标签（用于数字特征）、字符串拆分标签（用于名义变量）、给定标准的值（用于比较）仅此而已。这将为您节省一些线性内存
• 您不必为每个候选者拆分实例，因此您首先找到最佳候选者，并且只有在消除所有其他较弱的候选者之后，您才能拆分数据集。我经常看到这个错误，并且可能使每个评估节点的$O(n^2)$
• 对于数值变量，使用线性算法找到最佳分割：创建两组 bin，一组用于左节点，一组用于右节点，其中每个都有个 bin，对应于输出类的数量。最初，左侧的 bin 将包含所有总数。在迭代从左侧箱中减去并为右侧箱添加时，然后直接从箱中计算分割值标准。如果对于每个拆分值，您从数据点重新计算总数，您将再次获得$k$$O(n^2)$
• 对于名义变量，对 bin 使用相同的技巧，但这次有个bin，其中是名义变量的因子数。$P$$P$
• 您可以使用变量的预排序。最初，您在任何学习之前对所有变量进行排序。在每个节点评估时使用排序向量，在选择最佳分割后，您将分割数据点和排序索引，以便将数据子集和排序索引子集发送到子节点。因此，您可以在递归中应用这个想法。但是请注意，如果数据实例的数量大于输入特征的数量，则此方法有效
• 尽可能使用并行。由于它们的设计，有很多事情可以并行化：并行评估多个变量，并行评估多个树（对于随机森林，装袋）
• 不必要时避免评估：如果将二进制变量用作拆分变量，那么尝试在子节点中再次评估它是无用的，因为所有实例都将具有该变量的相同值
• 如果您有一个带有标签的二进制变量：“男性”、“女性”，您可以避免评估将“女性”发送到左侧、“男性”发送到右侧以及将“女性”发送到左侧和“男性发送到右侧”。两种变体是等价的.
• 对于数值变量，如果有很多数据点，可以避免评估所有分割的候选位置，仅针对随机选择的样本。据我所知，这是在 R 中实现的。人们可以安全地将这个技巧用于随机森林，其中关于分割点的精度并不重要，因为它被平均覆盖了

PS：但是我相信这个问题更多地属于SO