资料参考来源：

清华大学出版社-周志华《机器学习》第十章 降维与度量学习

清华大学出版社-李航《统计学习方法》第三章 k近邻法

基本概念

k近邻（k-Nearest Neighbor ，简称kNN）学习是一种较为常用的监督学习方法，其工作机制就是在给定测试样本后基于某种距离度量来找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。

这种先给出测试集才会处理训练集，也即没有显式训练过程的学习方法与我们之前所用过的方法一些区别，这种学习方法被称为懒惰学习（lazy learning）。而与之相比，前面我们所介绍的在训练阶段就对样本进行学习处理的方法，就被称为急切学习（eager learning）

k近邻算法针对“分类问题”和“回归问题”有不同的应对方式。通常来说，对“分类问题”可以采用“投票法”，即选择在训练集中找出的k个“邻居”出现最多的类别标记作为预测结果；对“回归”问题这是将这k个样本的实值输出标记的平均值作为预测结果。（还可以基于距离远近进行加权平均或者加权投票，距离越近的样本权重越大。）

k近邻算法与模型

我们这里仅讨论分类问题中的k近邻法。

在分类问题中，k近邻法实际上是一个利用训练数据集对特征向量空间进行划分，并作为其分类的模型。其中，k值的选择，距离度量以及分类决策规则是k近邻法的三个基本要素。k近邻法1968年由Cover和Hart提出。

k近邻算法

k近邻算法简单直观，和上面所介绍地一样：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，那么输入的实例就会被划分到哪个类。

假设我们有输入的训练样本集：

其中，$x_i∈X\subseteq R^n$为实例的特征向量，$y_i∈Y=\{c_1,c_2,...,c_k\}$为实例的类别，$i=1,2,...,N$；实例的特征向量为$x$。

那么就会输出实例样本$x$所属的类别$y$。

中间算法的计算过程：

1. 根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域就记作$N_k(x)$
2. 在$N_k(x)$中根据分类决策规则（如多数表决）决定$x$的类别$y$：

在上面的这个公式中I为指数函数，这与我们前面所讲的指数函数是一个意思，只是在我现在所参考的这本书（《统计学习方法》）里用了另一种表达形式（用原来的形式表达就是$1\{y_i=c_j\}$）

这条公式的意思就是挑出在邻近那k个点中最多的那个类别作为输入的测试实例x的类别y。

k近邻法的特殊情况发生在k=1的时候，这个时候我们称其为最近邻算法。因为这个时候对于输入的特征向量x，最近邻法会直接将训练数据集中与x最接近的点的类别作为x的类。

k近邻模型

k近邻模型实际上就是对特征空间的划分，它由三个基本要素组成：

1. 距离度量
2. k值的选择
3. 分类决策的规则

在k近邻法中，当训练集，距离度量，k值以及分类的决策规则确定后，对于任何一个新的输入实例，它所属的类都是唯一确定的。这就相当于根据上述要素将特征空间划分为一些子空间，从而确定子空间中每个点所属的类，这个时候如果有新的输入实例，那么模型就会判断它属于哪个子空间从而决定将它划分到哪个类。

特征空间中，对每个训练样本的特征点（训练实例点），离该点比离其它点更近的所有点组成的一个区域，叫做单元（cell）。每个训练样本的特征点都拥有一个单元，所有训练样本的特征点的单元构成对特征空间的一个划分。

最近邻法会将样本特征为$x_i$的点的类$y_i$作为其单元中所有点的类标记(class label)。这样，每个单元的特征点的类别就是确定的。

下图就是一个二维特征空间划分的例子：

距离度量

特征空间中两个实例点的距离就是两个实例点（特征点）的相似程度的反映。k近邻模型的特征空间一般是n维实数向量空间$R^n$。k近邻模型使用的距离度量方式一般是欧氏距离，当然，有时也可以是其它距离，如$L_p$距离，($L_p$ distance)或Minkowski距离(Minkowski distance)

