K-means ++
Aug 28, 2017 · 1 min read
K-means算法在使用时需要指定初始时的聚类中心,指定的聚类中心不同,运算时间不同,得到的结果也不同。一般而言,对于初始点,会做多次随机选择。但是在数据规模比较大的情况下,纯粹随机获得的初始点,可能并不能保证运算效率。
K-means ++是一种有效改善k-means初始化的方法,他的思想很直观,让每个点等概率成为初始点的方法并不合理,应该让初始的聚类中心间的距离近尽量远。
算法描述(wikipedia):
- 随机选择一个点作为初始点
- 计算数据集中每个点到最近聚类中心的距离
- 选择一个新的数据点,计算方法:距离越大,被选为中心的概率越大
- 重复2和3直到k个聚类中心全部被选出来
- 利用这些初始点运行k-means算法
step-3:
dist = [step-2 result]
dist_choose = sum(dist) * random(0, 1)
for d in dist:
dist_choose -= d
loop until dist_choose < 0 另外还有一个问题,为什么不直接选取最远的点作为初始点?
这是因为我们不能保证最远的点作为初始点的结果是最优的,更不希望每次运行的k-means结果是相同的。