知识卡片
CART为何用二叉树反复切分
C4.5 之后仍有三个问题:熵模型带来大量对数运算;多叉树把特征一次性用尽;无法处理回归。CART(Classification And Regression Tree)用两个决定同时回应了前两个。
决定一:换准则。 分类用基尼系数,回归用平方误差最小化,都不需要 log,计算量大幅下降。
决定二:只做二叉切分。 这是 CART 与 ID3/C4.5 最本质的差别,落在”特征选择的最小单位”上:
- ID3/C4.5 的最小单位是一个特征。选定”婚姻状况”,划分方式就自动定死为按它的三个取值开三叉,之后这个特征再也不会出现。
- CART 的最小单位是某个特征下的某个切分点。同样是取值 {1,2,3} 的特征,CART 会枚举 {1}|{2,3}、{2}|{1,3}、{3}|{1,2} 三种二分,各算一次基尼或平方误差,选最小的那一种。
因为每次只定”切在哪”,同一特征可以在树的不同层被反复使用:先按收入切 12 万,之后再按收入切 18 万,把高收入段再细分。相比之下,C4.5 把 [0,12) 整体归为一类,区间内 3 万和 11 万的差异被直接丢弃——这是”划分过于粗糙、特征信息利用率低”的根源。
连续特征的处理也顺势统一:把取值排序,依次取相邻两值的中位数作候选切分点,n 个不同取值就有 n−1 个候选,逐个算指标取最优。枚举的代价是每层要扫描”特征数 × 切分点数”,比 ID3 只看特征数要贵,但换来的是更细的划分粒度和特征的复用。分类树的完整流程见 [[ID3的递归生成流程]] 的同构版本:判纯 → 找最优切分点 → 分左右递归。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第06章 决策树
原书出处 · 1 处
- 第6章 决策树 6.3.3 CART决策树 · 查看原书依据
当某一特征是离散值时,比如样本的某特征有{1,2,3}三种可能取值,那么CART将分别计算按照{1}和{2,3}、{2}和{1,3}、{3}和{1,2}三种情况划分时对应的基尼系数或平方误差,然后从中选择基尼系数最小或平方误差最小的划分组合来进行二切分,分叉成两个二叉子树。
参考来源
- 位置:《机器学习基础:从入门到求职》第6章《决策树》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00009.html)
- 结论依据:原文指出 C4.5 存在对数计算复杂、多叉划分粗糙、不能回归三点不足,说明 CART 分类用基尼、回归用平方误差,并以离散特征 {1,2,3} 的三种二分组合为例说明二叉切分的枚举方式。
- 原始内容:当某一特征是离散值时,比如样本的某特征有{1,2,3}三种可能取值,那么CART将分别计算按照{1}和{2,3}、{2}和{1,3}、{3}和{1,2}三种情况划分时对应的基尼系数或平方误差,然后从中选择基尼系数最小或平方误差最小的划分组合来进行二切分,分叉成两个二叉子树。