知识卡片
决策树的三个分裂准则
决策树用贪心策略自顶向下递归生长:每一步在当前节点上挑一个“最能分开样本”的特征与切分点。三种经典准则的差别就在“怎么衡量分得开”。
1)ID3:用信息增益。熵 H(D) = −Σ p_i log p_i 度量节点的不纯度,条件熵 H(D|A) 是知道特征 A 之后剩下的不纯度,增益 = H(D) − H(D|A)。增益越大,说明用 A 划分后纯度提升越多。它只能处理离散特征,且天然偏爱取值多的特征——取值越多,越容易把样本切碎而显得“纯”。 2)C4.5:用增益率 = 增益 / 分裂信息,分母惩罚取值多的特征,从而纠正 ID3 的偏好;同时可处理连续特征与缺失值。 3)CART:二叉递归,每次按“是/否”二分,分类用基尼系数最小化,回归用误差平方和最小化;既可分类也可回归,是后续 GBDT、XGBoost 里回归树的原型。
工程边界:贪心分裂只保证局部最优;树越深越容易把噪声记成规则,因此还需要剪枝控制复杂度。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第8章 推荐系统的主要算法 · 查看原书依据
C4.5算法则使用增益率(Gain Ratio)作为选择分支的准则,同时引入分裂信息(Split Information)来惩罚取值较多的分类。
参考来源
- 位置:《智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)》第8章 推荐系统的主要算法(源文件:extracted/智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)/_epub-src/text/part0113.html)
- 结论依据:原文点明 C4.5 用增益率并以分裂信息惩罚多取值特征,说明它是在修正 ID3 偏爱多取值属性的缺陷。
- 原始内容:C4.5算法则使用增益率(Gain Ratio)作为选择分支的准则,同时引入分裂信息(Split Information)来惩罚取值较多的分类。