← COMP5541 全部讲次
T01 · 第 2 周

T01 Tutorial 1:从 Python 语法到一行算完所有距离

一份 notebook 的四个练习、三条 NumPy 规则,和 KNN 类里一处不报错的排序 bug。

一句话版

这份 notebook 用三段内容铺一条路:Python 语法、NumPy 的形状规则、最后用两行代码一次算出测试点到全部训练点的距离,写得出那两行就算过关。

先认识这几个词

读之前最好先懂 KNN 的四步(算距离、排序、取前 k 个、投票),见 L01b。

词 全称 / 读法 一句人话
notebook Jupyter 笔记本 代码和说明混排、可以一段段运行的文件
NumPy Numerical Python Python 里做数组和矩阵运算的库
shape 形状 每一维有多长:(4, 3) 是 4 行 3 列,(4,) 是只有一维、长度 4
dtype data type,数据类型 数组里元素的类型,如整数、浮点数、字符串
axis 轴 运算沿哪一维做,做完那一维就消失
broadcasting 广播 形状不同的数组运算时,自动把小的那个拉伸对齐
点积 dot product,np.dot 两个等长向量对应位置相乘再加总,得一个数
argsort 读「arg sort」 不返回排好的值,返回「从小到大排时每个位置该放原来第几个」的下标

题目地图

notebook 发了留空版和带答案版两份,内容相同,留空的练习一共四个。

段 讲什么 留空的练习 主要失分点
Python 基础 运算符、切片、函数、容器、循环、类、读报错 FizzBuzz 分支顺序写反
NumPy 基础 list 与 array、shape、dtype、reshape 无 分不清 (n,) 和 (n, 1)
矩阵运算 切片、sum 与 axis、点积、矩阵乘法 matrix_multiplication 结果矩阵的形状开错
Broadcasting 形状兼容规则、先猜形状再运行 无,但有五个形状要自己判断 从左往右对齐
Final practice 用 NumPy 写 KNN 类 get_distance、get_all_distance 对样本写 for 循环
Bonus 逆矩阵、特征值 无 对非对称矩阵用 eigh

会写代码的人,Python 基础那段扫一眼即可;axis、broadcasting、KNN 类这三节必须亲手跑。

概念卡

1. dtype:一个数组只有一种元素类型

人话定义:它解释为什么数字和字母混放后没法直接算。NumPy 数组像一排同样尺寸的格子,所有元素必须是同一种类型,混着放就全部统一成能装下所有元素的那一种。

例子:np.array([1, 2, 3, 4, 5, 6, 7.0]) 七个数里只有一个浮点,整个数组的 dtype 变成 float64。把数字和字母标签写进同一个数组,全部元素都变成字符串,切出来的「特征」是 '2'、'4' 这样的字符串。KNN 类里 train_data[:, :-1] 后面跟的 .astype(np.float32) 就是在把它们转回数值。

常见误解

以为 list 和 array 只是写法不同 → [1, 2, 3] * 2 把列表重复一遍得到六个元素,np.array([1, 2, 3]) * 2 是逐元素乘得到 [2 4 6]。一个变量是 list 还是 array 决定了 * 和 + 的含义,拿不准就打印 type(x)。

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

2. axis:记被消掉的那一维

人话定义:它决定求和、求均值这类运算沿哪个方向做。axis 写的是哪一维在运算后消失,剩下的维度原样保留。

例子:形状 (4, 3) 的矩阵 [[1,2,3],[2,3,4],[0,0,5],[4,2,6]],对 axis=1 求和消掉长度 3 的那一维,得到 [6, 9, 5, 12],形状 (4,),每行一个数。对 axis=0 求和消掉长度 4 的那一维,得到 [7, 7, 18],形状 (3,),每列一个数。加上 keepdims=True,被消掉的那一维留成长度 1,形状是 (4, 1)。

常见误解

用「行方向、列方向」来记 → 二维时还凑合,到三维就说不清哪个是行。记形状永远成立:写下输入形状,划掉 axis 指的那一维,剩下的就是输出形状。

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

3. broadcasting:从右往左对齐

人话定义:它让形状不同的数组也能直接加减。NumPy 把两个形状靠右对齐,一维一维往左比,每一维要么相等、要么有一边是 1(这一边被拉伸),维数不够的一边在左边补 1。

例子:形状 (3, 4, 5) 的数组,加 (4, 5) 可以,加 (3, 1, 5) 可以,加 (3, 4) 报错——(3, 4) 的最后一维 4 撞上了 5。notebook 在这里的注释是 broadcasting happens backwardly。

常见误解

看到 (3, 4) 和 (3, 4, 5) 前两维一样就以为能加 → 对齐是从最右边开始的,前面对得上没有用。常见的触发场景是 tensor + tensor.sum(-1):求和后少了最后一维,正好落进这个情形,加上 keepdims=True 就好了。

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

4. 矩阵化:一次算完所有距离

人话定义:它去掉 KNN 里最慢的那个循环。做法是把「对每个训练点算一次距离」的循环,换成对整个矩阵做一次减法和一次求范数(范数就是向量的长度)。

例子:训练特征是 (N, d) 的矩阵,测试点是 (d,) 的向量。相减时测试点被自动拉伸到每一行,得到 (N, d) 的差矩阵;再对最后一维求范数,那一维被消掉,剩下 (N,),每个训练点一个距离。切片、broadcasting、axis 三条规则各用一次,没有任何 for。

常见误解

觉得循环和矩阵写法只是风格之分 → 双重 Python 循环比内置实现慢几个数量级。notebook 让人手写一遍矩阵乘法是为了理解定义,实际代码一律用 @ 或 np.dot。

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

逐题拆解

练习一:FizzBuzz

对 1 到 20,能被 3 整除打印 Fizz,能被 5 整除打印 Buzz,都能整除打印 FizzBuzz,否则打印数字本身。考点只有分支顺序:if / elif 链命中第一个为真的分支就结束,所以要先判 number % 15 == 0。如果先判 % 3,15 会在那一支被截走,永远打印不出 FizzBuzz。

练习二:手写矩阵乘法

三个 TODO 是代码里留空待填的地方,对应三件事。先检查形状,前一个矩阵的列数不等于后一个的行数就报错。再按结果形状 (nrow1, ncol2) 开零矩阵。最后双重循环,第 (i, j) 个元素填 np.dot(m1[i, :], m2[:, j])。

测试用的两个矩阵都是 (4, 3)。直接相乘时中间两维是 3 和 4,应当报错;把后一个转置成 (3, 4) 再乘才合法,结果是 (4, 4)。

一步一步看

目标:拿两个 (4, 3) 矩阵先直接相乘、再转置后相乘,看形状对不上为什么报错,对上后第一格怎样算。

青绿框是这一步要盯的那个数或那一格。

  1. 两个 (4, 3) 直接相乘:前一个的列数 3 不等于后一个的行数 4,函数报错。

    第 1 步:两个形状 (4, 3) 的矩阵相乘,前者列数 3 和后者行数 4 被框出,对不上所以报错

  2. 把后一个转置成 (3, 4),中间两维都是 3;结果形状取两头,开 np.zeros((4, 4))。

    第 2 步:后一个矩阵转置成 (3, 4) 后可以相乘,按结果形状开一个 4×4 的零矩阵

  3. 第 (0, 0) 格:matrix1 第 0 行 [1, 2, 3] 点乘转置后第 0 列 [2, 0, 3],1·2 + 2·0 + 3·3 = 11。其余格同理。

    第 3 步:第一个矩阵第 0 行与转置后第 0 列点乘得 11,填进 4×4 结果矩阵左上角那一格

判断题:五个形状能不能和 (3, 4, 5) 相加

notebook 给一个形状 (3, 4, 5) 的 tensor,让你先猜再运行。规则是从最右一维往左对齐,每一对要么相等、要么有一边是 1,维数少的一方左边补 1。

  • v1 形状 (3, 2, 1):最右 5 对 1 可以,中间 4 对 2 不行,报错。
  • v2 形状 (1, 4, 5):三对依次是 5 对 5、4 对 4、3 对 1,结果 (3, 4, 5)。
  • v3 形状 (3, 1, 5):中间 4 对 1 可以扩展,结果 (3, 4, 5)。
  • v4 形状 (3, 4):最右 5 对 4,报错。
  • v5 形状 (4, 5):右边两维都对上,左边补 1,结果 (3, 4, 5)。

v4 和 v5 这一对是考点。(3, 4) 和 (3, 4, 5) 的前两维看上去一样,但对齐从右边开始,前面对得上没有用。

一步一步看

目标:把五个形状逐个和 (3, 4, 5) 靠右对齐,看哪些能拉伸相加,报错的又卡在哪一维。

每帧一个形状,和 (3, 4, 5) 靠右对齐;报错的帧里,青绿框框出从右往左第一处对不上的那一维。

  1. v1 (3, 2, 1):最右 5 对 1 可以,往左 4 对 2 两边都不是 1,报错。

    第 1 步:v1 形状 (3, 2, 1) 与 (3, 4, 5) 靠右对齐,中间一维 4 对 2 被框出,报错

  2. v2 (1, 4, 5):右边两维相等,最左 3 对 1 拉伸,结果 (3, 4, 5)。

    第 2 步:v2 形状 (1, 4, 5) 三维逐一对上,最左的 1 被拉伸,结果 (3, 4, 5)

  3. v3 (3, 1, 5):中间 4 对 1 拉伸,结果 (3, 4, 5)。

    第 3 步:v3 形状 (3, 1, 5) 中间一维是 1 被拉伸成 4,可以相加,结果 (3, 4, 5)

  4. v4 (3, 4):左边补 1 成 (1, 3, 4),最右 5 对 4 就失败,报错。

    第 4 步:v4 形状 (3, 4) 左边补 1 后靠右对齐,最右一维 5 对 4 被框出,报错

  5. v5 (4, 5):左边补 1,右边两维都对上,结果 (3, 4, 5)。

    第 5 步:v5 形状 (4, 5) 左边补 1,右边两维相等,可以相加,结果 (3, 4, 5)

练习三、四:KNN 类里留空的两个方法

def get_distance(self, point1, point2):
    return np.linalg.norm(point1 - point2)

def get_all_distance(self, train_data, test_point):
    train_points = train_data[:, :-1].astype(np.float32)
    differences = train_points - test_point           # (N, d) − (d,) → (N, d)
    return np.linalg.norm(differences, axis=-1)       # 消掉最后一维 → (N,)

get_all_distance 是整份 tutorial 的落点。类里其余方法照着 KNN 的四步走:算距离、排序、取前 k 个、投票。有两处读代码时容易疑惑:get_distance 写了但没被调用,它放在那里是和「一次算完」的写法做对比;fit_and_predict 里没有任何训练步骤,KNN 的训练就是把数据存着,方法名里的 fit 只是沿用通行叫法。

notebook 的四特征示例可以手算核对:训练点 [2,2,2,2](a)、[4,4,4,4](b)、[3,3,3,3](b)、[1,1,1,1](a),测试点 [5,5,5,5],k = 3。到四个点的距离依次是 6、2、4、8,最近三个是 b、b、a,预测 b。

一步一步看

目标:用四个训练点走完求差、求范数、排序、投票,看 KNN 类里留空的两个方法各该算出什么。

表格一列一列往右填,青绿色是这一步新算出来的那一列。

  1. train_points - test_point:(4, 4) − (4,),测试点被拉伸到每一行,差矩阵仍是 (4, 4)。

    第 1 步:四个训练点各减测试点 [5,5,5,5],差这一列依次是全负 3、全负 1、全负 2、全负 4

  2. 对最后一维求范数,每行剩一个距离:6、2、4、8,形状 (4,)。

    第 2 步:差矩阵每一行求范数,得到四个距离 6、2、4、8,表格新增距离一列

  3. 按距离从小到大排,下标顺序是 [1, 2, 0, 3],取前 3 个:距离 2、4、6。

    第 3 步:按距离排出名次,距离 2、4、6 的三个训练点排前三并打勾入选

  4. 三个邻居的标签是 b、b、a,b 两票,预测 b。

    第 4 步:入选的三行用青绿框标出,标签 b 两票、a 一票,预测结果为 b

课件里的坑

  • [课件有误] find_k_neighbors 的排序按字符串排。它先用 np.stack 把距离和标签叠进同一个数组,距离因此全部变成字符串,随后的 argsort 按字典序比较,'10.0' 排在 '2.0' 前面。构造到测试点距离为 2、10、30 的三个训练点,取 k = 1,这段代码返回的是距离 10 的那个点,而且不报任何异常。notebook 自带的两个示例里距离都小于 10,所以看不出来。改法是让数值留在数值数组里排序,标签按同一组下标取:
