|
### 什么是决策树
决策树（Decision Tree）是一种基本的分类与回归方法，它基于树状图来进行决策。
**核心思想**：通过一系列的规则（if-then）对数据进行递归分割，最终形成一个树形的判断结构。
**直观理解**：类似于流程图，从根节点开始，每个内部节点表示一个属性上的判断条件，每个分支代表一个判断结果的输出，每个叶子节点代表一种分类结果（类别标签或连续值）。
### 为什么学决策树
- 决策树是机器学习中最基础的算法之一，是理解更复杂算法（随机森林、GBDT、XGBoost）的基石
- 具有极好的**可解释性**，结果直观可视，非技术人员也能理解
- 既可以处理**分类问题**，也可以处理**回归问题**
- 不需要复杂的特征工程，能同时处理数值型和类别型特征
- sklearn 中通过 `DecisionTreeClassifier` 和 `DecisionTreeRegressor` 实现
### 快速上手
```python
from sklearn.tree import DecisionTreeClassifier
# 定义模型
model = DecisionTreeClassifier(criterion="gini", max_depth=5)
# 训练
model.fit(X_train, y_train)
# 预测
y_pred = model.predict(X_test)
# 评估准确率
model.score(X_test, y_test)
```
|
|
### 决策树的树结构
```
根节点(Root Node)
/ 特征A ≤ 阈值? \
/ \
内部节点(Internal) 内部节点(Internal)
/ 特征B ≤ 阈值? \ / 特征C ≤ 阈值? \
/ \ / \
叶子节点 叶子节点 叶子节点 叶子节点
(类别A) (类别B) (类别B) (类别C)
```
**节点类型**：
| 节点类型 | 说明 |
|---------|------|
| **根节点** (Root) | 树的起点，包含全部训练数据 |
| **内部节点** (Internal) | 表示一个特征上的判断条件，执行二分划分 |
| **叶子节点** (Leaf) | 终端节点，表示最终的分类结果或回归值 |
**重要特性**：
- 决策树是**二叉树**结构（CART算法），每个非叶子节点最多有两个分支
- 从根到任一叶子节点的路径构成一条**分类规则**
- 路径上的条件用 `AND` 连接，形成 `if-then` 规则
|
|
### 决策树学习的三大步骤
决策树的学习过程包括三个核心步骤：**特征选择 → 决策树生成 → 决策树剪枝**。
#### 1. 特征选择
选取对训练数据具有分类能力的特征，决定使用哪个特征来划分数据空间。常用标准：
- **信息增益**（ID3 算法）：得知特征 X 的信息而使得类 Y 的不确定性减少的程度
- **信息增益比**（C4.5 算法）：信息增益和特征熵的比值，克服偏向取值多的属性
- **基尼指数**（CART 算法）：衡量数据集的纯度，基尼指数越小纯度越高
#### 2. 决策树生成
根据选择的特征评估标准，从上至下**递归地**生成子节点：
1. 选择最优特征和切分点
2. 按条件将数据分为两个子集
3. 对每个子集递归重复步骤1~2
4. 直到数据不可再分或满足停止条件
这一过程形成的树往往对训练数据拟合很好，但可能**过拟合**。
#### 3. 决策树剪枝
为了解决过拟合问题，需要剪枝：
| 剪枝策略 | 说明 |
|---------|------|
| **预剪枝** (Pre-pruning) | 在生成过程中，若当前节点划分不能提升泛化性能，则停止划分 |
| **后剪枝** (Post-pruning) | 先生成完整树，再自底向上考察，若替换子树为叶节点能提升泛化性能则替换 |
> **关键理解**：生成是"从上到下"构建树，剪枝是"从下到上"简化树。两者结合才能得到泛化能力好的模型。
|
|
### 决策树算法总览与对比
| 算法 | 提出者 | 特征选择标准 | 树的类型 | 支持任务 | 剪枝 |
|------|--------|-------------|---------|---------|------|
| **ID3** | Quinlan (1986) | 信息增益 | 多叉树 | 分类（离散特征） | 无 |
| **C4.5** | Quinlan (1993) | 信息增益比 | 多叉树 | 分类（离散+连续） | 有 |
| **CART** | Breiman (1984) | 基尼指数 / 平方误差 | 二叉树 | 分类+回归 | 有 |
**选择建议**：
- sklearn 中 `DecisionTreeClassifier` 默认使用 CART + 基尼指数
- 基尼指数 vs 信息熵：实际效果基本相同，基尼指数计算更快
- CART 是最常用的决策树算法，sklearn 的实现就是基于 CART
### 核心区别
```
ID3：根据信息增益选择特征 → 剔除该特征 → 递归
倾向于选择取值多的属性
C4.5：用信息增益比替代信息增益 → 克服ID3偏向
能处理连续特征和缺失值
CART：根据某个指标选择特征 → 将数据分为两类 → 递归
生成二叉树，既能分类也能回归
```
|
|
### ID3 算法
**核心思想**：使用**信息增益**（Information Gain）作为特征选择标准。
**信息增益的含义**：反映在给定条件后不确定性减少的程度。特征取值的信息增益越高，意味着确定性越高，条件熵越小。
**算法流程**：
1. 计算每个特征的信息增益
2. 选择信息增益最大的特征作为当前节点的划分特征
3. 根据该特征的取值创建子节点
4. 剔除已选特征，递归处理子节点
5. 直到所有特征用完或信息增益小于阈值
**ID3 的局限**：
- 倾向于选择**取值多的属性**（因为取值越多，信息增益越大）
- 只能处理**离散型**变量，无法直接处理连续值
- 对样本**缺失值**比较敏感
- **没有剪枝**过程，容易过拟合
- 多叉树结构，非二叉树
|
|
### C4.5 算法
C4.5 是 ID3 的改进版本，由同一作者 Quinlan 提出。
**核心改进**：使用**信息增益比**（Gain Ratio）替代信息增益来选择划分属性。
**信息增益比** = 信息增益 / 特征本身的熵（Split Information）
这个改进**克服了 ID3 偏向取值多属性**的问题，因为信息增益比考虑了特征本身的熵，对取值多的属性进行了惩罚。
**C4.5 相对 ID3 的增强**：
| 特性 | ID3 | C4.5 |
|------|-----|------|
| 特征选择标准 | 信息增益 | 信息增益比 |
| 连续数值特征 | 不支持 | 支持（离散化处理） |
| 剪枝技术 | 无 | 有（悲观剪枝） |
| 缺失值处理 | 不支持 | 支持 |
| 树的类型 | 多叉树 | 多叉树 |
**C4.5 的局限**：
- 效率相对较低，需要对数据集多次扫描和排序
- 只能用于分类问题，不能处理回归问题
- 树结构仍为多叉树，不如二叉树简洁
|
|
### CART 算法（Classification and Regression Trees）
CART 是目前最主流的决策树算法，sklearn 的决策树实现就是基于 CART。
**核心特点**：
- 采用**二分递归分割**技术，每个非叶子节点只有两个分支
- 既能处理**分类问题**（使用基尼指数），也能处理**回归问题**（使用平方误差）
- 生成结构简洁的**二叉树**
**CART 分类树**：
- 使用**基尼指数**作为划分标准
- 每次选择使基尼指数最小的特征和切分点
**CART 回归树**：
- 使用**平方误差**（MSE）作为划分标准
- 每个叶子节点的预测值 = 该叶子节点所有样本目标变量的**均值**
- 选择最优切分点：遍历所有特征和切分值，使划分后的平方误差最小
**CART 回归树示例**：
```python
from sklearn.tree import DecisionTreeRegressor
model = DecisionTreeRegressor(max_depth=5)
model.fit(X_train, y_train) # y_train 为连续值
y_pred = model.predict(X_test)
```
**CART 的剪枝**：
- **预剪枝**：通过设置停止条件限制树的生长（max_depth、min_samples_leaf 等）
- **后剪枝**：代价复杂度剪枝（Cost-Complexity Pruning），通过计算表面误差率增益值来选择是否剪枝
|
|
### 基尼（Gini）算法详解
基尼指数是 CART 决策树在处理**分类问题**时的核心评价指标。
#### 什么是基尼指数
基尼指数（Gini Index / Gini Impurity）衡量的是：**从数据集中随机选取两个样本，其类别标签不一致的概率**。
- 基尼指数**越小**，数据集的**纯度越高**
- 基尼指数 = 0 时，表示节点完全纯净（所有样本属于同一类别）
- 基尼指数最大值为 1 - 1/k（k 为类别数）
#### 计算公式
$$Gini(D) = 1 - \sum_{k=1}^{K} p_k^2$$
其中 $p_k$ 表示第 k 类样本所占的比例，K 为类别总数。
**条件基尼指数**（按特征 A 划分后）：
$$Gini(D, A) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2)$$
#### 基尼指数在决策树中的应用
1. **遍历**每个特征及其所有可能的划分点
2. 计算每个划分点产生的**左右子节点的基尼指数加权平均**
3. 选择使基尼指数**最小化**的特征和划分点作为当前节点
4. 递归对子节点重复步骤 1~3
#### 基尼指数 vs 信息熵
| 对比项 | 基尼指数 | 信息熵 |
|--------|---------|--------|
| 公式 | $1 - \sum p_k^2$ | $-\sum p_k \log_2(p_k)$ |
| 计算速度 | 更快（无需对数运算） | 较慢 |
| 分类效果 | 与信息熵基本相同 | 与基尼基本相同 |
| sklearn默认 | **是** | 否（可选 `criterion='entropy'`） |
> **实际使用建议**：两者效果几乎无差异，sklearn 默认使用基尼指数是因为计算更快。无需纠结选哪个。
|
|
### 信息熵（Information Entropy）
信息熵是度量数据**不确定性（混乱程度）**的指标。
#### 定义
$$H(D) = -\sum_{k=1}^{K} p_k \log_2(p_k)$$
其中：
- $D$ 是数据集
- $K$ 是类别总数
- $p_k$ 是第 k 类样本所占的比例（$p_k = \frac{|C_k|}{|D|}$）
#### 直观理解
- 熵**越大** → 数据越**混乱**（各类别均匀分布）
- 熵**越小** → 数据越**纯净**（某一类占绝对多数）
- 熵 = 0 → 数据完全纯净（所有样本属于同一类）
#### 举例
```
数据集A: [正,正,正,正,正,负,负,负,负,负] → 5正5负 → H = 1.0（最大混乱）
数据集B: [正,正,正,正,正,正,正,正,正,负] → 9正1负 → H ≈ 0.47（较纯净）
数据集C: [正,正,正,正,正,正,正,正,正,正] → 10正0负 → H = 0（完全纯净）
```
> **决策树的目标**：通过不断划分，使子节点的熵越来越小（越来越纯净）。
|
|
### 信息增益（Information Gain）
信息增益 = 划分前的熵 - 划分后的熵（条件熵）
$$Gain(D, A) = H(D) - H(D|A)$$
其中条件熵：
$$H(D|A) = \sum_{i=1}^{n} \frac{|D_i|}{|D|} H(D_i)$$
- $A$ 是划分特征
- $D_i$ 是按特征 A 的第 i 个取值划分后的子集
- $n$ 是特征 A 的取值个数
#### 信息增益比
$$Gain\_ratio(D, A) = \frac{Gain(D, A)}{H_A(D)}$$
其中 $H_A(D)$ 是特征 A 本身的熵（Split Information）：
$$H_A(D) = -\sum_{i=1}^{n} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$$
#### 计算示例
假设 10 个样本，6 个正例、4 个反例：
```
划分前：H(D) = -(6/10)log2(6/10) - (4/10)log2(4/10) ≈ 0.971
按特征A划分后：
子集D1(4正1反)：H = -(4/5)log2(4/5) - (1/5)log2(1/5) ≈ 0.722
子集D2(2正3反)：H = -(2/5)log2(2/5) - (3/5)log2(3/5) ≈ 0.971
条件熵 = (5/10) × 0.722 + (5/10) × 0.971 ≈ 0.847
信息增益 = 0.971 - 0.847 = 0.124
```
信息增益越大，说明该特征对分类的贡献越大。
|
|
### 基尼指数计算详解
#### 公式
$$Gini(D) = 1 - \sum_{k=1}^{K} p_k^2$$
#### 计算示例
假设 10 个样本，6 个正例、4 个反例（二分类）：
```
Gini(D) = 1 - (6/10)² - (4/10)²
= 1 - 0.36 - 0.16
= 0.48
```
按特征 A（阈值 t）划分后：
```
左子集 D1 (≤ t)：4正1反
Gini(D1) = 1 - (4/5)² - (1/5)² = 1 - 0.64 - 0.04 = 0.32
右子集 D2 (> t)：2正3反
Gini(D2) = 1 - (2/5)² - (3/5)² = 1 - 0.16 - 0.36 = 0.48
划分后的基尼指数 = (5/10) × 0.32 + (5/10) × 0.48 = 0.40
```
基尼指数从 0.48 降到 0.40，说明这次划分有效。
#### sklearn 中的验证
```python
from sklearn.tree import DecisionTreeClassifier
import numpy as np
# 模型使用基尼指数
model = DecisionTreeClassifier(criterion="gini", max_depth=5)
model.fit(X_train, y_train)
# 查看每个节点的不纯度（基尼指数）
print(model.tree_.impurity)
# array([0.4675, 0.1589, 0.0299, 0.0074, ...])
# 根节点不纯度最高，叶子节点最低
```
> **决策树每次划分的目标**：找到使条件基尼指数最小的特征和切分点。
|
|
### DecisionTreeClassifier 参数总览
| 参数 | 默认值 | 说明 |
|------|--------|------|
| `criterion` | `'gini'` | 特征选择标准：`'gini'`（基尼系数）或 `'entropy'`（信息熵） |
| `splitter` | `'best'` | 划分策略：`'best'`（最优划分）或 `'random'`（随机局部最优） |
| `max_depth` | `None` | 树的最大深度，None 表示不限制 |
| `min_samples_split` | `2` | 内部节点再划分所需最小样本数 |
| `min_samples_leaf` | `1` | 叶子节点最少样本数 |
| `min_weight_fraction_leaf` | `0` | 叶子节点最小样本权重和 |
| `max_features` | `None` | 划分时考虑的最大特征数 |
| `random_state` | `None` | 随机种子，设置后结果可复现 |
| `max_leaf_nodes` | `None` | 最大叶子节点数 |
| `min_impurity_decrease` | `0` | 节点划分最小不纯度下降值 |
**参数调优优先级**：`max_depth` > `min_samples_leaf` > `min_samples_split` > `max_features`
|
|
### criterion — 特征选择标准
决定不纯度的计算方法，影响特征选择的结果。
```python
# 基尼系数（默认，计算更快）
model = DecisionTreeClassifier(criterion="gini")
# 信息熵（效果与基尼基本相同）
model = DecisionTreeClassifier(criterion="entropy")
```
| 选项 | 公式 | 特点 |
|------|------|------|
| `'gini'` | $1 - \sum p_k^2$ | 计算更快，无需对数运算 |
| `'entropy'` | $-\sum p_k \log_2(p_k)$ | 理论基础更强，对纯度更敏感 |
**两者效果基本相同**，sklearn 默认使用 `'gini'` 主要是因为计算效率更高。在实际项目中无需纠结选哪个。
### splitter — 划分策略
| 选项 | 说明 | 适用场景 |
|------|------|---------|
| `'best'` | 在所有划分点中找最优 | 样本量不大（推荐） |
| `'random'` | 随机在部分划分点中找局部最优 | 样本量非常大时加快训练 |
|
|
### max_depth — 最大深度
决策树的最大深度（从根到最远叶子的最长路径）。
**这是最重要的调参参数**，直接控制模型复杂度。
#### 深度与节点数的关系（完全二叉树）
```
depth=1 → 最多 3 个节点（1根 + 2叶）
depth=2 → 最多 7 个节点
depth=3 → 最多 15 个节点
depth=n → 最多 2^(n+1) - 1 个节点
depth=6 → 最多 127 个节点
depth=7 → 最多 255 个节点
```
> 通常机器学习中的特征列到不了 128，所以 **max_depth 取 6 就算大的了**。
#### 设置建议
| 场景 | 建议 max_depth |
|------|---------------|
| 特征少（<10） | 3~5 |
| 特征中等（10~50） | 5~10 |
| 特征多（>50） | 10~20 |
| 不确定 | 先不设（None），观察过拟合后调整 |
#### 调参策略
1. **开始不设** max_depth，让树自由生长，观察是否过拟合
2. 尝试设置 max_depth 为特征数量的**平方根或对数**
3. 使用**交叉验证**评估不同 max_depth 的效果
4. 结合 `min_samples_leaf` 等参数共同调优
|
|
### min_samples_leaf — 叶子节点最少样本数
控制叶子节点上最少的样本数量。如果某叶子节点样本数少于该值，会和兄弟节点一起被**剪枝**。
```python
# 叶子节点至少包含10个样本
model = DecisionTreeClassifier(min_samples_leaf=10)
```
**作用**：
- 控制了叶子节点上样本的数量不能过少
- 限制了树的复杂度，防止过拟合
- 值越大，树越简单（越保守）
**设置建议**：
| 场景 | 建议值 |
|------|--------|
| 样本量小（<1000） | 1~5 |
| 样本量中（1000~10000） | 5~50 |
| 样本量大（>10000） | 50~200 |
> **经验法则**：通常设置为样本量的 1%~5%，但不低于 5。
|
|
### 其他重要参数
#### min_samples_split — 内部节点最小分裂样本数
如果某节点的样本数少于该值，则不会继续划分。
```python
model = DecisionTreeClassifier(min_samples_split=10)
# 默认值为 2
```
#### max_features — 划分时考虑的最大特征数
限制每次划分时考虑的特征数量，有助于防止过拟合。
```python
model = DecisionTreeClassifier(max_features='sqrt') # 特征数的平方根
model = DecisionTreeClassifier(max_features=10) # 最多考虑10个特征
model = DecisionTreeClassifier(max_features=0.5) # 考虑50%的特征
```
| 值 | 说明 |
|----|------|
| `None`（默认） | 考虑所有特征 |
| `'sqrt'` | 考虑 √n 个特征 |
| `'log2'` | 考虑 log₂(n) 个特征 |
| `int/float` | 指定数量或比例 |
#### min_impurity_decrease — 最小不纯度下降值
如果某次划分的不纯度下降值小于该阈值，则不会划分。
```python
model = DecisionTreeClassifier(min_impurity_decrease=0.01)
# 默认值为 0
```
#### max_leaf_nodes — 最大叶子节点数
直接限制叶子节点的数量，防止树过于复杂。
#### class_weight — 类别权重
防止训练集某些类别的样本过多导致模型偏向。
```python
model = DecisionTreeClassifier(class_weight='balanced') # 自动平衡
```
|
|
### Iris 鸢尾花分类示例
```python
import joblib
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from tpf.datasets import load_iris
X_train, y_train, X_test, y_test = load_iris()
# 模型定义
model = DecisionTreeClassifier(criterion="gini", max_depth=5)
# 训练
model.fit(X=X_train, y=y_train)
# 预测
y_pred = model.predict(X=X_test)
# 评估
score = model.score(X_test, y_test)
print(f"准确率: {score:.4f}")
# 保存模型（推荐使用 joblib）
joblib.dump(model, "model1.pkl")
# 加载模型
model_loaded = joblib.load("model1.pkl")
```
|
|
### 分类预测与概率
`predict` 返回类别标签，`predict_proba` 返回各类别的概率。
```python
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from ai.datasets import load_iris
X_train, y_train, X_test, y_test = load_iris()
model = DecisionTreeClassifier(criterion="gini", max_depth=5)
model.fit(X=X_train, y=y_train)
# predict 返回标签的类别索引
print(model.predict(X=X_test))
# [1, 0, 2, 0, 1, 1, 0, 2, 1, 2, 2, 2, 0, 0, 0, 2, 1, 2, 1, 2,
# 2, 2, 2, 0, 2, 1, 0, 0, 0, 0]
# predict_proba 返回各类别的概率（one-hot 向量）
print(model.predict_proba(X=X_test))
# [[0., 1., 0.], → 第1个样本属于类别1的概率为100%
# [1., 0., 0.], → 第2个样本属于类别0的概率为100%
# [0., 0., 1.], → 第3个样本属于类别2的概率为100%
# ...]
```
**关键理解**：
- `predict` → 返回概率最大的类别索引（确定性预测）
- `predict_proba` → 返回所有类别的概率分布（不确定性量化）
|
|
### 决策树回归示例
决策树回归使用 `DecisionTreeRegressor`，预测值为叶子节点样本的均值。
```python
from sklearn.tree import DecisionTreeRegressor
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split
# 生成回归数据
X, y = make_regression(n_samples=1000, n_features=10, noise=10, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
# 回归树模型
model = DecisionTreeRegressor(max_depth=5, min_samples_leaf=10)
model.fit(X_train, y_train)
# 预测连续值
y_pred = model.predict(X_test)
# 评估（R²分数）
score = model.score(X_test, y_test)
print(f"R² 分数: {score:.4f}")
# 叶子节点的预测值 = 该叶子所有训练样本 y 的均值
```
**分类树 vs 回归树对比**：
| 对比项 | 分类树 | 回归树 |
|--------|--------|--------|
| sklearn类 | `DecisionTreeClassifier` | `DecisionTreeRegressor` |
| 预测输出 | 类别标签 | 连续值 |
| 划分标准 | 基尼指数/信息熵 | 平方误差(MSE) |
| 叶子节点值 | 多数类别的标签 | 样本目标值的均值 |
| 评估指标 | accuracy, F1 | R², MSE, MAE |
|
|
### 特征重要性的原理
`model.feature_importances_` 返回每个特征对决策的重要性分数。
**原理**：一个特征的重要性 = 该特征在所有节点上带来的不纯度下降值的加权平均。
```python
model = DecisionTreeClassifier(criterion="gini", max_depth=5)
model.fit(X_train, y_train)
# 特征重要性数组，与 X 的列一一对应
importances = model.feature_importances_
print(importances)
# [0. , 0.0018, 0. , 0. , ..., 0.1199, 0. , 0. ]
# 所有特征重要性之和 = 1.0
print(sum(importances)) # 1.0
```
**解读**：
- 值为 0 的特征：该特征未被使用（对划分无贡献）
- 值越大：该特征对分类决策越重要
- 可以用于**特征筛选**：剔除重要性为 0 的特征
```python
import numpy as np
# 获取重要性排序后的特征索引
sorted_idx = np.argsort(importances)[::-1]
# 取前 N 个重要特征的索引
top_n = 10
top_features = sorted_idx[:top_n]
```
|
|
### 简易示例：验证特征重要性
通过加入噪声列来验证特征重要性的正确性：
```python
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from ai.datasets import load_iris
X_train, y_train, X_test, y_test = load_iris()
# 原始特征重要性
model = DecisionTreeClassifier(criterion="gini", max_depth=5)
model.fit(X=X_train, y=y_train)
print(model.feature_importances_)
# [0.0167, 0.0300, 0.4199, 0.5334]
# → 后两个特征（花瓣长宽）远比前两个（花萼长宽）重要
# 加入噪声列
a = np.random.randint(-3, 3, size=120).reshape(-1, 1) # 假1
b = np.random.randint(-3, 3, size=120).reshape(-1, 1) # 假2
c = np.random.randint(-3, 3, size=120).reshape(-1, 1) # 假3
X_train = np.concatenate([X_train[:, :2], a, X_train[:, 2:], b, c], axis=1)
model = DecisionTreeClassifier(criterion="gini", max_depth=5)
model.fit(X=X_train, y=y_train)
m = model.feature_importances_
# 排序查看
a = np.argsort(m)[::-1]
cols = ["真1", "真2", "假1", "真3", "真4", "假2", "假3"]
print(np.array(cols)[a][:2].tolist()) # ['真3', '真4']
# → 真实特征（花瓣长宽）仍是最重要的，噪声列被正确识别为不重要
```
|
|
### 累积列重要性：多轮训练筛选特征
通过多轮训练统计每个特征出现的贡献次数，筛选出真正重要的特征。
**核心思路**：
```
1. 初始化 list_a = [0, 0, ..., 0]（长度=特征数）
2. 每次训练后，对有贡献（importance > 0）的特征，list_a 对应位置 +1
3. 多轮训练后，list_a 中值越大的特征越重要
```
```python
import joblib
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
model = DecisionTreeClassifier(criterion="gini", max_depth=10)
col_feature_importance = []
def get_feature_col(model, X, y, col_feature_importance=col_feature_importance):
model.fit(X, y)
fti = model.feature_importances_
fti_len = len(fti)
if len(col_feature_importance) == 0:
for i in range(fti_len):
col_feature_importance.append(0)
# 原列重要性列表索引倒序排列
feature_index_desc = np.argsort(fti)[::-1]
# 将有贡献的列加1
for i in range(fti_len):
index_pos = feature_index_desc[i]
if fti[index_pos] == 0:
print(f"前{i+1}列有贡献")
break
else:
col_feature_importance[index_pos] += 1
return i
# 10轮训练
for i in range(10):
X, y = make_classification(n_samples=1000, n_features=1000, n_classes=2)
get_feature_col(model, X, y)
# 筛选：至少出现过 N 次的列
def get_used_cols(col_feature_importance, max_cols=200, arise_atleast=1):
col_feature_desc = np.argsort(col_feature_importance)[::-1]
col_feature_not0 = []
for i in range(len(col_feature_desc)):
index_value_desc = col_feature_desc[i]
importance_value = col_feature_importance[index_value_desc]
if importance_value < arise_atleast:
col_feature_not0 = col_feature_desc[:i]
break
use_cols = col_feature_not0[:max_cols]
return use_cols
# 至少出现过1次：263个列；至少出现过2次：34个列
# 可以分别测试使用34个列与263个列的效果（精度、性能）
```
|
|
### sklearn 自带可视化
使用 `sklearn.tree.plot_tree` 快速绘制决策树：
```python
import matplotlib.pyplot as plt
from sklearn import tree
from sklearn.datasets import load_breast_cancer
# 加载数据并训练
data = load_breast_cancer()
X = pd.DataFrame(data.data, columns=data.feature_names)
y = pd.Series(data.target)
clf = tree.DecisionTreeClassifier(max_depth=3, min_samples_leaf=50)
clf = clf.fit(X, y)
# 绘制决策树
plt.figure(figsize=(12, 8), dpi=150)
tree.plot_tree(clf, feature_names=data.feature_names,
class_names=['good', 'bad'], filled=True)
plt.savefig('tree.svg', format='svg', bbox_inches='tight')
plt.show()
```
**注意**：二叉树的前序遍历读取顺序为 `20, 27, 1, -2, -2, -2, 7, -2, -2`，其中 `-2` 表示叶子节点。
|
|
### dtreeviz 高级可视化
dtreeviz 提供更丰富的可视化效果，包含分布饼图。
```python
import dtreeviz
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_breast_cancer
data = load_breast_cancer()
X = pd.DataFrame(data.data, columns=data.feature_names)
y = pd.Series(data.target)
clf = DecisionTreeClassifier(max_depth=3, min_samples_leaf=30)
clf = clf.fit(X, y)
viz_model = dtreeviz.model(clf,
X_train=X, y_train=y,
target_name='label',
feature_names=X.columns,
class_names={0: 'good', 1: 'bad'})
v = viz_model.view(fancy=False)
v.show()
v.save("img.svg")
```
|
|
### 决策树内部属性详解
通过 `clf.tree_` 可以访问决策树的内部结构：
```python
# 查看所有属性和方法
[x for x in dir(clf.tree_) if not x.startswith('_')]
# ['apply', 'capacity', 'children_left', 'children_right',
# 'feature', 'impurity', 'max_depth', 'n_leaves', 'n_node_samples',
# 'node_count', 'predict', 'threshold', 'value', ...]
```
#### 核心属性说明
| 属性 | 含义 | 示例值 |
|------|------|--------|
| `children_left` | 每个节点的左子节点索引，-1 为叶子 | `[1, 2, 3, -1, -1, -1, 7, -1, -1]` |
| `children_right` | 每个节点的右子节点索引，-1 为叶子 | `[6, 5, 4, -1, -1, -1, 8, -1, -1]` |
| `feature` | 节点分裂使用的特征索引，-2 为叶子 | `[20, 27, 1, -2, -2, -2, 7, -2, -2]` |
| `threshold` | 分裂阈值（≤阈值进左，>阈值进右） | `[16.795, 0.133, 21.435, ...]` |
| `value` | 每个节点的类别分布概率 | `[[[0.37, 0.63]], ...]` |
| `impurity` | 每个节点的不纯度（基尼指数） | `[0.468, 0.159, 0.030, ...]` |
| `n_node_samples` | 每个节点的样本数 | `[569, 379, 329, 269, ...]` |
| `n_leaves` | 叶子节点数量 | `5` |
| `node_count` | 总节点数 | `9` |
| `capacity` | 预分配存储容量 | `9` |
#### 关键解读
```
根节点(0): feature=20, threshold=16.795
→ 特征20 ≤ 16.795 → 左子节点(1)
→ 特征20 > 16.795 → 右子节点(6)
9个节点中5个为叶子节点(-1)，符合 max_depth=3 的限制
所有叶子节点的样本数之和 = 训练数据总数 569
```
#### 分裂验证示例
```python
import numpy as np
data_arr = np.array(X)
label_arr = np.array(Y)
# 根节点按特征20、阈值16.795分裂
left_labels = label_arr[data_arr[:, 20] <= clf.tree_.threshold[0]]
right_labels = label_arr[data_arr[:, 20] > clf.tree_.threshold[0]]
len(left_labels) # 379（左子树样本数）
len(right_labels) # 190（右子树样本数）
# 379 + 190 = 569 ✓
```
|
|
### 策略生成
将决策树的规则提取为可读的策略表：
```python
import numpy as np
import pandas as pd
from sklearn.datasets import load_breast_cancer
data = load_breast_cancer()
X = pd.DataFrame(data.data, columns=data.feature_names)
y = pd.DataFrame(data.target, columns=['target'])
from tpf.link.tree import Decision
dcs = Decision()
df = dcs.rules(X=X, y=y, max_depth=5)
df
```
策略生成将决策树的每条从根到叶子的路径转换为一条规则，便于业务理解和部署。
#### 属性查看方法
```python
# 查看特征重要性
clf.feature_importances_
# array([0., 0.0018, 0., ..., 0.8616, 0., 0., 0.1199, 0., 0.])
# 分裂节点有4个，特征重要性 > 0 的特征刚好4个
# value 属性详解
clf.tree_.value # shape: (9, 1, 2)
# 9个节点，每个节点有2个值代表类别 [0, 1] 的概率
# 计算每个节点的类别样本数
a = clf.tree_.n_node_samples[:, np.newaxis, np.newaxis]
value = np.round(a * clf.tree_.value).astype(np.int64)
# [[[212, 357]], [[33, 346]], [[5, 324]], ...]
```
|
|
### 网格搜索（GridSearchCV）
使用交叉验证自动搜索最优参数组合：
```python
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV
# 定义参数搜索空间
param_grid = {
'criterion': ['gini', 'entropy'],
'max_depth': [3, 5, 7, 10, None],
'min_samples_split': [2, 5, 10, 20],
'min_samples_leaf': [1, 5, 10, 20],
}
# 网格搜索 + 5折交叉验证
grid_search = GridSearchCV(
DecisionTreeClassifier(random_state=42),
param_grid,
cv=5,
scoring='accuracy',
n_jobs=-1 # 并行计算
)
grid_search.fit(X_train, y_train)
# 最优参数和分数
print(f"最优参数: {grid_search.best_params_}")
print(f"最优分数: {grid_search.best_score_:.4f}")
# 使用最优模型
best_model = grid_search.best_estimator_
```
> **注意**：网格搜索会遍历所有参数组合，参数空间大时计算量很大。可以考虑使用 `RandomizedSearchCV` 进行随机搜索。
|
|
### max_depth 调参详解
#### 深度与节点数的关系
```
2⁰ + 2¹ + 2² + ... + 2ⁿ = 2^(n+1) - 1
2⁶ = 64, 2⁷ = 128
通常特征列到不了128，所以 max_depth 取 6 就算大的了
```
#### 调参策略
**策略一：不设限制 → 观察过拟合**
```python
# 先让树自由生长
model = DecisionTreeClassifier()
model.fit(X_train, y_train)
print(f"训练集准确率: {model.score(X_train, y_train):.4f}")
print(f"测试集准确率: {model.score(X_test, y_test):.4f}")
print(f"树的深度: {model.get_depth()}")
print(f"叶子节点数: {model.get_n_leaves()}")
# 如果训练集准确率远高于测试集 → 过拟合 → 需要限制深度
```
**策略二：交叉验证选最优深度**
```python
from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as plt
depths = range(1, 21)
train_scores = []
test_scores = []
for depth in depths:
model = DecisionTreeClassifier(max_depth=depth, random_state=42)
model.fit(X_train, y_train)
train_scores.append(model.score(X_train, y_train))
test_scores.append(model.score(X_test, y_test))
plt.plot(depths, train_scores, label='Train')
plt.plot(depths, test_scores, label='Test')
plt.xlabel('max_depth')
plt.ylabel('Accuracy')
plt.legend()
plt.show()
# 选择测试集准确率最高且与训练集差距不大的深度
```
**策略三：结合数据特性**
- 数据噪声多/异常值多 → 设置较小的 max_depth
- 数据很干净 → 可尝试较大的 max_depth
- 结合 `min_samples_leaf`、`min_samples_split` 共同调优
|
|
### 学习曲线分析
通过学习曲线判断模型是过拟合还是欠拟合：
```python
from sklearn.model_selection import learning_curve
import numpy as np
model = DecisionTreeClassifier(max_depth=5, random_state=42)
train_sizes, train_scores, test_scores = learning_curve(
model, X_train, y_train,
train_sizes=np.linspace(0.1, 1.0, 10),
cv=5, scoring='accuracy'
)
train_mean = train_scores.mean(axis=1)
test_mean = test_scores.mean(axis=1)
# 诊断
if train_mean[-1] - test_mean[-1] > 0.1:
print("过拟合：训练集和测试集差距较大")
print("建议：减小 max_depth，增大 min_samples_leaf")
elif train_mean[-1] < 0.8 and test_mean[-1] < 0.8:
print("欠拟合：训练集和测试集都表现不佳")
print("建议：增大 max_depth，减小 min_samples_leaf")
else:
print("模型拟合良好")
```
#### 常见过拟合/欠拟合处理
| 问题 | 表现 | 解决方案 |
|------|------|---------|
| **过拟合** | 训练精度高，测试精度低 | 减小 max_depth，增大 min_samples_leaf |
| **欠拟合** | 训练精度和测试精度都低 | 增大 max_depth，减小 min_samples_leaf |
|
|
### 决策树的优点
1. **可解释性强**：树结构直观可视，规则清晰，非技术人员也能理解
2. **无需特征缩放**：不需要标准化或归一化，对特征的量纲不敏感
3. **能处理混合类型数据**：同时处理数值型和类别型特征
4. **自动特征选择**：通过特征重要性自动筛选关键特征
5. **能处理缺失值**（部分实现）
6. **非线性建模能力**：能捕捉特征间的复杂非线性关系和交互效应
7. **训练和预测速度快**：训练复杂度 O(n·m·log(m))，预测复杂度 O(log(m))
8. **对异常值有一定鲁棒性**：使用中位数或投票机制
> 其中 n 为特征数，m 为样本数。
|
|
### 决策树的缺点
1. **容易过拟合**：如果不限制树的深度，会完美拟合训练数据但泛化能力差
2. **不稳定**：训练数据的微小变化可能导致生成完全不同的树
3. **贪心算法的局限**：局部最优不保证全局最优
4. **对类别不平衡敏感**：容易偏向多数类
5. **难以捕捉线性关系**：对于线性可分的数据，决策树不如线性模型高效
6. **外推能力差**：不能预测训练数据范围之外的值（回归树）
7. **某些特征可能被忽略**：信息增益或基尼指数低的特征可能永远不会被选中
#### 单棵决策树 vs 集成方法
| 对比项 | 单棵决策树 | 随机森林 / GBDT |
|--------|-----------|----------------|
| 准确率 | 一般 | 高 |
| 过拟合风险 | 高 | 低 |
| 可解释性 | 强 | 弱 |
| 稳定性 | 低 | 高 |
| 适用场景 | 需要解释性 | 追求准确率 |
> **实践建议**：如果追求准确率，优先使用集成方法（随机森林、XGBoost）；如果需要可解释性，使用单棵决策树并控制深度。
|
|
### 适用场景
#### 最适合的场景
1. **需要模型可解释性**：医疗诊断、金融审批等需要向非技术人员解释决策过程
2. **特征工程探索**：通过特征重要性快速了解哪些特征对预测有用
3. **快速原型**：作为基线模型快速评估数据集的可分性
4. **规则提取**：将业务规则从数据中提取出来
#### sklearn API 速查
```python
# 分类树
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(
criterion='gini', # 特征选择标准
splitter='best', # 划分策略
max_depth=None, # 最大深度
min_samples_split=2, # 内部节点最小分裂样本数
min_samples_leaf=1, # 叶子节点最小样本数
max_features=None, # 划分时考虑的最大特征数
random_state=None, # 随机种子
max_leaf_nodes=None, # 最大叶子节点数
min_impurity_decrease=0, # 最小不纯度下降值
class_weight=None # 类别权重
)
# 回归树
from sklearn.tree import DecisionTreeRegressor
reg = DecisionTreeRegressor(
criterion='squared_error', # 回归用平方误差
max_depth=5,
min_samples_leaf=10
)
```
#### 不适合的场景
- 数据量大且特征多、需要高精度 → 使用随机森林或 XGBoost
- 特征间存在强线性关系 → 使用线性模型（逻辑回归、线性回归）
- 数据量非常小（<50样本） → 树容易过拟合
|
|
### Bagging：随机森林（Random Forest）
随机森林是决策树的集成，通过构建**多棵决策树**来提高模型的准确性和稳定性。
#### 核心思想
```
1. 从训练集中有放回地随机抽取多个子集（Bootstrap Sampling）
2. 对每个子集训练一棵决策树
3. 每棵树在分裂时，随机选择部分特征（特征随机性）
4. 分类：多棵树投票 → 多数决定
回归：多棵树预测 → 取平均值
```
#### 为什么有效
- 每棵树都有一定的"偏见"，但通过**多棵树的平均**，偏见被消除
- 随机选择特征 → 减少强特征被每棵树都选中的概率 → 增加多样性
- 多棵树共同决策 → 大幅降低**过拟合**风险
#### sklearn 实现
```python
from sklearn.ensemble import RandomForestClassifier
model = RandomForestClassifier(
n_estimators=100, # 树的数量
max_depth=10, # 每棵树的最大深度
min_samples_leaf=5,
random_state=42,
n_jobs=-1 # 并行训练
)
model.fit(X_train, y_train)
print(f"准确率: {model.score(X_test, y_test):.4f}")
```
|
|
### Boosting：GBDT / XGBoost
Boosting 方法的核心思想是：**串行训练多棵树，每棵新树纠正前一棵树的错误**。
#### GBDT（Gradient Boosting Decision Tree）
```
1. 训练第1棵树，得到预测值
2. 计算残差 = 真实值 - 预测值
3. 用残差作为目标值训练第2棵树
4. 重复步骤2~3，直到满足条件
5. 最终预测 = 所有树的预测值之和
```
#### XGBoost / LightGBM
XGBoost 和 LightGBM 是 GBDT 的高效实现，是目前机器学习竞赛和工业界最常用的算法之一。
```python
# sklearn 的 GBDT
from sklearn.ensemble import GradientBoostingClassifier
model = GradientBoostingClassifier(
n_estimators=100, # 树的数量
max_depth=5, # 每棵树的深度（通常较浅）
learning_rate=0.1, # 学习率
random_state=42
)
model.fit(X_train, y_train)
```
#### Boosting vs Bagging
| 对比项 | Bagging（随机森林） | Boosting（GBDT） |
|--------|-------------------|-----------------|
| 训练方式 | 并行（独立训练每棵树） | 串行（依次训练每棵树） |
| 目标 | 降低方差 | 降低偏差 |
| 树的深度 | 较深（不剪枝） | 较浅（通常 depth=3~5） |
| 过拟合风险 | 低 | 相对较高（需要正则化） |
| 训练速度 | 快（可并行） | 慢（串行依赖） |
| 准确率 | 高 | 通常更高 |
|
|
### 常用集成方法对比
#### 三大集成方法总结
| 方法 | 代表算法 | 核心思想 | sklearn 类 |
|------|---------|---------|-----------|
| **Bagging** | 随机森林 | 多棵独立树投票 | `RandomForestClassifier` |
| **Boosting** | GBDT, XGBoost, LightGBM | 串行纠错 | `GradientBoostingClassifier` |
| **Stacking** | 多模型融合 | 多个基模型的输出作为新特征 | `StackingClassifier` |
#### 如何选择
```
单棵决策树：需要可解释性 → 直接用
随机森林：需要高准确率 + 相对简单 → 选它
GBDT/XGBoost/LightGBM：需要最高准确率 → 选它
```
#### 进阶学习路径
```
决策树（基础）
├── 随机森林（Bagging 集成）
├── GBDT（Boosting 集成）
├── XGBoost（高效 GBDT）
├── LightGBM（更快 GBDT）
└── CatBoost（处理类别特征）
```
> 决策树是所有这些高级算法的**基础**。理解好单棵决策树的原理，是学习集成学习的关键前提。
|
|
### 信息增益核心公式
信息增益是决策树算法（如 **ID3**、**C4.5**）中选择最优划分特征的核心指标。它衡量的是：使用某个特征对数据集进行划分后，**不确定性（熵）减少了多少**。信息增益越大，说明该特征对分类的贡献越大。
$$
\text{信息增益} = \text{Entropy(划分前)} - \text{Entropy(划分后)}
$$
#### 熵（Entropy）的定义
熵是信息论中衡量数据不确定性的指标。对于数据集 $S$，其熵定义为：
$$
E(S) = -\sum_{i=1}^{c} p_i \log_2(p_i)
$$
其中：
- $p_i$ 表示第 $i$ 类样本在数据集 $S$ 中所占的比例
- $c$ 为类别总数
**熵的特点：**
- 当数据集完全纯净（所有样本属于同一类）时，$E(S) = 0$
- 当各类样本均匀分布时，熵最大，不确定性最高
#### 信息增益率的引入
> 信息增益倾向于选择**取值种类多**的特征（如用户ID），因为取值种类越多，每个取值对应的子集越小，越容易将数据划分得更"纯净"。这里的"取值多"不是指某个值的比例大，而是指该特征有**很多不同的取值（类别）**。例如"用户ID"有 1000 个不同值，每个 ID 只对应 1 条样本，按 ID 划分后每个子集都是纯的，但这种划分毫无意义。
>
> 为解决这一问题，**C4.5 算法引入了"信息增益率"（Gain Ratio）**，通过对信息增益进行归一化来惩罚取值过多的特征。
#### 信息增益率的公式
$$
GainRatio(D, A) = \frac{Gain(D, A)}{SplitInfo(A)}
$$
其中分母 **SplitInfo(A)** 是特征 A 本身的熵（也叫分裂信息），用来衡量特征取值的均匀程度：
$$
SplitInfo(A) = -\sum_{i=1}^{n} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}
$$
- $n$ 是特征 A 的取值个数
- $|D_i|$ 是取第 $i$ 个值的样本数
- $|D|$ 是总样本数
**直觉理解**：
- 如果特征 A 有 1000 个不同取值且均匀分布 → $SplitInfo$ 很大 → $GainRatio$ 被大幅缩小 → 该特征被"惩罚"
- 如果特征 A 只有 2 个取值 → $SplitInfo$ 较小 → $GainRatio$ 被缩小的幅度有限
- 因此，信息增益率能自动抑制取值种类过多的特征
|
|
### 用户流失预测：按"性别"划分
假设有 15 个用户样本，其中 Positive（已流失）5 人，Negative（未流失）10 人。
**整体熵：**
$$
E(S) = -\frac{5}{15}\log_2\left(\frac{5}{15}\right) - \frac{10}{15}\log_2\left(\frac{10}{15}\right) = 0.9182
$$
#### 按"性别"划分
| 性别 | Positive | Negative | 汇总 |
|:---:|:---:|:---:|:---:|
| 男性 | 3 | 5 | 8 |
| 女性 | 2 | 5 | 7 |
$$
E(g_1) = -\frac{3}{8}\log_2\left(\frac{3}{8}\right) - \frac{5}{8}\log_2\left(\frac{5}{8}\right) = 0.9543
$$
$$
E(g_2) = -\frac{2}{7}\log_2\left(\frac{2}{7}\right) - \frac{5}{7}\log_2\left(\frac{5}{7}\right) = 0.8631
$$
$$
IGain(S, g) = E(S) - \frac{8}{15}E(g_1) - \frac{7}{15}E(g_2) = 0.0064
$$
**信息增益仅为 0.0064**，说明性别对用户流失的区分能力很弱。
|
|
### 用户流失预测：按"活跃度"划分
#### 按"活跃度"划分
| 活跃度 | Positive | Negative | 汇总 |
|:---:|:---:|:---:|:---:|
| 高 | 0 | 6 | 6 |
| 中 | 1 | 4 | 5 |
| 低 | 4 | 0 | 4 |
$$
E(a_1) = 0, \quad E(a_2) = 0.7219
$$
$$
IGain(S, a) = E(S) - \frac{6}{15}E(a_1) - \frac{5}{15}E(a_2) - \frac{4}{15}E(a_3) = 0.6776
$$
#### 结论
活跃度的信息增益（**0.6776**）远大于性别的信息增益（**0.0064**），说明**活跃度对用户流失的影响比性别大得多**。在做特征选择或数据分析时，应重点考察活跃度这个指标。
#### 纯度（Purity）的概念
| 状态 | 描述 | 纯度 |
|:---:|:---|:---:|
| 不纯 | 节点中包含多种类别，混乱程度高 | 低 |
| 有点不纯 | 节点中某类占主导，但仍含少量其他类 | 中 |
| 够纯 | 节点中基本属于同一类别 | 高 |
- **熵越低，纯度越高**
- **基尼值越低，纯度越高**
|
|
### 贷款违约预测数据集
基尼不纯度是 **CART 决策树**（Classification and Regression Trees）算法中使用的划分标准。它表示：从数据集中随机抽取两个样本，其类别标记不一致的概率。
**基尼公式：**
$$
Gini(D) = 1 - \sum_{k=1}^{n} p_{i,k}^2
$$
**基尼增益：**
$$
\Delta Gini = Gini(父节点) - \sum_{j} \frac{|D_j|}{|D|} Gini(D_j)
$$
决策树选择**基尼增益最大**的特征进行划分。
#### 数据集（共 10 条记录）
| 序号 | 是否有房 | 婚姻状况 | 年收入 | 是否拖欠贷款 |
|:---:|:---:|:---:|:---:|:---:|
| 1 | yes | single | 125K | no |
| 2 | no | married | 100K | no |
| 3 | no | single | 70K | no |
| 4 | yes | married | 120K | no |
| 5 | no | divorced | 95K | yes |
| 6 | no | married | 60K | no |
| 7 | yes | divorced | 220K | no |
| 8 | no | single | 85K | yes |
| 9 | no | married | 75K | no |
| 10 | no | single | 90K | yes |
#### 根节点的基尼系数
其中拖欠贷款（yes）3 条，不拖欠（no）7 条：
$$
Gini(\text{是否拖欠贷款}) = 1 - \left(\frac{3}{10}\right)^2 - \left(\frac{7}{10}\right)^2 = 0.42
$$
|
|
### 按"是否有房"划分
| 是否拖欠贷款 | 有房产 | 无房产 |
|:---:|:---:|:---:|
| Yes | 0 | 3 |
| No | 3 | 4 |
- 左子节点（有房产）：3 条记录，全部不拖欠
$$Gini(左) = 1 - \left(\frac{0}{3}\right)^2 - \left(\frac{3}{3}\right)^2 = 0$$
- 右子节点（无房产）：7 条记录，3 条拖欠，4 条不拖欠
$$Gini(右) = 1 - \left(\frac{3}{7}\right)^2 - \left(\frac{4}{7}\right)^2 = 0.4898$$
**基尼增益：**
$$
\Delta Gini(\text{是否有房}) = 0.42 - \frac{7}{10} \times 0.4898 - \frac{3}{10} \times 0 = 0.077
$$
> 有房产的节点 Gini = 0，表示完全纯净（全部不拖欠），这是理想情况。
|
|
### 按"婚姻状况"划分
婚姻状况有三种取值：single、married、divorced。CART 只支持二分划分，需要尝试不同的分组方式，选择基尼增益最大的分组。
#### 分组方式一：{single} | {married, divorced}
- single 组（4 条）：2 yes, 2 no
$$Gini(single) = 1 - 0.5^2 - 0.5^2 = 0.5$$
- married+divorced 组（6 条）：1 yes, 5 no
$$Gini(married+divorced) = 1 - (1/6)^2 - (5/6)^2 = 0.2778$$
$$
\Delta Gini = 0.42 - \frac{4}{10} \times 0.5 - \frac{6}{10} \times 0.2778 = 0.053
$$
#### 分组方式二：{divorced} | {single, married}
- divorced 组（2 条）：1 yes, 1 no → Gini = 0.5
- single+married 组（8 条）：2 yes, 6 no → Gini = 0.375
$$
\Delta Gini = 0.42 - \frac{2}{10} \times 0.5 - \frac{8}{10} \times 0.375 = 0.02
$$
#### 分组方式三：{married} | {single, divorced}（最优）
对比以上分组结果，婚姻状况的最优分组为 **{married} | {single, divorced}**，此时基尼增益最大。
#### 三种特征对比
| 特征 | 基尼增益 |
|:---:|:---:|
| 是否有房 | 0.077 |
| 婚姻状况（最优分组） | > 0.053 |
| 年收入（最优划分点） | 0.12 |
|
|
### 连续特征的相邻中值法
对于连续型特征（如"年收入"），决策树不能直接按离散值划分，需要将其转化为二分问题。常用的方法是：
1. 将连续特征的所有取值按**从小到大排序**
2. 取**相邻两个值的中点**作为候选划分点
3. 计算每个候选划分点的基尼增益（或信息增益）
4. 选择增益最大的中点作为**最优划分点**
> **补充说明：** 对于连续特征，C4.5 和 CART 的处理方式类似，都是在排序后的取值中寻找最佳分割点。不同的是，C4.5 使用信息增益率，而 CART 使用基尼系数。时间复杂度为 $O(n \log n)$（排序）加上 $O(n)$ 的扫描。
|
|
### 年收入排序及候选划分点
将年收入按从小到大排序，并计算相邻中值：
| 是否拖欠 | no | no | no | yes | yes | yes | no | no | no | no |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 年收入 | 60 | 70 | 75 | 85 | 90 | 95 | 100 | 120 | 125 | 220 |
| 相邻中点 | 65 | 72.5 | 80 | 87.5 | 92.5 | 97.5 | 110 | 122.5 | 172.5 | - |
| Gini增益 | 0.02 | 0.045 | 0.077 | 0.003 | 0.02 | **0.12** | 0.077 | 0.045 | 0.02 | - |
由表可知，当划分点为 **97.5** 时，基尼增益最大（**0.12**），因此选择年收入 ≤ 97.5 和 > 97.5 作为划分。
#### 最终各特征基尼增益对比
| 特征 | 最优划分点/分组 | 基尼增益 |
|:---:|:---:|:---:|
| 是否有房 | yes / no | 0.077 |
| 婚姻状况 | {married} / {single, divorced} | > 0.053 |
| **年收入** | **≤ 97.5 / > 97.5** | **0.12** |
> 年收入的基尼增益最大，因此在根节点应优先选择年收入作为划分特征。但根据实际课件图示，最终的决策树根节点选择了婚姻状况，这可能是因为综合比较后的结果。无论如何，决策树的构建原则是一致的：**每次选择使不纯度下降最多的特征进行划分**。
|
|
### 第一步：选择根节点
比较各特征的基尼增益：
- 是否有房：0.077
- 婚姻状况（最优分组）：大于 0.053
- 年收入（最优划分点 97.5）：0.12
根据课件第7页的决策树图示，根节点选择了**婚姻状况**，划分为 married 和 single/divorced。
> **说明：** 决策树的构建原则是一致的：**每次选择使不纯度下降最多的特征进行划分**。实际构建中可能综合比较后选择了婚姻状况。
|
|
### 决策树结构示例（贷款违约预测）
根据课件图示，最终生成的决策树结构如下：
```
[婚姻状况]
/ \
married single, divorced
| |
no(4) [是否有房]
/ \
yes no
| |
no(2) [年收入]
/ \
≤ 77.5 > 77.5
| |
no(1) yes(3)
```
**解读：**
- 如果已婚（married）→ 不拖欠（no），共 4 个样本
- 如果未婚/离异（single/divorced）且有房 → 不拖欠（no），共 2 个样本
- 如果未婚/离异且无房，年收入 ≤ 77.5 → 不拖欠（no），1 个样本
- 如果未婚/离异且无房，年收入 > 77.5 → 拖欠（yes），3 个样本
|
|
### 递归构建过程
对于每个子节点，重复以下过程：
1. **计算**当前节点数据集的基尼系数（或熵）
2. **计算**对剩余特征计算基尼增益（或信息增益）
3. **选择**增益最大的特征进行划分
4. **递归**直到满足停止条件
#### 停止条件
| 停止条件 | 说明 |
|:---|:---|
| 节点纯度足够高 | 基尼系数或熵低于阈值 |
| 样本数过少 | 节点中样本数少于 `min_samples_split` |
| 所有特征已用完 | 没有更多特征可供划分 |
| 增益不足 | 信息增益或基尼增益低于 `min_impurity_decrease` |
| 达到最大深度 | 树的深度达到 `max_depth` |
#### ID3、C4.5、CART 算法对比
| 特性 | ID3 | C4.5 | CART |
|:---|:---|:---|:---|
| **提出时间** | 1986 | 1993 | 1984 |
| **划分标准** | 信息增益 | 信息增益率 | 基尼系数 |
| **特征类型** | 离散值 | 离散值 + 连续值 | 离散值 + 连续值 |
| **缺失值处理** | 不支持 | 支持 | 支持 |
| **树类型** | 多叉树 | 多叉树 | **二叉树** |
| **任务类型** | 分类 | 分类 | 分类 + 回归 |
| **剪枝策略** | 无 | 后剪枝 | 后剪枝 |
|
|
### 为什么要剪枝
决策树如果生长得太深，会过度分析训练数据中的噪声，导致 **过拟合（Overfitting）**。过拟合的模型在训练集上表现很好，但在测试集上表现很差。
**核心问题：**
- 100 = 99 + 1 时，这个"1"可能是噪声
- 没有必要为了分出这个"1"再增加一个分支
- 树的结点总数越多，训练精度越高，但测试精度可能下降
**决策树的最终效果是：数据特征与算法的综合结果**。树最后的分支，熵/基尼系数低到一定阈值即可，不必为 0——这正是剪枝的思想。
|
|
### 预剪枝（Pre-Pruning）
在树构建过程中提前停止生长：
| 参数/策略 | 说明 |
|:---|:---|
| **最大深度（max_depth）** | 限制树的最大深度，防止过深 |
| **最小样本分裂数（min_samples_split）** | 节点样本数少于该值时不再分裂 |
| **最小叶子样本数（min_samples_leaf）** | 叶子节点的最少样本数 |
| **信息增益阈值（min_impurity_decrease）** | 增益低于阈值时不分裂 |
#### sklearn 决策树核心参数
基于 `sklearn.tree.DecisionTreeClassifier`：
| 参数 | 默认值 | 说明 |
|:---|:---|:---|
| `criterion` | `'gini'` | 划分标准：`'gini'` 基尼系数；`'entropy'` 信息熵 |
| `splitter` | `'best'` | 分裂策略：`'best'` 最优分裂；`'random'` 随机分裂 |
| `max_depth` | `None` | 树最大深度，`None` 表示不限制 |
| `min_samples_split` | `2` | 节点最少样本数，少于该数不再分裂 |
| `min_samples_leaf` | `1` | 叶子节点最少样本数 |
> 预剪枝实现简单、效率高，但可能因过早停止而错过后续的重要划分（"近视"问题）。
|
|
### 后剪枝（Post-Pruning）与 CCP
先构建完整的树，再**自底向上**剪去对泛化能力无贡献的分支。
> **重要澄清：后剪枝 ≠ 特征选择**
>
> 后剪枝**不是**根据"特征重要性"选择前 N 个特征。特征选择是在建模前从所有特征中挑选最相关的子集；而后剪枝是在树**已经生成之后**，直接剪掉某些分支（子树），将其替换为一个叶子节点。
#### 代价复杂度剪枝（CCP）详解
**CCP 是 sklearn 中 `DecisionTreeClassifier` 使用的后剪枝方法**，其核心是为每棵子树定义一个"代价复杂度"：
$$
R_\alpha(T) = R(T) + \alpha \cdot |T_{leaf}|
$$
其中：
- $R(T)$：树 $T$ 在训练数据上的预测误差（如误分类率或 MSE）
- $|T_{leaf}|$：树 $T$ 的**叶子节点数量**，代表模型复杂度
- $\alpha$：复杂度参数（非负），$\alpha$ 越大，惩罚越重，剪枝越激进
**剪枝过程：**
1. **生成完全树 $T_0$**：不做任何限制，让树生长到最深层
2. **计算每个内部节点的"剪枝强度"** $g(t)$：
$$
g(t) = \frac{R(t) - R(T_t)}{|T_{t,leaf}| - 1}
$$
3. **迭代剪枝**：找到 $g(t)$ 最小的节点，将其子树剪除，得到更小的树 $T_1$，重复直到只剩根节点
4. **交叉验证选择最优树**：用交叉验证在验证集上评估，选择误差最小的 $T_k$
```python
from sklearn.tree import DecisionTreeClassifier
# ccp_alpha 就是公式中的 α
clf = DecisionTreeClassifier(ccp_alpha=0.01, random_state=42)
# 获取不同 ccp_alpha 值对应的剪枝路径
path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities
```
|
|
### 预剪枝 vs 后剪枝
| 维度 | 预剪枝 | 后剪枝 |
|:---|:---|:---|
| **时机** | 构建过程中停止 | 构建完成后修剪 |
| **数据使用** | 训练集本身 | 通常需要额外验证集 |
| **效果** | 容易"近视"，可能错过后续重要划分 | 通常泛化能力更好 |
| **计算成本** | 低（提前停止） | 高（先生成完全树） |
| **代表** | `max_depth`、`min_samples_split` | CCP（sklearn `ccp_alpha`） |
| **风险** | 欠拟合（Underfitting） | 计算开销大 |
#### 常见的后剪枝算法
| 算法 | 代表实现 | 核心思想 |
|:---|:---|:---|
| **错误率降低剪枝（REP）** | C4.5 | 用验证集直接比较剪枝前后的分类错误率 |
| **悲观错误剪枝（PEP）** | C4.5 早期版本 | 用训练集误差加上统计修正项来估计泛化误差 |
| **代价复杂度剪枝（CCP）** | CART、sklearn | 引入复杂度惩罚项，通过参数 α 平衡拟合与复杂度 |
| **最小错误剪枝（MEP）** | — | 基于概率估计的贝叶斯方法 |
> **实践建议：** 在 sklearn 中，通常先使用预剪枝参数（如 `max_depth`、`min_samples_leaf`）做粗调限制过拟合；如果需要更精细地控制模型复杂度，再结合 `ccp_alpha` 进行后剪枝。也可以**同时使用**预剪枝和后剪枝。**交叉验证**是确定最优剪枝参数的标准方法。
|