设特征空间$X$是n维实数向量空间$R^n$，$x_i,x_j∈X$，$x_i=(x^{(1)}_i,x^{(2)}_i,...,x^{(n)}_i)^T$，$x_i=(x^{(1)}_j,x^{(2)}_j,...,x^{(n)}_j)^T$，则$x_i,x_j$的$L_p$距离定义为：

在上面这个公式中，p ≥ 1。

当p = 2时，则称为欧氏距离(Euclidean instance)：

当p = 1时称为曼哈顿距离（Manhattan distance）：

当p = ∞ 时，它是各个坐标距离的最大值：

下图给出了二维空间中p取不同值时，与远点的$L_p$距离为1（$L_p=1$）的点的图形：

下面我们举个例子来说明，由不同的距离度量所确定的最近邻点是不同的：

已知二维空间的3个点$x_1=(1,1)^T,x_2=(5,1)^T,x_3=(4,4)^T$,试求在p取不同值时，$L_p$距离下$x_1$的最近邻点：

因为$x_1$和$x_2$只有第二维上值不同，所以不论p为何值，都有$L_p(x_1,x_2)=4$。

而

因此我们可以得到，当p等于1或2时，$x_2$是$x_1$的最近邻点，p大于等于3时，$x_3$是$x_1$的最近邻点。

k值的选择

k值的选择会对k近邻法的结果产生重大的影响。

如果我们选择的k值过小，那么就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，但“学习”的估计误差(estimation error)就会增大。我们可以理解为，k值过小会导致预测结果对近邻的特征点十分敏感，如果特征点恰好是噪音，预测就会出错，换句话说，就是容易发生过拟合。

如果的k值过大，就相当于用较大邻域中的训练实例进行预测。优点是可以减少学习的估计误差，但近似误差就会相应增大。换句话说，就是容易欠拟合。

在应用中，k值一般都会取一个偏小的数值。并且，通常会使用交叉验证法来选取最优的k值。

选择模型的方法 正则化与交叉验证

提到交叉验证，我们显然有必要了解一下这方面的内容，它是一种模型选择方法，而说到模型选择方法，我想我们有必要介绍一下我们以后会较为常用的两个模型选择方法：

正则化

正则化（regularzation）是一个典型的用于选择模型的方法。它是结构风险最小化策略的实现，是在经验风险上加一个正则化项（regularizer）或罚项（penalty term）。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。

结构风险一词第一次在我们的笔记中出现，但实际上，我们可以将它看作是对经验风险的一个优化。

那么经验风险(empirical risk)是什么呢？事实上，我们从第一章就在应用经验风险了。我们知道，我们之前所讲过的学习模型不论是线性回归还是逻辑回归都是建立在以“误差”最小化为目的的基础上的，而这里的“误差”其实与我们一般所讲的误差是有区别的，将模型应用到测试集中，测试结果与实际情况的误差才是我们通常认为的“误差”，这种误差我们通常称做一般误差，亦被称为期望风险。而我们用于建立模型的，以最小化模型在训练集中的“误差”为目的的算法中的那个“误差”，便是我们所说的经验误差，对应于期望风险，它又被称作经验风险。而用于表示经验风险（也可称经验损失（empirical loss））的函数：

便与我们曾经介绍过的“成本函数”（cost function）（例如$J(θ)=\frac{1}{2}\sum^m_{i=1}(y-h_θ(x))^2$）很相似。另外，计算误差所用的成本函数也可以被称为损失函数(loss function)，损失函数中常用的形式，除了我们用过的平方损失函数之外，还有：

你可能会想三者似乎没有什么区别，事实上成本函数和损失函数确实没有什么区别。但我们在线性回归中用的$J(θ)$严格来讲仅仅是一个用于衡量经验误差大小的函数，它与现在我们所讨论的损失函数有一点点区别就是它可以为了方便计算而做出一些修改，也就是说只要它适合我们用于建立模型即可，而目的并不是严格计算出经验风险。

有这么一层理解，我们就可以知道经验风险函数与成本函数的区别了，成本函数仅是为了方便计算而用于表示风险的一个计算式，经验风险函数$R_{emp}$则更偏向于严格衡量模型的经验风险。

