决策树
像玩"20个问题"游戏一样做分类——每次提一个问题，顺着答案走，最终得出结论
01 核心原理（大白话版）
你早上要不要带伞？先问：今天会下雨吗？会 → 带伞。不会 → 再问：会刮风吗？会 → 带伞。不会 → 不带。
这就是决策树：把一个复杂决策拆成一连串"是/否"问题，沿着树枝走到叶子节点，得出答案。
算法只做一件事：找最好的问题
遍历所有特征，找"问哪个问题能把数据分得最干净"——用信息增益或基尼系数来量化"干净程度"。
按选出的特征把数据集一分为二（或更多），各子集递归重复第 1 步。
当子集已全是同一类别、深度达到上限、或样本数太少时，停止分裂，该节点成为叶子（预测结果）。
信息增益 vs 基尼系数
信息增益（ID3/C4.5）
用熵衡量"混乱程度"，选分裂后熵下降最多的特征。对取值多的特征有偏好，C4.5 用增益率修正。
基尼系数（CART）
衡量随机取两个样本类别不同的概率，计算更快。sklearn 默认使用 CART 算法。
随机森林 = 很多棵决策树投票。每棵树随机抽样本、随机选特征来训练，集体投票比单棵树准得多，且不容易过拟合。
一步步构建决策树
用非线性的月牙形数据来测试——线性模型在这里会失败，正好展现决策树的优势。
基尼系数越小说明数据越纯净。决策树每次分裂都追求让子集的基尼系数尽可能小。
遍历所有特征和所有可能的阈值，选出基尼增益最大的那个切法——这就是决策树"学习"的全部。
找到最优分裂点后，把数据一分为二，左右子树递归重复同样的过程，直到满足停止条件为止。
四段拼在一起，加上可视化，就是完整演示代码——看下面。
02 代码
03 学术性讲解
信息熵与信息增益
数据集 S 的熵定义为：
其中 pᵢ 为第 i 类样本的占比。熵越大表示越混乱（不确定性越高）。
按特征 A 分裂后的信息增益：
选 IG 最大的特征分裂，即每次分裂后信息的不确定性降低最多。
基尼系数（CART）
节点 t 的基尼不纯度：
CART 选使加权基尼不纯度下降最多的特征和阈值，构建二叉树（每次只分两支）。
过拟合与剪枝
不加限制的决策树会过拟合（把训练集完全记住）。常用控制手段：
- 预剪枝：限制最大深度（max_depth）、最小分裂样本数（min_samples_split）
- 后剪枝：先长满，再从叶子向上合并不必要的分裂（代价复杂度剪枝）
随机森林的方差减少原理
若 n 棵独立同分布的树各有方差 σ²，均值的方差为 σ²/n。随机森林通过 Bootstrap 采样 + 随机特征子集引入差异性，使树间相关性 ρ 降低，集成方差为：
当树数量足够多时，第二项趋于 0，集成误差主要由树间相关性决定。
复杂度
- 训练：O(n·d·log n)，n 为样本数，d 为特征数
- 预测：O(depth)，深度通常为 O(log n)
- 随机森林训练：O(T·n·√d·log n)，T 为树的棵数