构造和执行回归树的计算复杂度是多少? [英] What is the computational complexity of constructing and performing a regression tree?

问题描述

构造和执行回归树的计算复杂度是多少?是否有任何分析或结论?

What is the computational complexity of constructing and performing a regression tree? Is there any analysis or conclusion on it?

谢谢！

推荐答案

答案很大程度上取决于选择最佳分割属性和分割点的过程.在分析中起关键作用的两个参数:

The answer largely depends on the procedure for selecting the best attribute to split and the split point. The two parameters that play a key role in the analysis:

• 属性数量；
• 培训示例数.

昂贵的部分将是计算连续属性的最佳分割点(本质上是离散化)，然后从候选属性集中选择最佳属性进行分割.

The expensive part will be computing the best split point for continuous attribute (this is essentially discretization), and selection the best attributes from among the set of candidate attributes to split on.

根据我的经验，复杂度通常在属性数量*(表示为a)上是二次的，而在示例数量(表示为n)上是线性的，即O(n * a ^ 2).

In my experience the complexity is often quadratic in the number of attributes *(denoted a) and linear in the number of examples (denoted n), that is, O(n * a^2).

但是，正如我所说，这确实取决于您的具体情况.如果您想要更具体的答案，请向我们提供更多详细信息.

But, as I said, it really depends on your specific case. Provide us with more details if you want a more concrete answer.

这篇关于构造和执行回归树的计算复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！