请逐一阐述决策树中的 ID3、C4.5 和 CART 算法。

回答思路

1. 【回答框架 1】ID3 算法由 Quinlan 提出，使用信息增益作为分裂准则，选择信息增益最大的属性进行划分。信息增益基于熵，公式为 Gain(A) = Ent(D) - Σ(|Dv|/|D|) * Ent(Dv)。其偏向于选择取值较多的属性，且只能处理离散特征，不能处理缺失值。
2. 【回答框架 2】C4.5 是 ID3 的改进，使用信息增益率作为分裂准则，通过引入分裂信息来惩罚多值属性，克服偏好问题。同时支持连续特征离散化、缺失值处理和剪枝。信息增益率 = 信息增益 / 分裂信息，但增益率可能偏向取值较少的属性，因此通常先选择信息增益高于平均的属性，再从中选增益率最高的。
3. 【回答框架 3】CART 算法既可分类也可回归，分类树使用基尼指数选择最优特征，回归树使用平方误差最小化。CART 生成二叉树，通过递归分割特征空间。基尼指数衡量数据纯度，选择基尼指数最小的特征进行分裂，并对特征取值二分化。
4. 【回答框架 4】三者的主要区别：分裂准则不同（信息增益、增益率、基尼指数），树结构不同（ID3和C4.5可能多叉，CART是二叉树），处理能力不同（ID3仅离散，C4.5支持连续和缺失，CART支持回归）。
5. 【关键点 1】ID3 用信息增益，C4.5 用信息增益率，CART 用基尼指数（分类）或平方误差（回归）。
6. 【关键点 2】C4.5 改进 ID3：克服多值偏好，支持连续特征与缺失值。
7. 【关键点 3】CART 是二叉树，可分类回归，是随机森林和 GBDT 的基学习器。
8. 【关键点 4】ID3 只能处理离散特征，易过拟合。
9. 【易错点 1】信息增益率会偏向取值较少属性，C4.5 需结合信息增益筛选。
10. 【易错点 2】基尼指数与信息增益结果可能差异，但通常相似。
11. 【易错点 3】CART 回归树输出叶子节点均值，平方误差最小化。