知识卡片
K-Means 的分配与更新
K-Means 的目标可以写成一句话:把 M 个样本分成 K 个簇,使每个样本到它所属簇中心的距离平方之和最小。设簇 C_k 的均值向量为 μ_k、簇内样本数为 N_k,则损失为各簇”样本到均值向量的均方误差”之和;这个量越小,簇越紧凑。
难点在于”分到哪个簇”和”中心在哪”互相依赖,无法一次解出。K-Means 用坐标下降式的交替优化绕开它:
- 分配:固定 K 个中心,把每个样本归到距离最近的中心(欧氏距离最常用)。
- 更新:固定归属,把每个簇的中心换成该簇所有样本的均值——对给定的划分,均值正是使该簇平方误差最小的点,所以这一步一定不会让损失变大。
- 判断:重复 1、2,直到连续两次损失值之差小于设定阈值、中心不再移动,或达到最大迭代次数。
因为每一步都不增加损失,而划分方式只有有限种,迭代必然停在某个局部极小;但停在哪里取决于初始中心,这就是”K-Means 是受初始值影响的局部最优迭代算法”的含义。也因此实践中要跑多组初值取最优(见 [[K-Means调参的四个抓手]]),并用 [[k-means++选初始中心]] 改善起点。
结构图:
flowchart TD
A[随机选 K 个初始中心] --> B[每个样本归入最近中心]
B --> C[用簇内均值更新中心]
C --> D{中心或损失还变吗}
D -- 是 --> B
D -- 否 --> E[输出 K 个簇]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第12章 聚类
原书出处 · 1 处
- 第12章 聚类 12.2.1 K-Means聚类过程和原理 · 查看原书依据
可以看到,虽然刚开始时是随机选择的两个点作为初始聚类中心,但经过反复迭代第2步和第3步后,最终聚类中心会逐渐趋于稳定,如图12-2(f)所示;聚类中心稳定后,所有样本点的划分也会趋于稳定,从而达到比较理想的聚类效果。
参考来源
- 位置:《机器学习基础:从入门到求职》第12章《第12章 聚类》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00015.html)
- 结论依据:原文给出 K-Means"簇内紧凑、簇间分开"的核心思想、四步迭代流程(选中心—分配—重算均值—重复至损失稳定)以及以均方误差为损失函数的定义。
- 原始内容:可以看到,虽然刚开始时是随机选择的两个点作为初始聚类中心,但经过反复迭代第2步和第3步后,最终聚类中心会逐渐趋于稳定,如图12-2(f)所示;聚类中心稳定后,所有样本点的划分也会趋于稳定,从而达到比较理想的聚类效果。