← COMP5541 全部讲次
L01b · 第 1 周

L01b KNN 分类:量距离,问最近的几个邻居

从零讲清两点之间的距离怎么算、KNN 分类的四步怎么走、K 取多少会改变答案。

一句话版

KNN 不总结规律。来一个新样本,就在旧样本里找离它最近的 K 个,看它们是什么,照着报。

上一页 L01a 说过,KNN 是课里唯一的非参数模型。这一页讲它怎么做分类。

先认识这几个词

词 全称 / 读法 一句人话
KNN K-Nearest Neighbors,K 近邻 找 K 个最像的老样本,看它们的答案来猜新样本
特征 feature 描述一个样本的数字,比如面积、楼龄
特征空间 feature space 把每个样本的特征当坐标画出来的空间
距离度量 distance metric 算两个样本「差多远」的公式,由使用者自己定
分类 classification 输出一个类别,比如 cat 或 dog
投票 majority vote 数一数 K 个邻居里哪个标签最多,就报哪个
N、K 两个字母 N 是训练样本总数,K 是每次挑出来参考的邻居个数

一个类比:刚搬家,问最近的三户邻居

刚搬进一个小区,想知道楼下哪家早餐店好吃。你不去研究口味规律,直接敲开离你家最近的三户门问。两户说东门那家,一户说西门那家,你就去东门。

这就是 KNN 分类的全部动作。「最近」要先定义:按楼层算,还是按门牌号算?定法不同,问到的人就不同。问几户就是 K。人少了容易碰上口味古怪的,人多了会问到隔壁楼去。

类比在哪里失效:

  1. 你只问三户就完事。最基础的 KNN 要先把全小区每一户的距离都算一遍、排好序,再挑最近的 K 户。
  2. 人能凭常识判断「楼层近」比「门牌号近」更有意义。算法只认你写下的那条距离公式,公式荒唐它也照算。
  3. 邻居的答案带着各自的理由。KNN 拿到的只有标签本身,它不知道邻居为什么这么答。

从零讲起

1. 先补一块:两点之间的距离(补充)

它解决什么问题

KNN 的每一步都绕着「谁离谁近」转。要回答这个问题,得先把「近」变成一个能算的数。

一个样本有几个特征,就可以看成几维空间里的一个点。两个样本像不像,就变成两个点离得远不远。这一节讲两种最常用的量法。

从哪来(补充)

我们熟悉的直线距离叫欧氏距离(Euclidean distance),来自勾股定理。距离公式最早由 Alexis Clairaut 在 1731 年发表,后来 Cauchy 把它推广到三维以上。出处:Wikipedia: Euclidean distance。

另一种叫曼哈顿距离,也叫 taxicab、city block 或 L1 距离。Karl Menger 在 1952 年的一本小册子里给它起了 taxicab 这个名字。出处:Wikipedia: Taxicab geometry。

直觉

从家到超市,鸟飞过去走的是直线,这是欧氏距离。人在棋盘一样的街区里只能横着走、竖着走,走的是横向和纵向路程之和,这是曼哈顿距离。

两种量法都合理,只是回答的问题不一样。KNN 用哪一种,由使用者决定。

一步一步看

目标:用横差 3、纵差 4 的两点分别算欧氏距离和曼哈顿距离,再推到四维,看两种距离怎么算、差在哪。

  1. 在平面上画两个点 P 和 Q。从 P 到 Q,横向差 3,纵向差 4。

    两点距离示意:P 和 Q 之间横向差 3、纵向差 4,青绿斜线标出欧氏距离 5,虚线沿横再沿竖标出曼哈顿距离 3 加 4 等于 7,旁边两个说明框分别写着两种距离的算法

  2. 欧氏距离走斜边。横向差和纵向差是直角三角形的两条直角边,斜边长 √(3² + 4²) = √25 = 5。

  3. 曼哈顿距离沿着格子走,先横后竖,路程是 3 + 4 = 7。

  4. 换到四维,做法不变。下表是点 [5,5,5,5] 和 [0,3,3,3] 逐维相减的结果:

    维度 第 1 维 第 2 维 第 3 维 第 4 维
    差 5 2 2 2
    差的平方 25 4 4 4
  5. 欧氏距离是平方加起来再开根号,√37 约为 6.08。曼哈顿距离是差直接加起来,等于 11。

