01 / 本课学习路线
本课学习路线
阅读与推演约 112 分钟，练习约 90 分钟，进阶练习另需约 20 分钟
02 / 学习目标与先修自测
学完本课你能做什么，以及开始前需要会什么
两个模型只有一条共同的距离路线：先统一尺度，再算平方距离，再按题目的并列规则选最小。
| 学完后能做的事 | 正文位置 | 检查方式 |
|---|---|---|
| 按顺序说出一轮的两个动作：先全部分配，再统一更新 | 第 05 节 | 自查第 2 条、练习 4 |
| 手动计算分配结果表任意一行的距离并给出归属 | 第 05 节 | 自查第 3 条、练习 1 |
| 解释空簇为什么沿用旧中心、并列为什么选小编号 | 第 05 节 | 自查第 4 条 |
| 说出 fit 只读训练集的原因，并举出数据泄漏的数字例子 | 第 04 节 | 自查第 5 条 |
| 通过 AI001 与 AI011，输出前检查两位小数格式与 -0.00 | 第 06、07 节 | 自查第 1、6 条 |
先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你已完成上一课「浮点精度与稳定 softmax」和模块 2 的「堆与 Top-K 问题」。
| 题号 | 题目 | 补看位置 |
|---|---|---|
| 自测 1 | sum((a - b) ** 2 for a, b in zip([0.3, 0.2], [0.1, 0.9])) 是多少？ | 常用内置函数 |
| 自测 2 | 训练日志 [[0,0],[1000,0],[0,10],[1000,10]]：每列的最小值、最大值各是多少？ | 列表常用操作 |
| 自测 3 | 五个点 x 坐标 0.1、0.2、0.3、0.7、0.9 的均值是多少？ | 数字与运算符 |
| 自测 4 | 用字典给标签计票：votes[y] = votes.get(y, 0) + 1，票数相同要选标签小的，怎么取？ | 计数与并列规则第 04 节 |
| 自测 5 | sorted([(1, 4), (0, 2), (1, 1)]) 得到什么？元组怎么比较？ | 排序与并列规则 |
展开先修自测答案
自测 1：0.04 + 0.49 = 0.53——就是第 04 节 Q 到 C1 的归一化平方距离。
自测 2：最小值 [0, 0]、最大值 [1000, 10]。这就是 fit 保存下来的参数。
自测 3：2.2 / 5 = 0.44——第 05 节第 1 轮更新后 C2 的 x 坐标。
自测 4：min(votes, key=lambda lab: (-votes[lab], lab))——先按票数降序，再按标签升序。AI011 的两级并列规则。
自测 5：[(0, 2), (1, 1), (1, 4)]——先比第 1 项，相同再比第 2 项。AI011 里把 (距离, 样本编号) 排序，距离相同自然取编号小的。
03 / 概念与术语
样本、特征、参数、标签；fit 与 transform；最近中心与并列规则
两个模型都可以拆成同样两个动作：先从数据里得出参数（fit），再用这组参数对新数据给出结论。
| 术语 | 含义 | 代码里的位置 |
|---|---|---|
| fit / transform | fit 只用训练集算参数（每列最小值最大值）；transform 用已保存的参数转换任意一行，超出范围不截断 | fit_minmax / transform |
| 平方欧氏距离 | 逐列差的平方和，省掉开方不改变谁最小 | squared_distance |
| 最近中心 / argmin | 距离最小的中心的下标；相差不超过 1e-9 视作并列，保留先遇到的小编号 | if dist < best_dist - EPS |
| 分配 / 更新 | 一轮的两个动作：先把全部点分配完，再用各簇均值统一更新中心 | assign / update |
| 空簇 | 某轮没有点分到的中心；AI001 规定沿用旧中心 | if not g: new.append(old[c]) |
| KNN 投票 | 取最近 k 条训练样本按标签计票；距离并列取样本编号小、票数并列取类别编号小 | order.sort()、min(votes, key=...) |
补充学习（选学）机器学习的四个基本词：样本、特征、参数、标签约 6 分钟四个词在本课的网关日志里分别指什么，以及监督学习与无监督学习的分界
本课出现的两个模型，都可以拆成同样两个动作：先从数据里得出参数（fit），再用这组参数对新数据给出结论（predict，归一化这一步对应的动作叫 transform）。K-Means 的 fit 产物是 k 个中心，结论是一个中心编号；KNN 的 fit 只是把训练数据保存下来，结论是一个类别编号。四个基本词就落在这两个动作上。
| 词 | 含义 | 在本课里指什么 |
|---|---|---|
| 样本（sample） | 数据表的一行 | 一条网关请求，例如 (300, 2) |
| 特征（feature） | 数据表的一列 | 词元数这一列、等待秒数这一列 |
| 参数（parameter） | fit 从训练数据里得出、后续要保存下来的量 | 归一化用的每列最小值与最大值；K-Means 的 k 个中心 |
| 标签（label） | 希望模型给出的答案 | AI011 里每条训练样本的类别编号；AI001 的聚类没有标签 |
区分参数与标签是读题的关键：参数由训练数据算出来，标签是数据本身自带的答案。AI001 的输入里没有标签，AI011 的输入里每条训练样本都带一个类别编号。
数据自带标签的任务叫监督学习：判断一封邮件是否为垃圾邮件属于分类，预测一套房子的价格属于回归。数据没有标签、需要自己从数据里找出结构的任务叫无监督学习，把请求日志分成几种画像就是聚类。本课两道必做题正好各占一边：AI001 的 K-Means 是无监督，输入只有坐标；AI011 的 KNN 是监督，每条训练样本都带类别。两者共用同一条距离路线，差别只在比较对象是中心还是全部训练样本。
补充学习（选学）训练集、验证集与测试集的用途约 6 分钟三块数据各自负责什么，以及混用它们在数字上的后果
一份数据通常切成三块，各自承担不同的职责，不能互相替代。
| 数据块 | 负责什么 | 使用次数 |
|---|---|---|
| 训练集 | 算出参数：归一化的每列最小值与最大值、模型的权重与中心 | 反复使用 |
| 验证集 | 比较不同方案：Min-Max 还是标准分数、k 取几、阈值定在哪；参数本身仍由训练集算出 | 在调整方案的过程中多次使用 |
| 测试集 | 报告最终结果 | 最后只用一次 |
验证集和测试集都只走 transform，用训练集保存下来的参数转换，自己不参与 fit。若用验证集反复挑选方案，最终结果仍应以测试集为准。
打分要用没有参与 fit 的数据，原因很直接：参数是从训练集算出来的，再拿训练集自己打分，反映的只是模型在已见过的数据上的拟合程度，通常偏乐观，说明不了它对没见过的请求是否同样有效。验证集和测试集的作用就是模拟「没见过」。
混用它们在数字上是这样的：把新请求 Q=(1200, 12) 一起放进 fit，两列的最大值从 [1000, 10] 变成 [1200, 12]，C1 从 (0.1, 0.9) 挪到 (0.083, 0.75)，C2 从 (0.7, 0.1) 挪到 (0.583, 0.083)，Q 自己落在 (1, 1)——被判断的那个点改写了整个坐标系。在实际推理中，这意味着网关每来一条请求都重算一次最小值和最大值，同一条请求在不同批次里会得到不同坐标，结果无法复现。
落到代码上只有一条规则：fit 只接收训练集；验证集、测试集和线上新请求一律只走 transform。
补充学习（选学）Min-Max 之外：标准分数（z-score）与异常值约 6 分钟异常值如何缩小其他样本归一化后差异的数字例子，以及 z-score 的计算过程
Min-Max 的范围由两端极值决定，一个极端值就能把整列其他样本的差异缩小到几乎不可见：给训练日志加一条 (100000, 0)，token 列的距离贡献只剩 4e-6 和 1.6e-5 的量级——相对贡献几乎可以忽略，排序完全由等待列决定。
z-score（按均值和标准差标准化）的计算过程（原四行训练集）
token 列：均值 500，标准差 500；等待列：均值 5，标准差 5 Q -> (-0.4, -0.6) C1 -> (-0.8, 0.8) C2 -> (0.4, -0.8) d(Q,C1) = 0.16 + 1.96 = 2.12 d(Q,C2) = 0.64 + 0.04 = 0.68 -> 仍选 C2
z-score 用均值和标准差，单个极端值的影响被摊薄——但均值和标准差本身仍受离群点影响，只是影响程度通常小于直接使用最大值和最小值。怎么选：值域天然有界用 Min-Max；分布大致对称用 z-score；离群点较多时考虑稳健缩放（RobustScaler）——它用中位数和四分位距缩放。三者的 fit / transform 结构完全一样，换的只是参数的算法。
补充学习（选学）省平方根为什么不影响结果约 4 分钟单调性论证 + 曼哈顿距离对照
开方是单调递增的：a < b 当且仅当 √a < √b。选最近中心只关心谁最小，开不开方最小的都是同一个中心——省掉开方少算一步、还避免精度损失。真要报告「距离是多少」再开方。
换距离也行：曼哈顿距离逐列取绝对差再相加，Min-Max 后 Q 到 C1 是 0.2 + 0.7 = 0.9、到 C2 是 0.4 + 0.1 = 0.5，本例结论相同。它对单列大偏差更宽容，平方距离会放大大偏差——题目用哪个就写哪个。
04 / 尺度与距离
先统一尺度，再谈距离；fit 只读训练集
训练日志四行：(0,0)、(1000,0)、(0,10)、(1000,10)；候选中心 C1=(100,9)、C2=(700,1)，新请求 Q=(300,2)。
同一条请求，两种尺度，两个结论
原始尺度: d(Q,C1) = 200² + (-7)² = 40049
d(Q,C2) = (-400)² + 1² = 160001 -> 选 C1,token 列主导距离
Min-Max 后(除以 1000 和 10):
Q=(0.3,0.2) C1=(0.1,0.9) C2=(0.7,0.1)
d(Q,C1) = 0.04 + 0.49 = 0.53
d(Q,C2) = 0.16 + 0.01 = 0.17 -> 选 C2,结论翻转尺度与距离的四个参考函数
PythonEPS = 1e-9
def fit_minmax(train):
# 只用训练集算参数:逐列的最小值与最大值
d = len(train[0])
mins = train[0][:]
maxs = train[0][:]
for row in train[1:]:
for j in range(d):
mins[j] = min(mins[j], row[j])
maxs[j] = max(maxs[j], row[j])
return mins, maxs
def transform(row, mins, maxs):
# 用已保存的参数转换任意一行;常数列(上下界相等)统一归 0
scaled = []
for x, lo, hi in zip(row, mins, maxs):
scaled.append(0.0 if hi == lo else (x - lo) / (hi - lo))
return scaled
def squared_distance(a, b):
# 省掉开方:平方距离与欧氏距离的大小顺序一致
return sum((x - y) ** 2 for x, y in zip(a, b))
def predict_one(query, centers, mins, maxs):
# 查询点同样只走 transform,不参与 fit
scaled_query = transform(query, mins, maxs)
best_id = -1
best_dist = float("inf")
for center_id, center in enumerate(centers, start=1):
dist = squared_distance(scaled_query, transform(center, mins, maxs))
if dist < best_dist - EPS: # EPS 内视作并列,保留先遇到的小编号
best_dist = dist
best_id = center_id
return best_id
train = [[0, 0], [1000, 0], [0, 10], [1000, 10]]
mins, maxs = fit_minmax(train)
assert (mins, maxs) == ([0, 0], [1000, 10])
assert transform([300, 2], mins, maxs) == [0.3, 0.2]
assert abs(squared_distance([0.3, 0.2], [0.1, 0.9]) - 0.53) < 1e-9
assert abs(squared_distance([0.3, 0.2], [0.7, 0.1]) - 0.17) < 1e-9
assert predict_one([300, 2], [[100, 9], [700, 1]], mins, maxs) == 2
assert transform([5, 3], *fit_minmax([[5, 0], [5, 10]])) == [0.0, 0.3] # 常数列归 0
assert transform([1200, 12], mins, maxs) == [1.2, 1.2] # 超出训练范围不截断
assert predict_one([0, 0], [[0, 0], [0, 0]], mins, maxs) == 1 # 并列取小编号四个函数带九条断言：参数只由训练集算出、常数列归 0、超出训练范围不截断（1200 → 1.2）、并列取小编号。写 AI001 时不要自行加 Min-Max——题目没要求归一化就按原始坐标算。
数据泄漏的表现
把 Q=(1200,12) 放进 fit，每列最大值（maxs）从 [1000,10] 变成 [1200,12]：C1、C2、Q 的坐标全部跟着变——被判断的点改写了坐标系。在实际推理中，这会使同一条请求因批次数据不同而得到不同坐标，结果无法复现。因此归一化参数应只由训练集计算（fit）；验证集、测试集和新请求都使用已保存的参数转换（transform）。
05 / 分配与更新
一轮只有两个动作：六个点、两个中心的两轮逐格表
归一化后的六条请求 P1..P6 与初始中心 C1=(0.1,0.9)、C2=(0.7,0.1)。
| 点 | 到 C1 | 到 C2 | 归属 |
|---|---|---|---|
| P1 (0.1, 0.1) | 0.64 | 0.36 | C2 |
| P2 (0.2, 0.3) | 0.37 | 0.29 | C2 |
| P3 (0.3, 0.2) | 0.53 | 0.17 | C2 |
| P4 (0.7, 0.7) | 0.40 | 0.36 | C2 |
| P5 (0.8, 0.9) | 0.49 | 0.65 | C1 |
| P6 (0.9, 0.8) | 0.65 | 0.53 | C2 |
初始中心偏离样本分布，第一轮分配就不均：C1 只分配到 P5。不必急着修正——更新步会在迭代里修正；但 K-Means 可能停在局部最优，工程上要多次初始化。
| 轮 | C1 | C2 | 簇内平方和 |
|---|---|---|---|
| 起点 | (0.10, 0.90) | (0.70, 0.10) | 2.200 |
| 第 1 轮更新后 | (0.80, 0.90) | (0.44, 0.42) | 0.428 |
| 第 2 轮更新后 | (0.80, 0.80) | (0.20, 0.20) | 0.080 |
| 第 3 轮 | 不再移动 | 不再移动 | 分配不变，收敛 |
第 1 轮后 C2 = ((0.1+0.2+0.3+0.7+0.9)/5, (0.1+0.3+0.2+0.7+0.8)/5) = (0.44, 0.42)。表里的簇内平方和都是「拿这一行的中心把六个点重新分配一遍」之后算的。如果不重新分配、只把第 1 轮的旧分组配上新中心，得到的是 0.860——那是更新步刚做完的中间值；重新分配后 P4、P6 归入 C1，簇内平方和才降到 0.428。第 2 轮分配得到的分组已是最终分组：均值落到 (0.80,0.80) 和 (0.20,0.20)。
K-Means 主循环
Pythondef run_kmeans(points, centers, t):
k = len(centers)
d = len(centers[0])
for _ in range(t):
groups = [[] for _ in range(k)]
for p in points: # ① 先全部分配
groups[assign_one(p, centers)].append(p)
new_centers = []
for cid in range(k): # ② 再统一更新
g = groups[cid]
if not g:
new_centers.append(centers[cid]) # 空簇沿用旧中心
else:
new_centers.append(
[sum(p[j] for p in g) / len(g) for j in range(d)]
)
centers = new_centers
return centersassign_one(p, centers) 与第 04 节 predict_one 用同一套平方距离和并列规则，但有两处不同：不做归一化（AI001 用原始坐标）；返回 0 基下标（enumerate(centers) 不加 start=1），否则 groups[...] 会越界——写法与第 07 节 assign 对单个点的处理相同。每轮先把 n 个点全部分配完，再统一更新 k 个中心。
分配与更新的顺序
一轮内先把 n 个点全部分配完，再统一更新 k 个中心。边分配边移动中心，后面的点看到的中心已经变了，结果和题目定义对不上——题库用例 5 2 3 2 / 0 0 / 0 0 / 10 10 / … 期望 0.00 0.00 / 0.00 0.00 / 10.00 10.00，边分配边更新的程序输出 0.50 0.50 / -1.00 -1.00 / 10.00 10.00（第 08 节错误表）。
补充学习（选学）为什么用均值当新中心约 5 分钟一维两点的小证明：平方和在均值处最小
一维就能看清：簇里有点 1 和 5，中心放在 x，簇内平方和 (x−1)² + (x−5)²。代几个值：x=2 时 10，x=3 时 8，x=4 时 10——最小值在 x=3，恰是均值。展开是 2x² − 12x + 26，抛物线最低点 x = 12/4 = 3。推广到 n 个点、逐维成立，所以多维最优中心就是逐维均值。
这也是簇内平方和不升的另一半根据：分配步每个点只会换到更近的中心，更新步均值又是让本簇平方和最小的位置——两步都不升。
补充学习（选学）空簇的三种处理约 4 分钟沿用旧中心、删簇、重新播种的取舍
某轮里一个中心一个点都没分配到，均值就没法算。三种常见处理：沿用旧中心（这一轮原地不动）；删掉这个簇（k 变小）；重新播种（把离所有中心最远的点设为新中心）。AI001 明确规定「沿用旧中心」——结果确定、可复现。这是题目约定而不是数学定理，实现时应遵循题目规则。
补充学习（选学）初始中心和 k 怎么选约 5 分钟初始中心的影响、k-means++ 初始化方法的思路、AI024 的确定性初始化
K-Means 只保证簇内平方和不升，不保证全局最优——初始中心不同可能收敛到不同结果。工程里多跑几次取最小的簇内平方和，或用改进的初始化方法（k-means++）挑初始中心：先随机选第一个中心，之后每个点按「到最近已选中心的平方距离」加权随机抽样，离得远的点更容易被抽中。
本课的进阶练习 AI024 使用确定性初始化：直接取 D(x) 最大的点、并列取编号最小——它不是标准的 k-means++，但用于练习「最远点优先」的选择过程。k 本身也是选出来的：k=1..6 各跑一遍看簇内平方和的拐点（肘部法）；AI001 里 k 由题目给定。
06 / 题面示例逐步
AI001 两轮、AI011 两个查询
AI001「多维样本聚类器」：第一行 n d k t，接下来 k 行初始中心、再 n 行样本；每轮按平方距离分配（并列取小编号），再用簇内均值更新（空簇沿用旧中心）；t 轮后输出 k 行、每行 d 个两位小数（绝对值小于 0.0005 输出 0.00）。题面示例：4 2 2 2 / 0 0 / 8 8 / 1 1 / 2 2 / 8 9 / 9 8 → 1.50 1.50 / 8.50 8.50；t = 0 直接输出初始中心。
| 轮 | 分配（点 → 中心编号） | 更新后的中心 |
|---|---|---|
| 1 | (1,1)→1、(2,2)→1、(8,9)→2、(9,8)→2 | (1.50, 1.50)、(8.50, 8.50) |
| 2 | 分配不变 | 不变 |
输出 1.50 1.50 / 8.50 8.50。题目的中心编号从 1 开始，代码里数组下标从 0 开始，输出时不需要编号（只输出坐标）；AI011 的并列规则里「样本编号」是输入顺序、从 0 开始。
AI011「KNN 分类器」：第一行 n d k m，接下来 n 行「d 个整数特征 + 标签」，再 m 行查询；对每个查询取平方距离最小的 k 个样本（距离相同取样本编号小的）按标签投票（票数相同取类别编号小的），输出 m 行类别。题面示例：5 2 3 2 / 0 0 0 / 1 0 0 / 5 5 1 / 6 5 1 / 0 1 0 / 0 0 / 5 4 → 0 / 1。
| 查询 | (距离, 编号) 升序 | 最近 3 条的标签 | 投票 | 输出 |
|---|---|---|---|---|
| (0, 0) | (0,0) (1,1) (1,4) (50,2) (61,3) | 0、0、0 | 0 票 3 | 0 |
| (5, 4) | (1,2) (2,3) (32,1) (34,4) (41,0) | 1、1、0 | 1 票 2、0 票 1 | 1 |
第一个查询里样本 1 与样本 4 距离都是 1，按编号小的在前——k = 3 时两者都进了近邻，不影响结果；题库用例 3 1 1 1 / -2 5 / 2 9 / 4 9 / 0 才是它起作用的地方：到 −2 与 2 距离都是 4，取 0 号，类别 5。票数并列：4 1 4 1 / 0 4 / 2 1 / 10 4 / 12 1 / 6 两种标签各 2 票，取类别 1。
07 / 从两个函数到程序
参考实现与三份完整程序，每一步落在哪几行
先分别用断言验证分配函数和更新函数，再组合完成 AI001 的读入、迭代与输出；AI011 用同一套距离和并列规则。
| 步骤 | AI001 | AI011 | AI024 |
|---|---|---|---|
| 读入 | n d k t，先 k 行中心再 n 行样本 | n d k m，n 行特征+标签，m 行查询 | n d k，n 行样本 |
| 距离 | 平方欧氏（浮点） | 平方欧氏（整数，精确） | 平方欧氏（整数） |
| 并列 | dist < best - 1e-9 才更新 | (dist, idx) 排序；(-票数, 标签) 取最小 | D[i] > D[best] 才更新 |
| 主循环 | t 轮：全部分配 → 统一更新（空簇沿用） | 每个查询排序取前 k 投票 | 选 D 最大者 → 增量更新 D |
| 输出 | k 行两位小数，|v| < 0.0005 → 0.00 | m 行类别 | 一行 k 个编号 |
展开参考实现：assign 与 update（自带断言；先自己写完再对照）
assign 与 update 的参考实现（自带断言）
PythonEPS = 1e-9
def assign(points, centers):
# 返回每个点的中心下标（0 基）：平方距离最小；相差不超过 EPS 视作并列，保留先遇到的小编号
out = []
for p in points:
best, best_dist = 0, sum((a - b) ** 2 for a, b in zip(p, centers[0]))
for c in range(1, len(centers)):
dist = sum((a - b) ** 2 for a, b in zip(p, centers[c]))
if dist < best_dist - EPS:
best, best_dist = c, dist
out.append(best)
return out
def update(groups, old):
# groups[c] 是分到中心 c 的点；逐维求均值；空簇沿用旧中心
new = []
for c, g in enumerate(groups):
if not g:
new.append(old[c])
else:
new.append([sum(p[j] for p in g) / len(g) for j in range(len(old[c]))])
return new
CENTERS = [[0.1, 0.9], [0.7, 0.1]]
POINTS = [[0.1, 0.1], [0.2, 0.3], [0.3, 0.2], [0.7, 0.7], [0.8, 0.9], [0.9, 0.8]]
assert assign(POINTS, CENTERS) == [1, 1, 1, 1, 0, 1] # 第 05 节第 1 轮分配表
assert assign([[0.5, 0.5]], [[0.4, 0.5], [0.6, 0.5]]) == [0] # 等距并列取小编号
groups = [[[0.8, 0.9]], [[0.1, 0.1], [0.2, 0.3], [0.3, 0.2], [0.7, 0.7], [0.9, 0.8]]]
got = update(groups, CENTERS)
assert [[round(v, 9) for v in c] for c in got] == [[0.8, 0.9], [0.44, 0.42]] # 第 1 轮更新后
assert update([[], [[2.0, 2.0]]], [[1.0, 1.0], [9.0, 9.0]]) == [[1.0, 1.0], [2.0, 2.0]] # 空簇沿用旧中心
# 再跑一轮：分配 → 更新，得到第 2 轮的中心 (0.80, 0.80) 与 (0.20, 0.20)
a = assign(POINTS, got)
g2 = [[p for p, x in zip(POINTS, a) if x == c] for c in range(2)]
assert [[round(v, 9) for v in c] for c in update(g2, got)] == [[0.8, 0.8], [0.2, 0.2]]断言覆盖第 05 节第 1 轮分配、等距并列、第 1 轮更新、空簇、以及再跑一轮得到 (0.80, 0.80) 与 (0.20, 0.20)。
展开完整参考程序 1：AI001 多维样本聚类器
完整程序：AI001（标准输入 → 标准输出）
Pythonimport sys
EPS = 1e-9
data = sys.stdin.read().split()
pos = 0
def take():
global pos
pos += 1
return int(data[pos - 1])
n, d, k, t = take(), take(), take(), take()
centers = [[float(take()) for _ in range(d)] for _ in range(k)] # 先 k 行初始中心
points = [[float(take()) for _ in range(d)] for _ in range(n)] # 再 n 行样本
for _ in range(t):
groups = [[] for _ in range(k)]
for p in points: # ① 先把全部样本分配完（中心此时不动）
best, best_dist = 0, sum((p[j] - centers[0][j]) ** 2 for j in range(d))
for c in range(1, k):
dist = sum((p[j] - centers[c][j]) ** 2 for j in range(d))
if dist < best_dist - EPS: # 1e-9 内视作并列：保留先遇到的小编号
best, best_dist = c, dist
groups[best].append(p)
new_centers = []
for c in range(k): # ② 再统一更新
g = groups[c]
if not g:
new_centers.append(centers[c]) # 空簇：沿用旧中心
else:
new_centers.append([sum(p[j] for p in g) / len(g) for j in range(d)])
centers = new_centers
out = []
for row in centers:
vals = []
for v in row:
if abs(v) < 0.0005: # 避免 -0.00
v = 0.0
vals.append(f"{v:.2f}")
out.append(" ".join(vals))
print("\n".join(out))输出前把绝对值小于 0.0005 的值改成 0.0——AI001 的整数坐标下这一步是防御性的，但 f"{-0.0004:.2f}" 确实会打出 -0.00。用题面示例和 t = 0 的输入核对；n = 2000、k = 20、t = 20 的规模在时限内。
展开完整参考程序 2：AI011 KNN 分类器
完整程序：AI011（标准输入 → 标准输出）
Pythonimport sys
data = sys.stdin.read().split()
pos = 0
def take():
global pos
pos += 1
return int(data[pos - 1])
n, d, k, m = take(), take(), take(), take()
xs, ys = [], []
for _ in range(n):
xs.append([take() for _ in range(d)]) # d 个整数特征
ys.append(take()) # 标签
out = []
for _ in range(m):
q = [take() for _ in range(d)]
order = []
for idx in range(n): # 到每个训练样本的平方距离（整数，精确）
dist = sum((xs[idx][j] - q[j]) ** 2 for j in range(d))
order.append((dist, idx)) # 距离相同时样本编号小的在前
order.sort()
votes = {}
for dist, idx in order[:k]: # 最近 k 条投票
votes[ys[idx]] = votes.get(ys[idx], 0) + 1
best_label = min(votes, key=lambda lab: (-votes[lab], lab)) # 票多者胜；票数相同取类别编号小的
out.append(str(best_label))
print("\n".join(out))整数平方距离没有浮点误差，并列比较可以直接用 ==。用题面示例 → 0 / 1 和第 06 节的两组并列用例核对。
展开完整参考程序 3：AI024 K-Means++ 确定性初始化（进阶练习）
完整程序：AI024（标准输入 → 标准输出）
Pythonimport sys
data = sys.stdin.read().split()
n, d, k = int(data[0]), int(data[1]), int(data[2])
pts = [[int(data[3 + i * d + j]) for j in range(d)] for i in range(n)]
chosen = [0] # 第 1 个中心固定为 0 号
D = [sum((pts[i][j] - pts[0][j]) ** 2 for j in range(d)) for i in range(n)] # D(x) = 到已选中心集的最小平方距离
is_center = [False] * n
is_center[0] = True
while len(chosen) < k:
best = -1
for i in range(n): # 选 D(x) 最大的未选样本；并列取编号最小（严格大于才更新）
if not is_center[i] and (best == -1 or D[i] > D[best]):
best = i
chosen.append(best)
is_center[best] = True
for i in range(n): # 增量更新：只和新中心比一次
dist = sum((pts[i][j] - pts[best][j]) ** 2 for j in range(d))
if dist < D[i]:
D[i] = dist
print(" ".join(map(str, chosen)))新中心加入后每个点的 D(x) 只和「到新中心的距离」取较小值，每轮 O(n·d)。用题面示例 4 2 3 / 0 0 / 0 0 / 5 5 / 5 5 → 0 2 1 核对。
08 / 边界、反例与复杂度
错误做法在题库用例上各输出什么
下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。
| 错误做法 | 输入 | 错误输出 | 正确输出 | 判题结果 |
|---|---|---|---|---|
| AI001 边分配边移动中心 | 5 2 3 2 / 0 0 / 0 0 / 10 10 / 0 0 / 1 1 / -1 -1 / 9 9 / 11 11 | 0.50 0.50 / -1.00 -1.00 / 10.00 10.00 | 0.00 0.00 / 0.00 0.00 / 10.00 10.00 | 答案错误（WA） |
AI001 并列写成 <=（取大编号） | 3 2 2 1 / 0 0 / 2 0 / 1 0 / 0 0 / 2 0 | 0.00 0.00 / 1.50 0.00 | 0.50 0.00 / 2.00 0.00 | 答案错误（WA） |
| AI001 空簇写成零向量 | 4 2 3 4 / 0 0 / 100 100 / -100 -100 / … | 0.67 0.67 / 0.00 0.00 / 0.00 0.00 | 0.50 0.50 / 100.00 100.00 / -100.00 -100.00 | 答案错误（WA） |
| AI001 先读样本后读中心 | 题面示例 | 1.00 1.00 / 8.00 8.00 | 1.50 1.50 / 8.50 8.50 | 答案错误（WA） |
| AI011 票数并列取大标签 | 4 1 4 1 / 0 4 / 2 1 / 10 4 / 12 1 / 6 | 4 | 1 | 答案错误（WA） |
| AI011 距离并列取大编号 | 3 1 1 1 / -2 5 / 2 9 / 4 9 / 0 | 9 | 5 | 答案错误（WA） |
AI024 并列写成 >=（取后者） | 4 2 3 / 0 0 / 0 0 / 5 5 / 5 5 | 0 3 2 | 0 2 1 | 答案错误（WA） |
第一行：分配到第 2 个点时中心已经被第 1 个点挪走，后面的点看到的中心和题目定义对不上。
| 做法 | 时间 | 本课规模下 |
|---|---|---|
| AI001 每轮 n·k·d | O(t·n·k·d) | 20 × 2000 × 20 × 8 = 6.4×10⁶ 次基础运算，可通过 |
| AI011 每个查询排序全部样本 | O(m·n·(d + log n)) | 200 × 2000，可通过 |
| AI024 每轮增量更新 | O(k·n·d) | 100 × 10000 × 8 = 8×10⁶，可通过；每轮重扫全部中心是 O(k²·n·d) |
09 / 渐进练习与参考答案
跟做 → 改一个条件 → 独立实现 → 迁移
每题先在纸上或文件里做完，再展开答案。
练习 1（跟做）：按第 05 节第一张表的格式，用第 1 轮更新后的中心 (0.80, 0.90)、(0.44, 0.42) 把六个点再分配一遍，写出各点的归属和更新后的中心。
展开练习 1 答案
P1、P2、P3 → C2（到 (0.44, 0.42) 更近），P4、P5、P6 → C1。C1 = 均值 (0.80, 0.80)，C2 = 均值 (0.20, 0.20)——与第二张表的第 2 轮一致。手动计算时用「手动计算 → 跑代码核对」的顺序，先预测再验证。
练习 2（改一个条件）：AI001 题面示例的初始中心改成 (0,0)、(1,1)，两轮后中心是多少？为什么初始中心会影响结果？
展开练习 2 答案
第 1 轮：(1,1) 到 (1,1) 距离 0 → C2；(2,2) 到 (0,0) 是 8、到 (1,1) 是 2 → C2；(8,9)、(9,8) 也都离 (1,1) 更近 → C2；C1 空簇沿用 (0,0)。更新后 C2 = (5, 5)。第 2 轮：(1,1)、(2,2) 离 (0,0) 更近 → C1，(8,9)、(9,8) → C2；结果 (1.50, 1.50)、(8.50, 8.50)——这一组碰巧收敛到同一处，但一般情况下不同初始中心可能停在不同的局部最优（补充学习「初始中心和 k 怎么选」）。
练习 3（改一个条件）：AI001 的 k 改成 1，任意 t ≥ 1 的输出是什么？
展开练习 3 答案
全体样本的均值（每维各自求均值），一轮就到；题库用例 4 1 1 3 / 100 / -5 -2 4 9 输出 1.50。t = 0 时仍输出初始中心。
练习 4（独立实现）：完成「代码自测」的 assign 与 update，再加两条断言：用第 1 轮更新后的中心再跑一轮，得到 (0.80, 0.80) 与 (0.20, 0.20)。
展开练习 4 答案
assign 与 update 的参考实现（自带断言）
PythonEPS = 1e-9
def assign(points, centers):
# 返回每个点的中心下标（0 基）：平方距离最小；相差不超过 EPS 视作并列，保留先遇到的小编号
out = []
for p in points:
best, best_dist = 0, sum((a - b) ** 2 for a, b in zip(p, centers[0]))
for c in range(1, len(centers)):
dist = sum((a - b) ** 2 for a, b in zip(p, centers[c]))
if dist < best_dist - EPS:
best, best_dist = c, dist
out.append(best)
return out
def update(groups, old):
# groups[c] 是分到中心 c 的点；逐维求均值；空簇沿用旧中心
new = []
for c, g in enumerate(groups):
if not g:
new.append(old[c])
else:
new.append([sum(p[j] for p in g) / len(g) for j in range(len(old[c]))])
return new
CENTERS = [[0.1, 0.9], [0.7, 0.1]]
POINTS = [[0.1, 0.1], [0.2, 0.3], [0.3, 0.2], [0.7, 0.7], [0.8, 0.9], [0.9, 0.8]]
assert assign(POINTS, CENTERS) == [1, 1, 1, 1, 0, 1] # 第 05 节第 1 轮分配表
assert assign([[0.5, 0.5]], [[0.4, 0.5], [0.6, 0.5]]) == [0] # 等距并列取小编号
groups = [[[0.8, 0.9]], [[0.1, 0.1], [0.2, 0.3], [0.3, 0.2], [0.7, 0.7], [0.9, 0.8]]]
got = update(groups, CENTERS)
assert [[round(v, 9) for v in c] for c in got] == [[0.8, 0.9], [0.44, 0.42]] # 第 1 轮更新后
assert update([[], [[2.0, 2.0]]], [[1.0, 1.0], [9.0, 9.0]]) == [[1.0, 1.0], [2.0, 2.0]] # 空簇沿用旧中心
# 再跑一轮：分配 → 更新，得到第 2 轮的中心 (0.80, 0.80) 与 (0.20, 0.20)
a = assign(POINTS, got)
g2 = [[p for p, x in zip(POINTS, a) if x == c] for c in range(2)]
assert [[round(v, 9) for v in c] for c in update(g2, got)] == [[0.8, 0.8], [0.2, 0.2]]见第 07 节展开区（同一份代码）。
练习 5（迁移）：AI024 每加入一个新中心后，为什么每个点的 D(x) 只需和「到新中心的距离」取较小值？用第 06 节的思路写出增量更新那两行，并用题面示例 4 2 3 / 0 0 / 0 0 / 5 5 / 5 5 手推三轮。
展开练习 5 答案
D(x) 是到「已选中心集合」的最小距离；集合只多了一个元素，最小值只可能被这个新元素刷新，所以 if dist < D[i]: D[i] = dist。手推：第 1 个中心固定 0 号；D = [0, 0, 50, 50] → 取最大且编号最小的 2 号；更新后 D = [0, 0, 0, 0] → 全部并列，取编号最小的未选样本 1 号。输出 0 2 1。
10 / 读题要求与复习自评
三道题的要求对照，以及完成本课之后怎么复习
提交前把下表过一遍；题目页的题面与样例是最终依据。
| 项目 | AI001 聚类器 | AI011 KNN | AI024 K-Means++ 初始化 |
|---|---|---|---|
| 输入顺序 | n d k t；k 行中心；n 行样本 | n d k m；n 行特征+标签；m 行查询 | n d k；n 行样本 |
| 并列规则 | 距离差 ≤ 1e-9 取小编号 | 距离同取样本编号小；票同取类别小 | D 同取编号小 |
| 特殊规则 | 空簇沿用旧中心；t = 0 输出初始中心 | 整数平方距离 | 第 1 个中心固定 0 号 |
| 输出 | k 行两位小数；|v| < 0.0005 → 0.00 | m 行类别 | 一行 k 个编号 |
| 示例 | 4 点 2 中心 → 1.50 1.50 / 8.50 8.50 | → 0 / 1 | 3 1 2 / 0 / 10 / 3 → 0 1 |
需要对照解法时，展开本页第 07 节的三份完整参考程序。复习与自评：本课的「学习完成检查」六条是自评，不改变题目的通过（AC）状态，本课算完成的条件以页面下方「学习完成检查」处的说明为准。复习时用三个问题自测：① 不看正文，说出一轮的两个动作与空簇、并列两条规则；② 不看表格，重算第 1 轮 P4 到两个中心的距离；③ 说出 fit 只读训练集的原因和 Q=(1200,12) 放进 fit 会怎样。答不出哪一条，就回到对应的节重读，再做第 09 节对应的练习。
补充实验
归一化与最近中心：改动查询点，观察归属如何变化
下面两个实验演示同一件事：缩放参数只能用训练集计算（先拟合、再变换）；查询点如果参与拟合，就会在被判断的同时改变坐标系，这就是数据泄漏。第一个实验按步骤展示一次完整计算，第二个实验允许你改动查询点，观察最近中心在什么位置发生变化。
四步推演 · 约 10 分钟
从请求日志到最近中心
四个按钮就是接下来代码里的四个动作。表中 C1、C2 是两个固定中心，Q 是要分类的查询向量。读懂当前结果，再进入下一步。
拟合参数来自首屏的 4 条训练日志
矩阵形状（X.shape）= (4, 2)- 词元数量（token）
- 0 → 1000
- 等待秒数
- 0 → 10
第 1 步，从训练日志保存每列范围。各列最小值（mins）= [0, 0]，各列最大值（maxs）= [1000, 10]。
01 / 拟合参数
从训练日志保存每列范围
遍历训练矩阵 X 的每一列。词元数量（token）这一列从 0 到 1000，等待时长这一列从 0 到 10；这四个数会留给后面的新请求使用。各列最小值（mins）= [0, 0]，各列最大值（maxs）= [1000, 10]。
交互实验
调整查询向量（Q），观察取最小值下标（argmin）的结果
下表中 Q 是这次要分类的查询向量，C1、C2 是两个固定中心；每个点的两列分别是词元数量（token）与等待时长。 三个快捷点分别对应分配反转、归一化后并列和训练范围外。也可以拖动滑杆，自己找一组归一化前后结果相同的坐标。
先试三个有代表性的点
训练集给出的每列范围
- 词元数量
- 0 → 1000
- 等待时长
- 0 → 10
各列最小值（mins）= [0, 0]，各列最大值（maxs）= [1000, 10]
可以左右滑动查看完整坐标表
| 点 | 原始坐标 | 归一化坐标 |
|---|---|---|
| C1 | (100, 9) | (0.1, 0.9) |
| C2 | (700, 1) | (0.7, 0.1) |
| Q | (300, 2) | (0.3, 0.2) |
原始尺度选择 C1，归一化后选择 C2。
直接比较原始数值
C1 最近- C1 各列平方差与总距离
- 40000 + 49 = 40049
- C2 各列平方差与总距离
- 160000 + 1 = 160001
词元数量这一列的数值跨度更大，距离几乎由第一列决定。
先做 Min-Max 归一化
C2 最近- C1 各列平方差与总距离
- 0.04 + 0.49 = 0.53
- C2 各列平方差与总距离
- 0.16 + 0.01 = 0.17
两列都缩放到相近范围后，等待时长不再被词元数量这一列主导。
11 / 练习
按顺序完成本课的任务
必做题已通过 0/2 道；进阶练习已通过 0/1 道
实现一轮分配（assign）
代码自测自主练习练习重点：对每个点算到全部中心的平方距离，1e-9 内并列取小编号；预计用时：15 分钟
完成标准：能不看正文独立写出带并列规则的最近中心选择
需要时查看提示
当前距离（dist）< 最优距离（best）− 1e-9 才更新；中心数组（centers）按编号升序遍历时自然保留先遇到的小编号。AI001 题目中的中心编号从 1 开始，代码里数组下标从 0 开始——并列时选题目编号更小的，等价于选数组下标更小的。第 05 节有逐格表，参考实现在第 07 节。
自测代码（复制到你的代码文件中运行，检查输出是否一致）
CENTERS = [[0.1, 0.9], [0.7, 0.1]]
POINTS = [[0.1, 0.1], [0.2, 0.3], [0.3, 0.2],
[0.7, 0.7], [0.8, 0.9], [0.9, 0.8]]
# assign(points, centers) 返回每个点的中心下标(0 基)
assert assign(POINTS, CENTERS) == [1, 1, 1, 1, 0, 1]
# 并列：两个中心等距，选下标小的
assert assign([[0.5, 0.5]], [[0.4, 0.5], [0.6, 0.5]]) == [0]实现中心更新（update）：均值与空簇
代码自测自主练习练习重点：逐维求均值；空簇沿用旧中心；全部中心一起换；预计用时：15 分钟
完成标准：能说出为什么要等全部分配完再更新中心
需要时查看提示
新中心先存进新中心列表（new_centers），循环结束整体替换。边分配边移动中心，后分配的点看到的中心就已经变了——第 08 节错误表第一行给了题库用例上的错误输出。
自测代码（复制到你的代码文件中运行，检查输出是否一致）
groups = [
[[0.8, 0.9]],
[[0.1, 0.1], [0.2, 0.3], [0.3, 0.2], [0.7, 0.7], [0.9, 0.8]],
]
old = [[0.1, 0.9], [0.7, 0.1]]
got = update(groups, old)
assert [[round(v, 9) for v in c] for c in got] == [[0.8, 0.9], [0.44, 0.42]]
# 空簇沿用旧中心
got = update([[], [[2.0, 2.0]]], [[1.0, 1.0], [9.0, 9.0]])
assert got == [[1.0, 1.0], [2.0, 2.0]]AI001 · 多维样本聚类器
必做任务 1练习重点：组合分配（assign）与更新（update）两个函数迭代 t 轮，再按要求写对浮点输出格式；预计用时：35 分钟
完成标准：能整段说出一轮的顺序，并通过全部测试用例
需要时查看提示
输入顺序为先 k 行初始中心、再 n 行样本。题目没要求归一化就不要自行加 Min-Max。t = 0 直接输出初始中心；输出保留两位小数，绝对值小于 0.0005 的值先改成 0.0，避免输出 -0.00——这是 AI001 自己规定的归零阈值，与上一课 fmt 用的「精度一半」（两位时是 0.005）不同，按题面写 0.0005。第 06 节有题面示例的两轮表。
AI011 · KNN 分类器
必做任务 2练习重点：平方欧氏距离取 k 近邻多数表决；两级确定性并列规则；预计用时：25 分钟
完成标准：能说出 KNN 的 fit 为什么只是保存数据
需要时查看提示
整数特征的平方距离是精确整数，没有浮点误差：距离相同取样本编号小的，票数相同取类别编号小的。距离在 C++/Java 里用 64 位。KNN 没有中心：Q 和每一条训练行算距离，取最近 k 条按标签投票。第 06 节有示例的距离表。
AI024 · K-Means++ 确定性初始化
进阶练习 1进阶练习练习重点：维护每个点到已选中心集的最小距离，选最大者、并列取编号小；预计用时：20 分钟
完成标准：能说出为什么每轮只需增量更新 D(x) 而不是重算
需要时查看提示
新中心加入后，每个点的 D(x) 只需和「到新中心的距离」取较小值——O(n·d) 一轮，不需要对每个点重扫全部中心。首个中心固定为编号 0。第 09 节练习 5 有题面示例的手推。
提交结果
提交结果说明与处理方法
- WA
答案错误
四个常见错误：并列没选小编号、空簇没沿用旧中心、边分配边移动中心、读入顺序反了。第 08 节的表给出了每种错误在题库用例上的输出
- PE
格式错误
AI001 每行 d 个数、空格分隔、保留两位小数；绝对值小于 0.0005 要输出 0.00，注意 -0.00
- RE
运行错误
读入顺序是先 k 行中心、再 n 行样本；反了会把样本当中心，中途下标越界
- TLE
超时
AI001 按题目数据范围上限估算，每轮约 32 万次基础迭代、20 轮约 640 万次，常规循环写法通常可以在时限内完成；AI011 距离排序 O(n log n)——超时先查内层循环是否重复创建列表
- AC
通过
再测 t = 0、单点簇、全部点重合；想想 k = 1 时 AI001 的答案是什么（全体均值）
12 / 学习完成检查
本课学习完成检查
完成本课需要：必做题全部通过，并勾选本课的全部学习完成检查；进阶练习、基础加练与复习题单独统计，不影响完成状态。登录后，勾选记录会保存到账号，并更新课程总览的完成状态。