2个 POSSIBLE 问题的数量由的子集的不同组合的数量定义，这些组合可能是第一个分区的一部分，然后是第二个分区，依此类推，直到树完成。那是最坏的情况。$2^{|S|}$$S$

想象一下：是第一个分隔符，所以分为Yes/No。然后分为 Yes/No。$loc \in{} N$$loc \in{} S$

然后是第三个分区，答案相同（是/否），您有 8 (2^3) 个问题。有许多组合使用/不使用/哪个组合在哪个步骤等，但最终您将要求树考虑所有可能性，即。$loc \in{} E$$2^{card(S)}$

作者指的是在构建树期间通过给定特征，给定节点可能分裂的数量。树可以将任何级别的子集发送到左侧，并将剩余级别发送到右侧。（好吧，实际上左右对称意味着选项的数量减少了一半，发送空集与发送完整集没有意义，因此实际的选择数是，但重点仍然是具有多个级别的分类变量是有问题的。）$2^{|S|-1}-1$

与连续变量或有序变量相比，我们考虑的拆分类型仅为与，并且只需要在级别数的范围内（再次到忽略发送什么都没有）。$x\leq\alpha$$x>\alpha$$\alpha$$|S|-1$$-1$

简而言之，当训练决策树时，它会计算所有可用类别值的拆分。现在假设您的数据中有 3 个类别，您将进行 2**3 计算 = 8（考虑到该特征的所有子集）

但是现在假设如果您在一个特征中有 20 个类别来计算单个拆分，您必须执行 2**20 = 1,048,576（大约 100 万次增益计算）。这就是为什么当类别数量增加时，运行决策树变得棘手