ReConcept Lab
English 中文
图谱连接

草稿

K-Means 聚类

通过“分配到最近质心”和“把质心移到均值”这两个步骤反复划分数据点。

algorithm intermediate machine-learningclusteringalgorithms

Hook problem：没有标签时怎么分堆

假设地图上有一批点，但没有答案标签。你只知道想得到 k = 3 个紧凑的组。

朴素想法是凭眼睛画三个圈。**K-Means 聚类（K-Means clustering）**把这种直觉变成可重复的循环。

质心追着分配移动K-Means 在最近质心分配和均值重算之间交替。
a1a2a3b1b2b3c1c2c3outC1C2C3
1. assignassign-1

按平方距离，把每个点分给当前最近的质心。

2. updateupdate-1

把每个质心移动到分给它的样本均值处。

3. assignassign-2

用移动后的质心重新分配；只有边界附近的点可能改变。

4. donedone

在这个固定样本中，分配和质心已经一致，因此局部最优稳定。

First naive idea：中心只选一次

如果最初的中心有点偏，很多点就会被分到错误的堆里。一直固定这些中心，会把错误保留下来。

最小修补是：分配完点以后，让中心移动。

Core invention：先分配，再更新

K-Means 交替做两件事：

  1. 把每个点分配给最近的质心（centroid）。
  2. 把每个质心移动到分给它的点的均值位置。

它试图降低的目标是簇内平方误差：

∑i=1n∥xi−μci∥2\sum_{i=1}^{n}\lVert x_i-\mu_{c_i}\rVert^2

直观地说：每个点都为自己到所属簇质心的平方距离付出代价。

Interactive trace lab

聚类算法轨迹实验台

步骤 1/4: 按平方距离，把每个点分给当前最近的质心。

assign

不断移动质心，直到平方距离簇基本稳定。

centers

C1=(1, 1); C2=(6.20, 1); C3=(3.40, 5.60)

changed points

a1->C1, a2->C1, a3->C1, b1->C2, b2->C2, b3->C2, c1->C3, c2->C3, c3->C3, out->C3

Implementation sketch

while (assignmentsChanged) {
  assign each point to the nearest centroid;
  replace each centroid with the mean of its assigned points;
}

算法停止时得到的是局部最优，不保证是全局最好的聚类。

Correctness intuition and cost

分配步骤不会增加目标值，因为每个点都选择当前最便宜的质心。更新步骤也不会增加目标值，因为在固定簇内，均值能最小化平方距离和。

对于 n 个点、k 个簇、d 维特征、t 次迭代，常见实现的代价是 O(t n k d)。

Common confusions

  • k 要在算法运行前给定。
  • K-Means 假设簇大致紧凑、接近质心形状。
  • 不同初始质心可能得到不同局部最优。
  • 均值可能落在空白位置，不一定是真实数据点。
每个算法修补哪种痛点？这组算法按中心假设、密度假设、层级和软概率分开。
K-Means

不断移动质心，直到平方距离簇基本稳定。

K-Medoids

用真实样本点做中心，降低离群点的影响。

DBSCAN

从高密度邻域扩张簇，并把孤立点留作噪声。

OPTICS

按密度可达性排序点，而不是只选一个固定半径。

HDBSCAN

保留在多个密度层级中保持稳定的簇。

GMM 的 EM

在软成员概率估计和高斯参数更新之间交替。

Exercises

  1. 为什么 K-Means 使用距离，而不是参考标签？
  2. 如果某个簇又长又弯，会出现什么问题？
  3. 为什么两次不同随机初始化可能结果不同？

图谱连接 : K-Means 聚类