怎么算

两个点 p = (p₁, p₂, …, pₙ) 和 q = (q₁, q₂, …, qₙ):

欧氏距离 d(p, q) = √((p₁ − q₁)² + (p₂ − q₂)² + … + (pₙ − qₙ)²)

意思是:每一维各自相减,平方,全部加起来,最后开根号。二维时就是勾股定理,斜边² = 直角边² + 直角边²;多一维就多加一项平方。

曼哈顿距离 d(p, q) = |p₁ − q₁| + |p₂ − q₂| + … + |pₙ − qₙ|

意思是:每一维各自相减取绝对值,直接加起来,不平方也不开根号。

课件的图片分类例子里,距离是「逐像素 RGB 绝对误差之和」:每个像素的红、绿、蓝三个值各自相减取绝对值,再全部加起来。按上面的定义,这就是曼哈顿距离(L1),只是维度很多,每个像素占三维。

常见误解

以为 KNN 只能用欧氏距离

课件原话是 Distance Metric; You define it!。欧氏、曼哈顿都可以,图片例子用的就是曼哈顿。定法不同,挑出来的邻居可能不同,答案也可能不同。

开根号可以省掉,所以欧氏距离和平方和是一回事

只比大小、挑最近的点时,省掉开根号不改变排序,可以这么偷懒。要报出距离的具体数值时,不能省。

试一下

点 (1, 1) 和点 (4, 5) 的欧氏距离和曼哈顿距离各是多少?

横向差 3,纵向差 4。欧氏距离 √(9 + 16) = √25 = 5,曼哈顿距离 3 + 4 = 7。

2. KNN 分类的四步

它解决什么问题

手里有一堆带标签的老样本,来了一个没有标签的新样本,怎么给它猜一个标签?KNN 的回答很直接:看离它最近的几个老样本是什么,就猜什么。

它背后的假设是课件原话 The nearest data points in feature space have similar properties:特征空间里离得近的点性质相似。

从哪来(补充)

KNN 的做法由 Evelyn Fix 和 Joseph Hodges 在 1951 年提出,后来 Thomas Cover 做了扩展,他和 Hart 在 1967 年发表了论文 Nearest neighbor pattern classification。出处:Wikipedia: k-nearest neighbors algorithm。

直觉

KNN 没有训练这一步,或者说训练就是把数据存下来。所有功夫都花在预测时:每来一个新样本,都要和全部 N 个老样本比一遍。

所以 KNN 定性是三条:非参数模型、监督学习方法、分类和回归都能做。这一页讲分类,回归在 L01c。

一步一步看

目标:用五个训练点和 K = 3 走完算距离、排序、取近邻、投票四步,看测试点为什么判成 cat。

平面上有 5 个训练点:A、C、E 是 dog,B、D 是 cat。测试点「?」在 (4, 4),取 K = 3。

  1. 算距离:测试点到全部 5 个训练点各算一次欧氏距离。

    第 1 步:坐标平面上一个菱形测试点,五个训练点里圆圈是 cat、方块是 dog,测试点到每个训练点都连了一条灰线;右边表格列出 A dog 3、B cat 1、C dog 5、D cat 2、E dog 4.24

  2. 排序:把 5 个距离从小到大排好。

    第 2 步:右边表格按距离升序重排,依次是 B cat 1、D cat 2、A dog 3、E dog 4.24、C dog 5,第一行标着最近,最后一行标着最远

  3. 取前 K 个:K = 3,取排在最前面的 B、D、A,连同它们的标签。

    第 3 步:一个虚线青绿椭圆圈住测试点和最近的 B、D、A 三个点,E 和 C 变淡;右边表格前三行加粗,下面一条青绿横线标出横线以上是 K 等于 3 个邻居

  4. 投票:三个邻居里 cat 两票、dog 一票,预测 cat。

    第 4 步:测试点的菱形变成青绿色,下面写着 cat;表格底部写 cat 2 票大于 dog 1 票

怎么算

把四步写成一行:

预测标签 = K 个最近邻居的标签里出现次数最多的那个

意思是:先用距离把全部训练点排队,只看排在最前面的 K 个,再在这 K 个里数票。上面的例子里,邻居是 B、D、A,标签是 cat、cat、dog,cat 有 2 票,所以预测 = cat。

预测一次要算多少个距离?训练集有 N 个点,就要算 N 次距离,再排一次序。课件给的朴素实现每次都这么做,所以 KNN 训练开销约等于零,代价全压在预测时。

做回归时,前三步一字不改,只把第 4 步的「数票」换成「取平均」,见 L01c。

常见误解

以为 KNN 有一个训练阶段在学东西

KNN 没有训练出来的参数。它的「模型」就是那份被完整存下来的训练集,所以它是非参数模型。

以为每次预测只用看 K 个点

最后投票只看 K 个,但为了知道哪 K 个最近,第 1 步要和全部 N 个点各算一次距离。课件的朴素实现就是这样。

试一下

同样五个点,把 K 改成 1,预测什么?

只看最近的 B,B 是 cat,预测 cat。

3. K 取多少

它解决什么问题

K 是 KNN 里唯一要人拍板的数。它不从数据里学,由使用者选定,所以叫超参数。K 取不同的值,同一个测试点可能得到不同的答案。

从哪来(补充)

二分类时取奇数 K 可以避免票数打平,这是 KNN 的通行做法。出处:Wikipedia: k-nearest neighbors algorithm。

直觉

问邻居这件事,问一户太冒险,碰上口味怪的就全错。问全小区等于没问,只是在数哪家店的粉丝多,跟你住哪儿没关系了。合适的 K 落在中间。

一步一步看

目标:让 K 从 1 加到 5 重新数票,看偶数 K 会平票,K 取满后测试点在哪里已经不起作用。

还用上一节的五个点,排好序是 B cat 1、D cat 2、A dog 3、E dog 4.24、C dog 5。

  1. K 从 1 往上加,每次多取一个邻居,重新数票:

    K 取到的邻居 票数 预测
    1 B cat 1 cat
    2 B、D cat 2 cat
    3 B、D、A cat 2 : dog 1 cat
    4 B、D、A、E cat 2 : dog 2 平票
    5 全部 cat 2 : dog 3 dog
  2. K = 4 时两类各两票,没法决定。这就是偶数 K 在二分类里的麻烦。

  3. K = 5 时把所有点都取了,预测变成「训练集里哪类多就报哪类」,测试点在哪里已经不起作用。

怎么判断

选 K 时问三句:

  1. 数据里噪声多不多?多的话 K 不能太小,否则一个标错的点就能带偏结果。
  2. K 会不会大到把远处不相关的点也拉进来?K 一直加到 N,就退化成数整体多数。
  3. 是不是二分类?是的话优先取奇数,避开平票。

常见误解

以为偶数 K 一定平票

偶数 K 只是可能平票。上表里 K = 2 时两个邻居都是 cat,没有平票;K = 4 才平。

以为 K 越大越稳

K 大了确实不容易被单个噪声点带偏,但远处的点也会混进来。极端情况 K = N,测试点的位置完全不起作用。

试一下

一个三分类问题,K = 3,三个邻居分别是 cat、dog、bird。会发生什么?

三类各一票,平票。奇数 K 只能保证二分类不平票,类别多了仍可能打平,要另定规则,比如选最近那个邻居的标签。

把它们串起来

KNN 的定性有三条:非参数、监督学习、分类回归都能做。它没有训练出来的参数,整个训练集就是模型。

整条链从一个假设出发:特征空间里离得近的点性质相似。有了这个假设,就必须先定义「近」,所以距离度量是关键步骤,而且只能由使用者来定。欧氏距离走直线,曼哈顿距离沿格子走,课件的图片例子用的是后者。

距离定好以后,四步里前三步全是机械动作:算距离、排序、取前 K 个。第 4 步数票。K 由人选,它决定数谁的票,K 变了答案可能就变。

