2.5 K近邻与距离度量

1.物以类聚：KNN到底在做什么

说起来，前面十几章我们一直围着神经网络转，讲的全是怎么拿梯度一遍遍地调参数，把一个模型慢慢训练出来。从这一篇开始，我们换换口味，聊几样经典机器学习里的算法。这些算法没那么多层、没那么深的网络，但思路都特别清楚，面试的时候也常常考到，把它们认全了，对后面理解深度学习本身也有好处。第一个登场的，叫K近邻，英文缩写KNN，全称K-Nearest Neighbors。

KNN的核心思想其实就一句话，物以类聚。给你一个新样本，你去训练集里找和它最像的K个邻居，看这K个邻居里哪一类最多，就把新样本归到哪一类。这里的 $K$ 是一个手动设定的正整数，比如 $K=5$，意思就是看5个最近的邻居，少数服从多数。要判断两个样本像不像，自然得量距离，这件事我们待会专门展开。

我先举个带数字的小例子，大家感受一下。假设我们在做一个相亲匹配的小系统，每个用户用两个特征描述，年龄和月收入，要预测他会不会喜欢某个推荐对象。训练集里有5个人。前3个标记为喜欢（正类），分别是1号（25岁、月收入8000元）、2号（28岁、9500元）、3号（30岁、12000元）。后2个标记为不喜欢（负类），即4号（40岁、20000元）和5号（45岁、25000元）。现在来了一个新用户，32岁，月收入11000元。我们把他和训练集里每个人都比一下距离（这里先用欧氏距离，下一节细讲），发现离他最近的3个邻居是3号、2号、1号，这3个人全都属于喜欢那一类，按多数投票，新用户顺理成章被判为喜欢。这就是KNN做一次预测的全过程，是不是格外直白。

你看，KNN几乎不训练。普通神经网络要花好几个小时甚至几天反复调参，KNN不一样，它的训练阶段就做一件事，把训练数据原样存起来，等预测的时候再一个个去比。所以大家给它起了个外号叫lazy learning（懒惰学习），活儿都拖到最后一刻才做。这脾气其实和我大学室友挺像，平时作业一题不动，到了考试前一晚才开始翻书，KNN大概也是这路数。不过这种懒惰也带个好处，新数据来了直接加进训练集就行，完全不用重新训练，在数据变化频繁的场景里还挺实用。

2.距离怎么量：三种最常见的尺子

KNN里要判断像不像，背后靠的是一把量距离的尺子。尺子不同，量出来的邻居就不一样，分类结果也跟着变。我们挑三种最常用的讲，欧氏距离、曼哈顿距离和余弦相似度。

第一种是欧氏距离（Euclidean distance），它就是我们在1.3 节讲过的L2范数。两个样本 $x$ 和 $y$ 之间的欧氏距离记作 $d(x,y)$，写成公式是：

$$d(x,y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}$$

这里的 $x$ 和 $y$ 是两个样本，$x_i$ 和 $y_i$ 分别是它们在第 $i$ 个特征上的取值，$i$ 是特征的编号，$n$ 是特征的总个数，$\sum$ 是连加符号，意思是从第 $1$ 个特征到第 $n$ 个特征，每一项 $(x_i-y_i)^2$ 全部加起来，最外层的 $\sqrt{}$ 是开根号。算出来的就是初中学的勾股定理那种直线距离。我们拿刚才的相亲例子算一下，新用户是 $(32, 11000)$，3号是 $(30, 12000)$，那 $d=\sqrt{(32-30)^2+(11000-12000)^2}=\sqrt{4+1000000}\approx1000.002$。你看，收入那一项几乎把整个距离都占满了，年龄的差别简直可以忽略。这其实就暴露了KNN一个大麻烦，特征尺度不一致的时候，数值大的特征会一家独大，这点我们第三节专门解决。

第二种是曼哈顿距离（Manhattan distance），它就是1.3 节讲过的L1范数。公式是这样的：