也正因此，极大似然估计也可以看作是经验风险最小化的一个策略。

那么，结构化风险又是什么呢？

如我们前面所说，一般来说，我们建立模型的基准都是通过最小化经验风险（empirical risk minimization ,ERM），但经验风险并不代表期望风险，也即测试集中的误差和训练集中的误差是有区别的，这就意味着，当经验风险真的最小化的时候，就会出现过拟合的现象，模型完美贴近训练集，但在测试集中往往会表现不佳。

那么为了避免这一情况出现，也即防止过拟合出现，就有了结构风险最小化（structural risk minimization,SRM），而这个策略，事实上就等价于正则化。

现在，我们就又回到了我们的正则化。

首先，我们知道，结构风险就是在经验风险上加上表示模型复杂度的正则化项或罚项，在假设空间，损失函数以及训练数据集确定的情况下，结构风险的定义是：

前面一项就是我们才介绍过的经验风险，而后一项中的$J(f)$就表示模型的复杂度，它是定义在假设空间$F$上的泛函（通常是指一种定义域为函数，而值域为实数的“函数”。换句话说，就是从函数组成的一个向量空间到实数的一个映射。也就是说它的输入为函数，而输出为实数，来自维基百科），模型f越复杂，复杂度$J(f)$就越大；反之，模型越简单，复杂度$J(f)$就越小。也就是说，复杂度表示了对复杂模型的惩罚。$λ≥0$是系数，用以权衡经验风险和模型复杂度。结构风险小的模型往往对训练数据以及位置的测试数据都有较好的预测。

贝叶斯估计中的最大化后验概率估计(maximum posterior probability estimation ,MAP)就是结构风险最小化的一个例子。当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大化后验概率估计。

因此，结构风险最小化策略就是使结构风险最小化的求解最优化问题的模型：

而这个公式同时也是正则化的一般形式。$λJ(f)$我们就称之为正则化项。

正则化项可以取不同的形式。例如，回归问题中，损失函数是平方损失，正则化项就可以是参数向量的$L_2$范数：

这里$\mid\mid w\mid\mid$表示参数向量的$L_2$范数：

正则化项也可以是参数向量的$L_1$范数：

其中$\mid\mid w\mid\mid_1$表示参数向量w的$L_1$范数。

这时候，如果第1项的经验的经验风险较小，模型就有可能比较复杂（有多个非零参数），这时第2项的模型复杂度就会较大。正则化的作用就是选择经验风险与模型复杂度同时较小的模型。

正则化比较符合我们曾提到过的奥卡姆剃刀（Occam’s razor）原理，它应用于模型选择时变为以下想法：能够很好的解释已知数据，并且在所有可以选择的模型中十分简单的模型，才是好模型。

从贝叶斯估计的角度来看，正则化项对应于模型的先验概率，可以假设复杂的模型有较小的先验概率，简单的模型有较大的先验概率。

交叉验证

对比于正则化，另一种常用的模型选择方法就是交叉验证（cross validation）

如果给定的数据集充足，我们选择模型时常用的一个简单地方法是随机地将数据集切分成三部分，训练集（training set）、验证集（validation set）、和测试集（test set）。训练集用来训练模型，验证集用于模型的选择，测试集用于最终对学习方法地评估（类似于我们在上一章决策树中所提到过的剪枝）。当验证集有足够多的数据时，用它对模型进行选择也是有效的。

但是，在实际应用中我们往往会遇到数据不够充足的情况，这种时候，就可以用到交叉验证了。交叉验证的基本思想是先将给定的数据集进行切分，将切分的数据组合为训练集与测试集，然后对模型进行训练并测试，在此基础上反复进行训练、测试以及模型选择。

这里我们来简单地介绍一下交叉验证的三个方法：

1.简单交叉验证

简单交叉验证的方法是：首先随机地将已给的数据集分为两部分，一部分作为训练集，一部分作为测试集；然后，用训练集在各种条件下（如不同的参数个数）训练模型，从而得到不同的模型；然后再在测试集上评价各个模型的测试误差，选出测试误差最小的模型。

