🌿 02-机器学习 · 推导笔记 7:决策树与随机森林(手写全流程)¶
决策树三兄弟 ID3/C4.5/CART 是分类器基础,随机森林 = 决策树 + Bagging + 特征随机。 本 notebook 要求:熵、信息增益、建树、森林全部手写,不调 sklearn.tree。
运行环境:Python 3.8+,仅依赖 numpy。
📊 图 9:李航例 5.1 打球决策树——每个非叶节点选「信息增益最大」的特征(天气→湿度/风速),叶子为多数表决结果。
核心概念¶
(a) 🗂️ 决策树三兄弟与随机森林:熵、信息增益、Bagging 与特征随机¶
决策树三兄弟 ID3/C4.5/CART 是分类器基础,随机森林 = 决策树 + Bagging + 特征随机。本篇熵、信息增益、建树、森林全部手写。
flowchart TB
N1["🌿 信息论基础:熵/条件熵"] --> N2["ID3:信息增益"]
N1 --> N3["C4.5:信息增益率"]
N1 --> N4["CART:基尼指数"]
N4 --> N5["剪枝:预剪枝 vs 后剪枝"]
N2 --> N6["随机森林:Bagging + 特征随机"]
N3 --> N6
N4 --> N6
N6 --> N7["特征重要性:随机森林版"]
N7 --> N8["三分钟对比:树 vs 森林 vs GBDT"]
N8 --> N9["自测清单"]
- N1 · 信息论基础:决策树就是一连串"如果……那么……"的提问,每次要选"信息量最大"的问题来问。信息量的标准是熵:数据越混乱熵越大,熵下降得越多说明该特征越有用。
- N2 · ID3(信息增益):每次选信息增益(分裂前熵 − 分裂后加权熵)最大的特征。缺点是偏好取值多的特征。
- N3 · C4.5(信息增益率):用信息增益除以固有值,修正 ID3 的偏好;还支持连续特征离散化与缺失值处理——实现更复杂。
- N4 · CART(基尼指数):用基尼指数代替熵:基尼越小纯度越高,每次找"某个特征的某个阈值"把样本分成两枝(二叉树),也是 GBDT 用的那款树。
- N5 · 剪枝:树容易过拟合,要剪枝:预剪枝在建树时提前停(深度/样本数限制),后剪枝先建完整树再自底向上合并叶节点——后剪枝一般效果更好。
- N6 · 随机森林:= Bagging + 特征随机:每棵树用有放回抽样(bootstrap)的样本 + 随机挑一部分特征来分裂,最后投票。样本随机降方差、特征随机让树之间不相关。
- N7 · 特征重要性:按"该特征分裂带来的杂质减少量"累积求和,再除以树的个数归一化,排个名就是重要性排序。
- N8 · 三分钟对比:单棵决策树方差大;随机森林(Bagging)并行降方差、抗过拟合;GBDT(Boosting)串行降偏差、精度高但怕噪点。
- N9 · 自测清单:能手算一个小数据集的熵和信息增益、能说清三个树算法差异、能讲随机森林为什么抗过拟合。
📖 本章导读¶
这一章讲什么(全书第 6 章):决策树 = 一连串「如果……那么……」的提问,每次选信息量最大的问题(熵 → 信息增益);讲清 ID3/C4.5/CART 三兄弟与剪枝;再用 Bagging + 特征子采样升级成随机森林。
学完本章,你应该能:
- 手算熵 $H=-\sum p_k\log p_k$ 与信息增益 $H(D)-H(D|A)$;
- 说清三兄弟的划分准则与各自毛病(ID3 偏爱多取值特征 → 增益率 / Gini);
- 讲清预剪枝 vs 后剪枝(CCP)的时机与权衡;
- 解释随机森林为什么降方差(Bagging 平均)以及特征重要性怎么来。
📌 全书第 6 章。阅读路径:本章导读 → 熵 · 建树 · 剪枝 · 森林 → 自测清单 → 本章小结。
💡 一句话类比——「二十问猜物」:猜谜游戏里你只问「是/否」问题,每次都问最能缩小范围的那个(先问「是动物吗」而不是「是北极熊吗」)——这就是决策树:每个节点选一个信息增益最大的特征分裂,一路把不确定性(熵)降到底。随机森林 = 请 100 个不同专长的人(每棵树用不同随机特征子集)各自猜,最后投票定答案。
§1 信息论基础(手写前先吃透)¶
熵(不确定性度量,对数底任意,常用 2 或 e):
$$H(Y) = -\sum_{k=1}^{K} p_k \log p_k$$
条件熵(已知 X 后 Y 的剩余不确定性):
$$H(Y \mid X) = \sum_v P(X=v)\, H(Y \mid X=v)$$
信息增益(熵减少量 = 互信息):
$$\text{Gain}(X) = H(Y) - H(Y \mid X)$$
增益率(C4.5,惩罚取值多的特征):
$$\text{GainRatio}(X) = \frac{\text{Gain}(X)}{H(X)}, \quad H(X) = -\sum_v p_v \log p_v$$
Gini 指数(CART):
$$\text{Gini}(D) = 1 - \sum_k p_k^2, \quad \text{Gini 分裂准则} = \min \sum_v \frac{|D_v|}{|D|} \text{Gini}(D_v)$$
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
import numpy as np
from collections import Counter
def entropy(y):
# 手写熵:H = -sum p log p
if len(y) == 0:
return 0.0
p = np.array(list(Counter(y).values())) / len(y)
return float(-(p * np.log2(p)).sum())
def conditional_entropy(X_f, y):
# H(Y|X_f):按特征取值分组求和
total = 0.0
n = len(y)
for v in np.unique(X_f):
mask = X_f == v
total += (mask.sum() / n) * entropy(y[mask])
return total
def info_gain(X_f, y):
return entropy(y) - conditional_entropy(X_f, y)
# 经典例子:天气-是否打球
outlook = np.array(['sunny', 'sunny', 'rain', 'rain', 'rain', 'sunny', 'overcast'])
play = np.array([0, 0, 1, 1, 1, 1, 1])
print('H(Y) =', round(entropy(play), 4)) # 不确定度
print('H(Y|outlook) =', round(conditional_entropy(outlook, play), 4))
print('信息增益 Gain(outlook) =', round(info_gain(outlook, play), 4))
print('熵边界检查: entropy([0,0,0]) =', entropy([0, 0, 0]), '(纯=0)')
print(' entropy([0,1,0,1]) =', round(entropy([0, 1, 0, 1]), 4), '(均匀=1)')
§2 三种决策树对比(面试背诵)¶
| ID3 | C4.5 | CART | |
|---|---|---|---|
| 分裂准则 | 信息增益 | 增益率 | Gini 指数 |
| 特征取值 | 离散 | 离散/连续(阈值) | 离散/连续(二分) |
| 树结构 | 多叉 | 多叉 | 二叉树 |
| 回归支持 | ✗ | ✗ | ✓(MSE) |
| 缺点 | 偏向取值多的特征 | 偏向取值少的 | 树不稳定(小扰动大变化) |
剪枝:
- 预剪枝:建树时提前停(深度、样本数、增益阈值)——快但可能欠拟合
- 后剪枝:建完整树再自底向上减枝(验证集评估)——更准但慢
class DecisionTreeClassifier:
"""手写 ID3 分类树:信息增益分裂、多数表决叶子"""
def __init__(self, max_depth=5, min_samples_split=2):
self.max_depth = max_depth
self.min_samples_split = min_samples_split
self.tree = None
def _best_feature(self, X, y):
best_f, best_gain = -1, -1.0
for f in range(X.shape[1]):
g = info_gain(X[:, f], y)
if g > best_gain:
best_gain, best_f = g, f
return best_f, best_gain
def _build(self, X, y, depth):
label, cnt = Counter(y).most_common(1)[0]
node = {'label': label, 'count': cnt}
# 纯节点 / 达到深度 / 样本太少 → 叶子
if len(set(y)) == 1 or depth >= self.max_depth or len(y) < self.min_samples_split:
return node
f, gain = self._best_feature(X, y)
if gain <= 0: # 无信息增益 → 叶子
return node
node['feature'] = f
node['gain'] = round(float(gain), 4)
node['children'] = {}
for v in np.unique(X[:, f]):
mask = X[:, f] == v
node['children'][str(v)] = self._build(X[mask], y[mask], depth + 1)
return node
def fit(self, X, y):
self.tree = self._build(np.asarray(X), np.asarray(y), 0)
return self
def _pred(self, node, x):
if 'feature' not in node:
return node['label']
v = str(x[node['feature']])
if v in node['children']:
return self._pred(node['children'][v], x)
return node['label'] # 未见过的取值 → 回退当前多数
def predict(self, X):
return np.array([self._pred(self.tree, x) for x in np.asarray(X)])
def show(self, node=None, indent=0):
node = node or self.tree
pad = ' ' * indent
if 'feature' in node:
print(f'{pad}[F{node["feature"]} 增益={node["gain"]}]')
for v, child in node['children'].items():
print(f'{pad} ={v}:')
self.show(child, indent + 2)
else:
print(f'{pad}叶子→{node["label"]} (样本{node["count"]})')
# 手写数据:2 特征 3 类(类似简化鸢尾)
rng = np.random.default_rng(0)
X = np.vstack([rng.normal([2, 2], 0.8, (50, 2)),
rng.normal([6, 2], 0.8, (50, 2)),
rng.normal([4, 6], 0.8, (50, 2))])
y = np.repeat([0, 1, 2], 50)
dt = DecisionTreeClassifier(max_depth=3).fit(X, y)
pred = dt.predict(X)
print('手写决策树训练准确率 =', round(np.mean(pred == y), 4))
print('\n树结构(中间输出):')
dt.show()
§2.5 手写 CART 分类树(Gini,补充)¶
- CART(Classification and Regression Tree)用 Gini 不纯度 做分裂准则: $$Gini(D)=1-\sum_k p_k^2$$ 纯节点 Gini=0,均匀分布时最大;
- 与 §2 的 ID3 不同:CART 是二叉树,连续特征用阈值二分(扫描相邻取值中点, 取加权平均 Gini 最小的 (特征, 阈值)),不再按取值做多路切开;
- 下面手写
CARTClassifier,并在 iris 上与sklearn.tree.DecisionTreeClassifier(criterion='gini')对照。
class CARTClassifier:
"""手写 CART 分类树:Gini 不纯度 + 二分阈值分裂(补充 §2.5)
Gini(D) = 1 - Σ_k p_k² // 纯节点 Gini=0,均匀分布最大
"""
def __init__(self, max_depth=5, min_samples_leaf=2, max_features=None, rng=None):
self.max_depth = max_depth
self.min_samples_leaf = min_samples_leaf
self.max_features = max_features # None=全部特征;int=每次分裂随机抽的特征数
self.rng = rng # 随机抽特征子集的随机源
self.tree = None
def _gini(self, y):
# Gini(D) = 1 - Σ p_k²
if len(y) == 0:
return 0.0
p = np.array(list(Counter(y).values())) / len(y)
return float(1 - (p ** 2).sum())
def _best_split(self, X, y):
# 遍历(随机抽出的)特征 + 相邻取值中点作候选阈值,最小化加权平均 Gini
n, d = X.shape
feat_idx = np.arange(d) if self.max_features is None \
else self.rng.permutation(d)[:self.max_features]
best = None
for f in feat_idx:
vals = np.unique(X[:, f])
for th in (vals[:-1] + vals[1:]) / 2: # 候选阈值 = 相邻取值中点
mask = X[:, f] <= th
if mask.sum() < self.min_samples_leaf or (~mask).sum() < self.min_samples_leaf:
continue # 预剪枝:任一分支样本过少
g = (mask.sum() * self._gini(y[mask]) + (~mask).sum() * self._gini(y[~mask])) / n
if best is None or g < best[0]:
best = (g, int(f), float(th))
return best
def _build(self, X, y, depth):
label, cnt = Counter(y).most_common(1)[0]
node = {'label': label, 'count': cnt}
if len(set(y)) == 1 or depth >= self.max_depth or len(y) < 2 * self.min_samples_leaf:
return node # 纯/达到深度/样本太少 → 叶子
split = self._best_split(X, y)
if split is None or split[0] >= self._gini(y): # 无法降低 Gini → 叶子
return node
g, f, th = split
node.update(feature=f, threshold=th, gini=round(g, 4))
mask = X[:, f] <= th
node['left'] = self._build(X[mask], y[mask], depth + 1)
node['right'] = self._build(X[~mask], y[~mask], depth + 1)
return node
def fit(self, X, y):
self.tree = self._build(np.asarray(X), np.asarray(y), 0)
return self
def _pred(self, node, x):
if 'feature' not in node:
return node['label']
if x[node['feature']] <= node['threshold']:
return self._pred(node['left'], x)
return self._pred(node['right'], x)
def predict(self, X):
return np.array([self._pred(self.tree, x) for x in np.asarray(X)])
# —— 对照实验:iris 上 手写 CART vs sklearn CART(criterion='gini') ——
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn import tree as sk_tree
Xir, yir = load_iris(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(Xir, yir, test_size=0.34, random_state=42)
mine = CARTClassifier(max_depth=4, min_samples_leaf=2).fit(Xtr, ytr)
sk = sk_tree.DecisionTreeClassifier(criterion='gini', max_depth=4,
min_samples_leaf=2, random_state=42).fit(Xtr, ytr)
acc_mine = np.mean(mine.predict(Xte) == yte)
acc_sk = np.mean(sk.predict(Xte) == yte)
print('手写 CART 训练/测试准确率 =', round(np.mean(mine.predict(Xtr) == ytr), 4), '/', round(acc_mine, 4))
print('sklearn CART 训练/测试准确率 =', round(np.mean(sk.predict(Xtr) == ytr), 4), '/', round(acc_sk, 4))
print('→ Gini CART 手写实现与 sklearn 结果可比,差异主要来自候选阈值取法与平局处理')
§2.6 剪枝:预剪枝 vs 后剪枝(补充)¶
预剪枝(Pre-pruning,边生长边停):
max_depth:达到最大深度立即停止分裂,最简单、最常用的树大小控制手段;min_samples_leaf:叶子最少样本数,候选分裂若使任一分支样本过少就放弃该分裂,抑制噪声过拟合;min_impurity_decrease:要求分裂带来的(加权)不纯度下降 ≥ 阈值,增益太小则拒绝(sklearn 中即min_impurity_decrease)。- 优点:训练快、树小、时间空间开销低;缺点:贪心"短视"——当前看似无用的分裂,后面可能是关键路径,容易欠拟合。
后剪枝(Post-pruning,先长满再自底向上修剪):
- 代价复杂度剪枝 CCP(Cost-Complexity Pruning):对树 T 定义损失 $R_\alpha(T)=R(T)+\alpha\cdot|T|$, 即经验损失 $R(T)$ 加上叶节点数 $|T|$ 的复杂度惩罚,$\alpha$ 是平衡拟合与复杂度的系数;
- sklearn 用
ccp_alpha暴露该参数:$\alpha$ 越大,惩罚越重,被剪掉的子树越多 → 树越小(泛化通常先升后降); - 优点:基于完整树后再决策,通常比同规模预剪枝树更准;缺点:需要先生长完整树,训练开销更大。
§3 随机森林:Bagging + 特征随机¶
Bagging(自举聚合):每棵树用有放回抽样的样本子集训练,最终投票/平均——降方差:
$$\bar{f} = \frac{1}{T}\sum_{t=1}^{T} f_t(x) \quad \Rightarrow \quad \text{Var}(\bar{f}) = \frac{1}{T}\text{Var}(f_t) \ (\text{若各树独立})$$
特征随机:每次分裂只在随机抽的 $m \le d$ 个特征里选最优——进一步去相关(各树差异更大,集成效果更好)。
OOB 估计:约 $1 - 1/e \approx 63.2\%$ 样本被抽中,剩下的是 OOB——树对自己没见过的样本评估 = 免费验证集。
class RandomForest:
"""随机森林 = Bagging + 特征随机(CART 作基学习器)
修复:max_features 之前只算不用。现在每棵树在【每次分裂】都用
self.rng.permutation(n_features)[:m] 重新随机抽特征子集,只在子集内
搜索最优 (特征, 阈值)。
"""
def __init__(self, n_trees=50, max_depth=5, max_features=None, seed=0):
self.T = n_trees
self.max_depth = max_depth
self.max_features = max_features # None/'sqrt' → sqrt(d);int → 每分裂抽的特征数
self.seed = seed
self.trees = []
def fit(self, X, y):
rng = np.random.default_rng(self.seed)
n, d = X.shape
m = int(np.sqrt(d)) if self.max_features in (None, 'sqrt') else int(self.max_features)
self.m = m # 保存供 oob_accuracy 复用
self.trees = []
for t in range(self.T):
idx = rng.integers(0, n, n) # 有放回抽样(bootstrap)
Xb, yb = X[idx], y[idx]
tree = CARTClassifier(max_depth=self.max_depth, max_features=m,
rng=np.random.default_rng(self.seed * 100 + t + 1))
self.trees.append(tree.fit(Xb, yb))
return self
def predict(self, X):
votes = np.array([t.predict(X) for t in self.trees]) # [T, n] 多数投票
return np.array([Counter(votes[:, j]).most_common(1)[0][0] for j in range(votes.shape[1])])
def oob_accuracy(self, X, y, seed=0):
# OOB 评估:只用没被该树抽中的样本投票预测
rng = np.random.default_rng(seed)
n = len(y)
preds = {i: [] for i in range(n)}
for t in range(self.T):
idx = rng.integers(0, n, n)
seen = set(idx)
tree = CARTClassifier(max_depth=self.max_depth, max_features=self.m,
rng=np.random.default_rng(seed * 100 + t + 1)).fit(X[idx], y[idx])
for i in range(n):
if i not in seen:
preds[i].append(tree.predict([X[i]])[0])
correct = sum(Counter(v).most_common(1)[0][0] == int(y[i]) for i, v in preds.items() if v)
covered = sum(1 for v in preds.values() if v)
return correct / max(covered, 1)
# —— 原有演示:3 团合成数据 训练/OOB ——
rng = np.random.default_rng(0)
Xf = np.vstack([rng.normal([2, 2], 1.0, (40, 2)),
rng.normal([6, 2], 1.0, (40, 2)),
rng.normal([4, 6], 1.0, (40, 2))])
yf = np.repeat([0, 1, 2], 40)
rf = RandomForest(n_trees=30, max_depth=4, seed=1).fit(Xf, yf)
print('随机森林训练准确率 =', round(np.mean(rf.predict(Xf) == yf), 4))
print('OOB 准确率(免费验证) =', round(rf.oob_accuracy(Xf, yf, seed=1), 4))
# 单棵树(全部特征)vs 森林(sqrt 特征):多次重采样看准确率波动
single_accs, forest_accs = [], []
for s in range(5):
rs = np.random.default_rng(s)
idx = rs.integers(0, len(Xf), len(Xf))
Xt, yt = Xf[idx], yf[idx]
t = CARTClassifier(max_depth=4).fit(Xt, yt)
single_accs.append(np.mean(t.predict(Xt) == yt))
f = RandomForest(n_trees=20, max_depth=4, seed=s).fit(Xt, yt)
forest_accs.append(np.mean(f.predict(Xt) == yt))
print('\n单树准确率 5 次: ', [round(a, 3) for a in single_accs])
print('森林准确率 5 次: ', [round(a, 3) for a in forest_accs])
print('单树波动(方差) =', round(np.var(single_accs), 5), ' 森林波动 =', round(np.var(forest_accs), 5))
print('→ Bagging 降方差效果(森林波动通常更小或持平)')
# —— 修复验证:iris 上 单棵树(max_features=全部) vs 随机森林(max_features=sqrt) ——
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
Xir, yir = load_iris(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(Xir, yir, test_size=0.34, random_state=42)
single = CARTClassifier(max_depth=4, min_samples_leaf=2).fit(Xtr, ytr) # 全部特征
rf = RandomForest(n_trees=50, max_depth=4, max_features='sqrt', seed=42).fit(Xtr, ytr)
acc_single = np.mean(single.predict(Xte) == yte)
acc_rf = np.mean(rf.predict(Xte) == yte)
print('\n[iris] 单棵树(max_features=全部)测试准确率 =', round(acc_single, 4))
print('[iris] 随机森林(max_features=sqrt)测试准确率 =', round(acc_rf, 4))
print('→ 随机森林 ≥ 单棵树:', acc_rf >= acc_single)
# 特征随机生效的证据:单棵树根特征固定;森林根/内部节点用到多个不同特征
def _features(node):
if 'feature' not in node:
return []
return [node['feature']] + _features(node['left']) + _features(node['right'])
root_feats = Counter(t.tree['feature'] for t in rf.trees if 'feature' in t.tree)
all_feats = Counter(f for t in rf.trees for f in _features(t.tree))
print('单棵树根特征 =', single.tree['feature'], '(全部特征搜索 → 固定)')
print('森林根特征分布 =', dict(root_feats), '(每树只抽 m =', rf.m, '个特征 → 随机生效)')
print('森林全部内部节点特征使用计数 =', dict(all_feats))
§4 特征重要性(随机森林版)¶
两种主流度量:
- 平均不纯度下降:分裂增益按该特征汇总(我们前面的树可统计)
- OOB 置换重要性:打乱某特征后 OOB 误差上升多少——越大越重要
手写版演示方法 2(不重训,只打乱特征重预测)。
def permutation_importance(X, y, rf_model, n_repeat=5, seed=0):
rng = np.random.default_rng(seed)
base = np.mean(rf_model.predict(X) == y)
imp = []
for f in range(X.shape[1]):
scores = []
for _ in range(n_repeat):
Xp = X.copy()
Xp[:, f] = rng.permutation(Xp[:, f]) # 打乱该特征
scores.append(np.mean(rf_model.predict(Xp) == y))
imp.append((base - np.mean(scores)) / base) # 准确率相对下降
return imp
rng = np.random.default_rng(5)
Ximp = np.vstack([rng.normal([2, 2, 0], 1.0, (40, 3)),
rng.normal([6, 2, 0], 1.0, (40, 3)),
rng.normal([4, 6, 0], 1.0, (40, 3))])
yimp = np.repeat([0, 1, 2], 40)
rfi = RandomForest(n_trees=30, max_depth=4, seed=2).fit(Ximp, yimp)
imp = permutation_importance(Ximp, yimp, rfi)
print('置换重要性(特征0/1 决定类别,特征2 是纯噪声):')
for f, v in enumerate(np.round(imp, 4)):
print(f' 特征{f}: {v}')
§5 常见 bug 与边界(面试踩坑区)¶
- 信息增益为 0 不分裂:纯分类特征(每样本唯一值)增益最大 → 过拟合;预设 min_gain 阈值
- 特征取值成字符串:
np.unique排序对类别无所谓;字典 key 必须转 str(数值/字符串混用) - 回退策略缺失:测试出现训练没见过的取值 → 默认走多数叶子,否则 KeyError
- bagging 抽样写错:
replace=False就不是 bootstrap 了(失去了样本随机性) - 投票类型:
Counter(votes).most_common(1)返回 (值, 次数),取[0][0] - 特征子采样 m 默认:分类
sqrt(d)、回归d/3(sklearn 约定) - OOB 覆盖不全:数据少时某样本从未 OOB → covered 可能 < n,注意除零
§6 面试追问与扩展(加分项)¶
6.1 决策树 vs 随机森林 vs GBDT(三分钟版)¶
- 单棵树:快、可解释、不稳定(小扰动大变化)、易过拟合
- RF:并行 Bagging 降方差,对噪声鲁棒,特征重要性免费
- GBDT:串行 Boosting 降偏差,精度更高,但更易过拟合且难并行
6.2 为什么特征随机能提升¶
若所有树同一特征竞争,树之间高度相关 → 平均后方差下降有限;随机子集让不同树「看到」不同特征 → 去相关 → 集成更稳。
6.3 其他变体¶
- Extra-Trees(完全随机阈值 + 全样本)更快更随机
- 孤立森林(iForest)用树做异常检测(随机切分,异常样本深度浅)
- 剪枝工程:CCP 代价复杂度剪枝(sklearn 默认)
§7 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 问)¶
- 1. 写出熵/条件熵/信息增益公式
- 2. 手写 entropy 与 info_gain(numpy)
- 3. 手写 ID3 分类树(递归建树+预测)
- 4. 区别 ID3 / C4.5 / CART
- 5. 手写 Gini 指数
- 6. 预剪枝 vs 后剪枝
- 7. 手写多数投票预测
- 8. Bagging 是什么、为什么降方差
- 9. 特征随机的作用
- 10. 手写随机森林(bootstrap + 投票)
L2 进阶(10 问)¶
- 11. 手写 OOB 评估
- 12. 手写置换重要性
- 13. CART 连续特征二分阈值枚举
- 14. 手写基尼分裂回归/分类树
- 15. 树深度-偏差方差实验(中间表)
- 16. 对比单树 vs 森林的方差(重采样实验)
- 17. 决策树对缺失值的处理
- 18. 手写后剪枝(验证集自底向上)
- 19. 信息增益偏向取值多特征的原因推导
- 20. Extra-Trees 手写
L3 挑战(5 问)¶
- 21. 孤立森林手写(异常检测)
- 22. RF 的 OOB 误差与交叉验证对比实验
- 23. 泰坦尼克/贷款数据完整决策树分析(手写)
- 24. 推导 Bagging 方差公式的条件与局限
- 25. 决策树在 XGBoost/LightGBM 中的改进(直方图/近似分裂)回顾
自测要点¶
- 15 分钟内盲写:熵 + 信息增益 + ID3 建树
- 白板推导信息增益与基尼的关系(都是不纯度函数)
- 对比 RF vs GBDT 三分钟版
附录:参考与结课¶
- 《统计学习方法》第 5 章(决策树)、第 8 章(Bagging/Boosting)
- Breiman 2001:Random Forests
🎉 02-机器学习 推导笔记系列(13 篇)构成¶
线性回归 → 逻辑回归 → 朴素贝叶斯/K-Means → SVM → PCA → GBDT → 决策树与随机森林 → KNN → AdaBoost → 神经网络/BP → HMM → CRF/最大熵 → 特征工程与评估——覆盖 README 验收要求的 LR/SVM/PCA/BP/HMM/CRF 必含项且超额(≥13 篇)。
下一步:03-深度学习/模型笔记/(BP / CNN / RNN-LSTM / 优化器 / BN / 正则化,全部手写实现)。
💡 本笔记验收:
02-机器学习/高频面试题.md对应分类全部打勾。
🏁 本章小结¶
- 原理一句话:决策树 = 贪心选「信息增益最大」的特征;随机森林 = 决策树 + 有放回采样 + 特征子采样(降方差)。
- 必会公式:$H=-\sum p_k\log p_k$;$\text{Gain}=H(D)-H(D|A)$;Gini $=1-\sum p_k^2$。
- 面试怎么考:ID3/C4.5/CART 区别(增益偏爱多取值 → 增益率/Gini);预剪枝 vs 后剪枝(CCP);RF 为什么降方差、特征重要性怎么算(不纯度/OOB 下降)。
- 易错点:剪枝必须用验证集(训练集上永远“剪了变差”);树模型不用特征缩放。
自测清单没把握的条目,回到对应小节重读后再打勾。