K-means · Lloyd 交替优化

每次只动一半,目标为什么不会上升?

固定质心时,每个点选最近的一簇;固定归属时,每个质心移动到成员均值。把两步拆开,你能直接看到每次选择怎样压低同一个簇内平方和。

亲手走一轮“分配 → 更新”

拖动任一样本或质心。键盘操作时,先 Tab 聚焦图中对象,再用方向键移动;按住 Shift 可加快步幅。

三团 · 分散初始化
二维点集与三个质心 虚线连接当前归属;粗虚线箭头显示最近一次质心移动
Lloyd 算法二维分配与更新图 图中包含可拖动的样本点和三个质心。分配后显示每个点到所属质心的连线,更新后显示质心移动箭头。
  • 簇 A
  • 簇 B
  • 簇 C
  • 可拖动质心

把质心移动和 J 的下降对上

更新步骤把每个非空簇的质心放到成员均值。空簇没有均值,本实验明确保留它的旧质心。

运行账本

质心状态

出现空簇:该簇本轮保留旧质心。真实实现也可以选择重新播种,但必须提前规定策略。

目标函数轨迹

每个点是一项合法的分配或更新;横轴是步骤,纵轴是 J。

    执行第一步后,这里会记录 J 与相对上一步的下降。

    单调下降不等于全局最优

    每一步都把一半变量优化到当前最优,但分配和质心的联合问题仍然非凸。

    读图边界
    分配为什么不会让 J 上升?

    质心固定时,每个样本独立选择平方距离最小的质心。原归属仍是候选之一,所以换成最近质心后的总和不会更大;完全等距时按固定编号打破平局。

    更新为什么一定去成员均值?

    固定成员集合后,到同一中心的平方距离和关于中心是凸二次函数。它的零梯度点就是成员坐标的算术平均,这一步给出当前分配下的精确最小值。

    怎样看“较优”和“较差”局部解?

    四团数据只给三个中心时,必须合并一对团块。两种预设分别合并更近和更远的一对;它们都能停止,但终点 J 不同。这就是初始化影响局部终点的直接例子。

    拖动以后为什么要清空历史?

    拖动质心改变初始化,拖动样本改变数据。Lloyd 的单调性只比较同一问题里连续的合法步骤,不能把人为改图前后的 J 接成一条算法轨迹。

    建议先让“较优局部解”和“较差局部解”各自自动收敛,再比较最终 J。两条轨迹都单调下降,却停在不同高度;这正是多次初始化仍然必要的原因。