#P4483. K-Means 聚类算法
-
1000ms
Tried: 20
Accepted: 4
Difficulty: 5
-
算法标签>机器学习算法
K-Means 聚类算法
一.初始化聚类中心
根据题目要求,直接从数据点中取前 k 个点作为初始中心:
centers[0..k-1] = nums[0..k-1]。
二.重复迭代(最多 max_iter 次) 每次迭代分为两步:
1)分配簇标签(Assignment Step)
对于每个点 nums[i] = (xi, yi):
- 计算到每个中心
centers[j]的欧氏距离的平方(不用开根号,比较平方即可) - 选取距离最小的中心
j,将该点的标签设为labels[i] = j - 如果标签发生变化,则说明本轮有更新
2)更新聚类中心(Update Step)
-
对每个簇
j统计所有被分到簇j的点的坐标和及数量:sumX[j]、sumY[j]、cnt[j]
-
若
cnt[j] > 0,则新中心为:centers[j].x = sumX[j] / cnt[j]centers[j].y = sumY[j] / cnt[j]
-
若某个簇本轮没有点(
cnt[j] == 0),可以简单地保持原中心不变,避免除零与复杂操作。
三.收敛判断(提前结束)
如果某一轮迭代中,所有点的标签都没有发生变化(即没有任何 labels[i] 更新),说明算法已经收敛,可以提前退出循环。
class Solution:
def kMeans(
self,
n: int,
k: int,
max_iter: int,
nums: List[List[float]]
) -> Tuple[List[List[str]], List[int]]:
"""
n: 点的数量
k: 聚类簇的数量
max_iter: 最大迭代次数
nums: 点的坐标列表 [[x1, y1], [x2, y2], ...]
返回值: (centers_str, labels)
centers_str: 每个中心坐标为 4 位小数的字符串 [["1.2345","2.0000"], ...]
labels: 每个点所属的簇编号 [c0, c1, ...]
"""
# 初始化聚类中心:直接取前 k 个点(浮点计算)
centers = [[float(nums[i][0]), float(nums[i][1])] for i in range(k)]
# 初始化每个点所属的簇标签,初始为 -1 表示未分配
labels = [-1] * n
for _ in range(max_iter):
changed = False # 标记本轮是否有标签变化
# 第一步:为每个点分配最近的簇
for i in range(n):
x, y = nums[i]
best_cluster = 0
# 初始距离取到第 0 个中心
dx = x - centers[0][0]
dy = y - centers[0][1]
best_dist = dx * dx + dy * dy
# 遍历其他中心,找到最近的
for j in range(1, k):
dx = x - centers[j][0]
dy = y - centers[j][1]
dist = dx * dx + dy * dy
if dist < best_dist:
best_dist = dist
best_cluster = j
# 如果标签发生变化,记录下来
if labels[i] != best_cluster:
labels[i] = best_cluster
changed = True
# 如果本轮没有任何标签变化,说明已经收敛,提前结束
if not changed:
break
# 第二步:根据新标签更新每个簇的中心
sum_x = [0.0] * k
sum_y = [0.0] * k
count = [0] * k
# 累加每个簇中的点坐标和
for i in range(n):
c = labels[i]
sum_x[c] += nums[i][0]
sum_y[c] += nums[i][1]
count[c] += 1
# 计算新的中心坐标(浮点数)
for j in range(k):
if count[j] > 0:
centers[j][0] = sum_x[j] / count[j]
centers[j][1] = sum_y[j] / count[j]
# 如果某个簇没有点,可以选择保持原中心不变
# 把中心转换成「固定 4 位小数」的字符串形式,补足尾部 0
centers_str: List[List[str]] = []
for x, y in centers:
centers_str.append([f"{x:.4f}", f"{y:.4f}"])
return centers_str, labels
题面描述
实现一个二维数据的 K-Means 聚类算法。
给定:
- 一个整数
n表示数据点数量; - 一个整数
k表示聚类数; - 一个整数
max_iter表示最大迭代次数; - 一个二维数组
nums,其中nums[i] = [xi, yi]表示第i个二维数据点的坐标。
你需要对 nums 中的 n 个点进行 K-Means 聚类,将它们划分为 k 个簇。在聚类过程中,允许最多进行 max_iter 次迭代(如果在此之前收敛则可以提前停止)。初始聚类中心:从数据点中选择读入进来的前 k 个点作为初始中心。
算法结束后,需要返回两个结果:
- 一个长度为
k的二维数组,表示最终的聚类中心坐标,形式为
[[x1, y1], [x2, y2], ..., [xk, yk]]。 - 一个长度为
n的整数数组,表示每个数据点所属的聚类标签,标签范围为[0, k - 1],顺序与nums中数据点的顺序一致。
注意:保留4位小数,误差容忍度 1e-3
示例
输入:
n = 4 , k = 2 , max_iter = 100
nums = [[1.0,1.0],[1.5,2.0],[5.0,8.0],[8.0, 8.0]]
输出:
[[1.25,1.5],[6.5,8.0]]
[0,0,1,1]
数据范围:
1 <= n <= 2 * 10^4
1 <= k <= 20
1 <= max_iter <= 100
-1e4 <= nums[i][0], nums[i][1] <= 1e4