自动确定簇数的 X-Means 聚类
P5940. 自动确定簇数的 X-Means 聚类
场次:2026年10月21日-AI方向 · 来源:CodeFun2000 P5940
题目描述
做用户分群、图像分割、测点归组这类任务时,"究竟该分成几组"往往事先说不准。K-Means 必须由人给定簇数 K;X-Means 在它外面套上一层 BIC(贝叶斯信息准则),让程序自己在候选区间里把 K 挑出来。
本题要求实现 X-Means:给定 N 个 d 维数据点以及簇数候选区间 [Kmin, Kmax],自动选出最优簇数 K,并输出各簇的中心坐标和每个数据点的簇标签。
算法介绍
K-Means 基础
K-Means 是最经典的无监督聚类算法:把 N 个点划分成 K 个簇,使簇内误差平方和(SSE)尽可能小。
SSE 定义:
也就是把每个点到其所属簇中心的欧氏距离平方全部累加。
算法步骤:
初始化:按确定性策略从数据中挑出 K 个点作为初始簇中心(见文末提示,不允许随机初始化)
分配(Assign):把每个点归到距离最近的簇中心
更新(Update):把每个簇的中心改成该簇内所有点的均值
重复 2、3 两步,直到某一轮迭代结束后所有点的簇标签都不再变化(视为收敛),或迭代轮数达到 100 轮上限
BIC(贝叶斯信息准则)
BIC 用于在若干 K 值对应的聚类结果之间做选择,既衡量拟合程度,也衡量模型复杂度:
参数说明:
| 符号 | 含义 |
|---|---|
| n | 数据点总数 |
| SSE | 误差平方和 |
| p = K·(d+1) | 模型参数个数(K 个 d 维中心 + 每簇 1 个权重参数) |
| K | 实际簇数(重合中心合并之后的簇数) |
| ε | 常数 1e-8,避免 SSE=0 时出现 log(0) |
理解要点:
BIC 越小越好
第一项 刻画拟合误差 —— SSE 越小越好
第二项 是复杂度惩罚 —— 簇数越多,惩罚越重
簇数变多能压低 SSE,同时抬高惩罚,BIC 在两者之间取平衡
注意事项:
若 K-Means 收敛后簇中心重合而被合并,K 取合并后的实际簇数,而不是枚举时传入的 K
所有点重合导致 SSE=0 时,用 ε=1e-8 兜住 log(0)
若多个 K 算出的 BIC 相同,取其中最小的 K 作为最终结果
X-Means 算法流程
X-Means 的核心是枚举 + BIC 选优:
输入:数据集 X,簇数区间 [Kmin, Kmax]
对 K = Kmin, Kmin+1, ..., Kmax
调用 KMeans(X, K),得到 centers, labels, SSE
合并重合的中心,得到实际的 centers, labels, k_actual
计算 BIC = n·ln((SSE + 1e-8)/n) + k_actual·(d+1)·ln(n)
选取 BIC 最小的 K 对应的聚类结果作为最终输出输入格式
第一行是两个整数 N 和 d,分别表示数据点个数与每个点的维度
接下来 N 行,每行 d 个浮点数,描述一个数据点的坐标
最后一行是两个整数 和 ,表示允许的最小簇数与最大簇数,保证
输出格式
第一行输出一个整数 K,表示算法最终确定的簇数
随后 K 行,每行 d 个浮点数,表示各簇的中心坐标(保留小数点后 2 位)
最后一行包含 N 个整数(取值 0 到 K-1),按输入顺序表示每个点所属的簇
若无法进行聚类,则输出 0
数据范围
坐标绝对值不超过
保证
时间限制:C/C++ ms,其他语言 ms。
内存限制:C/C++ MB,其他语言 MB。
示例
示例 1
输入:
12 2
1.0 1.0
15.0 12.0
7.0 6.0
2.0 1.0
8.0 6.0
17.0 12.0
1.0 2.0
7.0 7.0
15.0 14.0
2.0 2.0
17.0 14.0
8.0 7.0
1 5输出:
3
1.50 1.50
7.50 6.50
16.00 13.00
0 2 1 0 1 2 0 1 2 0 2 1说明: 12 个二维点明显聚成三小堆,每堆 4 个点,分别围绕 (1.5,1.5)、(7.5,6.5)、(16,13),堆内距离远小于堆间距离。把 K 从 1 枚举到 5,对应 BIC 依次为 56.29、43.86、22.36、29.13、32.90,K=3 时最小,所以最终簇数为 3。三个簇按中心坐标的字典序升序编号:0 号 (1.50,1.50)、1 号 (7.50,6.50)、2 号 (16.00,13.00)。再按输入顺序逐点判定:(1,1) 属于 0 号簇,(15,12) 属于 2 号簇,(7,6) 属于 1 号簇……得到最后一行标签。
示例 2
输入:
8 2
4.0 2.0
20.0 10.0
5.0 2.0
22.0 10.0
4.0 3.0
20.0 12.0
5.0 3.0
22.0 12.0
1 3输出:
2
4.50 2.50
21.00 11.00
0 1 0 1 0 1 0 1说明: 8 个二维点分成左右两堆,各 4 个点。左堆 (4,2)、(5,2)、(4,3)、(5,3) 的均值为 (4.50,2.50),右堆 (20,10)、(22,10)、(20,12)、(22,12) 的均值为 (21.00,11.00),两堆之间的距离远大于堆内距离。K 取 1、2、3 时 BIC 分别为 42.00、14.26、19.95,K=2 时最小,所以最终簇数为 2。按中心字典序编号后,左堆为 0 号、右堆为 1 号,最后一行按输入顺序交替给出 0、1 标签。
提示
| 要点 | 说明 |
|---|---|
| 确定性初始化 | 把数据点按第一维坐标升序排序,取排序后第 i*(N-1)/(K-1) 个点(i=0,1,...,K-1,除法向下取整)作为第 i 个初始簇中心;K=1 时直接取全体点的均值。不要使用随机初始化 |
| 收敛条件 | 一轮迭代结束后所有点的簇标签都没有变化,即视为收敛;迭代最多 100 轮 |
| 标签排序 | 输出前按簇中心的坐标字典序升序(先比第一维,第一维相同再比第二维,依此类推)把簇重新编号为 0,1,2,...,保证同一份数据的输出唯一 |
| Kmax 截断 | 先令 Kmax = min(Kmax, N);若截断后 Kmin > Kmax,则令 Kmin = Kmax |
| 边界保护 | Kmax 可能大于 N,必须截断为 min(Kmax, N) 后再枚举 |
| SSE 为零 | 所有点坐标完全相同时 SSE=0,计算 BIC 时用 (SSE + 1e-8) / n 代替 SSE / n,防止 log(0) |
| 空簇处理 | 迭代过程中某个簇没有任何点时,保留该簇原有的中心,不参与均值更新 |
| 重合中心合并 | K-Means 收敛后逐个检查簇中心,若任意两个中心的距离平方 < 1e-4,就把二者并成同一簇(标签重新映射,可传递合并);合并后中心取该簇所有点的均值。例如 30 个点都挤在 (5,5) 附近,合并后实际簇数应为 1 |
| Kmin = Kmax | 此时只需对固定的 K 做一次 K-Means,不需要枚举 |
| 距离相同处理 | 某个点到多个簇中心的距离相等时,归给编号最小的那个簇。例如使用 min(..., key=lambda i: (dist_sq, i)) |
| 零的符号 | 若某坐标四舍五入后为 -0.00,请输出 0.00 |
解题思路
题面把算法写死成五段流水线
这题没有"设计一个更好的聚类算法"的余地,正确性等价于把题面的流水线逐步复现。把它拆开看,一共五段,每段都有自己的坑:
| 阶段 | 决定什么 | 题面写死的地方 |
|---|---|---|
| 初始化 | 起点 | 按第一维升序排序,取第 个(向下取整); 取均值 |
| 迭代 | 收敛到哪个局部最优 | 分配平局取小编号;空簇保留旧中心;一轮后标签不变即停;最多 100 轮 |
| 合并 | 实际簇数 | 距离平方 的两簇合并,可传递;中心取合并后所有点的均值 |
| BIC | 选哪个 | ;并列取最小 |
| 输出 | 编号方式 | 按中心坐标字典序升序重编号;两位小数; 写成 |
输出里有个容易读漏的"小机关":BIC 罚的是 ,不是枚举的 。中心重合被合并之后,模型的复杂度按合并后的簇数算——这条决定了「点全挤在一起」这类数据上选出的 是不是 1。
初始化:一条公式,两个分支
提示里那句"第 个点(除法向下取整)"是整数运算 i * (n - 1) // (k - 1),不是 round。 时 算出来是 ,向下取整取第 3 个点,四舍五入取第 4 个——起点不同, 的最终 SSE 和 BIC 都会变。
时公式分母为 0,必须单独走"全体均值"这一支。
if k == 1:
centers = [[sum(p[j] for p in points) / n for j in range(d)]]
else:
order = sorted(range(n), key=lambda i: points[i][0]) # 第一维升序
centers = [points[order[i * (n - 1) // (k - 1)]][:] for i in range(k)]key=lambda i: points[i][0] 只比第一维;sorted 是稳定排序,第一维相同的点保持输入顺序——这决定了初值到底是哪几个点,所以不能顺手写成 key=lambda i: tuple(points[i])。
迭代:分配、更新、判停
分配要同时做到"最近"和"平局取小编号"。后者不需要额外的排序,只要遍历时用严格小于比较:
new = []
for p in points:
best_c, best_d = 0, dist2(p, centers[0])
for c in range(1, k):
dd = dist2(p, centers[c])
if dd < best_d: # 严格更近才换 → 距离相同自然留在小编号
best_c, best_d = c, dd
new.append(best_c)更新时把每个簇的中心改成簇内均值,空簇按题面"保留原有的中心":
sums = [[0.0] * d for _ in range(k)]
cnt = [0] * k
for p, c in zip(points, labels):
cnt[c] += 1
for j in range(d):
sums[c][j] += p[j]
for c in range(k):
if cnt[c]: # 空簇保留旧中心,绝不做 0 除
centers[c] = [sums[c][j] / cnt[c] for j in range(d)]if cnt[c] 这一行不是可选的: 大于不同点的个数时(题面提示里那个「30 个点都挤在 (5,5)」就是),必然有空簇;不判断就 ZeroDivisionError。
判停按题面的说法是"某一轮迭代结束后所有点的簇标签都不再变化",所以比较的是标签而不是中心位移:
labels = None
for _ in range(100):
new = [...] # 分配
if new == labels: # 一轮结束,标签没变 → 收敛
break
labels = new
centers = [...] # 更新labels 初值用 None 而不是全 0 的列表:标签本身就是 的整数,用 None 才能明确区分"还没分配过"与"第一轮分配结果恰好全是 0 号簇"这两种情况,保证第一轮的更新一定执行。
合并重合中心:并查集做"可传递合并"
题面要求"若任意两个中心的距离平方 ,就把二者并成同一簇(标签重新映射,可传递合并)"。可传递是关键词:中心 与 近、 与 近、 与 不近时,三者仍算一堆。逐个比较加两两合并要写"合并后重新检查",用并查集表达最自然:把"近"当成一条边,同一个连通块里的中心就是一簇。
parent = list(range(k))
for i in range(k):
for j in range(i + 1, k):
if dist2(centers[i], centers[j]) < 1e-4:
ri, rj = find(i), find(j)
if ri != rj:
parent[rj] = ri
roots = sorted({find(c) for c in range(k)})
index = {r: i for i, r in enumerate(roots)}
k2 = len(roots)
new_labels = [index[find(c)] for c in labels] # 标签必须重新映射new_labels 这一步是整题最容易漏的一行:合并之前标签的取值范围是 ,合并之后只剩 个簇,不重映射的话最后一行会冒出 标签 的编号,与题面"取值 0 到 K-1"直接冲突。合并后的中心按题面取"该簇所有点的均值",所以要用新标签再统计一次。
BIC:拟合项与惩罚项各管一头
两项的方向正好相反: 随 增大而减小(第一项下降), 随有效簇数增大而增大(第二项上升)。 就是"拟合得好、又不复杂"的度量,所以取 BIC 最小。
只为一件事:所有点重合时 , 会抛 ValueError。加上它之后 是个很小的负数,不影响选择。
best_bic, best = None, None
for k in range(kmin, kmax + 1):
centers, labels, sse = kmeans(points, k, n, d)
centers, labels, k_actual = merge_centers(centers, labels, points, k, d)
bic = n * log((sse + 1e-8) / n) + k_actual * (d + 1) * log(n)
if best_bic is None or bic < best_bic - 1e-12: # 并列时保留更小的 K
best_bic, best = bic, (centers, labels, k_actual)k 从 kmin 升序遍历 + 只在严格更小时替换,就是"BIC 相同取最小 K"的实现,与前面决策树那题的"平局取小编号"是同一个写法。- 1e-12 的作用是让数学上相等的 BIC 不被第 位的噪声判成"更小"。
枚举区间前还要按提示做截断:kmax = min(kmax, n),若截断后 kmin > kmax 则 kmin = kmax。 时必然有空簇,纯属白算。
输出:按中心字典序重编号
最后一步是把内部编号"翻译"成题面要的编号。内部编号来自合并时的并查集根顺序,跟坐标没有关系;题面要求按中心坐标字典序升序重新编号,这样同一份数据只有一种输出。
order = sorted(range(k_actual), key=lambda c: tuple(centers[c])) # 字典序
rank = [0] * k_actual
for new_id, c in enumerate(order):
rank[c] = new_id
out = [str(k_actual)]
for c in order:
out.append(" ".join(fmt(v) for v in centers[c]))
out.append(" ".join(str(rank[c]) for c in labels))fmt 负责两件事:固定两位小数(f"{v:.2f}" 会把 1.5 写成 1.50),以及把 -0.00 改回 0.00。
def fmt(v):
s = f"{v:.2f}"
return "0.00" if s == "-0.00" else s关于"若无法进行聚类,则输出 0":数据范围给了 ,所以合法输入里这个分支不会触发;代码里保留 n == 0 的守卫,让这条规则有对应的位置。
完整代码实现
import sys
from math import log
def dist2(a, b):
s = 0.0
for x, y in zip(a, b):
s += (x - y) * (x - y)
return s
def kmeans(points, k, n, d):
"""按题面规则跑 K-Means,返回 (centers, labels, sse)。"""
if k == 1:
centers = [[sum(p[j] for p in points) / n for j in range(d)]]
else:
order = sorted(range(n), key=lambda i: points[i][0]) # 第一维升序
centers = [points[order[i * (n - 1) // (k - 1)]][:] for i in range(k)]
labels = None
for _ in range(100):
new = []
for p in points:
best_c, best_d = 0, dist2(p, centers[0])
for c in range(1, k):
dd = dist2(p, centers[c])
if dd < best_d: # 严格更近才换 → 距离相同取小编号
best_c, best_d = c, dd
new.append(best_c)
if new == labels: # 一轮结束后标签没变 = 收敛
break
labels = new
sums = [[0.0] * d for _ in range(k)]
cnt = [0] * k
for p, c in zip(points, labels):
cnt[c] += 1
for j in range(d):
sums[c][j] += p[j]
for c in range(k):
if cnt[c]: # 空簇保留原中心
centers[c] = [sums[c][j] / cnt[c] for j in range(d)]
sse = 0.0
for p, c in zip(points, labels):
sse += dist2(p, centers[c])
return centers, labels, sse
def merge_centers(centers, labels, points, k, d):
"""把距离平方 < 1e-4 的中心并成一簇(可传递),中心取该簇所有点的均值。"""
parent = list(range(k))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for i in range(k):
for j in range(i + 1, k):
if dist2(centers[i], centers[j]) < 1e-4:
ri, rj = find(i), find(j)
if ri != rj:
parent[rj] = ri
roots = sorted({find(c) for c in range(k)})
index = {r: i for i, r in enumerate(roots)}
k2 = len(roots)
new_labels = [index[find(c)] for c in labels]
sums = [[0.0] * d for _ in range(k2)]
cnt = [0] * k2
for p, c in zip(points, new_labels):
cnt[c] += 1
for j in range(d):
sums[c][j] += p[j]
new_centers = [[sums[c][j] / cnt[c] for j in range(d)] if cnt[c] else centers[roots[c]][:]
for c in range(k2)]
return new_centers, new_labels, k2
def fmt(v):
s = f"{v:.2f}"
return "0.00" if s == "-0.00" else s
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
pos = 0
n = int(data[pos]); d = int(data[pos + 1]); pos += 2
points = []
for _ in range(n):
points.append([float(x) for x in data[pos:pos + d]])
pos += d
kmin = int(data[pos]); kmax = int(data[pos + 1])
if n == 0: # 题面:无法聚类时输出 0
print(0)
return
kmax = min(kmax, n)
if kmin > kmax:
kmin = kmax
best_bic, best = None, None
for k in range(kmin, kmax + 1):
centers, labels, sse = kmeans(points, k, n, d)
centers, labels, k_actual = merge_centers(centers, labels, points, k, d)
bic = n * log((sse + 1e-8) / n) + k_actual * (d + 1) * log(n)
if best_bic is None or bic < best_bic - 1e-12: # 并列时保留更小的 K
best_bic, best = bic, (centers, labels, k_actual)
centers, labels, k_actual = best
# 按中心坐标字典序升序重新编号
order = sorted(range(k_actual), key=lambda c: tuple(centers[c]))
rank = [0] * k_actual
for new_id, c in enumerate(order):
rank[c] = new_id
out = [str(k_actual)]
for c in order:
out.append(" ".join(fmt(v) for v in centers[c]))
out.append(" ".join(str(rank[c]) for c in labels))
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()示例推演
示例 1:五个 K 的 BIC 分别怎么来的
12 个点明显是三堆,每堆 4 个:
| 堆 | 成员 | 均值 | 堆内 SSE |
|---|---|---|---|
| 左 | |||
| 中 | |||
| 右 |
的初值。 按第一维升序(相同第一维保持输入顺序)排列后,第 、、 个点是 、、,这就是三个初始中心。迭代收敛后中心落到三堆的均值上,。
。 全体均值是 ,各点偏差平方和累加得 。
。 收敛后中心落在 与 :左边 8 个点归一堆、右边 4 个点归一堆,。
、。 三堆里必有一堆被拆成两半, 继续下降(、),但簇数多了。
把 、、 代进 BIC(本题没有中心重合,):
| 拟合项 | 惩罚项 | BIC | ||
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 |
从 3 加到 4 时,拟合项只降了 ,惩罚项却涨了 ,BIC 反而变大——这就是"簇数变多能压低 SSE,同时抬高惩罚"的具体形状。最小值在 ,与题面给的五个数(56.29、43.86、22.36、29.13、32.90)一致。
输出。 三个中心按字典序排好就是 ,编号 不变;再按输入顺序逐点判定:
| 输入点 | 归属 | 标签 |
|---|---|---|
| 左 | 0 | |
| 右 | 2 | |
| 中 | 1 | |
| 左 | 0 | |
| 中 | 1 | |
| 右 | 2 | |
| 左 | 0 | |
| 中 | 1 | |
| 右 | 2 | |
| 左 | 0 | |
| 右 | 2 | |
| 中 | 1 |
3
1.50 1.50
7.50 6.50
16.00 13.00
0 2 1 0 1 2 0 1 2 0 2 1示例 2:为什么 反而不如
8 个点是左右两堆(各 4 个),左堆均值 、右堆 ,两堆内 SSE 各为 与 , 时 ; 时全体均值 ,。
会把某一堆再劈成两半, 只从 降到 ,而惩罚项从 涨到 ,于是 BIC 从 升到 。五个数字(42.00、14.26、19.95)与题面一致,选 。
这题的 初值是排序后第 、、 个点:、、 —— 注意第 个位置算出来是 ,向下取整取第 3 个(下标从 0 起),四舍五入会取到 ,起点就不同了。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 按题面流程:每个 各跑一次 K-Means(最优) | 单轮分配 ,轮数 ,实际常是个位数 | ||
| 不判收敛、固定跑满 100 轮 | 同上 | 少了"标签不变就退出",同样数据上慢一个数量级 |
枚举 这一步无法回避——题面就是"对每个 跑一遍再比 BIC",所以主项是 而不是单独的 。把上界代入:、、 轮,理论上确实很大,实际收敛很快(本例三堆数据在 上十几轮就停),真正的代价集中在"每个点对每个中心算一次距离"这个内层循环上。
除 K-Means 之外的部分都很轻:合并中心是 ,BIC 是 ,输出重编号是 。空间上只要存原始点表 、中心与标签 ,不需要距离矩阵。
易错点总结
1. 空簇也去做均值更新
centers[c] = [sums[c][j] / cnt[c] for j in range(d)] 少了 if cnt[c] 这一层, 一旦大于"不同点的个数"就会 ZeroDivisionError(cnt[c] 是 0)。题面提示里那个「30 个点都挤在 (5,5) 附近」正是这种数据: 起所有点都会归到 0 号簇(距离相同取小编号),其余簇全是空簇,更新时当场除零,标准输出一行都没有。
2. 合并中心后忘了把标签重新映射
合并只改了 centers 与簇数,labels 里还留着 的旧编号。示例里没有出现合并(两个样例的 都等于枚举的 ),所以照样能过,但一旦发生合并就会坏在两个地方:要么后续按新簇数 开桶、却拿旧标签去 cnt[c] += 1,旧编号超出桶数直接 IndexError;要么干脆跳过统计、把旧标签原样输出,最后一行冒出 的编号,与题面"取值 0 到 K-1"矛盾。代码里 new_labels = [index[find(c)] for c in labels] 必须在合并之后、统计新中心之前。
3. 中心用 print(round(v, 2)) 输出
round 只改数值不改文本:round(1.5, 2) 打印出来是 1.5,示例 1 的第二、三行会变成 7.5 6.5、16.0 13.0,逐字节对拍直接不通过。负零也一样:某坐标四舍五入到 时 f"{-0.001:.2f}" 是 -0.00,题面明确要求写 0.00。所以要么统一走 f"{v:.2f}" 再单独把 -0.00 换成 0.00,要么在格式化前把 的坐标归零。