摘要: k k kMeans 是数据分布未知时最合适的聚类算法.
1. 基本思想
最大化簇的内聚性 (即同一簇的点距离较近), 最小化簇间的耦合性 (即不同簇的点距离较远).
其优化目标可以写为
min ∑ i d ( x i , c ( x i ) ) , (1) \min \sum_i d(x_i, c(x_i)), \tag{1} mini∑d(xi,c(xi)),(1)
其中 c ( x i ) c(x_i) c(xi) 是第 i i i 个对象 x i x_i xi 所处的簇的中心 (即将该簇所有点的特征值取平均获得的虚拟中心).
2. 算法
- Step 1. (确定老大) 随机选择 k k k 个点作为中心点.
- Step 2. (分派别) 对于任意对象, 计算它到这 k k k 个点的距离, 离谁最近, 就与它属于同一簇.
- Step 3. (重新选择老大) 每个簇求虚拟中心, 将其作为老大.
- Step 4. (判断是否收敛) 如果本轮的中心点与上一轮的中心点相同, 则结束; 否则转 Step 2.
3. 算法特点
- 与 k k kNN 的共同点在于, 都使用某个距离度量.
- 涉及迭代, 因此比 k k kNN 复杂.
- 初始点的选择会影响最终的结果. 很可能只收敛到局部最优解.
- 适合"球型"数据. 即每一簇从三维的角度来看都像一个球. 而并不适合于有较多离群点的数据. 所谓离群点, 可以认为是指离所有聚类中心的都挺远的数据点. 它会对 k k kMeans 的重心计算产生较大影响.
- 并不是在所有的数据集上, 都能很快收敛. 我试过的数据中, 有 50 轮都未收敛的, 干脆就凑合了.
4. 参数设置与距离度量
只有一个 k k k.
显然, k k k 越大, (1) 式的值就越小. 确定 k k k 值多大合适, 有可能比确定如何聚类更困难.
距离度量参见 k k kNN. 这方面两个算法确实相同.
5. 简单改进
- 删除离群点.
- 多次初始化聚类中心点, 选择 (1) 式最小化那个. 当数据集不大的时候, 局部最优解的个数并不多.
6. 常见误区
- 不知道 k k kMeans 是有优化目标的 (反正我初学的时候就不知道).
- 不知道 k k kMeans 仅保证局部最优.
- 小瞧了 k k kMeans 的适应性 (与小瞧 k k kNN 同理).
