决策树算法详解
一、经典决策树算法
1. ID3 算法
ID3 算法是决策树发展中的重要里程碑，其核心在于信息增益的应用。
- 信息增益：衡量某个属性对数据集 “纯度提升” 的程度，即该属性带来的熵减。信息增益越大，说明使用该属性划分数据能使分类结果更明确。
- 应用逻辑：在构建树的过程中，每次选择信息增益最大的属性作为当前节点的划分依据，逐步递归生成子树。
不过，ID3 存在明显局限：对可取值数目较多的属性有天然偏好。例如，若数据集中存在 “编号” 这类唯一标识属性，其信息增益往往最大，但以此划分毫无实际意义，会导致模型泛化能力极差。
2. C4.5 算法
为解决 ID3 的缺陷，C4.5 算法引入信息增益率作为划分标准：
- 信息增益率 = 信息增益 ÷ 属性自身的熵
- 优势：通过除以属性自身的熵（即属性的不确定性），抵消了对多值属性的偏好，使划分更合理。
例如，在判断 “是否出去玩” 的数据集（包含天气、温度、湿度等属性）中，C4.5 能更科学地选择划分属性，避免 ID3 可能出现的偏差。
3. CART 算法
CART（分类与回归树）是一种灵活的决策树算法，既可用于分类，也可用于回归，其核心指标是基尼指数：
- 基尼指数：反映从数据集 D 中随机抽取两个样本，类别标记不一致的概率。公式为 \(Gini(D) = 1 - \sum_{k=1}^{n} p_k^2\)，其中 \(p_k\) 是第 k 类样本在 D 中的占比。
- 特性：基尼指数越小，数据集纯度越高。CART 通过选择最小化基尼指数的属性进行划分，且始终生成二叉树（每个节点分为两个子节点）。
二、决策树的关键技术
1. 连续值处理
现实数据中常包含连续属性（如收入、年龄），处理方式如下：
- 步骤 1：对连续值排序，生成候选分界点（相邻样本值的中点）。例如，收入数据 [60K,70K,85K,...] 可生成 65K、77.5K 等分界点。
- 步骤 2：使用贪婪算法，选择最优分界点（如将收入划分为 “≤80K” 和 “>80K”），使划分后的数据纯度提升最大（通过信息增益或基尼指数衡量）。
- 本质：将连续值 “离散化”，转化为可用于划分的离散属性。
2. 剪枝策略
决策树易因过度拟合训练数据而导致泛化能力下降，剪枝是解决这一问题的核心手段，分为两种策略：
（1）预剪枝
- 原理：在决策树构建过程中同步剪枝，通过设置限制条件停止树的生长。
- 常见限制：最大深度（如限制树深不超过 20）、叶子节点最小样本数（如每个叶子至少包含 5 个样本）、最小信息增益（若某属性的信息增益低于阈值，则停止划分）。
- 优势：计算高效，能有效避免过拟合。
（2）后剪枝
- 原理：先构建完整的决策树，再从叶节点向上回溯，移除对泛化能力无增益的子树。
- 衡量标准：通过损失函数判断是否剪枝，损失函数为 “自身纯度（如基尼指数）+ α× 叶子节点数量”，其中 α 是正则化参数：
- α 越大，惩罚叶子节点数量的力度越强，树越简单（避免过拟合）；
- α 越小，更注重提升训练精度，可能保留更多复杂结构。
- 优势：剪枝更彻底，模型泛化能力通常优于预剪枝，但计算成本较高。
三、决策树的代码实现
在 Python 中，可通过scikit-learn库的DecisionTreeClassifier快速实现决策树，关键参数如下：
| 参数 | 说明 |
|---|---|
criterion | 划分标准，可选gini（基尼指数）或entropy（信息熵） |
splitter | 切分点选择方式，best（全局最优）或random（随机选择部分特征） |
max_depth | 树的最大深度，推荐设置为 5-20 以平衡拟合与泛化 |
max_features | 划分时考虑的最大特征数，可选None（所有特征）、sqrt（特征数的平方根）等 |
四、应用示例
决策树在实际场景中应用广泛，例如 “泰坦尼克号幸存者预测”：通过乘客的年龄、性别、票价等特征，构建决策树模型，可预测某名乘客是否幸存。其核心是从历史数据中学习特征与生存结果的关联规则（如 “女性更可能幸存”“儿童存活率更高” 等），并通过剪枝优化模型，提升预测准确性。
总结
决策树以其直观易懂、处理能力强（可处理离散与连续属性、多类别问题）等优势，成为机器学习中的经典算法。ID3、C4.5、CART 各有侧重，而连续值处理和剪枝技术则进一步提升了其适用性与稳健性。在实际应用中，需根据数据特点选择合适的算法和参数，以构建高效、可靠的决策树模型。