← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 9751.f · 生成模型:DeepSeek-V4.1-Flash

贪心分裂的局部最优

理解等级:高级

贪心(greedy) 指每一步都选当前看上去最好的属性分裂,不回溯,也不比较“先选较差属性、后面或许能得到更小整树”的方案。ID3、C4.5、CART 都如此。

为什么这样做:候选组合的数量随属性数指数增长,穷举全局最优不可行;贪心把问题拆成每层一次局部比较,代价低、可扩展,这是决策树能用于高维数据的原因。

代价: - 一次坏分裂不可撤销。某属性在根节点增益略高,却把数据切得零散,后续每个子节点都只剩少量样本,树被迫长深; - 深层节点的统计量少,分裂结果噪声大,容易过度拟合; - 树对训练集的细微变动敏感,换一个子集可能得到结构很不同的树。

补救:用集成方法把多棵树的投票合起来,例如随机森林在选分裂点时再随机限制候选属性,装袋对样本重抽样。单棵树的方差被平均掉,预测更稳,代价是失去单棵树的可读性。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第7章 高级分析理论与方法:分类 · 查看原书依据

      决策树使用贪心算法(greedy algorithm),因为算法总是选择在当时看起来最好的选项。在每一步,算法选择使用哪个属性来分裂余下的记录。这种选择可能不是整体最好的,但是它能保证至少在那一步是最好的。

    参考来源

    - 位置:《数据科学与大数据分析 数据的发现 分析 可视化与表示》第7章 高级分析理论与方法:分类(源文件:extracted/数据科学与大数据分析 数据的发现 分析 可视化与表示/_epub-src/text/part0017_split_001.html) - 结论依据:7.1.4 节指出决策树使用贪心算法,每步选当下最好的分裂,并说明这种选择未必全局最优且坏分裂会影响后续。 - 原始内容:决策树使用贪心算法(greedy algorithm),因为算法总是选择在当时看起来最好的选项。在每一步,算法选择使用哪个属性来分裂余下的记录。这种选择可能不是整体最好的,但是它能保证至少在那一步是最好的。