完美的决策树分类

Question

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

什么是建立一个分类功能，提供了一个完美的映射与下列时间和空间复杂度的目标（匹配，没有假阳性或假阴性的先验知识）的变量值标签的一个算法：

• 时间复杂性为O下（| V | *登录| T |）
• 空间复杂性为O更少（| V | ^ķ），K ≤ Ë

或者表述为：决策树问题：

1. 如何决策树算法进行调整，以创造一个完美的映射？
2. 如何有效地表示培训数据以保证？

Answer 1

你试图实现的任何决策树分类器都应该是可能的，它允许你以某种方式指定修剪的级别。这个想法是为了不让它做任何修剪。您最终得到的决策树每个训练实例（可能会）具有一个叶子（即非常大），但会以预测时间O（| V | * log | T |）给出“完美”的准确度。

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

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