聚类算法

K-means 算法

算法步骤

  1. 随机确定好 k个聚类中心
  2. 根据离聚类中心最近的原则给样本点分类
  3. 根据分类后的样本点集合进行平均重新 计算聚类中心。返回2；
  4. 存在聚类中心差异小的时候，结束计算。

K值的挑选

  • cost function ： 分类后的样本点和聚类中心的方差作为代价函数。
  • K值变大，cost function 变小

Elbow method 可以确定变化的骤变点。该点是 K-cost function图像上曲率最大的点。

使用K-means进行图像分割

  1. 特征聚类
  2. 亮度聚类
  3. 颜色空间聚类

优点：

  1. 类密集且区别明显的时候，分类效果好
  2. 强的一致性
  3. 算法复杂度O(NMt)，处理大数据集是高效的

缺点：

  1. 初始化中心的选择影响收敛
  2. 需要预先给出k值
  3. 噪声敏感
  4. 收敛到局部最优解，可能效果感人。。

Mean shift

在数据空间中，确定一个圆区域，计算圆内数据质心，然后圆心漂移到质心，重新在圆内计算质心，直到圆心等于质心。即收敛，达到局部最小值。

另外一种表述，在窗口中计算均值漂移向量，变换密度窗口，重复计算变换直到收敛。

  • 不受噪声敏感(除三维颜色，还引入位置坐标信息)
  • 参数单一
  • 维度越高，聚类越慢
  • 重复计算(染色标记降低冗余)