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|)。

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

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