决策树分类属性的复杂性

Question

我正在尝试找出二元决策树算法的时间复杂度。我了解到，在每个节点，复杂性受搜索最佳属性

O(m nlog n)

的复杂性的限制，知道

m

是特征的数量，

n

是训练集中示例的数量。我认为我们应该将

O(m nlog n)

乘以节点数来找到整个算法的复杂性，是吗？我不明白为什么在某些资源中，只考虑决策树的复杂性

O(m nlog n)

！

谁能解释一下？根据使用的是分类属性还是连续属性，复杂性的计算有什么不同吗？

Answer 1

只需排序一次，成本为

m*nlog(n)

。实际上从排序数组构建决策树是渐近小于这个的。

比如我们构造决策树的初始节点。为此，我们采用贪心法并迭代每个特征 (

n

) 中的每个枢轴点 (

m

)，每次计算损失并给出复杂度

n*m

。树的下一层需要类似的复杂性，即使数据被分区，因为两个分区都被迭代。因此构建树的复杂度是

n*m*d

。与排序时间相比，这通常可以忽略不计，除非您的树深度与

log(n)

相当。

如果你的决策树没有给出最大深度，而是在每个数据点被分类之前构建，深度可以是

log(n)

和

n

之间的任何地方，分别用于完全平衡和不平衡的树。

Answer 2

天真的实现是将

m*nlog(n)

乘以节点数，在最好的情况下（平衡树）是

log(n)

，在最坏的情况下是

n

。

但是通过使用缓存，可以在

O(m*nlog(n))

中一次完成排序。然后在每个节点，计算时间复杂度将是

O(nm)

以在每个节点找到最佳分割，因为排序已经完成。 Scikit-learn 声称可以将这个时间复杂度降低到

mlog(n)

。来源：https://scikit-learn.sourceforge.net/dev/modules/tree.html#complexity

因此，整体时间复杂度为

O(m*nlog(n)) + O(n*mlog(n)

，大致为

O(m*nlog(n))

。