kmeans++和kmeans||

kmeans是经典的聚类算法,但是它有两个缺点:

1)k值不好确定;

2)初始值敏感,不同的初始值得到的聚类结果差异很大。


对于第一点我们无能为力。

对于第二点,常用的办法是多迭代几次,选择使得代价函数最小的初始值。但是这无疑增加了计算量,而且容易把两个聚类中心初始化到一个聚类里。如下图所示。

kmeans++和kmeans||

一些学者就提出了一些改进方法。


kmeans++

首先介绍kmeans++,它的思想是尽可能的让聚类中心分散开。算法流程如下:

  • 随机选取一个聚类中心C1

  • 重复k-1次

    • 对于数据集中的每个点xi,计算x到已经确定的聚类中心的距离D(xi)

    • 以一定的概率从数据集中选择一个点x0作为新的聚类中心,D(xi)越大,被选择的概率越大


    我们看一下kmeans++初始化聚类中心的迭代过程:

    kmeans++和kmeans||kmeans++和kmeans||

    kmeans++和kmeans||kmeans++和kmeans||


kmeans++以上面的方式初始化了k个聚类中心。从上面可以看出,它基于已经确定的聚类中心来选择下一个聚类中心,距离确定的聚类中心越大的点越容易被选为聚类中心,从而使得聚类中心之间的距离尽可能大。

但是优点也是它的缺点,由于选择新的聚类中心需要依赖确定的聚类中心,它需要迭代k次,不能并行计算。不能大规模计算。


kmeans||

kmeans++每次迭代只选择一个样本作为聚类中心,kmeans|| 作出的改变是每次迭代选取多个样本,最后使用kmeans++从这些选择出来的样本选出k个初始聚类中心作为整体数据的初始聚类中心。

算法流程:

  • 选择过采样因子 l>1

  • 随机初始化第一个聚类中心C

  • 迭代R次:

    • 选择出满足一定概率条件的样本点

    • 将这些样本点加入C构成聚类中心候选集C'

  • 从C'中选出k个聚类中心


下面我们来看一下迭代过程,oversampling factor就是每次迭代选取的样本个数。

kmeans++和kmeans||

kmeans++和kmeans||

kmeans++和kmeans||

从这7个候选聚类中心中选择出4个聚类中心

kmeans++和kmeans||



参考:http://web.stanford.edu/group/mmds/slides2012/s-bahmani.pdf

评论

Live Sex Cams Free