本文共 1464 字，大约阅读时间需要 4 分钟。
笔记（二十二）需要等我找到上一本笔记本再说，暂时不知道扔到哪里去了...汗。届时补上。
这一章主要是讲的原型方法（prototype）和最近邻（KNN）。相对而言直觉更强，公式没那么复杂。
--------------------------笔记开始-------------------
1) 1-NN 最近邻居方法
最极端的情况：只找到最近的一位邻居。
数据集 D={ (xi,yi),1≤i≤N}
，输入 xi ，在 { xj,j≠i} 中找到与 xi 最近的邻居 xk ，输出 xk 对应的类标记 yk。
2) 类中心的方法
类中心： ck=1Nk∑yi=kxi,1≤k≤K
，相当于对于一群有着同样类标记的点，对x取平均。
输入： xi
，而后在所有类中心中与其最近的类中心 cl。
输出： cl
对应的类标记。
3) 对每个类可计算若干个“中心”（称之为原型或者样板，比如在每类中做聚类）。
输入： xi
，而后在所有类中心中与其最近的类中心 cl。
输出： cl
对应的类标记。
4) K-NN方法
输入： xi
，在 { xj,j≠i} 中找到与 xi最近的K个邻居。
输出： maxyk
(最多的那一类，从众原则的感觉）。
由于这一类方法都比较懒，所以称之为lazy learning methods.
1) 结果
设 P∗(e)
为Bayes分类器的错误概率（最优分类器）； P¯(e)为1-NN分类器的错误概率。
则有：当样本数 N→∞
时， P∗(e)≤P¯(e)≤2P∗(e)。接下来会证明这个优良的性质。
2) 分类问题
给定 (x,y)
，则 P(x,y)=P(y)P(x|y)。
这里我们称 P(y=k)=πk
为先验分布， P(x|y=k)=fk(x)为类分布。从而
Pk(x)=P(y=k|x)=P(y=k,x)P(x)=P(y=k)P(x|y=k)∑kP(x,y)=πkfk(x)∑kπkfk(x)
，称之为后验概率。
3) Bayes分类器
x对应的 k=argmaxkPk(x)
，即使得后验概率最大的k。
所以， P∗(e|x)=P∗(y≠k∗|x)=1−P(y=k∗|x)=1−Pk∗(x)
，从 P∗(e)=Ex[P∗(e|x)]。
4) 1-NN分类器
1-NN输出的是离x最近的 x¯
对应的 y¯，则
P¯(e|x)=P(y≠y¯|x)=1−P(y=y¯|x)=∑Kk=1P(y=k,y≠y¯|x)=∑Kk=1P(y=k|x)P(k≠y¯|x,y=k)
。
由于 k≠y¯
只限训练集，而 y=k那部分只跟测试集有关，所以由独立性我们可以拆分为：
=∑Kk=1Pk(x)P(k≠y¯|x)
，则当 N→∞ 时， x→x¯ , y→y¯ ，上面一项可以收敛为 ∑Kk=1Pk(x)(1−Pk(x))=1−∑Kk=1P2k(x)，为后验概率（条件误差）。
5)由于 P∗(e|x)=1−Pk∗(x)
，设 Pk∗ 为所有 Pk中最大的，则
P¯(e|x)=1−P2k∗−∑k≠k∗P2k≤1−P2k∗−1K−1(1−P2k∗)=2P∗(e|x)−P∗(e|x)2−1K−1P∗(e|x)2
6) P¯(e)=Ex[P¯(e|x)]=Ex[2P∗(e|x)−P∗(e|x)2−1K−1P∗(e|x)2]≤2P∗(e)−KK−1P∗(e)2≤2P∗(e)
。得证。
下一章会讲到聚类，然后就是降维了。
转载地址：http://jcvqj.baihongyu.com/