ID3、C4.5 和 CART 三种决策树有什么区别？

简化版

三者是决策树的三代经典算法。ID3：用信息增益选特征，只能处理离散特征、只做分类，不能处理连续值和缺失值，偏向取值多的特征，也不剪枝。C4.5：ID3 的改进版，改用信息增益比（修正偏向多值特征的缺陷），能处理连续特征和缺失值，支持剪枝，仍是多叉树、只做分类。CART：用基尼指数（分类）或平方误差（回归），既能分类又能回归，固定生成二叉树，支持剪枝，是 sklearn、随机森林、GBDT 等现代实现的基础。演进主线：ID3 → C4.5（修缺陷、加功能）→ CART（二叉、能回归、更实用）。

详细版

三者对比：

维度	ID3	C4.5	CART
分裂标准	信息增益	信息增益比	基尼指数(分类)/平方误差(回归)
任务	仅分类	仅分类	分类 + 回归
树结构	多叉树	多叉树	二叉树
连续特征	不支持	支持（阈值二分）	支持（阈值二分）
缺失值	不支持	支持	支持（代理分裂）
剪枝	无	悲观剪枝（后剪枝）	代价复杂度剪枝 CCP
特征复用	用过即弃	用过即弃	可重复使用
缺陷	偏向多值特征、易过拟合	计算慢（log、增益比）	—

关键改进链：

ID3 → C4.5：增益比修正多值偏好；加连续值、缺失值、剪枝。
C4.5 → CART：改二叉树 + 基尼（更快）；支持回归；成为工业标准。

完整版教学

一、为什么会有三代——一条「查漏补缺」的演进线

这三个算法不是并列关系，而是层层改进的三代：ID3 最早、最简单、缺陷最多；C4.5 修补 ID3 的缺陷、补齐工程能力；CART 进一步简化结构、扩展到回归，成为现代主流实现的基石。理解它们的最好方式，就是看后者解决了前者的什么问题。

二、ID3：最早的决策树，缺陷明显

ID3（Iterative Dichotomiser 3）是最早的决策树算法，核心是用信息增益选特征：每次选信息增益最大的特征分裂，直到子集纯净。

它的局限很多：

只能处理离散特征：对连续值（如年龄、收入）束手无策。
只能做分类，不能回归。
信息增益偏向取值多的特征：极端如「身份证号」分裂后每个子集一个样本、增益最大，但毫无泛化意义（见分裂标准专题）。
不能处理缺失值。
不剪枝，树容易长得过深、严重过拟合。
特征用过一次就不再用（多叉分裂用尽取值）。

这些缺陷催生了 C4.5。

三、C4.5：ID3 的全面升级

C4.5 是 ID3 作者的改进版，针对上面每条缺陷做了修补：

改用信息增益比：增益 / 特征固有值，惩罚取值多的特征，修正 ID3 的偏好缺陷（同时用启发式避免矫枉过正，见分裂标准专题）。
支持连续特征：把连续值排序后取相邻中点为候选阈值，按「≤t / >t」二分，选最优阈值。
支持缺失值：用「已知该特征的样本」计算增益并按比例折算；分裂时把缺失样本按权重分到各分支。
支持剪枝：用悲观剪枝（后剪枝）去掉泛化无益的分支，缓解过拟合。

代价：C4.5 计算较慢——要算 log（熵）、要算增益比、连续特征要排序遍历阈值，开销比后来的 CART 大。而且它仍是多叉树、只做分类。

四、CART：走向实用与统一

CART（Classification And Regression Tree）是现在最主流的实现（sklearn 的决策树、随机森林、GBDT 都基于它）。相比 C4.5 的关键变化：

二叉树结构：无论特征是离散还是连续，CART 每次都只分成两支（如离散特征按「属于某取值子集 / 不属于」二分）。二叉树结构统一、简洁、便于集成。
基尼指数替代熵（分类）：Gini=1-Σp²，不用 log、计算更快，效果和熵接近。
支持回归：叶子输出连续值，用平方误差（方差） 作分裂标准，选让子集方差和最小的分裂（详见回归树专题）。这让 CART 能同时干分类和回归。
代价复杂度剪枝（CCP）：用带正则项 误差 + α×叶子数 的准则做后剪枝，通过交叉验证选最优 α。
特征可重复使用：二叉分裂不会一次用尽一个特征的信息，同一特征可在不同层多次分裂。
缺失值用代理分裂（surrogate split） 处理。

