machine-learning - 完善的决策树分类

Question

想象一下，一组变量 V 的值与一组标签名称 T（分类标签）之间的所有已知映射的宇宙是已知的。此外，假设唯一变量值组合的总空间很大（> 100B 个点），标签集的大小相对较小（数千个元素）并且变量的数量非常少（4-10）。

什么是构建分类器函数的算法，它提供了从变量值到具有以下空间和时间复杂度目标的标签的完美映射（匹配没有误报或误报的先验知识）：

• 时间复杂度低于 O(|V|*log|T|)
• 空间复杂度小于 O(|V| ^k ), k ≤ e

或者，改写为决策树问题：

1. 如何调整决策树算法以创建完美映射？
2. 如何有效地表示训练数据以保证这一点？

Answer 1

您尝试实现的目标应该可以使用任何允许您以某种方式指定修剪级别的决策树分类器。这个想法是让它根本不做任何修剪。您最终得到的决策树将（可能）每个训练实例有一个叶子（即非常大），但会在预测时间 O(|V|*log|T|) 的情况下为您提供“完美”的准确性。

这完全独立于训练数据的表示方式（并且应该是）。唯一重要的是决策树诱导器可以读取和处理它。构建这种树的一种简单方法是为第一个示例添加路径，然后为第二个示例合并一个路径，依此类推。

当然，这样的分类器在实践中是否有用是一个完全不同的问题——在大多数情况下不会有用。