1.1 k近邻学习

k近邻学习（k-Nearest Neighbor,简称kNN）学习是一种常见的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。通常，在分类任务中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这k个样本的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

与前面介绍的学习相比，k近邻学习有一个明显的不同之处：它似乎没有显示的训练过程！事实上，它是“懒惰学习“（laze learning）的代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后在进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法，称为“急切学习”（eager learning）.

下图是k近邻分类器的一个示意图。显然，k是一个重要参数，当k取不同值时，分类结果会有显著的不同。另一方面，若采用不同的距离计算方式，则找出“近邻”可能有显著差别，从而也会导致分类结果有显著不同。

k近邻分类示意图。虚线显示出等距线；测试样本在k=1或k=5时判别为正例，k=3时被判别为反例

暂且假设距离计算是“恰当”的，即能够恰当地找出k个近邻，我们来对“最近邻分类器”（1NN,即k=1）在二分类问题上的性能做一个简单的讨论。

给定测试样本x，若其最近邻样本为z，则最近邻分类器出错的概率就是x与z类别标记不同的概率，即

假设样本独立同分布，且对任意x和任意小正数，在x附近距离范围内总能找到一个训练样本；换言之，对任意测试样本，总能在任意范围内找到上式中的训练样本z。令

表示贝叶斯最优分类器的结构，有

于是我们得到了有点令人吃惊的结论：最近邻分类器虽简单，但它的泛化能力错误率不超过贝叶斯最优分类器的错误率的两倍。

1.2 低维嵌入