Marigold: 高效的高维k-means聚类

ABSTRACT & 1 INTRODUCTION

• k-means的泛用性不必多说，但在高维空间中，由于距离计算的代价线性增加，所以在高维空间中k-means用得不多。
• 本文提出了一些k-means中距离计算剪枝的方法：
  1. 距离bounding scheme
  2. 基于多分辨率转换的逐步计算
  3. 对三角不等式利用

2 BACKGROUND

2.2 Applying the triangle inequality

• 比较有意思的是下图粉色这个不等式，x和中心ci的距离如果小于中心ci和cj距离的一半，那x一定离ci更近。

  • 推导很简单就在图中这段话。

    
    image.png

4 MARIGOLD

4.1 Applying the triangle inequality

首先是基于三角不等式的剪枝，发生在为每个点x分配centroid的时候：

1. 尝试剪枝掉所有非当前Centroid的Centroid，基于两个不等式进行剪枝，
   • 一个是上文2.2提到的不等式，这里near[]是遍历了所有的中心，找到和（当前中心）最近的中心的距离的一半
   • 另一个是Hamerly下界，x和某聚类中心c的下界，可以由上一次迭代的该下界，和本次迭代c移动的距离构成三角不等式，见我手绘图。这个是Elkan下界，Hamerly下界是所有非当前中心的Elkan下界的最小值。
   • 用于剪枝的还有一个上界，即Elkan上界，表示和当前中心的距离上界，思想和Elkan下界是一样的。
2. 如果剪不掉所有其它Centroid，那就要计算x和当前中心的距离，然后逐个其它中心遍历；
3. 尝试剪枝某一个聚类中心，也是基于两个不等式：
   • 一个是Elkan下界，刚才已经说到了；
   • 一个是2.2的不等式。

4. 如果仍然剪枝不掉，只能计算和该聚类中心的精确距离。

   
   image.png
   7c85de0d0ac2d2bcbd8dcba0e71d00b.jpg

4.2 Leveraging stepwise distance calculations

使用DCT（Discrete Cosine Transformation）进行向量变换，分层计算距离，每层可得到下界距离进行剪枝，无法剪枝则继续计算，算到最后一层即为真实距离。