第三章 k近邻法-EW帮帮网

3.1 简介

3.1.1 直观理解

k近邻法（k-nearest neighbor，k-NN）顾名思义，就是k个相邻的邻居，这说明我们如果给定一个新的实例的时候，它是要根据最近的k个邻居来决定。

k近邻法是一种基本的分类与回归方法。主要思想是：假定给定一个训练数据集T，其中实例给定，当输入新的实例x时，可以根据其最近的k个训练实例的标签，预测新实例x对应的标注信息。

对于分类问题：对新的实例，根据与之相邻的k个训练实例的类别，通过多数表决等方式进行预测。也就是说，在这k个训练实例里面所属的哪一种类别占比最大，那么这个新的实例点就属于哪一个类别，这也可以称作是大概率事件。

对于回归问题：对新的实例，根据与之相邻的k哥训练实例的标签，通过均值计算进行预测。

下面我们通过一个图形进行简单直观的理解：

在这里，我们给定了11个训练样本，其中包括6个蓝色正方形，5个红色三角形。现在，假如给定一个新的实例，即绿色圆形，那么这个绿色点属于哪个类别呐？

如果这时候，k=3，那么在这个二维的图形里面，我们计算与这个绿色圆最近的三个点是一个蓝色的方框和两个红色的三角形。在这里，红色三角形所占的比例是2/3大于蓝色正方形所占比例的1/3。所以，可以认为这个绿色圆是属于红色三角形这个类别。

假如k=5，那么与绿色圆最近的5个点就是这三个蓝色正方形和两个红色三角形，这时候蓝色正方形所占比例是3/5，红色三角形所占比例是2/5，也就是多数是属于蓝色正方形类别的，所以根据多数表决规则，认为绿色圆点是属于蓝色正方形。

我们从这个例子可以看出，当k的值不一样时，绿色圆点所属的类别也有可能是不一样的；而且我们这里考虑的是一个二维平面，所以距离定义就是普通的一个欧式距离，如果我们换一种距离定义方式，这里绿色圆点所属的类别可能就会发生变化。

3.1.2 算法

假设我们输入一个训练集 $T=\begin{Bmatrix} (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N}) \end{Bmatrix}$ ，其中 $x_{i}\subseteq R^{n}$ ，类别 $y=\begin{Bmatrix} c_{1},c_{2},...,c_{K} \end{Bmatrix}$ 。如果给定实例x；希望输出：实例x所属类别y

具体算法包含三步：

（1）给出一种距离的度量方式，根据给定的距离度量方法，计算新的实例x与T中每个点的距离.

（2）找出与x最相近的k个点，这k个点都是位于训练集T中。我们将包含这k个点的x的邻域记作 $N_{k}(x)$

（3）在 $N_{k}(x)$ 中根据分类决策规则（如多数表决）决定x的类别y

3.2.1 k近邻法模型

对于k近邻法，它的模型主要是由距离度量、k-值的选择以及分类决策规则决定的，这三个就是构成k近邻算法的三要素。

k近邻法的模型实际上是对训练数据集所对应的特征空间进行了一个划分，每当给定一个新的实例时候，它可以通过最相近的k个邻居决定它所属分类，那么k近邻法就不具有显性的学习过程，所以我们也称这种学习方法为Lazy Learning。下面我们通过一个例子具体看一下k近邻法的模型是什么样子的。

这里的特征空间是二维的，我们考虑k近邻法。训练数据集包含了两类，一个是点所代表的类，一个是叉所代表的类，对于每一个训练示例，我们都画出了它的邻域，也就是划分。当给定一个新的输入实例时，它的类别将由这些划分或者这些小的子空间决定。

那么这一个个小的子空间是怎么划分出来的呐？这就需要考虑k近邻法的三要素了，也就是我们之前说的距离度量、k-值的选择以及分类决策规则，我们具体看一下这三个要素。

3.2.2 三要素

3.2.2.1 距离度量

我们先给出一般的 $L_{p}$ 距离，假如特征空间位 $R^{n}$ ，对于这个特征空间中的任意两个点 $x_{i},x_{j}$ ， $x_{i}=(x_{i}^{(1)},x_{i}^{(2)},...,x_{i}^{(n)})^{T}$ ， $x_{j}=(x_{j}^{(1)},x_{j}^{(2)},...,x_{j}^{(n)})^{T}$ ，则有 $L_{p}(x_{i},x_{j})=(\sum_{I=1}^{n}\left | x_{i}^{(I)}-x_{j}^{(I)} \right |^{p})^{\frac{1}{p}}$ ， $p\geq 1$ 。

我们日常所说的距离其实就是欧氏距离，它所对应的就是p=2的情况。 $L_{2}(x_{i},x_{j})=(\sum_{I=1}^{n}\left | x_{i}^{(I)}-x_{j}^{(I)} \right |^{2})^{\frac{1}{2}}$

当p=1时，就是曼哈顿距离。 $L_{1}(x_{i},x_{j})=\sum_{I=1}^{n}\left | x_{i}^{(I)}-x_{j}^{(I)} \right |$

