KNN - K近邻算法 | 慵懒的度量学习

前言

$K$ 近邻（K-Nearest Neighbors，简称KNN）算法是一种基本的机器学习算法，也是一种常见的监督学习方法。它既可以做分类也可以做回归。

$K$ 近邻法不具有显式的学习过程，它是直接预测。它是“惰性学习”(lazy learning)的著名代表。

它实际上利用训练数据集对特征向量空间进行划分，并且作为其分类的"模型"。
这类学习技术在训练阶段仅仅将样本保存起来，训练时间开销为零，等到收到测试样本后再进行处理。
那些在训练阶段就对样本进行学习处理的方法称作“急切学习”(eager learning)。

$K$ 近邻法是一个非参数学习算法，它没有任何参数（ $k$ 是超参数，而不是需要学习的参数）。

$K$ 近邻模型具有非常高的容量，这使得它在训练样本数量较大时能获得较高的精度。

它的缺点有：
1. 计算成本很高。因为需要构建一个 $n\times n$ 的距离矩阵，其计算量为 $O(n^2)$ ，其中 $n$ 为训练样本的数量。当数据集是几十亿个样本时，计算量是不可接受的。
2. 在训练集较小时，泛化能力很差，非常容易陷入过拟合。
3. 无法判断特征的重要性。

算法三要素

$K$ 近邻算法的三要素如下：

$k$ 值选择。
距离度量。
决策规则。

对于固定的训练集，只要这三点确定了，算法的预测方式也就决定了。

$k$ 值的选取

当 $k=1$ 时， $K$ 近邻算法就被称为最近邻算法，此时直接将训练集中与某个样本点 $\bf x$ 最近的点的类别作为 $\bf x$ 的分类。

事实上， $k$ 值的选择会对 $K$ 近邻法的结果产生重大影响：

若 $k$ 值较小，则相当于用较小的邻域中的训练样本进行预测，"学习"的偏差减小。
只有与输入样本较近的训练样本才会对预测起作用，预测结果会对近邻的样本点非常敏感。若近邻的训练样本点刚好是噪声，则预测会出错。即： $k$ 值的减小意味着模型整体变复杂，易发生过拟合。
- 优点：减少"学习"的偏差；
- 缺点：增大"学习"的方差（即波动较大）。
若 $k$ 值较大，则相当于用较大的邻域中的训练样本进行预测。
这时输入样本较远的训练样本也会对预测起作用，使预测偏离预期的结果。
即：值增大意味着模型整体变简单。考虑极端情况：假设 $k=n$ 为样本数，那么无论测试样本是什么，模型都会将其预测为测试样本集中标签最多的那一类。
- 优点：减少"学习"的方差（即波动较小）；
- 缺点：增大"学习"的偏差。

在实际应用中， $k$ 值一般取一个较小的数值。通常采用交叉验证法来选取最优的 $k$ 值。

距离度量

一般情况下，最常用的欧几里得距离都能满足我们的需求。当然也可以利用其他距离作为度量，比如曼哈顿距离等。它们是闵可夫斯基距离取 $p=2,p=1$ 的特例：

$D(x,y) =\sqrt[p]{(|x_1-y_1|)^p + (|x_2-y_2|)^p + \cdots + (|x_n-y_n|)^p} =\sqrt[p]{\sum\limits_{i=1}^{n}(|x_i-y_i|)^p}$

决策规则

分类问题：对新的样本，根据其 $k$ 个最近邻的训练样本的类别，通过多数表决进行分类。
回归问题：对新的样本，根据其 $k$ 个最近邻的训练样本的标签值，将它们的均值作为预测值。

可以证明，分类的多数表决和回归的均值回归决策都等价于经验风险最小化。

算法实现

通过决策规则，我们可以自然地得到 $K$ 近邻的实现算法（以分类问题为例）：

输入训练样本集 $\mathbb D=\{(\mathbf x_1,y_1),...,(\mathbf x_n,y_n)\}$ ；
根据给定的距离度量和给定的测试样本 $\bf x$ ，计算与之距离最近的 $k$ 个训练样本，得到集合 $\mathcal N_k(\mathbf x)$ ；
根据多数表决规则得到 $\bf x$ 的标签： $y=\arg\max\limits_{c_m}\sum_{\mathbf x_i\in\mathcal N_k(\mathbf x)}I(\tilde{y_i}=c_m)$ .

我们最主要解决的问题其实是如何快速得到与测试样本距离最近的训练样本。

一个最容易想到的方法自然就是蛮力法：对每一个训练样本都计算一次与测试样本的距离。
这个方法的确简单直接，在样本量少，样本特征少的时候有效。但是在实际运用中很多时候用不上，因为我们经常碰到样本的特征数有上千以上，样本量有几十万以上，如果我们这要去预测少量的测试集样本，算法的时间效率很成问题。

既然蛮力实现在特征多、样本多的时候很有局限性，那么我们有没有其他的好办法呢？有！
这里我们讲解两种办法，一个是KD树实现，一个是球树实现。

KD树

KD树算法没有一开始就尝试对测试样本分类，而是先对训练集建模，建立的模型就是KD树，建好了模型再对测试集做预测。

所谓的KD树就是 $K$ 个特征维度的树，注意这里的 $K$ 和 KNN 中的 $k$ 的意思是不同—— KNN中的 $k$ 代表最近的 $k$ 个样本，KD 树中的 $K$ 代表样本特征的维数。为了防止混淆，后面我们记特征维数为 $d$ 。

球树

Scikit-Learn实现

在scikit-learn 中，与近邻法这一大类相关的类库都在 sklearn.neighbors模块之中。

KNN分类树：KNeighborsClassifier；
KNN回归树：KNeighborsRegressor；
限定半径最近邻分类树：RadiusNeighborsClassifier；
限定半径最近邻回归树：RadiusNeighborsRegressor；
最近质心分类算法：NearestCentroid。

在这些算法中，KNN分类和回归的类参数完全一样。限定半径最近邻法分类和回归的类的主要参数也和KNN基本一样。

比较特别是的最近质心分类算法，由于它是直接选择最近质心来分类，所以仅有两个参数，距离度量和特征选择距离阈值，比较简单，因此后面就不再专门讲述最近质心分类算法的参数。

另外几个在 sklearn.neighbors模块中，但不是用来做分类回归预测的类也值得关注：

kneighbors_graph类：返回用 KNN 时和每个样本最近的 $k$ 个训练集样本的位置
radius_neighbors_graph 返回用限定半径最近邻法时和每个样本在限定半径内的训练集样本的位置。
NearestNeighbors是个大杂烩，它即可以返回用KNN时和每个样本最近的K个训练集样本的位置，也可以返回用限定半径最近邻法时和每个样本最近的训练集样本的位置，常常用在聚类模型中。