2.S折交叉验证

应用最多的交叉验证方法是S折交叉验证(S-fold cross validation)，方法如下：首先随机地将已给的数据集切分为S个互不相交大小相同的子集；然后，利用S-1个子集的数据来训练模型，而余下的子集就用于测试模型；将这一过程对可能的S种选择重复进行；最后，选出S次评测中平均测试误差最小的模型。

3.留一交叉验证

我们将S折交叉验证中的S = N，就是留一交叉验证（leave-one-out cross validation）。这里，N是给定数据集的容量。这种方法常常在数据相当缺乏的情况下使用。

分类决策规则

k近邻法中的分类决策规则往往是多数表决规则（majority voting note），即由输入实例的k个邻近的训练样本实例中的多数类来决定输入实例的类。

多数表决规则有如下解释：如果分类损失函数为0-1损失函数，则其分类函数为：

误分类的概率为：

对给定的实例$x∈X$，其最邻近的k个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$的区域类别是$c_j$，那么误分类率是：

要使误分类率最小即使经验风险最小，就要使$\sum_{x_i∈N_k(x)}I(y_i=c_j)$最大，所以多数表决规则等价于经验风险最小化。

kd树

实现k近邻法时，我们主要考虑的问题是如何对训练数据进行进行快速k近邻搜索。“快速”这点在特征空间的维数极大或者数据容量大时尤其必要。

k近邻法最简单的实现办法是线性扫描（linear scan），就是计算输入实例与每一个训练实例的距离。但这个方法过于简单粗暴，因此当训练集很大时这个方法相当不可取。

所以，为了提高k近邻搜索的效率，我们可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。这样的方法有很多，我们这里来介绍一下kd树（kd tree）方法。

构造kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树属于二叉树，表示对k维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域（在这里我们可以看到我们似乎可以看到决策树的影子，事实上二者确实很相像）。

另外，kd树的“k”和k近邻法的“k”的意义并不相同。

构造kd树的方法如下：

1. 首先构造根节点，使根节点对应于k维空间中包含所有实例点的超矩形区域
2. 通过下面所说的递归方法，不断地对k维空间进行划分，生成子节点：
3. 先在超矩形区域（根节点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面（就是能够将数据集分开的，在多维空间上的平面，公式为$wx+b=0$w是超平面的法向量，b是超平面的截距），这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子节点）
4. 将实例划分到两个子区域后，继续上述过程，直到子区域内没有实例，终止之后的节点为叶节点。在此过程中，将实例保存在相应的节点上。

这个构造方式我们可以参考决策树的构造方式，只是我们之前形容决策树的构造方式时是从树形结构的角度来表达的，而这里描述kd树的构造方式时，我们是从特征空间的角度来描述的，并无本质上的不同。

通常，我们在依次选择坐标轴对空间切分时，都会选择训练实例点在选定坐标轴上的中位数（median）作为切分点，这样得到的kd树是平衡的。注意，平衡的kd树搜索时的效率未必是最优的。

下面我们来举一个构造平衡kd树的例子。

例：构造平衡kd树

输入：k维空间数据集$T={x_1,x_2,...,x_N}$

其中，$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)})^T,i=1,...,N$

输出：kd树

过程：

1. 开始：构造根节点，根节点对应于包含T的k维空间的超矩形区域： 选择$x^{(1)}$为将与超平面垂直的坐标轴，以T（训练样本集合）中所有样本的$x^{(1)}$坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。 由根节点生成深度为1的左右子节点（子区域）：左子节点对应坐标$x^{(1)}$小于切分点的子区域，右子节点对应坐标$x^{(1)}$大于切分点的子区域。 落在切分超平面上的样本保存在根节点。
2. 重复：对深度为j的节点，选择$x^{(l)}$为切分的坐标轴，$l=j(mod~k)+1$（x mod y表示求余运算，即求x整除y的余数），以该节点的区域中所有样本的$x^{(l)}$的中位数作为切分点，将该节点对应的矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{(l)}$垂直的超平面实现： 由该节点生成的深度为j+1的左右子节点：左子节点对应坐标$x^{(l)}$小于切分点的子区域，有直接点对应坐标$x^{(l)}$大于切分点的子区域。
3. 直到两个区域没有实例存在时停止，从而形成对kd树区域的划分。

