"""用固定初始中心运行 Lloyd 算法,并比较两次聚类的簇内平方和。""" import json import matplotlib.pyplot as plt import numpy as np def assign(points, centers): # points[:, None, :] 与 centers[None, :, :] 广播后逐对相减。 # 三个轴依次表示样本、中心、坐标,沿坐标轴累加得到平方距离。 distance2 = np.sum((points[:, None, :] - centers[None, :, :]) ** 2, axis=2) # 对每行找最近的中心。并列时 argmin 取最先出现的中心索引。 labels = distance2.argmin(axis=1) # 对每个样本只取归属簇的距离平方,汇总得到簇内平方和。 objective = distance2[np.arange(len(points)), labels].sum() return labels, float(objective) def lloyd(points, initial_centers, *, max_updates=100): # 复制初值。历史快照也单独复制,防止后续更新覆盖先前的轨迹。 centers = initial_centers.copy() labels, objective = assign(points, centers) center_path, loss_path = [centers.copy()], [objective] for step in range(max_updates + 1): next_centers = centers.copy() for k in range(len(centers)): members = points[labels == k] # 若没有成员,保留该中心。成熟库也可能将它移到较远样本。 if len(members): # 固定簇成员时,各列的均值让该簇到中心的距离平方和最小。 next_centers[k] = members.mean(axis=0) # 新旧中心完全一致,在固定并列规则下再次分配也不会改变。 if np.array_equal(centers, next_centers): return centers, labels, np.array(center_path), loss_path # 最后一轮只检查收敛,已用完更新预算时不再移动中心。 if step == max_updates: break centers = next_centers labels, objective = assign(points, centers) center_path.append(centers.copy()) loss_path.append(objective) raise RuntimeError(f"Lloyd iteration did not converge within {max_updates} updates") def run(): # 三组无标签教学数据。两个坐标已经在可直接比较的尺度上。 points = np.array([[1, 1], [1, 2], [2, 1], [4, 1], [4, 2], [5, 1], [8, 6], [8, 7], [9, 6]], dtype=float) centers, labels, path, losses = lloyd(points, points[[0, 3, 6]]) _, other_labels, _, other_losses = lloyd(points, points[[0, 1, 6]]) # 左图看中心迁移与最终分组;右图用初始分配作为第 0 步比较目标下降。 fig, (left, right) = plt.subplots(1, 2, figsize=(8.5, 3.8), layout="constrained") for k in range(len(centers)): members = points[labels == k] color = f"C{k}" left.scatter(members[:, 0], members[:, 1], color=color, label=f"Cluster {k+1}") left.plot(path[:, k, 0], path[:, k, 1], "x--", color=color, alpha=0.85) left.scatter(*centers[k], color=color, marker="P", s=90, edgecolor="black") left.set(xlabel="Feature 1", ylabel="Feature 2", aspect="equal", title="Default center paths") left.legend(fontsize=8) right.plot(range(len(losses)), losses, "o-", label="Start rows 1, 4, 7") right.plot(range(len(other_losses)), other_losses, "s--", label="Start rows 1, 2, 7") right.set(xlabel="Completed updates", ylabel="Within-cluster sum of squares") right.legend(fontsize=8) fig.suptitle("K-means with fixed initialization") # 两点是否同簇用 0/1 表示。交换簇号不影响这个矩阵。 return { "centers": centers.tolist(), "cluster_sizes": np.bincount(labels, minlength=len(centers)).tolist(), "objective_trace": losses, "alternate_objective_trace": other_losses, "same_cluster": (labels[:, None] == labels).astype(int).tolist(), "alternate_same_cluster": (other_labels[:, None] == other_labels).astype(int).tolist(), } if __name__ == "__main__": print("LAB_RESULT " + json.dumps(run(), allow_nan=False)) plt.show()