当p=∞时，我们称之为切比雪夫距离。 $L_{\infty }(x_{i},x_{j})=max\left | x_{i}^{(I)}-x_{j}^{(I)} \right |$

下面我们通过一个例子来说明 $L_{p}$ 距离。假设我们考虑两点之间的距离，也就是点 $x_{i}=(x_{i}^{(1)},x_{i}^{(2)})^{T}$ 到原点 $x_{0}=(0,0)^{T}$ 的距离，我们来看看 $L_{p}(x_{i},x_{0})=1$ 所对应的图形是什么样的。

先看p=2的情况，代入可得 $L_{2}(x_{i},x_{0})=\sqrt{(x_{i}^{(1)}-0)^{2}+(x_{i}^{(2)}-0)^{2}}=1$ 。对于这个式子，恰好就是以原点为中心，半径为1的单位圆；而p=1时， $L_{1}(x_{i},x_{0})=\left | x_{i}^{(1)} \right |+\left | x_{i}^{(2)} \right |=1$ ；当p=∞时， $L_{\infty }(x_{i},x_{j})=max(\left | x_{i}^{(1)} \right |,\left | x_{i}^{(2)} \right |)$ 。这说明不同的p对应着不同的距离的定义。

我们具体看一个例子：

已知二维空间中的三个点： $x_{1}=(1,1)^{T},x_{2}=(5,1)^{T},x_{3}=(4,4)^{T}$ ，求p取不同的值时， $x_{1}$ 的最近邻点。

当p=1时， $L_{1}(x_{1},x_{2})=\left | 1-5 \right |+\left | 1-1 \right |=4$ ， $L_{1}(x_{1},x_{3})=\left | 1-4 \right |+\left | 1-4 \right |=6$ ，此时： $x_{2}$ 是最近邻点。当p=2时， $L_{2}(x_{1},x_{2})=\sqrt{\left | 1-5 \right |^{2}+\left | 1-1 \right |^{2}}=4$ ， $L_{2}(x_{1},x_{3})=\sqrt{\left | 1-4 \right |^{2}+\left | 1-4 \right |^{2}}=4.24$ ，此时： $x_{2}$ 是最近邻点。当p=3时， $L_{3}(x_{1},x_{2})=(\left | 1-5 \right |^{3}+\left | 1-1 \right |^{3})^{\frac{1}{3}}=4$ ， $L_{3}(x_{1},x_{3})=(\left | 1-4 \right |^{3}+\left | 1-4 \right |^{3})^{\frac{1}{3}}=3.78$ ，此时： $x_{3}$ 是最近邻点；当p=4时， $L_{4}(x_{1},x_{2})=(\left | 1-5 \right |^{4}+\left | 1-1 \right |^{4})^{\frac{1}{4}}=4$ ， $L_{4}(x_{1},x_{3})=(\left | 1-4 \right |^{4}+\left | 1-4 \right |^{4})^{\frac{1}{4}}=3.57$ ，此时： $x_{3}$ 是最近邻点。当p＞4时， $L_{p}(x_{1},x_{2})=(\left | 1-5 \right |^{p}+\left | 1-1 \right |^{p})^{\frac{1}{p}}=4$ ， $L_{p}(x_{1},x_{3})=(\left | 1-4 \right |^{p}+\left | 1-4 \right |^{p})^{\frac{1}{p}}=3\times 2^{\frac{1}{p}}< 4$ ，此时： $x_{3}$ 是最近邻点。当p=∞， $L_{p}(x_{1},x_{2})=max\begin{Bmatrix} \left | 1-5 \right |,\left | 1-1 \right | \end{Bmatrix}=4$ ， $L_{p}(x_{1},x_{3})=max\begin{Bmatrix} \left | 1-4 \right |,\left | 1-4 \right | \end{Bmatrix}=3$ ，此时： $x_{3}$ 是最近邻点。

因此，p=1,2时， $x_{2}$ 是最近邻点；p≥3时， $x_{3}$ 是最近邻点。这说明不同的距离度量，它所确定的最近邻点也是不同的。

3.2.2.2 k-值的选择

在之前这个例子中，我们知道当k=3时，绿色圆点是属于红色三角形类别；当p=5时，绿色圆点是属于蓝色正方形类别。

如果我们选择的k值比较小，相当于在一个比较小的邻域内，对于训练数据集中的实例进行预测，此时每一个点都由它最相近的极少的点决定类别，所以近似误差是比较小的，但是如果我们给定一个新的实例，它依然由附近比较少的k个点决定类别，有可能所属类别是错误的，这时候的估计误差其实是相对增大的，敏感性增强，而且模型复杂，容易过拟合。

如果我们选择的k值较大，那么就相当于在一个比较大的邻域里面对训练集的实例进行预测，这时候可以减少学习的估计误差，也就是当我们给定一个新的实例点的时候，这时候判断出差错的可能性会小一些，当然给定一个新的实例，它有可能受到距离它较远的一个训练实例点的影响，所以近似误差有可能增大，不过由于我们选择的k值比较大，这时候模型是比较简单的，如果考虑极端情况k=N（N代表训练数据集中样本的个数），那么这时候每给定一个新的实例点，它的类别都是由这个训练数据集中所包含最多样本的那个类别决定的，这时候的模型过于简单，完全不可行。

