K-means ++

tao zhan
tao zhan
Aug 28, 2017 · 1 min read

K-means算法在使用时需要指定初始时的聚类中心,指定的聚类中心不同,运算时间不同,得到的结果也不同。一般而言,对于初始点,会做多次随机选择。但是在数据规模比较大的情况下,纯粹随机获得的初始点,可能并不能保证运算效率。

K-means ++是一种有效改善k-means初始化的方法,他的思想很直观,让每个点等概率成为初始点的方法并不合理,应该让初始的聚类中心间的距离近尽量远。

算法描述(wikipedia):

  1. 随机选择一个点作为初始点
  2. 计算数据集中每个点到最近聚类中心的距离
  3. 选择一个新的数据点,计算方法:距离越大,被选为中心的概率越大
  4. 重复2和3直到k个聚类中心全部被选出来
  5. 利用这些初始点运行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结果是相同的。

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade