Marigold: 高效的高維k-means聚類

ABSTRACT & 1 INTRODUCTION

• k-means的泛用性不必多說，但在高維空間中，由于距離計算的代價線性增加，所以在高維空間中k-means用得不多。
• 本文提出了一些k-means中距離計算剪枝的方法：
  1. 距離bounding scheme
  2. 基于多分辨率轉(zhuǎn)換的逐步計算
  3. 對三角不等式利用

2 BACKGROUND

2.2 Applying the triangle inequality

• 比較有意思的是下圖粉色這個不等式，x和中心ci的距離如果小于中心ci和cj距離的一半，那x一定離ci更近。

  • 推導(dǎo)很簡單就在圖中這段話。

    
    
    image.png

4 MARIGOLD

4.1 Applying the triangle inequality

首先是基于三角不等式的剪枝，發(fā)生在為每個點x分配centroid的時候：

1. 嘗試剪枝掉所有非當(dāng)前Centroid的Centroid，基于兩個不等式進行剪枝，
   • 一個是上文2.2提到的不等式，這里near[]是遍歷了所有的中心，找到和（當(dāng)前中心）最近的中心的距離的一半
   • 另一個是Hamerly下界，x和某聚類中心c的下界，可以由上一次迭代的該下界，和本次迭代c移動的距離構(gòu)成三角不等式，見我手繪圖。這個是Elkan下界，Hamerly下界是所有非當(dāng)前中心的Elkan下界的最小值。
   • 用于剪枝的還有一個上界，即Elkan上界，表示和當(dāng)前中心的距離上界，思想和Elkan下界是一樣的。
2. 如果剪不掉所有其它Centroid，那就要計算x和當(dāng)前中心的距離，然后逐個其它中心遍歷；
3. 嘗試剪枝某一個聚類中心，也是基于兩個不等式：
   • 一個是Elkan下界，剛才已經(jīng)說到了；
   • 一個是2.2的不等式。

4. 如果仍然剪枝不掉，只能計算和該聚類中心的精確距離。

   
   
   image.png
   
   
   7c85de0d0ac2d2bcbd8dcba0e71d00b.jpg

4.2 Leveraging stepwise distance calculations

使用DCT（Discrete Cosine Transformation）進行向量變換，分層計算距離，每層可得到下界距離進行剪枝，無法剪枝則繼續(xù)計算，算到最后一層即為真實距離。