order = np.argsort(all_distances)[:self.k]
return np.stack([all_distances[order], train_data[order, -1]], -1)
  • [课件有误] 带答案版有三处照着跑会得到和注释相反的结果,以留空版为准:比较那一格把 >= 写成了 <=,成年且有票的例子输出 False;函数返回四个值却只用三个变量接,报 too many values to unpack;矩阵乘法测试那一格调用时加了转置,注释却还写着应当报错。
  • [课件留白] 平票怎么判没有讲。get_prediction 用 np.unique 统计票数再 argmax,np.unique 返回的类别是排好序的,所以平票时胜出的是字典序靠前的标签,与谁更近无关。二分类取奇数 k 可以绕开这件事。
  • [课件留白] np.zeros((3, 4)) 的形状参数是一个 tuple,np.random.rand(1, 2, 3) 的形状参数却直接摊开写。notebook 两种都用了但没有指出差别。
  • [补充] 更省事的做法是特征和标签从一开始就分成两个变量:数值矩阵一个,标签向量一个。这样 astype 和排序问题都不会出现。
  • [补充] broadcasting 形状不兼容时会报错,这是好事;危险的是形状碰巧兼容的时候。方阵减去自己每一行的均值,忘了 keepdims=True 也不报错,只是减到了列上,结果是错的。变式题 2 有算例。

课后 10 分钟:考点复习

这 10 分钟怎么用:先遮住下面的必背清单,把七条默写一遍;再做完整例题,重点看排序那一步;最后做两道变式题,全程先写形状、再写数值。

必背

  1. NumPy 数组全体元素共用一个 dtype,数字和字符串混放会全部变成字符串
  2. axis 指被消掉的那一维:(4, 3) 对 axis=1 求和得 (4,),对 axis=0 求和得 (3,);keepdims=True 把那一维留成 1
  3. broadcasting 从最右一维往左对比,每维要么相等要么有一边是 1,维数不够在左边补 1
  4. 矩阵乘法 (m×n)(n×p) → (m×p),中间两维必须相等;第 (i, j) 个元素是行与列的点积
  5. 一次算完所有距离:(N, d) − (d,) 广播成 (N, d),再 norm(axis=-1) 得 (N,)
  6. 距离和标签叠进同一个数组后距离变成字符串,argsort 按字典序排,‘10.0’ 排在 ‘2.0’ 前面
  7. if / elif 链命中第一个为真的分支就结束,最严格的条件放最前面

完整例题

训练集三个点:(7, 9) 标签 b、(4, 5) 标签 a、(13, 17) 标签 b。测试点 (1, 1),k = 1。分别按正确做法和 notebook 的 find_k_neighbors 求预测结果。

第一步,广播相减。 训练矩阵形状 (3, 2),测试点形状 (2,),右对齐后测试点被拉伸到每一行,差矩阵是 [[6, 8], [3, 4], [12, 16]],形状 (3, 2)。

第二步,对最后一维求范数。 三行分别是 √(36 + 64)、√(9 + 16)、√(144 + 256),得到 [10, 5, 20],形状 (3,)。

第三步,按数值排序。 升序下标是 [1, 0, 2],最近的是距离 5 的 (4, 5),预测 a。

第四步,按 notebook 的写法排序。 距离和标签叠在一起后是 ['10.0', '5.0', '20.0'] 三个字符串。字典序先比第一个字符,'1' < '2' < '5',排成 '10.0'、'20.0'、'5.0'。k = 1 取到的是距离 10 的 (7, 9),预测 b。

真正最近的点被排到了最后。两种做法答案相反,而第二种运行时没有任何提示。

变式题(先自己做)

变式 1 数组 A 的形状是 (2, 3, 4)。(a)它能否与形状 (3, 4)、(2, 3)、(2, 1, 4) 的数组相加?(b)A.sum(axis=1) 的形状是什么?(c)A - A.sum(axis=1) 能否运行?怎么改?

提示

把两个形状靠右对齐写成两行,从最右一列开始逐列比。求和的题先写输入形状,再划掉 axis 指的那一维。

参考答案与自检(非官方评分标准)

(a)(3, 4) 可以,左边补 1 后是 (1, 3, 4),结果 (2, 3, 4)。(2, 3) 报错,最右一维 3 对 4。(2, 1, 4) 可以,中间的 1 被拉伸成 3。

