algorithm - 在决策树中查找非单调区域

Question

我有一个二叉决策树 T，它采用 n 个实数的向量 V，并通过遵循 V 上的每个坐标二进制拆分来输出一个数字 S。我想找到树的非单调区域。也就是说，如果我在 V 中再减少一个输入以形成 V'，然后树为 V' 分配比 V 更大的输出，那么我发现了一个非单调区域。

怎样才能找到这些地区？

Answer 1

我假设“每个坐标二进制分割”意味着一次在一个坐标上做出决定。对于 L1 的值低于 L2 的所有叶 L1 和 L2 对，确定 L1 和 L2 的轴对齐边界框。如果对于某些 L1 和 L2，L1 的最大角超过 L2 的最小角，则树是非单调的。相反，如果不存在这样的对，则树是单调的。

Answer 2

我没有提供细节，只是大致的方向。如果您需要更多详细信息，请告诉我。

假设你有一棵树，它考虑一个单一的特征（即一个实数）并输出一个单一的数字或一个范围。现在，很容易找到该树的非单调区域（在任何节点，如果左子树的范围与右子树的范围重叠，则树的该部分存在非单调区域）。

您可以将您的通用 DT 转换为仅适用于一个功能的 DT 并应用上述方法。

一般来说，您可以在每个节点上维护每个特征的范围，并使用我上面提到的相同标准来查找这些区域。