近邻法

分类，k近邻

统计学习

发布日期: 2020-08-25

更新日期: 2022-08-20

文章字数: 3.1k

阅读时长: 11 分

阅读次数:

这一部分介绍一下$k$近邻算法，该算法于1968年由Cover和Hart提出，$k$近邻法是一种基本分类与回归方法，本文结构如下:

$k$近邻算法
压缩近邻法
$k$近邻实现：$kd$树
$k$近邻算法

算法流程

$k$近邻的算法非常简单朴素:

给定一个数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的$k$个实例，这$k$个实例中的多数属于某个类，就把该输入实例分为这个类。

$k$近邻的算法思想可以说是非常符合人的直觉，正如俗语所说:”物以类聚，人以群分“，对于分类问题就是，想要看这个样本点是什么类别，只需要看其周围的点都是啥类别就可以了。下面给出一般$k$近邻算法的定义:

$k$近邻法
输入: 训练数据集
$T = \{(x_1,y_1), (x_2,y_2),\dots, (x_N,y_N) \}$
其中，$x_i \in \mathcal{X} \subseteq R^n$为实例的特征向量，$y_i \in \mathcal{Y} = { c_1, c_2, \dots, c_K}$为实例的类别
输出: 实例$x$所属的类$y$
算法流程:

根据给定的距离度量，在训练集中找出与$x$最邻近的$k$个点，涵盖这$k$个点的$x$的邻域记做$N_k(x)$

在$N_k(x)$中根据分类决策规则(如多数表决)决定$x$的类别$y$: $y = \arg \max_{c_j} \sum_{x_i \in N_k(x)} I(y_i = c_j),\quad i = 1,2,\dots,N;j=1,2,\dots,K$

若$k=1$，则此时$k$近邻算法被称为最近邻算法，$k$近邻算法没有显示的学习过程

距离度量

$L_p距离$

使用$k$近邻算法的一个关键问题是需要明确如何定义最近，即选择什么样的距离度量，下面介绍下一般通用的距离度量$L_p$距离：

设特征空间$\mathcal{X}$是$n$维实数向量空间$R^n$,$x_i,x_j \in \mathcal{X}$,$x_i = (x_i^1,x_i^2,\dots,x_i^n),x_j = (x_j^1,x_j^2,\dots,x_j^n)$,则$x_i,x_j$之间的$L_p$距离定义为:
$L_p(x_i,x_j) = (\sum_{i=1}^n |x_i^{(l)} - x_j^{(l)}|^p)^{\frac{1}{p}}$

这一类距离度量都是由范数导出的：

$p = 1$,对应的是由1范数导出的曼哈顿距离
$p = 2$,对应的是由2范数导出的欧几里得距离
$p = \infty$,对应的是由无穷范数导出的切比雪夫距离 $L_\infty(x_i,x_j) = \max_l |x_i^{(l)} - x_j^{(l)}|$
上图显示的是在不同的$p$下距离原点距离为1的点所组成的等高线。

马氏距离

马氏距离是另一种常用的距离度量,首先给出维基百科中关于马氏距离的定义:

马氏距离(Mahalanobis distance)是由印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法，与欧式距离不同的是，它考虑到各种特性之间的联系(如体重与身高是相关联的)，并且是尺度无关的，即马氏距离独立于测量尺度。对于一个均值为$\mu$,协方差矩阵为$\Sigma$的变量，其马氏距离为:
$\sqrt{(x - \mu)^T \Sigma^{-1} (x - \mu)}$
马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为$\Sigma$的随机变量$x$与$y$的差异程度:
$d_M(x,y) = \sqrt{(x - y)^T \Sigma^{-1} (x - y)}$
若协方差矩阵为单位阵，则此时马氏距离便退化为欧式距离，若协方差矩阵为对角阵，此时马氏距离称为正规化的马氏距离:
$d(x,y) = \sqrt{\sum_{i=1}^p \frac{(x_i - y_i)^2}{\sigma_i^2}}$

下面我对马氏距离做一个简要的说明，首先协方差矩阵是一个对称半正定矩阵，可以进行特征值分解:

$\Sigma = U \Lambda U^T$

其中,$U$是酉矩阵，满足$U^T = U^{-1}$,是由矩阵$\Sigma$的特征向量组成(列向量)，而$\Lambda$是一个对角矩阵，对角元素是相应特征向量所对应的特征值。下面我们考虑将协方差矩阵写成下面的形式:

$\begin{aligned} \Sigma &= U \Lambda^{\frac{1}{2}} \Lambda^{\frac{1}{2}} U^T \\ &= U \Lambda^{\frac{1}{2}} (U \Lambda^{\frac{1}{2}})^T \\ &= AA^T \end{aligned}$

其中$A = U \Lambda^{\frac{1}{2}}$,所以马氏距离计算公式中的$\Sigma^{-1}$可以写做:

$\Sigma^{-1} = (A^T)^{-1} A^{-1}$

下面计算样本点$x,y$的马氏距离的平方:

$\begin{aligned} d_M(x,y)^2 &= (x-y)^T \Sigma^{-1} (x - y) \\ &= (x-y)^T (A^T)^{-1} A^{-1} (x-y) \\ &= [A^{-1}x - A^{-1}y]^T[A^{-1}x - A^{-1} y] \end{aligned}$

若记$A^{-1}x = x’,A^{-1}y = y’$,则$d_M(x,y)^2$可以写做：

$d_M(x,y)^2 = || x' - y'||^2$

这也就是说在原始空间计算$x,y$之间的马氏距离相当于计算变换后空间中对应点的欧式距离！最后我们看一下这个变换做了什么事情：

