机器学习期末急救包：KD树、朴素贝叶斯等5大核心算法手算详解（附可撕式答题模板）
机器学习期末急救包：5大核心算法手算实战与避坑指南
距离期末考试只剩48小时，当你翻开《机器学习》教材发现满眼都是数学公式和算法流程图时，是否感到无从下手？这份急救包将KD树、朴素贝叶斯等高频考点转化为可撕式答题模板，每个算法都包含手写计算全流程和考场避坑红绿灯，助你在考场上快速套用。我们特别标注了阅卷老师最关注的得分关键步骤，以及90%考生会踩中的计算雷区。
1. KD树构建：从原理到实战
构建KD树是近邻搜索的基础操作，考试常给6-8个二维数据点要求逐步构造。记住这个口诀："轮流切分选中位，左小右大建子树"。以经典数据集T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}为例：
步骤详解：
- 首次切分：x轴排序(2,3)(4,7)(5,4)(7,2)(8,1)(9,6)，中位数(7,2)作为根节点
- 第二次切分：y轴划分左子树{(2,3),(5,4),(4,7)}，中位数(5,4)作为节点
- 第三次切分：x轴划分(2,3)和(4,7)分别作为叶子节点
# 伪代码实现逻辑（考试可不写） def build_kdtree(points, depth=0): k = len(points[0]) axis = depth % k points.sort(key=lambda x: x[axis]) median = len(points) // 2 return { 'point': points[median], 'left': build_kdtree(points[:median], depth+1), 'right': build_kdtree(points[median+1:], depth+1) }红绿灯警示：
- 🚨红灯错误：切分轴未交替使用（如连续两次用x轴）
- 🚦黄灯注意：偶数个数据点时中位数取后者（如4个点取第3个）
- 🟢绿灯技巧：画图时用虚线标注切分边界
2. 决策树算法：ID3与C4.5对比实操
当题目给出类似下表的气象数据集要求构建决策树时，ID3和C4.5的核心区别在于分裂标准：
| 天气 | 温度 | 湿度 | 风速 | 打球 |
|---|---|---|---|---|
| 晴 | 高 | 高 | 弱 | 否 |
| 晴 | 高 | 高 | 强 | 否 |
| 阴 | 高 | 高 | 弱 | 是 |
ID3解题模板：
- 计算整体熵：H(D) = -[p(是)logp(是) + p(否)logp(否)]
- 对每个特征A计算信息增益：Gain(A) = H(D) - ∑(|Dᵥ|/|D|)H(Dᵥ)
- 选择增益最大的特征作为分裂节点
C4.5升级要点：
- 用增益率替代信息增益：Gain_ratio(A) = Gain(A)/SplitInfo(A)
- 处理连续值：将温度"高/中/低"转化为二分切割点
- 处理缺失值：按已知值比例分配权重
易错点诊断：
- 未对增益率分母做平滑处理（当SplitInfo→0时加微小量ε）
- 误用Gini指数（那是CART算法）
- 未标注递归终止条件（如所有样本同类别）
3. 朴素贝叶斯分类器：概率计算全流程
给定训练数据要求判断新样本x=(2,S)的类别时，按以下模板操作：
计算步骤：
- 估计先验概率：P(Y=1) = N₁/N, P(Y=-1) = N₂/N
- 计算条件概率：
- P(X⁽¹⁾=2|Y=1) = count(X⁽¹⁾=2且Y=1)/count(Y=1)
- P(X⁽²⁾=S|Y=1) = count(X⁽²⁾=S且Y=1)/count(Y=1)
- 带入朴素贝叶斯公式： P(Y=1|X) ∝ P(Y=1)∏P(X⁽ⁱ⁾|Y=1)
拉普拉斯平滑技巧：当某个特征值未出现时，使用修正公式： P(X⁽ⁱ⁾=a|Y=c) = [count(X⁽ⁱ⁾=a,Y=c) + α]/[count(Y=c) + αn]
考场秘籍：遇到"零概率问题"必写平滑处理，这是得分关键点
4. SVM最大间隔超平面：手推对偶问题
给定正负样本点求最大间隔超平面时，按步骤展示KKT条件应用：
- 写出原始优化问题： min ½||w||² s.t. yᵢ(w·xᵢ + b) ≥ 1
- 构建拉格朗日函数： L(w,b,α) = ½||w||² - ∑αᵢ[yᵢ(w·xᵢ + b) - 1]
- 求偏导得对偶问题： max ∑αᵢ - ½∑∑αᵢαⱼyᵢyⱼ(xᵢ·xⱼ) s.t. ∑αᵢyᵢ = 0, αᵢ ≥ 0
支持向量识别：
- αᵢ > 0对应的样本即为支持向量
- 决策函数：f(x) = sign(∑αᵢyᵢ(x·xᵢ) + b)
计算捷径：当样本数少时（如5个点），可直接列出所有约束条件求解α：
α₁ + α₂ - α₃ - α₄ = 0 α₁ + 4α₂ + 9α₃ + 4α₄ ≤ 1 ...5. EM算法：硬币抛掷问题完整推导
面对硬币概率估计问题，EM算法分E步和M步迭代：
E步（期望）：计算每次实验属于硬币A/B的概率： P(z=A|D,θ) = P(D|z=A)P(z=A)/[P(D|z=A)P(z=A) + P(D|z=B)P(z=B)]
M步（最大化）：重新估计参数： P₁ = ∑[#正面·P(z=A|D)] / ∑[5·P(z=A|D)]
迭代示例：
初始值：P₁=0.6, P₂=0.5 第1轮E步：实验1属于A的概率=0.45 第1轮M步：新P₁=0.71 第2轮E步：实验1属于A的概率=0.65 ...收敛判断：当两次迭代的|P₁ⁿ⁺¹ - P₁ⁿ| < ε时停止（通常ε=1e-5）
可撕式答题模板（考前最后一晚背诵）
KD树构建：
- 将数据集按当前轴排序 → 2. 取中位数作为节点 → 3. 左子树递归构建 → 4. 右子树递归构建 → 5. 标注切分轴
朴素贝叶斯：P(Y=c|X) ∝ P(Y=c)∏P(X⁽ⁱ⁾|Y=c) → 类别先验 × 条件概率连乘 → 比较大小取max
SVM对偶：原始问题 → 拉格朗日函数 → 求偏导 → 代入得对偶 → 解α → 求w,b → 得决策函数
把这份指南中的红绿灯警示部分剪下来贴到准考证背面，遇到计算题时先快速扫描可能陷阱。记住：机器学习考试不是比谁记得公式多，而是看谁能把算法步骤像食谱一样清晰呈现。