第十章降维与度量学习

10.1 k近邻学习

k近邻（k-Nearest Neighbor，kNN）学习是一种常用的监督学习方法，其工作机制非常简单：找离测试样本“最近”的k个训练样本，然后基于k个“邻居”的信息来进行观测。通常，在分类任务使用“投票法”，在回归任务使用“平均法”。
k近邻学习是懒惰学习（lazy learning）——在训练时仅仅保存样本，待收到测试样本后在进行处理；相应的，在训练阶段就对样本进行学习处理的方法称为急切学习（eager learning）。
给定测试样本x，其最近样本z，则最近邻分类器出错的概率就是x与z不同的概率，即

假设样本独立同分布，且对任意x和任意小正数δ，在x附近δ距离范围内总能找到一个训练样本z.令c=argmax_c∈YP(c|x*)表示贝叶斯最优分类器的结果，有

也就是说，最近邻分类器的泛化错误率不超过贝叶斯最优分类器的2倍。

10.2 低维嵌入

上一节的讨论基于一个前提：任意x和任意小正数δ，在x附近δ距离范围内总能找到一个训练样本，即训练样本密度足够大。在归一化d维空间内需要(1/δ)^d，而d往往非常大，于是所需的样本数是天文数字，样本不够学不了，称为“维数灾难”（curse of dimensionality），所以我们需要降维。
在很多时候，虽然数据是高维的，但是与学习任务有关的只有低维，即高维空间的一个低维“嵌入”

多维缩放（Multiple Dimensional Scaling）：
假定m个样本在原始空间的距离矩阵为D∈R^m×m，其第i行j列的元素dist_ij为样本x_i到x_j的距离。我们的目标是获取样本在d'维空间的表示Z∈R^d'×m，d'<=d，且||z_i-z_j||=dist_ij
令B=Z^TZ∈R^m×m，其中B为降维后样本的内积矩阵，b_ij=z_i^Tz_j，有