我不确定这是一个简单答案的问题，我也不认为这是一个甚至需要询问决策树的问题。

请咨询Aslan 等人。,计算树的 VC 维数(2009)。他们通过在小树中进行详尽的搜索来解决这个问题，然后提供一个近似的递归公式来估计大树上的 VC 维度。然后他们使用这个公式作为修剪算法的一部分。如果您的问题有一个封闭形式的答案，我相信他们会提供它。他们觉得有必要在很小的树上进行迭代。

我的两分钱值。我不确定谈论决策树的 VC 维度是否有意义。考虑一个$d$维度响应，其中每个项目都是二元结果。这是 Aslan 等人考虑的情况。有$2^d$该样本空间中的可能结果和$2^d$可能的响应模式。如果我建立一棵完整的树，$d$水平和$2^d$叶子，然后我可以粉碎任何图案$2^d$回应。但是没有人适合完整的树。通常，您会过度拟合，然后使用交叉验证进行修剪。最后得到的是一个更小更简单的树，但你的假设集仍然很大。阿斯兰等人。尝试估计同构树族的VC维数。每个族都是一个假设集，具有自己的 VC 维度。

上一张图片说明了一个空间树$d=3$这打破了4点：$(1,0,0,1),(1,1,1,0),(0,1,0,1), (1,1,0,1)$. 第四个条目是“响应”。阿斯兰等人。会认为一棵形状相同的树，但使用$x1$和$x2$，比如说，是同构的并且是同一假设集的一部分。因此，虽然这些树中的每棵树上只有 3 片叶子，但这些树的集合可以破碎 4 个点，在这种情况下，VC 维度为 4。但是，同一棵树可能出现在具有 4 个变量的空间中，在这种情况下，VC 维度将为 5。所以它很复杂。

Aslan 的蛮力解决方案似乎运作良好，但他们得到的并不是人们使用的算法的真正 VC 维度，因为这些依赖于修剪和交叉验证。很难说假设空间实际上是什么，因为原则上，我们从大量可能的树开始，然后修剪回更合理的东西。例如，即使有人先验地选择不超过两层，也可能仍然需要修剪树。而且我们并不真正需要 VC 维度，因为交叉验证直接针对样本外错误。

为了公平对待 Aslan 等人，他们不使用 VC 维度来表征他们的假设空间。他们计算分支的 VC 维度并使用该数量来确定是否应该切割分支。在每个阶段，他们使用所考虑分支的特定配置的 VC 维度。他们没有从整体上看待问题的 VC 维度。

如果您的变量是连续的并且响应取决于达到阈值，那么决策树基本上会创建一堆感知器，因此 VC 维度可能会大于该维度（因为您必须估计截止点才能进行拆分） . 如果响应单调地依赖于连续响应，CART 会将其分解为一系列步骤，尝试重新创建回归模型。在那种情况下，我不会使用树——可能是游戏或回归。

我知道这篇文章有点老了，并且已经有一个公认的答案，但由于它是第一个在询问决策树的 VC 维度时出现在 Google 上的链接，所以我将允许自己提供一些新信息作为跟进。

在最近的一篇论文中，Jean-Samuel Leboeuf、Frédéric LeBlanc 和 Mario Marchand 在最近的一篇论文中，Decision trees as partitioning machine to Characterize their generalization properties，作者在以下示例中考虑了决策树的 VC 维度：$\ell$功能（这是您问题的概括，仅涉及 2 个维度）。在那里，他们表明单个拆分（AKA 决策树桩）类的 VC 维度由最大整数给出$d$满足 。证明非常复杂，并且通过将问题重新表述为图上的匹配问题来进行。$2\ell \ge \binom{d}{\left\lfloor\frac{d}{2}\right\rfloor}$

此外，虽然仍然无法获得精确的表达式，但他们能够以递归方式给出一般决策树的增长函数的上限，从中他们表明 VC 维度是有序的，其中是树的叶子数。他们还根据他们的结果开发了一种新的剪枝算法，该算法在实践中似乎比 CART 的成本复杂度剪枝算法更好，无需交叉验证，表明决策树的 VC 维度是有用的。$\mathcal{O}(L_T \log (\ell L_T))$$L_T$

免责声明：我是该论文的作者之一。