统计学习精要(The Elements of Statistical Learning)课堂笔记（二十三）：原型方法和最近邻KNN

笔记（二十二）需要等我找到上一本笔记本再说，暂时不知道扔到哪里去了...汗。届时补上。

这一章主要是讲的原型方法（prototype）和最近邻（KNN）。相对而言直觉更强，公式没那么复杂。

--------------------------笔记开始-------------------

1. 原型方法

1) 1-NN 最近邻居方法

最极端的情况：只找到最近的一位邻居。

数据集，输入，在中找到与最近的邻居，输出对应的类标记。

2) 类中心的方法

类中心： ，相当于对于一群有着同样类标记的点，对x取平均。

输入：，而后在所有类中心中与其最近的类中心。

输出：对应的类标记。

3) 对每个类可计算若干个“中心”（称之为原型或者样板，比如在每类中做聚类）。

输入：，而后在所有类中心中与其最近的类中心。

输出：对应的类标记。

4) K-NN方法

输入：，在中找到与最近的K个邻居。

输出：(最多的那一类，从众原则的感觉）。

由于这一类方法都比较懒，所以称之为lazy learning methods.

2. K-NN方法的错误率（渐近性质）

1) 结果

设为Bayes分类器的错误概率（最优分类器）；为1-NN分类器的错误概率。

则有：当样本数时，。接下来会证明这个优良的性质。

2) 分类问题

给定，则。

这里我们称 为先验分布，为类分布。从而

，称之为后验概率。

3) Bayes分类器

x对应的，即使得后验概率最大的k。

所以，，从。

4) 1-NN分类器

1-NN输出的是离x最近的对应的，则

。

由于只限训练集，而那部分只跟测试集有关，所以由独立性我们可以拆分为：

，则当时，,，上面一项可以收敛为，为后验概率（条件误差）。

5)由于，设为所有中最大的，则

6)。得证。

下一章会讲到聚类，然后就是降维了。