我们来举一个实际的例子，假设有一个二维空间的训练样本集合：

我们藉构造的kd树的二维空间图形表示就是：

树形表示则是：

看到这里我们会觉得，kd树的划分似乎并没有决策树对样本点的每一次划分那么严谨，但实际上，kd树还需要根据当前子节点上各坐标轴上样本特征值的方差来决定用来划分的坐标轴，因为一条坐标轴上方差越大就说明样本在这条坐标轴上“散的越开”，就越适合切分。因此，这里介绍的kd树的划分方式实际上是比较简单的。但这也体现出了kd树与决策树的区别，前者的划分通过中位数和方差，而后者的划分要通过信息增益、增益率或是基尼系数等等。另外还有一个非常重要的区别是，决策树的叶节点导出的是样本的最终结果，即它的类别，而kd树的叶节点不是，它的叶节点只是一个超矩形区域。换句话说，当我们有一个测试样本时，在决策树中我们只需要根据样本特征不断分类，由根至叶来找到该样本的类别，而在kd树中，从包含测试样本点的叶节点的超矩形区域开始，由叶至根逐层搜索离测试样本点最近的训练样本点。

搜索kd树

接下来我们将利用kd树来进行k近邻搜索。

这里我们将以“最近邻”的搜索方式作为例子叙述：

假设我们有一个测试样本，要通过kd树搜索其最近邻：

• 首先要找到包含测试样本的叶节点；
• 然后，从该叶节点出发，依次回退到父节点
• 不断查找与测试样本最邻近的节点，当确定不可能存在更近的节点时终止搜索

这样，搜索就会被限制在空间的局部区域上，效率大为提高。

包含测试样本的叶节点实际上就是就是测试样本点在特征空间中所在的最小超矩形区域。以此叶节点（区域）对应的样本点作为当前最近点。测试样本点的最近邻一定在以该测试样本点为中心，并通过当前最近点的超球体内部，如图：

然后，返回当前节点的父节点，如果，父节点的另一子节点的超矩形区域与超球体相交，那么，就在相交的区域寻找与测试样本点更近的训练样本点。如果，存在这样的点，就可以将该点作为新的当前最近点，然后算法转到更上一级的父节点。重复此过程，直到找到的父节点的下的另一子节点的超矩形区域不与超球体相交，或者不存在比当前最近点更近的点，则停止搜索。

例：利用kd树的最近邻搜索

输入：已构造的kd树；测试样本点x；

输出：x的最近邻

1. 在kd树中找到包含测试样本点x的叶节点： 从根节点出发，递归向下访问kd树。若目标点当前维的坐标小于切分点的坐标，则移动到左子节点，否则移动到右子节点。直到子节点为叶节点为止
2. 将搜索到的叶节点作为“当前最近点”
3. 递归地向上回退，并在每个节点上进行以下操作： a. 如果该节点保存的训练样本点比当前最近点距离测试样本点还近，则将该训练样本点作为“当前最近点” b. 当前最近点一定存在于该节点一个子节点对应的区域。检查该子节点的父节点的另一个子节点对应的区域是否有更近的点。具体地说，就是当前区域是否与以测试样本点为球心，测试样本点与“当前最近点”的距离为半径的超球体相交。 如果相交，则可能在另一个子节点对应的区域内存在距离测试样本点更近的点，算法移动到另一个子节点，进行最近邻搜索 如不相交，则算法向上回退
4. 回退到根节点时，搜索结束，最后的“当前最近点”即为x的最近邻点。

如果，训练样本点是随机分布的，那么kd树搜索的平均计算复杂度就是$O(logN)$。kd树更适用于训练样本数远大于空间维数时的k近邻搜索。当空间维数接近训练样本数时，它的效率会迅速下降，几乎接近线性扫描。