正因为二叉、能回归、计算快、结构统一，CART 成了集成学习（随机森林、GBDT、XGBoost）的基学习器基础。

五、三代改进的逻辑串起来

ID3   ──信息增益──  仅离散/仅分类/偏多值/不剪枝/易过拟合
  │  改进：增益比修偏好 + 连续值 + 缺失值 + 剪枝
  ▼
C4.5  ──信息增益比── 多叉/仅分类/计算慢
  │  改进：二叉 + 基尼(更快) + 支持回归 + CCP剪枝
  ▼
CART  ──基尼/平方误差── 二叉/分类+回归/工业标准/集成基础

六、常见追问

现在实际用哪个？ 几乎都是 CART（或其变体）。sklearn 的 DecisionTreeClassifier/Regressor 就是 CART；随机森林、GBDT、XGBoost、LightGBM 的基树也源于 CART 思想。
为什么 CART 用二叉树？ 结构统一简洁、便于剪枝和集成；多叉树分支多、每支样本少、易过拟合且不好并入集成框架。
C4.5 为什么比 CART 慢？ 熵要算 log、还要算增益比、连续特征排序遍历，开销都比基尼大。
ID3 为什么偏向多值特征？ 多取值分出的子集更碎更纯、信息增益虚高（身份证号例子）。
C5.0 是什么？ C4.5 的商业改进版，更快更省内存，思路一致。

七、用同一高基数特征看三种算法的选择

假设 8 个样本正负各 4，父熵为 1。唯一 ID 把每个样本单独分开，信息增益为 1，但 SplitInfo 也是 log2(8)=3，增益率只有 1/3；一个真正有用的二值特征若信息增益 0.6、SplitInfo 为 1，增益率为 0.6。这个例子解释了 ID3 容易偏好多值特征，也说明增益率不是简单把所有小增益特征变好。

ID3: choose max InformationGain
C4.5: filter by information gain, then compare GainRatio
CART classification: choose max Gini decrease with binary splits

对象/方案	核心机制	选择或风险
ID3	信息增益	经典版本偏离散分类、无系统剪枝
C4.5	信息增益率启发式	支持连续/缺失与悲观剪枝，多叉或二分依特征
CART	分类 Gini、回归平方误差	始终二叉，成本复杂度剪枝

ID3 暴露多值偏好
  → C4.5 修正选择并补连续/缺失/剪枝
  → CART 统一分类与回归、固定二叉结构

记忆钩子：三者不是简单的版本号替换；面试要同时说清分裂指标、任务类型、分支形式与剪枝。

八、常见误区与追问

误区：C4.5 直接在所有特征中选增益率最大者。 经典启发式会先筛掉信息增益偏低的候选，避免增益率偏爱极少取值。
误区：CART 只能做分类。 CART 同时定义分类树与回归树。
追问：三者都能直接处理连续值吗？ 经典 ID3 不擅长，C4.5 和 CART 都有连续阈值机制。
追问：为什么 CART 坚持二叉分裂？ 二叉结构统一离散、连续以及分类/回归的递归处理。
追问：工程库一定严格实现论文原版吗？ 不一定，应检查具体库的缺失值、类别特征和剪枝能力。

九、加强记忆

三代决策树是层层改进：ID3 用信息增益，仅离散、仅分类、偏向多值特征、不剪枝、易过拟合；C4.5 改用信息增益比修正多值偏好，加上连续值、缺失值、剪枝，但仍是多叉、仅分类、计算慢（log+增益比）；CART 用基尼指数（分类，不用 log 更快）/ 平方误差（回归），是二叉树、既能分类又能回归、CCP 剪枝、特征可复用，成为 sklearn 和随机森林/GBDT/XGBoost 的基础。演进主线记牢：ID3 简单缺陷多 → C4.5 修缺陷补功能 → CART 二叉、能回归、最实用。

简化版

详细版