$$d(x,y)=\sum_{i=1}^{n}|x_i-y_i|$$

这里的 $|x_i-y_i|$ 就是差的绝对值。它的几何画面我们在1.3 节里画过，城市格子街区里只能横着走竖着走，没法斜穿。我记得有个在物流公司做事的朋友和我抱怨过，他们调度系统里两辆送货车之间的距离，用的就是曼哈顿距离，因为城市道路基本是横平竖直的网格，鸟飞过去的直线距离并不实用，司机实际要拐的弯一个都省不掉。

第三种比较特别，叫余弦相似度（cosine similarity）。它量的是两个向量方向上的夹角，至于两点在直线距离上隔多远，它是不管的。公式长这样：

$$\cos(x,y)=\frac{x\cdot y}{\lVert x\rVert_2\cdot\lVert y\rVert_2}$$

这里的 $\cos(x,y)$ 是两个向量夹角的余弦值，$x\cdot y$ 是两个向量的点积（对应位置相乘再求和），$\lVert x\rVert_2$ 和 $\lVert y\rVert_2$ 分别是 $x$ 和 $y$ 各自的L2范数，分母那一整项起到了归一化的作用。算出来的值落在 $[-1,1]$ 这个区间里，$-1$ 和 $1$ 是这个区间的两个端点，越接近 $1$ 表示两个向量方向越一致，越接近 $-1$ 表示方向相反。余弦相似度只看方向，不管长度，文本处理里特别爱用它。小明做新闻推荐的时候，每篇文章用一个几千维的词频向量表示，他要找两篇内容相近的报道，比起欧氏距离，余弦相似度更合适，因为两篇文章哪怕长短差很多，只要聊的是同一个话题，向量方向就接近，余弦值就高。

那么这三种尺子该怎么挑呢，给个大概的指引。样本是连续的数值特征，各维度尺度也差不多，欧氏距离最常用。数据本身就落在格子状的空间里，或者想让模型对个别异常值不那么敏感，可以考虑曼哈顿距离。样本是文本、用户行为这种方向比长度更要紧的稀疏向量，余弦相似度几乎是默认选择。

3.K怎么挑，特征尺度怎么调

讲完距离，我们来说两个最影响KNN效果的关键点，一个是K怎么选，一个是特征要不要先缩放。

先说K。$K$ 是邻居个数，它直接决定了模型的脾气。$K$ 太小，比如 $K=1$，模型就是看最近的那一个邻居是哪类，新样本就归哪类。这么做对训练数据特别忠心，可一旦最近那个邻居恰好是个噪声（标错的样本），新样本就被带歪了，这种现象叫过拟合，模型把训练集里的细节和噪声一股脑都背下来了。反过来，$K$ 太大，比如 $K$ 取到整个训练集那么大，模型就一律输出最多的那一类，对所有新样本都给同一个答案，这叫欠拟合，模型太懒，什么细节都不肯学。我们在3.9 节讲优化和正则化的时候，详细聊过过拟合和欠拟合这对老朋友，在KNN里调节K，本质上就是在这两端之间找平衡。

实际怎么做呢，一般用交叉验证。把 $K$ 从 $1$ 试到 $20$ 或者更大，看哪一个 $K$ 在验证集上准确率最高，就选它。工程里 $K$ 通常取一个不太大的奇数，比如 $3$、$5$、$7$，取奇数是为了避免投票时两类打平。我看过一本讲医学统计的书，里面提到医生用KNN做某种肿瘤良恶性判别的时候，$K$ 取 $7$，因为医学数据里噪声标签不少，$K$ 稍微大一点反而更稳，太小的 $K$ 容易被个别误诊的样本带跑。可见K选得太小未必精，选得太大也未必稳，到底选几，还得看数据本身。

