tree - 决策树分类属性的复杂性

Question

我正在尝试找出二元决策树算法的时间复杂度。我知道在每个节点，复杂性受限于搜索最佳属性的复杂性 O(m nlog n) 知道 m 是特征的数量并且 n 是训练集中的示例数。我认为我们应该将 O(m nlog n) 乘以节点数来计算整个算法的复杂度，对吗？我不明白为什么在某些资源中，决策树的复杂性仅被认为是O(m nlog n)!

谁能解释一下？根据使用的是分类属性还是连续属性，复杂度的计算是否有任何差异？

Answer 1

您只需排序一次，花费 m*nlog(n)。实际上，从排序数组构建决策树的过程渐近小于此。

例如，让我们构造决策树的初始节点。为此，我们采用贪心法并迭代每个特征 (m) 中的每个枢轴点 (n)，每次计算损失并给出阶数的复杂度n*米。树的下一层需要类似的复杂性，即使数据被分区，因为两个分区都被迭代。因此构建树的复杂度是n*m*d。与排序时间相比，这通常可以忽略不计，除非您的树深度与 log(n) 相当。

如果您的决策树没有给出最大深度，而是在每个数据点被分类之前构建，深度可以是 log(n) 和 n 分别用于完全平衡和不平衡的树。