概述

在 k-means, 我们使用了基于形心(簇均值)来对数据进行划分, 也讨论了 k-means 的初始值选取之重要, 若选得不好, 很容易陷入局部最优解的问题.
实质上来说, 我们会陷入到局部最优解的本质原因是:

• 当初始值选定之后, 我们有一个初始的簇
• 均值基本是在这个簇的最大值与最小值之间
• 每次更新的新的质心(均值)之后, 我们的簇只会有很小的移动, 因为均值无法跳出初始簇的范围

就像, 你已经给定了初始的形状, 而我们只是在这个初始形状上进行增减, 自然很难得到全局的最好的簇了

算法

下面给出 k-中心点的主要算法, 可以与 k-means 做比较

整体算法

1. 初始化选择 k 个质心 (随机选择, 或者领域知识选择), 该选择决定了聚类的速度与效果
2. 为所有点划分簇
3. 计算该种划分的损失
4. 当该损失还能减小时循环以下:
   对于每个质心(k个)执行:
   a. 随机选择一个新的点
   b. 以新的点代替这个质心
   c. 重新对所有数据划分簇
   d. 计算划分的损失
   e. 若 新的损失小于原先的损失, 则 用新的点代替原质心

损失计算

一种简单的方法是每个簇离质心方差的和
$$\sum _{i=1}^k\sqrt{\sum _j^n(d_j-d_k{)}^2}$$

优化

• 原始算法被称为 PAＭ 算法, 特点在于c, d步, 这里对所有数据进行了重新计算损失, 所以只能用于小型数据集.
• 优化方法是 CLARA算法, 该算法将c,d步改为对抽样数据计算损失, 减少了计算量, 但是, 若在抽样时正好丢失了 最好的 质心, 那么, 将永远无法找到最佳聚类!

优点

• 跳出均值的局部最优
• 不容易受离群点与噪声的影响

缺点

• 时间复杂度高

讨论

• 可以看到, 这个算法每次代表的选取是从整个数据集随机选取, 因此跳出了初始簇的范围, 使得算法有很大的概率跳出局部最优解, 从而在迭代种得到全局最优解
• 损失函数的选择对效率与结果很重要, 可以尝试其他的损失函数选择

实现