为什么运行时要构造决策树mnlog(n)？

当m是特征量而n是样本量时,python scikit-learn站点(http://scikit-learn.org/stable/modules/tree.html)指出构造二元决策树的运行时是mnlog(n).

我知道log(n)来自分割后树的平均高度.我知道在每次拆分时,你必须查看每个特征(m)并选择要拆分的最佳特征.我知道这是通过计算该节点(n)处每个样本的"最佳度量"(在我的情况下,基尼杂质)来完成的.但是,要找到最佳分割,这是否意味着您必须查看每种可能的方法来分割每个要素的样本？那不就是2 ^ n-1*m而不仅仅是mn吗？我在想这个错吗？任何建议都会有帮助.谢谢.

构建决策树的一种方法是在每个点上执行以下操作:

对于要拆分的每个可能功能:

找到该功能的最佳分割.

确定这种契合的"善".

在上面尝试的所有选项中,采取最好的方法并将其用于拆分.

问题是如何执行每一步.如果您有连续数据,找到最佳分割的常用技术是将数据按照该数据点按升序排序,然后考虑这些数据点之间的所有可能分区点,并采用最小化熵的分区.该排序步骤花费时间O(n log n),其占据运行时间.由于我们正在为每个O(m)功能执行此操作,因此运行时最终会计算出每个节点完成的O(mn log n)总工作量.