$A^{-1} = \Lambda^{-\frac{1}{2}} U^T$

$U^T$是一个旋转操作，相当于按照主成分方向旋转，消除各个维度之间的联系，而$\Lambda^{-\frac{1}{2}}$是一个scale操作，将变换后的各个维度的点再除以对应分布的标准差以消除由于分布不同带来的距离度量的差异。
最后总结下马氏距离与欧式距离的区别:

马氏距离的计算是建立在总体样本的基础上的，也就是说，如果拿同样的两个样本，放入两个不同的总体当中，最后计算得出的两个样本的马氏距离通常是不相同的。
在计算马氏距离过程中，要求总样本数大于样本的维数，否则协方差矩阵不满秩，无法求逆

马氏距离的优缺点:

优点：它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关，由标准化数据和中心化数据计算出的两点之间的马氏距离相同。马氏距离还可以排除变量之间相关性的干扰
缺点: 夸大了变化微小的变量的作用

$k$值选取

$k$是近邻法中一个重要的超参数，下面首先说明两种极端情况:

$k=1$,此时整个样本空间相当于被分割成了$N$块($N$为训练样本个数)，对于一个新的样本，需要判断它落在那一块，便将它归入对应中心点的类别，此时模型非常复杂。
$k =N$,这也就意味着对于一个新的样本点，直接将它归为整个训练实例中最多的类，此时模型又过于简单。

总结来看，若选择较小的$k$值，对与近邻实例点非常敏感，如果原始数据噪声较大，则会导致错分，$k$值的减小就意味着整体模型变得更加复杂，容易发生过拟合；若$k$值较大，就相当于用较大邻域中的训练数据进行预测，这一定程度上减轻了数据噪声对预测结果的影响，但因为将邻域扩大，导致一些不相似的样本点也在邻域中，这可能会导致分类错误。
下图是使用$k$近邻方法在MNIST数据集上的结果，距离度量选用的是欧几里得距离，图中横坐标表示训练样本规模，纵坐标则是分类错误率，从图中可以看出，当样本数量较少时，选取较小的$k$得到分类效果较好，但随着训练样本数的增加，不同$k$值的分类效果开始接近。
$k$值选取

算法复杂度分析

需要注意的是，$k$近邻法的时间复杂度非常高，假设特征空间维数为$n$，样本集容量为$N$，则每来一个样本，首先要计算该样本点$x$到样本集中各点的距离($O(N*n$)),然后需要对这$N$个距离进行排序($O(N\log N)$),因此对单个样本进行类别划分的复杂度便已经是:

$O(N * n) + O(N \log N)$

对于高维的数据，直接应用$k$近邻法的时间开销是非常大的，因此在应用中往往首先考虑对高维数据进行将维。

压缩近邻法

由于$k$近邻法计算复杂度过高，因此有很多旨在降低近邻法复杂度的算法被提出，压缩近邻法是其中一种，下面给出其算法流程:

压缩近邻法：
Step1: 从Grabbag中选择一个样本放入Store中
Step2: 用store中样本以近邻法测试Grabbag中样本。如果分错，则将该样本放入store
Step3: 重复上面方法直到Grabbag中没有样本再转入到Store中，或Grabbag为空则停止
Step4: 用Store中样本作为近邻法设计集合

压缩近邻法的思想也很简单，原始样本数据集中并不是所有的数据点都对分类有帮助，因此考虑挑选出一些具有代表性的点来组成新的训练集，该集合比之前的集合要小，当新来一个数据时，便用前面挑选出的那些点应用近邻法判断数据点类别。

$kd$树

$kd$树定义

$kd$树是一种对$k$维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。$kd$树是二叉树，表示对$k$维空间的一个划分。构造$kd$树相当于不断地用垂直于坐标轴的超平面将$k$维空间切分，构成一系列的$k$维超矩形区域，$kd$树的每一个节点对应于一个$k$维超矩形区域。

$kd$树构造

$kd$树的构造流程如下:

构造平衡$kd$树
输入: $k$维空间数据集$T = { x_1,x_2,\dots,x_N }$,其中$x_i = (x_i^1,x_i^2,\dots,x_i^k)^T$
输出: $kd$树

开始：构造根节点，根节点对应于包含$T$的$k$维空间的超矩形区域。选择$x^1$为坐标轴，以$T$中所有实例的$x^1$坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域。由根节点生成深度为$1$的左、右子节点：左子节点对应于坐标$x^1$小于切分点的子区域，右子节点对应于坐标$x^1$大于切分点的子区域。将落在切分超平面上的实例点保存在该节点。

重复：对深度为$j$的节点，选择$x^l$为切分的坐标轴，$l = j(mod k) +1$,以该节点的区域中所有实例的$x^l$坐标的中位数为切分点，将对应的超矩形区域再次分割为两个子区域。

直到两个子区域没有实例存在时停止，从而形成$kd$树的区域划分。

$kd$树搜索

下面给出$kd$树的最近邻搜索算法：

kd树搜索算法
输入: 已构造的$kd$树，目标点$x$
输出: $x$的最近邻

在$kd$树中找到包含目标点$x$的叶节点：从根节点出发，递归向下搜索即可

以此叶节点为”当前最近点”

递归地向上回退，在每个节点进行以下操作:

如果该节点保存的实例点比当前最近点距离目标点更近，则以该实例点为当前最近点

检查另一子节点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交，则可能在另一个子节点对应的区域内存在距目标点更近的点，移动到另一个子节点。接着递归地进行最近邻搜索

当回退到跟节点时，搜索结束。最后的”当前最近点”即为$x$的最近邻点。