k 近邻(k-Nearest Neighbor，简称 kNN)学习是一种常用的监督学习方法， 其工作机制非常简单: 给定测试样本?基于某种距离度量找出训练集中与其最 靠近的 k 个训练样本，然后基于这 k 个"邻居"的信息来进行预测. 通常， 在分 类任务中可使用"投票法" 即选择这 k 个样本中出现最多的类别标记作为预 测结果;在回归任务中时使用"平均法" ，即将这 k 个样本的实值输出标记的 平均值作为预测结果;还可基于距离远近进行加权平均或加权投票，距离越近 的样本权重越大. 与前面介绍的学习方法相比， k 近邻学习有一个明显的不同之处: 它似乎 没有显式的训练过程!事实上，它是"懒惰学习" (lazy learning)的著名代表， 此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到 测试样本后再进行处理;相应的，那些在训练阶段就对样本进行学习处理的方 法，称为"急切学习" (eager learning). 假设样本独立罔分布，且对任意 m 和任意小E数 8，在 z 附近 6 距离范围 内总能找到一个训练样本;换言之，对任意测试样本，总能在任意近的范围内找 到式(10.1)中的训练样本 z. 上一节的讨论是基于一个重要假设:任意测试样本 a 附近任意小的 6 距 离范围内总能找到一个训练样本，即训练样本的来样密度足够大，或称为"辛苦 来样" (dense sample). 然而，这个假设在现实任务中通常很难满足，例如若 8 = 0.001，仅考虑单个属性，则仅需 1000 个样本点平均分布在归一化后的属 性取值范围内，即可使得任意测试样本在其附近 0.001 距离范围内总能找到一 个训练样本，此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率 的两倍.然而，这仅是属性维数为 1 的情形，若有更多的属性，则情况会发生 显著变化.例如假定属性维数为 20，若要求样本满足密来样条件，则至少需 (103)20 = 1060 个样本.现实应用中属性维数经常成千上万，要满足密采样条件 所需的样本数目是无法达到的天文数字.此外，许多学习方法都涉及距离计算， 而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算内积都不再容易. 事实上，在高维情形下 出 现的数据样本稀疏、 距离计算困难等问 题， 是所有机器学习方法共同面 临 的严重障碍， 被称为" 维数灾难" (curse of dimensionality) . 缓解维数灾难的一个重要途径是降维(dimension red uction) ， 亦称"维数 约简 PP ，即通过某种数学变换将原始高维属性空间转变为一个低维"子空 间" (subspace)，在这个子空间 中样本密度大幅提高， 距离计算也变得更为容 易为什么能进行降维?这是因为在很多时候， 人们观测或收集到的数据样本 虽是高维的?但与学习任务密切相关的也许仅是某个低维分布，即高维空间中 的一个低维"嵌入" (embedding). 原始高维 空间中的样本点，在这个低维嵌入子空间中更容易进行学习. 若要求原始空间中样本之间的距离在低维空间中得以保持，即得到"多维缩放" (Multiple Dimensional Scaling，简称 MDS) [Cox and Cox, 2001] 这样一种经典的降维方法. 下面做一个简单的介绍. 假定 m 个样本在原始空间的距离矩阵为 D ε Jæmx气 其第 4 行 j 列的元 素 distij 为样本 Xi 到 Xj 的距离. 我们的目标是获得样本在 d’ 维空间的表示 Z E ]Rd’xm , d’ ~三 d， 且任意两个样本在 d’ 维空间中的欧氏距离等于原始空间中 的距离，即 IIZi - zjll = distij. 降维后低维空间的维数 d’ 通常是由用户事先指定，或通过在 d’ 值不同的 低维空间中对 k 近邻分类器(或其他开销较小的学习器)进行交叉验证来选取 较好的 d’ 值.PCA 仅需保留 W 与样本的均值向量即可通过简单的向量减法和矩阵"向 量乘法将新样本投影至低维空间中. 显然，低维空间与原始高维空间必有不同， 因为对应于最小的 d-d’ 个特征值的特征向量被舍弃了，这是降维导致的结果. 但舍弃这部分信息往往是必要的- 一方面舍弃这部分信息之后能使样本的采 样密度增大，这正是降维的重要动机; 另一方面，当数据受到噪声影响时， 最小 的特征值所对应的特征向量往往与噪声有关?将它们舍弃能在一定程度上起到 去噪的效果.