(b)划掉第 1 维,得 (2, 4)。

(c)报错。(2, 3, 4) 对 (2, 4):最右 4 对 4 通过,接着 3 对 2 不通过。改成 A.sum(axis=1, keepdims=True),形状 (2, 1, 4),就能相减。

自检:三问都先写出了形状再下结论,算对。只凭「前两维看着一样」判断的,回到概念卡 3。

变式 2 X = [[1, 2], [3, 6], [5, 10]],形状 (3, 2)。(a)让每一列减去该列的均值,写出代码与结果。(b)让每一行减去该行的均值,X - X.mean(axis=1) 能否运行?正确写法与结果是什么?(c)如果 X 是 (3, 3) 的方阵,(b)里那行不加 keepdims 的代码会怎样?

提示

均值的形状决定它被拉伸到哪个方向:(2,) 靠右对齐贴在列上,(3, 1) 贴在行上。

参考答案与自检(非官方评分标准)

(a)X - X.mean(axis=0)。列均值 [3, 6],形状 (2,),与 (3, 2) 右对齐兼容。结果 [[-2, -4], [0, 0], [2, 4]]。

(b)不能。行均值 [1.5, 4.5, 7.5] 的形状是 (3,),与 (3, 2) 右对齐是 2 对 3,报错。正确写法 X - X.mean(axis=1, keepdims=True),均值形状 (3, 1),结果 [[-0.5, 0.5], [-1.5, 1.5], [-2.5, 2.5]]。

(c)不报错,但结果是错的。(3,) 与 (3, 3) 形状兼容,行均值被当成一行贴到了每一列上。以 [[1,2,3],[4,5,6],[7,8,9]] 为例,行均值 [2, 5, 8],正确结果每行都是 [-1, 0, 1],不加 keepdims 得到的第一行却是 [-1, -3, -5]。

自检:(c)答出「不报错但算错」才算对。这是 broadcasting 最容易出事故的情形。

闪卡自测

7 / 3 的结果是整数还是浮点?整除和取余怎么写?

/ 永远得到浮点。整除是 //,取余是 %。乘方是 **;^ 是按位异或,写 x^2 不报错但结果是错的。

切片 [0:2] 取哪几个元素?[:, :-1] 和 [:, -1] 各取什么?

左闭右开,取下标 0 和 1。[:, :-1] 取除最后一列外的全部(特征),[:, -1] 取最后一列(标签)。

None 在 if 里按假处理,那 None == False 成立吗?

不成立。判断空值用 x is None。

(6,)、(1, 6)、(6, 1) 是同一种形状吗?

三种不同的形状。第一个是一维数组,后两个是二维数组,参与 broadcasting 时行为不同。

点积的结果是什么形状?范数和点积什么关系?

点积是一个数。向量的范数等于它与自己点积的平方根。

两个 (4, 3) 的矩阵能相乘吗?

不能,中间两维是 3 和 4。把后一个转置成 (3, 4) 就能乘,结果 (4, 4)。

tensor + tensor.sum(-1) 为什么报错?

求和后少了最后一维,右对齐时错位。加 keepdims=True 把那一维留成 1。

KNN 类里为什么要 .astype(np.float32)?

数字和字母标签放在同一个数组里,全部变成了字符串,要转回数值才能做减法。

traceback 先看哪里?

最后一行,那里是错误类型和最具体的信息。

np.linalg.eigh 能用在任意方阵上吗?

只用于对称矩阵,它不检查对称性。一般方阵用 np.linalg.eig。

下一步

  1. 把 get_all_distance 那两行不看答案写出来,写不出就回到概念卡 2、3。
  2. 遮住结果,判断 (3, 4, 5) 能否与 (3, 2, 1)、(1, 4, 5)、(3, 1, 5)、(3, 4)、(4, 5) 相加,再运行验证。
  3. 动手改掉 find_k_neighbors 的排序,用距离 2、10、30 那组数据比较改前改后的输出。
  4. 确认会用 X[y == c] 取出某一类的全部样本,再对 axis=0 求均值——后面的编程作业要求不对数据写循环,用的就是这一套。
下一讲 →
L02a L02a 线性回归:定一条直线,用最小二乘一次算出系数

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