C4.5 决策树：线性可分数据的深度是否可以高于非线性可分数据？
C4.5 decision tree: can deeps be higher in linear separable data then non-linear separable?
我突然想到，例如，假设我们有 N 个二维点的训练数据。我们知道我们总是可以天真地构建一个决策树，以便我们可以对每个数据点进行分类。 （可能我们过拟合了，深度可以到2N）
但是，我们知道如果数据集是线性可分的，那么决策树可能会占据优势。以上面的数据集为例，我们可以确定线性和非线性数据集的深度上限吗？是否保证线性情况的深度上限小于非线性情况？
suppose we have training data with N points in 2 dimensions. We know that we can always, naively, build a decision tree so that we can classify each data point.
如果有 2 个点具有相同的特征但标签不同，则不成立。
决策树根据轴进行拆分，因此线性可分离不一定会减少树中分离 classes 所需的拆分数。
Is it guaranteed that the upper bound of depth for linear case is smaller then nonlinear case?
没有。一个简单的反证是构造一个具有 2*N 个点和 N 个特征的线性可分数据集。对于class A，所有的特征值都是负的。对于class B，所有的特征值都是正的。让每个数据点只有 1 个非零特征值。
尽管是线性可分的，但此数据集需要对每个特征进行拆分（并因此增长到最大深度）才能学习。
有点晚了，但是，你仍然可以看看这个例子，在这个例子中，不可分离的线性数据集需要比线性可分离的更少的分割。
我突然想到，例如，假设我们有 N 个二维点的训练数据。我们知道我们总是可以天真地构建一个决策树，以便我们可以对每个数据点进行分类。 （可能我们过拟合了，深度可以到2N）
但是，我们知道如果数据集是线性可分的，那么决策树可能会占据优势。以上面的数据集为例，我们可以确定线性和非线性数据集的深度上限吗？是否保证线性情况的深度上限小于非线性情况？
suppose we have training data with N points in 2 dimensions. We know that we can always, naively, build a decision tree so that we can classify each data point.
如果有 2 个点具有相同的特征但标签不同，则不成立。
决策树根据轴进行拆分，因此线性可分离不一定会减少树中分离 classes 所需的拆分数。
Is it guaranteed that the upper bound of depth for linear case is smaller then nonlinear case?
没有。一个简单的反证是构造一个具有 2*N 个点和 N 个特征的线性可分数据集。对于class A，所有的特征值都是负的。对于class B，所有的特征值都是正的。让每个数据点只有 1 个非零特征值。
尽管是线性可分的，但此数据集需要对每个特征进行拆分（并因此增长到最大深度）才能学习。
有点晚了，但是，你仍然可以看看这个例子，在这个例子中，不可分离的线性数据集需要比线性可分离的更少的分割。