再说特征缩放。还记得2.1 节讲线性神经网络的时候，我们专门强调过，不同特征的尺度要是差太多，模型就会偏心数值大的那一项。KNN对这件事比线性模型还要敏感，因为它的距离是把各维度直接平方相加。拿相亲那个例子来说，年龄范围大概是 $20$ 到 $50$，收入范围却是 $5000$ 到 $30000$，两者差了几百倍。直接算欧氏距离，收入几乎包揽了全部贡献，年龄等于白给。

所以用KNN之前，标准化这一步几乎省不掉。最常见的做法和2.1 节里一样，对每一个特征，把整列数据先减去它的均值 $\mu$，再除以它的标准差 $\sigma$，得到新的取值 $x'$。这里的 $\mu$ 是这个特征在所有样本上的平均值，$\sigma$ 是衡量这列数据分散程度的数（标准差），$x'$ 上那个撇号表示这是标准化之后的版本。处理完之后，每个特征都大致围在零附近，量级也接近，距离才不会被某一个大尺度特征独占。说穿了，特征缩放就像考试前先把各科卷面分都换算成百分制，大家站在同一套标准下才好比个高低，这一步功夫在KNN里比在线性回归里还要紧。

4.KNN的代价：存储、预测和维度灾难

KNN虽然简单，代价却不小，我们一件件说。

第一件是存储。因为训练阶段什么都没学，所有训练样本都得原样存在内存里。3.10 节我们说过，神经网络训练完之后，知识都压缩进了参数里，原始数据就可以丢掉了。KNN正好反过来，训练数据就是它的模型，一条都不能扔。数据集一大，内存压力就很可观。

第二件是预测慢。每来一个新样本，KNN都得拿它和训练集里每一个样本比一次距离，再从这些距离里挑出最小的 $K$ 个。训练集要是有 $N$ 个样本，每个样本 $n$ 个特征，一次预测就得做大约 $N\times n$ 次基本运算。这里的 $N$ 是训练样本总数，$n$ 还是前面那个特征总个数。$N$ 一大，预测就慢，用户点一下要等好几秒，体验就很糟。工程上为了提速，会建一些专门的数据结构（比如KD树、球树）来加速找近邻，但这些结构在高维空间里效果又会打折，下面马上就讲。

第三件最阴险，叫维度灾难（curse of dimensionality）。说穿了就是，特征维度一旦变高，任意两个样本之间的距离都差不多，最近的和最远的几乎没区别，邻居这个概念就失效了。打个比方，你在一根数轴上随便撒十个点，它们有的挤有的散，差别挺明显。可你要是在一个100维的空间里撒十个点，它们彼此之间的距离就几乎一样远，谁也不比谁更近。我在某本讲数据挖掘的书里看过一个数字，光是到 $10$ 维左右，这个效应就已经相当明显了，再高上去KNN基本就废了。基因表达数据就是个典型，一份样本动辄几千个基因维度，直接喂给KNN准确率会掉得很厉害，这时候得先用PCA（1.3 节讲过，靠特征值分解把维度压下来）把维度降到几十维，KNN才说得通。也是因为同样的原因，KNN在文本这种动辄几千维的场景里，要么先做降维，要么直接配余弦相似度用，硬上欧氏距离多半要吃亏。

5.两个实在的例子

最后我们用两个例子把上面的概念串起来。

第一个是手写数字识别。经典的数据集叫MNIST，每张图片是 $28\times28$ 的灰度图，拉成一个向量就是 $784$ 维。要做的事是给一张新图，判断它是 $0$ 到 $9$ 里的哪一个数字。用KNN来做，先把所有像素值标准化，距离选欧氏，$K$ 取 $3$ 或 $5$，准确率大概能到 $96\%$ 以上。这个成绩在深度学习横空出世之前，已经是相当拿得出手的水平了。说起来，最早一批做邮政编码自动识别的系统，思路就和KNN加模板匹配很接近，简单可靠。当然，后来CNN一出，准确率直接顶到 $99\%$ 以上，KNN在这类图像任务里就慢慢退到教学和基线的位置上了，但它的思路依然值得学一遍。

