决策树寻找最佳划分为什么会有计算成本？

简化版

连续特征寻找最佳切分通常先排序，再扫描相邻取值间的候选阈值；单节点朴素成本约为 O(p·n log n)，预排序或直方图算法可降成本。高维、高基数和精确搜索会变慢，工程实现常用分箱、特征子采样与并行扫描换速度。

详细版

• 连续特征只需考虑相邻不同值之间，而不是所有实数阈值。

• 排序后可增量维护左右计数、和与平方和，避免每个阈值重扫样本。

• 类别特征的子集枚举可能指数增长，需要排序近似或限制。

• 直方图树先将连续值压到少量 bins，再扫描 bin 边界。

• 复杂度还受稀疏数据、缓存访问、节点深度和并行策略影响。

完整版教学

一、最佳切分是候选生成加增益扫描

树在每个节点都要回答“哪个特征的哪个边界最好”。

如果每试一个阈值都重新划分全部样本，成本会非常高；排序和前缀统计让相邻候选共享计算。

现代 GBDT 多采用直方图近似，用少量精度换取更规则的内存访问和更少候选。

单树规模虽小，原理相同。

二、数学机制怎么落到节点上

exact at one node: roughly O(p * n log n) with sorting；after sorted: threshold scan O(p * n)。

exact at one node: roughly O(p * n log n) with sorting
after sorted: threshold scan O(p * n)
histogram: O(p * n) build + O(p * B) scan, B << n

三、带数字的推演

节点有 100 万样本、100 特征，每个特征近 100 万唯一值；精确扫描候选巨大。

压成 256 个 bin 后，每特征只扫至多 255 个边界，候选由近 1 亿量级降到约 2.55 万。

四、方法对比

方法/对象	核心特点	代价或限制
精确排序	候选精细	时间和内存高
预排序	多节点复用次序	维护索引复杂
直方图	候选少、缓存友好	存在分箱近似误差

五、从训练到验证的执行链

节点样本 -> 生成特征候选/直方图 -> 前缀累计统计
-> 计算每个边界增益 -> 过滤叶约束 -> 选择最大合法增益 -> 分发样本

六、边界条件与工程代价

稀疏特征可只遍历非零值，并为缺失/零值选择默认方向；若仍按稠密矩阵扫描，会浪费大量计算和内存。

候选减少不必然降低泛化，适度分箱本身也有正则化作用；但关键阈值被合并时可能损失效果，应通过 bin 数消融评估。

记忆钩子：把切分搜索拆成“先排或分箱，再用前缀扫增益”。

七、常见误区与追问

• 误区：树会尝试所有实数作为阈值。 只需考虑排序后相邻不同值之间的边界。

• 追问：扫描时如何快速算回归损失？ 维护左右样本数、目标和与平方和即可增量计算 SSE。

• 误区：直方图算法只是为了省内存。 它也显著减少候选数量并改善缓存局部性。

• 追问：类别特征为何更难？ 无序类别的二分子集可能指数增长。

• 追问：特征子采样有什么作用？ 减少每个节点搜索成本，同时为集成模型增加多样性。

八、加强记忆

把切分搜索拆成“先排或分箱，再用前缀扫增益”。

精确法候选多，直方图用 B 个箱把扫描压到 p×B；类别子集则要警惕指数爆炸。