决策树是一种基于树结构的分类与回归方法。它通过一系列的判断规则， 将样本从根节点逐步划分到叶节点，每个叶节点对应一个类别或数值。
包含所有训练样本，树的起点
对应一个属性测试，将样本分流
表示决策结果（类别标签）
决策树的构建是一个自顶向下的递归过程， 基于分而治之策略：
从当前节点的属性集合中，选择最能降低不确定性的属性
根据选定属性的取值，将样本集划分到对应的子节点
对每个非空子集，递归执行上述步骤，直至满足停止条件
当满足以下任一条件时，停止分裂并将当前节点标记为叶节点：
决策树学习的关键是如何选择最优划分属性。我们希望选择的属性能够最大程度地降低数据的不纯度， 使得划分后的子节点尽可能"纯"（即包含单一类别的样本）。
不同的决策树算法使用不同的划分标准：ID3 使用信息增益，C4.5 使用信息增益率，CART 使用基尼指数。
信息熵是度量样本集合纯度的常用指标。假设样本集合 D 中第 k 类样本所占比例为 pk， 则 D 的信息熵定义为：
Ent(D) = -Σ pk log2 pk
Ent(D) = 0
完全纯，所有样本同类
Ent(D) = 1
最不纯，类别均匀分布
Ent(D) ↑
混乱度越高
调整不同类别的样本数量，观察信息熵如何变化。熵值越小，数据集越纯；熵值越大，数据集越混乱。
观察要点：
信息增益表示使用属性 a 进行划分所获得的"纯度提升"。 信息增益越大，说明使用属性 a 划分后纯度提升越大。
Gain(D, a) = Ent(D) - Σ (|Dv|/|D|) × Ent(Dv)
Dv 表示属性 a 取值为 v 的样本子集
信息增益倾向于选择取值数目较多的属性（如"编号"属性）， 这可能导致过拟合。C4.5 算法通过信息增益率来缓解这个问题。
信息增益率通过引入"固有值"来对信息增益进行归一化，缓解信息增益对取值数目多的属性的偏好：
Gain_ratio(D, a) = Gain(D, a) / IV(a)
IV(a) = -Σ (|Dv|/|D|) × log2(|Dv|/|D|)
IV(a) 称为属性 a 的固有值，属性取值数目越多，IV(a) 通常越大
先从候选属性中找出信息增益高于平均水平的属性， 再从中选择信息增益率最高的。
基尼指数反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率。 基尼指数越小，数据集的纯度越高。
Gini(D) = 1 - Σ pk²
Gini_index(D, a) = Σ (|Dv|/|D|) × Gini(Dv)
选择使得 Gini_index 最小的属性作为最优划分属性
选择划分标准（信息增益、信息增益率、基尼指数），观察决策树的构建过程。点击节点查看详细信息和计算过程。
使用说明：
决策树在训练时为了尽可能正确分类训练样本，会不断分裂生长。 这可能导致过拟合： 树的分支过多过细，把训练集自身的特点当作了所有数据的一般性质。
剪枝是决策树学习算法对付过拟合的主要手段，通过主动去掉部分分支来降低过拟合风险。
在决策树生成过程中，提前停止树的生长。 在每个节点划分前，先评估划分是否能提升泛化性能。
✓ 优点：计算开销小，生成过程直接停止
✗ 缺点：可能过早停止，欠拟合风险
先生成完整的决策树，然后自底向上地检查非叶节点， 若将该节点替换为叶节点能提升泛化性能，则进行剪枝。
✓ 优点：保留更多有用分支，泛化性能更好
✗ 缺点：训练时间更长，需要额外验证集
| 特性 | 预剪枝 | 后剪枝 |
|---|---|---|
| 时机 | 生成过程中 | 生成完成后 |
| 计算开销 | 小 | 大 |
| 过拟合风险 | 低 | 更低 |
| 欠拟合风险 | 较高 | 低 |
| 泛化性能 | 较好 | 更好 |
前面讨论的都是离散属性。 但实际任务中常会遇到连续属性（如身高、体重、温度）。 最常用的方法是二分法（Binary Split）。
排序
将连续属性的所有取值按从小到大排序：a1, a2, ..., an
候选划分点
考虑相邻两个值的中点：ti = (ai + ai+1) / 2
选择最优划分点
将样本分为 ≤ t 和 > t 两部分，计算信息增益，选择最优的 t
与离散属性不同，连续属性在生成子树时可以继续使用（多次划分）。 例如，可以先判断"年龄 <= 30"，在某个分支下再判断"年龄 <= 25"。
现实任务中常会遇到属性值缺失的情况。 这给决策树学习带来两个问题：
如何在某属性值缺失的情况下，进行划分属性的选择？
给定划分属性后，若某样本在该属性上的值缺失，如何对该样本进行划分？
为每个样本赋予权重 w，初始时 w = 1。在属性选择时，只考虑该属性上无缺失值的样本， 根据这些样本的权重比例来调整信息增益的计算。
ρ = Σ(无缺失样本权重) / Σ(全部样本权重)
若某样本在划分属性上的值缺失，则将该样本同时划入所有子节点， 但权重按子节点样本比例分配。
例如：某节点有 60% 样本进入左子树，40% 进入右子树。 缺失值样本以 0.6 的权重进入左子树，0.4 的权重进入右子树。
直接删除包含缺失值的样本。简单但可能损失大量信息，仅适用于缺失比例很小的情况。
用某个值填充缺失值：
决策过程直观，可以转换为规则
可处理连续值、类别型、缺失值
对数据缩放不敏感
适合大规模数据集
自动进行特征筛选
需要剪枝来控制复杂度
数据微小变化可能导致树结构大变
局部最优，无法保证全局最优
倾向于多数类
只能沿特征轴划分，难以处理斜向边界
根据症状、检查结果等制定诊断规则，医生可以理解决策依据
根据个人信息、财务状况评估信用风险，结果可解释
根据邮件特征快速判断是否为垃圾邮件
NPC决策树，根据玩家行为做出不同反应
根据用户画像和行为推荐商品
识别异常交易模式，防范金融欺诈
为了克服单棵决策树的缺点，研究者提出了多种改进方法：
集成多棵决策树，通过"投票"提高稳定性和准确率。 是最流行的集成学习方法之一。
通过逐步拟合残差来提升性能。XGBoost、LightGBM 等是其高效实现。
每个内部节点使用多个属性的线性组合进行测试，可以处理斜向边界。
支持在线学习，新数据到来时无需重新训练整棵树。
✓决策树通过递归划分构建树结构，每个内部节点对应属性测试，叶节点对应决策结果
✓信息增益（ID3）、信息增益率（C4.5）、基尼指数（CART）是三种主流的划分标准
✓信息熵衡量样本集合的纯度，熵越小表示纯度越高
✓剪枝是对抗过拟合的主要手段，分为预剪枝和后剪枝两种策略
✓连续值通过二分法离散化，缺失值通过样本权重和多分支划入处理
✓决策树具有可解释性强、训练快速等优点，但容易过拟合、对数据敏感
✓集成方法（如随机森林、GBDT）通过组合多棵树显著提升性能