在这里，我们有两条建议：k的取值可以通过交叉验证的方法进行选取，k的取值是比较小的，一般低于训练数据集样本量的平方根。

3.2.2.3 分类决策规则

分类决策规则一般采取的是多数表决规则：由多个输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

3.3 kd树

之前我们提到：k近邻法是一种Lazy Learning，也就是不就有显示表达式的一种机器学习方法。那么这种方法如何实现呐？它主要由三个基本要素决定：距离度量、k值的选择、分类决策规则。

假如我们现在给定一个训练数据集，这个训练数据集中包含N个训练样本，那么当给定一个新的实例点时，我们该怎么判断这个新实例点所属的分类呐？这时候，我们可以采取一种简单暴力的方法：分别计算训练数据集中的，每一个样本点与新实例点之间的距离，然后选择距离这个新实例点最近的k个样本点，然后根据多数表决规则判断这个新实例点属于哪个类别。但是这个时候会出现一个问题：如果我们训练数据集中N=10或20，那么每给定一个新实例点，我们计算十次或二十次距离就可以了，可是如果这时候训练数据集中的N非常大，成千上百或者上万上亿，每次给定一个新的实例点，我们就要计算成千上百或者上万上亿的距离，这时候的计算量是非常大的，而且如果训练数据集中的实例点，它所包含的特征非常多，比如说有一千或一万个特征，呢么每次计算距离其实是非常麻烦的，那么计算成千上万个距离就更麻烦了，这时候就没法通过刚才的简单暴力的方法来判断新实例点的类别了，这时候可以采用一种快速搜索的方法，快速搜索方法可以通过构造kd树来实现。

3.3.1 什么是kd树

kd树是一种k维空间中实例点进行储存以便对其进行快速检索的树形结构。

kd树的本质是二叉树，表示对k维空间的一个划分。kd树中的每一个结点对应于一个k维超矩形区域。

kd树中的k表示特征的个数，也就是数据是多少维的；而我们在上面讲的k值的选择，那里的k是指我们选择距离新的实例点最近的k个点。

3.3.2 构造kd树

假如我们输入的训练数据集 $T=\begin{Bmatrix} x_{1},x_{2},...,x_{N} \end{Bmatrix}$ ，其中， $x_{i}=(x_{i}^{(1)},x_{i}^{(2)},...,x_{i}^{(k)})^{T}$ ，我们的目的是输出kd树。

想输出kd树需要以下几个步骤：

（1）构造根节点。我们应该选择哪个特征作为坐标轴进行划分呐？在李航老师《统计学习方法》书中，是选择第一个特征作为坐标轴，可是实际处理的时候，不一定恰好就是第一个特征，有可能是第二个特征，也有可能是第k个特征，那么这个特征怎么选择呐？我们可以通过计算每一个特征上的方差来进行选择。也就是我们现在有N个实例点，每一个实例点都具有k个特征。我们可以计算每一个特征上的N个值得到的方差，那么现在就可以得到k个方差了，选择k个方差里面最大的方差所对应的特征。

现在我们依旧以 $x^{(1)}$ 为坐标轴为例，继续进行算法的说明。选择好坐标轴后，以训练集中的所有数据 $x^{(1)}$ 坐标中的中位数作为切分点（中位数可以通过对数据进行排序计算得出。比如这里选择 $x^{(1)}$ 坐标，可以将第一个特征所对应的N个数值进行排序，选择位于中间位置的数值就是中位数），将超矩形区域切割成两个子区域，并将该切分点作为根节点。

由根节点生出深度为1的左右子节点，左节点对应坐标小于切分点，右节点对应坐标大于切分点。

（2）重复。对深度为j的结点，选择 $x^{(l)}$ 为切分坐标轴，l=j%k+1，以该节点区域中所有实例 $x^{(l)}$ 坐标中的中位数作为切分点，将区域分为两个子区域。

生成深度为j+1的左、右子节点。左节点对应坐标小于切分点，右结点对应坐标大于切分点。

（3）直到两个子区域没有实例时停止。

3.3.3 例题解说

输入：训练集 $\begin{Bmatrix} (2,3),(5,4),(9,6),(4,7),(8,1),(7,2) \end{Bmatrix}$ ；输出：kd树

现在将第一个特征所对应的六个数值进行排序， $x^{(1)}$ 为2，4，5，7，8，9。此时中位数可以选择5或7，这里我们选择7作为中位数，7所对应的实例点具体坐标是(7,2)，因此切分点就是(7,2)这个实例点。我们沿着这个实例点将整个区域进行划分，位于左边的就是小于7的实例点，它们作为左节点，大于7的节点作为右节点，(7,2)这个切分点作为根节点，它所对应的深度为0