课件里的坑

  • [课件留白] p.49 的图片例子只给了四张训练图和距离定义,没有具体像素值,这题考的是步骤顺序,不考算数
  • [补充] p.49 的四步是朴素暴力搜索。「每次遍历全部 N 点」是这个实现的性质,实际的库会用 KD-tree、Ball-tree 等索引加速。答题按课件写,但别把它当成算法的固有下限
  • [补充] p.55 的 demo 取 K = 2,二分类出现平票,代码靠排序顺序隐式打破平局,这不是有意设计的规则

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写欧氏距离和曼哈顿距离的公式,再默写 KNN 四步。然后把下面的「完整例题」盖住答案自己算一遍,再做「变式题」。最后回查两个最容易错的地方:以为 K 是从数据里学出来的、以为偶数 K 一定平票。

必背

  1. KNN 是非参数、监督、可做分类也可做回归的方法;核心假设是特征空间中相邻的点性质相似。
  2. KNN 四步:算距离 → 距离升序排序 → 取前 K 个点及其标签 → 汇总;分类取最频繁的标签(投票),回归取 K 个邻居标签的均值或加权均值,只差第 4 步。
  3. 欧氏距离是各维差的平方和再开根号,曼哈顿距离(L1)是各维差的绝对值之和;逐像素 RGB 绝对误差之和就是 L1 距离。
  4. KNN 的关键步骤是距离度量的选择,它由使用者定义(Distance Metric; You define it!),距离决定了谁算邻居。
  5. K 是使用者选定的超参数:K 太小对噪声敏感,K 太大会把远处不相关的点拉进来;二分类取偶数 K 可能平票,所以习惯取奇数。

课件例题

例 1(课件 p.49):用四步给一张测试图分类

题面:训练集是四张带标签的图,分别是 cat、bird、ball、car,共 N = 4 张。来了一张测试图。两张图的距离定义为逐像素 RGB 绝对误差之和,也就是每个像素的红绿蓝三个值各自相减取绝对值,再全部加起来。按 KNN 的四步写出分类过程。

课件的 KNN 分类页:上排四张训练图分别标着 cat、bird、ball、car;中间的距离度量给的例子是 sum of per-pixel rgb absolute error,即逐像素 RGB 绝对误差之和;下方四步依次是 step 1 算测试图与全部 N 张训练图的距离、step 2 距离升序排序、step 3 取前 K 个训练点及其标签、step 4 取最频繁的标签作为预测;右边是待判别的测试图。
图片来源:COMP5541 L01 Intro+KNN, p.49
提示

不用真的算像素。按「算距离、排序、取前 K、投票」四步依次写,每步说清对谁做、做几次。

解答
  1. step 1:用给定的距离公式,算测试图和四张训练图各自的距离,一共算 4 次。
  2. step 2:把这 4 个距离从小到大排序。
  3. step 3:取排在最前面的 K 张训练图,连同它们的标签。
  4. step 4:数这 K 个标签里哪个出现最多,作为预测结果。K = 1 时就是离得最近那张图的标签。
  5. 要点:课件没有给具体的像素值,这题考的是步骤顺序和「每预测一张都要和全部 N 张比一遍」。这个距离是 L1 距离,逐维差的绝对值之和。

例 2(课件 p.55 demo):四点小题,K 取 1、2、3

见下方完整例题。

完整例题

题面:训练集四个点:[2,2,2,2]→cat、[4,4,4,4]→dog、[1,2,1,1]→cat、[0,3,3,3]→dog。测试点 [5,5,5,5],欧氏距离。K = 1、K = 2、K = 3 分别预测什么?

约定:欧氏距离 = 各维差的平方和再开根号;平票时如实写平票,不自己补规则。

解法:

  1. 到 [4,4,4,4]:四维各差 1,√(1+1+1+1) = 2,标签 dog。
  2. 到 [2,2,2,2]:四维各差 3,√(9+9+9+9) = √36 = 6,标签 cat。
  3. 到 [0,3,3,3]:差 5、2、2、2,√(25+4+4+4) = √37 ≈ 6.08,标签 dog。
  4. 到 [1,2,1,1]:差 4、3、4、4,√(16+9+16+16) = √57 ≈ 7.55,标签 cat。
  5. 升序排序:dog(2) < cat(6) < dog(6.08) < cat(7.55)。
  6. K = 1:只看 dog(2),预测 dog。
  7. K = 2:取前两个,dog、cat,票数 1:1 打平。demo 代码靠排序的稳定性隐式选了排在前面的 dog,这不是有意设计的规则。
  8. K = 3:取前三个,dog、cat、dog,票数 2:1,预测 dog。

