当 m 是特征数量，n 是样本数量时，python scikit-learn 站点 ( http://scikit-learn.org/stable/modules/tree.html ) 指出构建二叉决策树的运行时间是 mnlog(n)。
据我了解，log(n) 来自 split 后树的平均高度。我知道在每次拆分时，您都必须查看每个特征 (m) 并选择最佳的拆分依据。我知道这是通过为该节点 (n) 处的每个样本计算“最佳指标”(在我的例子中是基尼杂质)来完成的。但是，要找到最佳分割，这是否意味着您必须查看每种可能的方式来分割每个特征的样本？那不会是 2^n-1 * m 而不仅仅是 mn 之类的东西吗？我在想这个错误吗？任何建议都会有所帮助。谢谢。
最佳答案
构建决策树的一种方法是在每个点上执行如下操作:
- 对于要拆分的每个可能特征:
- 找到该特征的最佳分割。
- 确定这种拟合的“优度”。
- 在上面尝试过的所有选项中，选择最好的选项并将其用于拆分。
问题是如何执行每个步骤。如果您有连续数据，找到最佳分割的常用技术是将数据按该数据点的升序排序，然后考虑这些数据点之间所有可能的划分点，并采用使熵最小的划分点。这个排序步骤需要时间 O(n log n)，这在运行时占主导地位。由于我们对每个 O(m) 特性都这样做，因此运行时最终计算出每个节点完成的总工作量为 O(mn log n)。
关于algorithm - 为什么runtime要构造一个决策树mnlog(n)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34212610/