知识卡片
多数表决等价风险最小
“K 个邻居里哪类多就判哪类”不是约定俗成,而是 0-1 损失下的最优决策。
推导。取 0-1 损失,误分类概率为 P(Y≠f(X)) = 1 − P(Y=f(X)),其中 f(X) 是决策函数。对某个待预测点 x_j,设它被判定为 c_r,误分类率就是邻域 N_k 里标签不等于 c_r 的邻居占比:
L = (1/K) · Σ_i I(y_i ≠ c_r)
I 是指示函数,条件成立取 1,否则取 0。要让 L 最小,等价于让 Σ_i I(y_i ≠ c_r) 最小,也就等价于让 Σ_i I(y_i = c_r) 最大——即在 K 个邻居中,与 c_r 相同的标签数量最多。
结论。因为邻居的标签 y_i 已知、待预测点的类别 c_r 未知,唯一能做的选择就是取邻域中出现次数最多的那一类。多数表决因此是”让经验风险最小”的直接解,误分类率本身就是训练数据上的经验风险。
这个结论的用途。它说明 K 近邻不需要额外的优化:没有损失函数的梯度、没有参数求解,规则本身就是最优解,前提只是损失是 0-1。这与第 4 章朴素贝叶斯的[[后验最大等价风险最小]]是同一套论证——两者都在逐点最小化 0-1 损失,区别只是概率的来源:一个来自分布假设下的连乘,一个来自邻居计数的频率。
边界:
- 类别不平衡时多数表决偏向多数类。邻域里 90% 是 A 类时,哪怕该点明显更像 B 类,也大概率判 A。若各类错分代价不同或分布倾斜,应改用带权投票(按距离反比加权)或先做重采样。
- 距离被忽略。标准多数表决把最近邻和第 K 近邻当作同等权重。原文在实例中提到
weights='distance'(权重与距离成反比)的效果稍优于均等投票,这正是对这条边界的修正。 - K 为偶数时可能平票,实践上取奇数规避。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第05章 K近邻
原书出处 · 1 处
- 第5章 K近邻 5.2.3 分类决策规则 · 查看原书依据
从上面的式子可以看出:使误分类率最小等价于使预测样本实例xj 选定的K个最近邻训练样本实例xi (i=1,2,
参考来源
- 位置:《机器学习基础:从入门到求职》第5章《K近邻》5.2.3 分类决策规则(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00008.html)
- 结论依据:原文用 0-1 损失写出误分类率,推导出最小化误分类率等价于让邻域内同类标签尽可能多,从而得到多数表决规则,并指出它等价于经验风险最小化。
- 原始内容:从上面的式子可以看出:使误分类率最小等价于使预测样本实例xj选定的K个最近邻训练样本实例xi(i=1,2,…,K)的类别标签yi尽可能多的和预测样本实例xj的预测类别cr相同。