Kmeans是种相当简单优雅的聚类算法,被用在各种地方,而是各种聚类算法的baseline,也有很多算法用它当做后处理的手段。

最初是电话面试的时候被问到spark mllib里面一些算法的实现技巧,在分布式时候的优化,=。=,我还真没看过这么多源码,于是我就去翻了一翻,虽然现在也没弄懂他到底想问我什么。不过,仔细看看这种代码,感觉确实有很多Real World技巧可以学习。

Kmeans++到Kmeans||

Kmeans++

我kmeans用了这么多年都是随机初始化的,效果不好多跑几次,当我看到这么麻烦的初始化算法的时候,一开始,我是拒绝的。不过,kmeans对初始化点敏感这个问题确实挺严重的,你要是一开始选的好几个点都在一个密集的簇里面,那他们基本就别想分开了。所以就有了Kmeans++这种初始化方法。话说这篇07年的论文有1600+引用也是说明了重要性。

先定义基本问题,kmeans要做

\[\phi = \sum_{x \in \mathcal{X}} min_{c \in \mathcal{C}} ||x - c||^2\]

即是每一个元素x的到其最近中心点的距离和最小。

定义\(D(x)\)为一个数据点到其我们已经选择的聚类中心中最近的距离。

k-means++算法:

  1. 从数据\(\mathcal{X}\)中以均匀分布选择一个\(x\)作为\(c_1\)

  2. \(\frac{D(x)^2}{\sum_{x \in \mathcal{X}}D(x)^2}\)概率选择一个新的中心\(c_i\)

  3. 重复第二步直到我们得到所有中心。

这里有点问题的可能是第二步,如何从x中以概率生成点,我们需要先计算每个点到选择中心点的最近距离,然后生成一个随机数,乘以这个距离之和,最后计算累加值取最后一个小于累加值的那个。

1
2
3
4
5
6
7
8
9
10
11
C = data.simple(1)
for (i <- 1 until k) {
val sum = data.map(x => cost(findClosest(x, C), x)))
var cumulative = 0.0
var j = 0
while (j < data.size && cumulative < r) {
cumulative += cost(x, findClosest(x))
j += 1
}
center(i) = data(j - 1)
}

kmeans++的意义也容易理解,每次都倾向于选择离已经选择的中心点较远的点。

但是我们发现kmeans++本身难以并行,因为每一次的\(c_i\)依赖\(c_{i-1}\),所以就有接下来的kmeans||。

Kmeans||

kmeans||主要是修改了一点,主要是修改了中间随机选取点的过程。他每一次迭代中的采样的过程都是独立的,这样最后可能得到的中心点数目多于k,最后采用其他方法选择出来k个。

主要流程

  1. 随机采样一个点,作为C中的第一个点

  2. 对于每一个点x以\(p_x = \frac{l*d^d(x, C)}{\phi_X(C)}\)的概率选择它。

  3. 把选择的点加到C中。

  4. 迭代2 3步\(O(\phi(x))\)次。

  5. 对于C中的每一个点,计算其权值\(w_i\)为X中靠它最近的点的个数。

  6. 重新利用权值计算C中的点到k类。取其中心点为k的中心点。

这样,每次迭代中随机选取c中新点的时候,都可以并行化,而且最后第6步的操作只在一个较小的数据子集上,效率很高甚至单机就够了。

Spark mllib中的一些技巧

最后总结一些spark mllib中的一些技巧。

  • 所有的vector都同时缓存了norm,看以看到data中保存的是RDD[VectorWithNorm]也不是单纯的数据。这也是很多地方优化的基础。

  • 实现kmeans的时候,由于考虑到一次运行结果的不稳定性,所以在mmlib中的kmeans,可以通过指定runs参数,指定运行的次数。而多次运行,是并发的同时进行的。

  • kmeans||的每次采样中,缓存了之前计算的center到每个点的距离,所以每次只计算了新的中心点和每个点的距离

  • 查找最近的中心点的时候,不是真正计算的中心点的距离,而是利用不等式\(|a - b| \geq |a| - |b|\),用\(|a| - |b|\)这个下届来代替。这样在维度很高的情况下效率很高。(因为norm是预先计算好的)

  • 在计算两个点的距离的时候,也有个技巧。首先是计算相对误差应该为\(\epsilon\frac{||a||_2^2 + ||b||_2^2+2*||a^T*b||}{||a-b||^2_2}\)其上界为\(2*\epsilon\frac{||a||^2_2 + ||b||^2_2 }{(||a||_2 - ||b||_2)^2}\),后者不需要计算内积,所以更快。当这样计算能保证精度的时候,就用以及算出来的norm来计算距离。不然才直接计算距离.

废话

最近找工作,感觉自己平时看的是有点偏,也有些准备不充分的原因,那么多基础的东西居然没有立即反应过来,只能好好复习了。最近在尝试scalameta,作者很热心,每天都在gitter上,不过感觉工作量很大,scalacenter的会议居然可以看录像,感觉也很棒。




X