决策树算法是线性的还是非线性的？

Question

最近，我的一位朋友在一次采访中被问及决策树算法是线性算法还是非线性算法。我试图寻找这个问题的答案，但没有找到令人满意的解释。有人能回答并解释这个问题的解决方案吗？另外，还有其他一些非线性机器学习算法的例子吗？

Answer 1

决策树是X到y的非线性映射.这是很容易看到的，如果你采取一个任意的函数，并创建树的最大深度。

例如：

if x = 1, y = 1
if x = 2, y = 15
if x = 3, y = 3
if x = 4, y = 27
...

当然，这是一棵完全适合的树，不会泛化.但它说明了为什么决策树是一个非线性映射。

Answer 2

最近，我的一个朋友在一次采访中被问到决策树算法是线性的还是非线性的。

决策树是一种非线性分类器，如神经网络等，一般用于非线性可分数据的分类。

即使考虑回归实例，决策树也是非线性的。

例如，线性回归线看起来有点像这样：

红点是数据点。

决策树回归图如下所示：

因此，显然决策树是非线性的。

Answer 3

正如许多人指出的那样，回归/决策树是一个非线性模型。然而，请注意，它是一个分段线性模型:在每个邻域(以非线性方式定义)中，它是线性的。事实上，模型只是一个局部常数。

要在最简单的情况下看到这一点，使用一个变量和一个节点\theta，树可以写成一个线性回归：

y_i = \alpha_1 1(x_i < \theta) + \alpha_2 1(x_i \geq \theta) + \epsilon_i

其中，1(A)是指示函数，如果事件A为真，则取1的值，否则为0。