K-means 的基本流程

K-means 算法的基本流程如下:

  1. 随机取 K 个种子点。
  2. 然后对所有点求到这K个种子点的距离,假如点 Pi 离种子点 Si 最近,那么 Pi 属于 Si 点群
  3. 接下来,移动种子点到属于他的“点群”的中心。
  4. 然后重复第2)和第3)步,直到种子点没有移动。

其中求点群中心的算法,可以有更多的更灵活的公式:

  • Minkowski Distance 公式,λ 可以随意取值,可以是负数,也可以是正数,或是无穷大。
  • Euclidean Distance 公式,第一个公式 λ=2 的情况。
  • CityBlock Distance 公式,第一个公式 λ=1 的情况。

K-means 主要有两个缺陷:

  • K 是事先给定的,这个 K 值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。( ISODATA 算法通过类的自动合并和分裂,得到较为合理的类型数目 K)
  • K-means算法需要用初始随机种子点来搞,这个随机种子点太重要,不同的随机种子点会有得到完全不同的结果。(K-Means++ 算法可以用来解决这个问题,其可以有效地选择初始点)

K-means++ 算法的基本流程如下:

  1. 先从我们的数据库随机挑个随机点当“种子点”。
  2. 对于每个点,计算其和最近的一个“种子点”的距离 D(x) 并保存在一个数组里,把这些距离加起来得到 Sum(D(x))。
  3. 取一个随机值,用权重的方式来取计算下一个“种子点”。这个算法的实现是,先取一个能落在 Sum(D(x)) 中的随机值 Random,然后用 Random -= D(x),直到其 <=0,此时的点就是下一个“种子点”。
  4. 重复第(2)和第(3)步直到所有的K个种子点都被选出来。
  5. 进行 K-means 算法。
0%