数据挖掘 - 给定 M 个二元变量和 R 个样本，决策树中的最大叶子数是多少？ - 吾爱随笔录

数据挖掘决策树理论

2022-02-10 10:59:10

给定 M 个二元变量和 R 个样本，决策树中的最大叶子数是多少？

我的第一个假设是最坏的情况是每个样本都有一个叶子，因此 R 叶子最大。我错了，应该与变量 M 的数量有某种联系吗？我知道决策树的最大深度是 M，因为变量可以在分支中出现一次，但我看不到与叶子数的关系。

提前致谢！

1个回答

M 二元变量的最大可能组合是

2^{M}

$2^M$ 所以本质上如果所有这些值都有不同的类，那么叶子的数量应该等于

i f R < 2^{M} => R e l s e 2^{M}

$if \ R<2^M => R \\ else \ 2^M$

一棵具有 M 个二进制变量的所有可能叶子的树最多可以包含 2^M 个组合，认为每个叶子都有一个可能组合的书面值，例如：0000,0001,0002,...,1110,1111，这些可以来只有一次，因为每个叶子只能关联 1 个标签

如果一行有多个标签，对于同一组输入，最大叶子数将等于 R 中的唯一输入组合

    A   B   label
0   1   0   0
1   0   0   1
2   1   1   2
3   1   1   1

在这种情况下，叶子的数量将是 3 而不是 4（输入数量）

其它你可能感兴趣的问题