当m是特征量并且n是样本量时，python scikit-learn站点（http://scikit-learn.org/stable/modules/tree.html）声明构造二元决策树的运行时是mnlog（n） .
我知道log（n）来自分割后树的平均高度 . 我知道在每次拆分时，你必须查看每个特征（m）并选择要拆分的最佳特征 . 我知道这是通过计算该节点（n）上每个样本的“最佳度量”（在我的例子中，基尼杂质）来完成的 . 但是，要找到最佳分割，这是否意味着您必须查看每种可能的方法来分割每个要素的样本？那不就是2 ^ n-1 * m而不仅仅是mn吗？我在想这个错吗？任何建议都会有帮助 . 谢谢 .
1 回答
构建决策树的一种方法是在每个点上执行以下操作：
对于要拆分的每个可能功能：
找到该功能的最佳分割 .
确定此拟合的"goodness" .
在上面尝试的所有选项中，采取最好的方法并将其用于拆分 .
问题是如何执行每一步 . 如果您有连续数据，找到最佳分割的常用技术是将数据按照该数据点按升序排序，然后考虑这些数据点之间的所有可能分区点，并采用最小化熵的分区 . 该排序步骤花费时间O（n log n），其占据运行时间 . 由于我们正在为每个O（m）功能执行此操作，因此运行时最终会计算出每个节点完成的O（mn log n）总工作量 .