第二个是相亲和推荐里常见的找相似的人。假设小明在做一个电影推荐系统，每个用户用一个向量表示，每一维是对某部电影的评分（没看过记为 $0$）。新用户小张进来，看了几部电影打了分，系统要给他推下一部。这时候用余弦相似度，在所有老用户里找出和小张方向最接近的 $K$ 个（比如 $K=20$），然后看这 $K$ 个邻居喜欢而小张还没看过的电影，按评分高低推给他。这种思路在业内有个名字叫协同过滤，KNN就是它最朴素的实现版本。我之前看过一部讲硅谷创业的连续剧，主角团队做的推荐系统，核心思路也是这套找相似用户的办法，简单归简单，实际效果一直不差。金融场景里信用评分也常用类似的逻辑，银行看一个新客户的特征画像，去历史客户里找最像的几个，看他们后来有没有违约，借此给新客户估一个风险等级，本质上也是KNN的影子。

6.小结

我们今天把KNN从头到尾过了一遍。它的核心就是物以类聚，找最近的 $K$ 个邻居投票决定类别，几乎不训练，活儿都留给预测时做。距离的尺子有欧氏、曼哈顿、余弦三种，要根据数据特点挑选。$K$ 太小过拟合，太大欠拟合，得用交叉验证来定。用之前一定要做特征缩放，否则数值大的特征会独占距离。它的代价是存储和预测都贵，还要小心维度灾难。这些要点在面试里被问到的频率相当高，理解透了，既能应付考官，也是后面理解更复杂模型的好底子。

下一章我们换个角度，聊聊朴素贝叶斯。它和KNN的思路完全不同，朴素贝叶斯老老实实算概率，底子就是我们1.4 节讲过的贝叶斯定理。我们到时候见。

练习

Q1. KNN 里 $K$ 取太小（比如 1）和太大分别会犯什么毛病？实际怎么挑 $K$？

$K$ 太小，模型对训练数据特别忠心，最近那个邻居要是恰好是个噪声（标错的样本），新样本就被带歪，这是过拟合。$K$ 太大（比如取到整个训练集那么大），模型就一律输出最多的那一类，对所有新样本给同一个答案，这是欠拟合。实际一般用交叉验证，把 $K$ 从 1 试到 20 看验证集准确率最高的是哪个，工程里常取不太大的奇数（3、5、7），取奇数是为了避免投票时两类打平。

Q2. 相亲例子里，新用户 $(32,11000)$ 和 3 号 $(30,12000)$ 算欧氏距离，$d=\sqrt{(32-30)^2+(11000-12000)^2}\approx1000.002$。这几乎全被收入那一项占满，暴露了 KNN 一个什么大麻烦？怎么补救？

暴露了特征尺度不一致时数值大的特征会一家独大的麻烦——收入范围几千到几万，年龄才几十，直接算欧氏距离收入几乎包揽了全部贡献，年龄等于白给。补救办法是先做标准化，对每个特征减去均值 $\mu$ 再除以标准差 $\sigma$，让每个特征大致围在零附近、量级接近，距离才不会被某一个大尺度特征独占。这一步在 KNN 里比在线性回归里还要紧。

Q3. 为什么用 KNN 之前几乎一定要做特征缩放？另外"维度灾难"是说什么，它对 KNN 影响有多大？

因为 KNN 的距离是把各维度直接平方相加，特征尺度一不齐，数值大的特征就独占距离，必须先缩放（标准化）把大家拉到同一尺度。"维度灾难"是说特征维度一高，任意两个样本之间的距离都差不多，最近的和最远的几乎没区别，邻居这个概念就失效了——光是到 10 维左右效应就已经很明显，再高上去 KNN 基本就废了。这时得先用 PCA 把维度降到几十维，KNN 才说得通。