本文介绍了为什么运行时要构造决策树mnlog(N)?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
当m是特征量,n是样本量时,python acadkit-Learning站点(http://scikit-learn.org/stable/modules/tree.html)声明构建二叉决策树的运行时是mnlog(N)。
我知道log(N)来自分裂后树的平均高度。我理解,在每次拆分时,您必须查看每个功能(M),然后选择最好的一个进行拆分。我知道这是通过为该节点(N)的每个样本计算一个"最佳度量"(在我的例子中,是一个基尼杂质)来实现的。然而,要找到最佳分割,这不是意味着您必须考虑每种可能的方法来分割每个特征的样本吗?这不就是2^n-1*m而不仅仅是Mn吗?我想错了吗?任何建议都会有帮助。谢谢您。
推荐答案
构建决策树的一种方法是在每个点执行以下操作:
- 对于要拆分的每个可能的功能:
- 查找该功能可能的最佳拆分。
- 确定此贴合的"好坏"。
- 在上面尝试的所有选项中,选择最佳选项并将其用于拆分。
问题是如何执行每个步骤。如果您有连续的数据,寻找最佳可能拆分的常用技术是沿着该数据点将数据排序为升序,然后考虑这些数据点之间的所有可能的分割点,并选择熵最小的分割点。此排序步骤耗费O(Nlogn)时间,这在运行时占主导地位。因为我们对每个O(M)特性都这样做,所以运行时最终计算出每个节点完成的总工作量为O(MN Log N)。
这篇关于为什么运行时要构造决策树mnlog(N)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!