ID3、C4.5 和 CART 三种决策树有什么区别？
简化版
ID3、C4.5 和 CART 是三套经典决策树方法，但不能说成按年代顺序的“三代升级”：C4.5 是 ID3 的直接后继，CART 是独立发展的分类与回归树框架。经典 ID3 用信息增益，主要处理离散特征分类，容易偏好多值特征且原始版本没有系统剪枝；C4.5 用带筛选启发式的信息增益率，支持连续特征、缺失值和悲观剪枝；CART 分类常用 Gini、回归常用平方误差，每次固定二叉分裂，并用代价复杂度剪枝。具体库通常只借鉴其中思想，不一定完整复刻原算法。
详细版
| 维度 | ID3 | C4.5 | CART |
|---|---|---|---|
| 关系 | Quinlan 的早期算法 | ID3 的后继 | 独立的分类回归树体系 |
| 任务 | 经典版本做分类 | 分类 | 分类与回归 |
| 分裂指标 | 信息增益 | 信息增益率启发式 | 分类常用 Gini，回归常用 SSE |
| 分支形式 | 离散特征通常多叉 | 离散可多叉、连续阈值二叉 | 始终二叉 |
| 连续特征 | 经典版本不直接支持 | 支持阈值切分 | 支持阈值切分 |
| 缺失值 | 原始版本无完整机制 | 按可观测比例与分支权重处理 | 经典 CART 用 surrogate split |
| 剪枝 | 原始版本无系统后剪枝 | 悲观误差剪枝 | cost-complexity pruning |
C4.5 不是简单地“在所有候选中直接取增益率最大”：经典启发式会先约束候选的信息增益，避免极不均衡切分因 SplitInfo 很小而获得虚高比值。连续特征在后代节点仍可能以新阈值再次使用；“特征用一次就永远删除”主要适用于已按所有取值展开的离散多叉分裂。
完整版教学
一、先纠正三者的关系
ID3 与 C4.5 都由 Quinlan 提出，C4.5 明确继承并扩展 ID3。CART 则由 Breiman 等人形成独立体系，经典专著早于 C4.5；所以“ID3→C4.5→CART 的三代时间演进”是常见但错误的叙述。
更准确的记忆方式是两条线：
Quinlan 系：ID3 -> C4.5
Breiman 等：CART（Classification And Regression Trees）三者都采用自顶向下的贪心递归划分，但在指标、分支形式、任务范围、缺失处理和剪枝上有不同定义。
二、ID3：信息增益与离散分类
经典 ID3 在当前节点选择信息增益最大的离散特征：
InformationGain(D,A)
= H(D) - Σ_v |D_v|/|D| · H(D_v)离散特征通常按每个取值产生一个分支。若“用户 ID”几乎每个样本都不同，各子节点会很纯，信息增益很高，却没有新用户泛化能力，这就是多值偏好。原始 ID3 主要面向分类，不含 C4.5 那套连续值、缺失值和悲观剪枝机制。
说“ID3 永远不能扩展到连续值”也太绝对：工程上当然可以先离散化；面试中比较的是经典算法本身，而不是所有可能改造。
三、C4.5：ID3 的直接扩展
C4.5 以信息增益率为核心候选评分：
GainRatio(D,A) = InformationGain(D,A) / SplitInfo(D,A)
SplitInfo(D,A) = -Σ_v |D_v|/|D| · log₂(|D_v|/|D|)直接最大化比值可能偏爱极不均衡、SplitInfo 很小的切分，因此经典 C4.5 还结合信息增益筛选启发式，不是只背一个除法公式。它还加入：
- 连续变量排序后搜索阈值，产生
≤t与>t两支； - 缺失值下按非缺失比例修正评分，并让样本以分数权重进入分支；
- 对噪声和小样本误差作悲观估计后剪枝；
- 离散特征可多叉，连续特征阈值切分是二叉。
因此把 C4.5 统一说成“多叉树”会漏掉连续特征分裂；把所有用过的特征都删除，也会误伤可在后代使用新阈值的连续属性。
四、CART：统一分类与回归的二叉树
CART 的显著特征是每次都做二叉划分。连续变量按阈值二分；无序类别变量按 category∈S 与补集二分。分类树经典上用 Gini 不纯度，回归树常最小化左右节点残差平方和。
叶值也随任务变化：分类叶保存类别分布并取多数类，平方损失回归叶输出均值。CART 先生成一系列嵌套子树，再用代价复杂度目标选择复杂度：
R_α(T) = R(T) + α|leaves(T)|经典 CART 对缺失主切分值可寻找 surrogate split，即用另一特征尽量复现主切分的左右归属。某个现代库是否实现代理切分，必须查看具体实现，不能只因它叫“DecisionTree”就默认具备。
五、用同一高基数例子比较指标
假设 8 个样本正负各 4，父熵为 1 bit。唯一 ID 将每个样本分成单元素子节点，子熵为 0，因此 ID3 的信息增益为 1；其 SplitInfo 为 log₂8=3，增益率为 1/3。
另一个真正有用的二值特征若信息增益为 0.6、SplitInfo 为 1，增益率为 0.6。C4.5 的评分能抑制唯一 ID，但不是对所有高基数情况的数学免疫；有限样本、多次候选搜索仍会过拟合。
| 候选 | 信息增益 | SplitInfo | 增益率 |
|---|---|---|---|
| 唯一 ID | 1.0 | 3.0 | 0.333 |
| 有效二值特征 | 0.6 | 1.0 | 0.600 |
CART 若原生处理 8 类无序特征，要面对最多 2^(8-1)-1=127 个非重复二分集合；实际实现常通过排序、约束或编码避免穷举。
六、分支形式与特征复用
ID3/C4.5 对离散特征按所有取值多叉展开后，该路径下通常没有必要再用同一离散特征，因为取值已确定。C4.5 的连续属性只按一个阈值切开，后代仍可在剩余区间选择新阈值。
CART 始终二叉，一个类别集合或连续阈值只消耗部分划分能力，因此同一特征可在后代重复出现。复用不是 CART 独有到“其他方法绝不可能”的程度，必须连同特征类型和分裂方式说明。
七、现代库与集成树不要强行贴原版标签
许多现代库使用二叉树、Gini/SSE 或相似的贪心切分，看起来接近 CART，但可能没有原版 surrogate split、完整 cost-complexity pruning 或原生类别集合搜索。随机森林常以随机化的 CART 风格树为基学习器；GBDT、XGBoost、LightGBM 的叶值、增益、缺失路由和正则也各有扩展。
面试中可说“基于 CART 风格的二叉递归树思想”，不要说所有现代树库都是经典 CART 的逐行复刻。
选算法时也不应因为 Gini 少一次 log 就断言 CART 必然更快。总成本还取决于候选生成、排序/直方图、类别处理、稀疏访问和剪枝实现。
八、常见误区与追问
- 误区：ID3、C4.5、CART 是严格按年代升级的三代。 C4.5 继承 ID3，CART 是独立体系，且经典 CART 早于 C4.5。
- 误区：C4.5 在所有候选里无条件选增益率最大者。 经典算法还用信息增益筛选启发式，防止小 SplitInfo 造成异常比值。
- 误区：C4.5 永远是多叉且特征用过即弃。 连续属性做阈值二分，也可在后代使用新阈值。
- 追问：为什么 CART 能同时分类和回归？ 它为不同任务定义节点损失和叶值，同时保持统一二叉结构。
- 追问：CART 如何处理缺失值？ 经典方法使用代理切分，但具体软件可能改用默认方向、原生缺失分支或直接不支持。
- 追问：sklearn、XGBoost 都等于 CART 吗？ 不是；它们借鉴二叉递归树思想，但目标、缺失处理、正则和剪枝能力各不相同。
九、加强记忆
先记关系：C4.5 是 ID3 的后继，CART 是独立框架，不是第三代时间升级。再记差异：ID3 用信息增益做经典离散分类；C4.5 用带启发式的信息增益率，并补连续值、缺失值和悲观剪枝；CART 分类常用 Gini、回归常用 SSE，固定二叉并做代价复杂度剪枝。
最后补边界：C4.5 的离散特征可多叉、连续特征二叉且可复用；经典 CART 有 surrogate split，但现代库不一定完整复刻任何一个原版算法。