四个训练点到测试点 5,5,5,5 的欧氏距离升序排开:dog 距离 2、cat 距离 6、dog 距离 6.08、cat 距离 7.55。K 等于 1 只取到 dog,预测 dog;K 等于 2 取到 dog 与 cat,票数 1 比 1 打平;K 等于 3 取到 dog、cat、dog,票数 2 比 1 预测 dog

要点:K = 2 的平票正好暴露偶数 K 在二分类里的问题,所以实践中习惯取奇数 K。

答题格式:先列出四个距离及其标签,再写升序排序,最后对每个 K 写出取到的邻居、票数和预测。

变式题(先自己做)

改编自课件 p.55。同样四个训练点,把测试点换成 [1,1,1,1],仍用欧氏距离。

(1) K = 1、K = 2、K = 3 分别预测什么? (2) K 加到 4 会发生什么?

提示

四个距离重算一遍,排序时留意这次的顺序和例题不一样。第二问不用算,回头看排序里两类各有几个。

判分点与答案(非官方评分标准)

判分点:① 展示四个距离及排序;② 三个 K 值要分别作答;③ 第二问要答出平票,并说出「偶数 K 不一定平票,但 K 加到 N 就退化成整体多数类」。

  1. 到 [1,2,1,1]:差 0、1、0、0,√1 = 1,cat。
  2. 到 [2,2,2,2]:四维各差 1,√4 = 2,cat。
  3. 到 [0,3,3,3]:差 1、2、2、2,√13 ≈ 3.61,dog。
  4. 到 [4,4,4,4]:四维各差 3,√36 = 6,dog。
  5. 升序:cat(1) < cat(2) < dog(3.61) < dog(6)。
  6. K = 1 → cat;K = 2 → cat、cat,预测 cat,这次没有平票;K = 3 → cat、cat、dog,票数 2:1,预测 cat。
  7. K = 4 → cat、cat、dog、dog,2:2 平票。对比例题:偶数 K 只是可能平票;K 一直加到训练集规模 N,投票就退化成「训练集里哪类多选哪类」,测试点的位置完全不起作用了。

闪卡自测

1. KNN 的三条定性是什么?

非参数模型、监督学习方法、分类和回归都能做(p.48)。

2. 写出 KNN 分类的四个步骤。

算距离(和全部 N 个训练点) → 距离升序排序 → 取前 K 个点及其标签 → 投票取最频繁的标签(p.49)。

3. 欧氏距离和曼哈顿距离怎么算?课件图片例子用的是哪一种?

欧氏:各维差的平方和开根号。曼哈顿:各维差的绝对值之和。课件的逐像素 RGB 绝对误差之和是曼哈顿距离,也叫 L1 距离(p.49)。

4. KNN 的核心假设是什么?

特征空间里离得近的点性质相似,课件原话 The nearest data points in feature space have similar properties(p.48)。

5. KNN 的关键步骤是哪一步?为什么是它?

距离度量的选择。排序、取前 K、投票都是机械动作,唯独距离由使用者定义,课件原话是 Distance Metric; You define it!,它决定了谁算邻居,也就决定了全部结果(p.50、p.52)。

6. K 取得过小和过大分别有什么问题?二分类时为什么建议 K 取奇数?

K 太小对噪声敏感,K 太大会把远处不相关的点也拉进来(p.52)。K 取偶数时二分类可能出现票数打平,demo 里 K = 2 就打成了 1:1,只能靠排序顺序隐式决定,所以习惯取奇数(p.55)。

7. KNN 的训练时间和预测时间各是什么量级?和线性回归相比是怎样的对照?

KNN 训练开销约等于零(只是把数据存下来),预测时要和全部 N 个训练点各算一次距离。线性回归正好相反,训练要做优化、预测只是代入公式(p.43、p.49)。

下一讲

下一页 L01c KNN 回归与局限:标签从类别换成数值,第 4 步怎么改;特征尺度为什么必须先统一;KNN 的四问怎么答。

下一讲 →
L01c L01c KNN 回归与局限:取平均、统一尺度、四问

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。