К средних || aka Scalable K-Means ++

Бахман Бахмани и соавт. представил k-means ||, который является более быстрой версией k-means ++.

Этот алгоритм взят из страницы 4 их работы , Бахмани Б., Мозли Б., Ваттани А., Кумар Р. и Васильвицкий С. (2012). Масштабируемое k-означает ++. Труды фонда VLDB , 5 (7), 622-633.

К сожалению, я не понимаю эти причудливые греческие буквы, поэтому мне нужна помощь, чтобы понять, как это работает. Насколько я понимаю, этот алгоритм является улучшенной версией k-means ++, и он использует передискретизацию для сокращения числа итераций: k-means ++ должен выполнить итерацию раз, где $k$$k$ - количество требуемых кластеров.

Я получил очень хорошее объяснение на конкретном примере того, как работает k-means ++, поэтому я снова буду использовать тот же пример.

пример

У меня есть следующий набор данных:

(7,1), (3,4), (1,5), (5,8), (1,3), (7,8), (8,2), (5,9), (8 , 0)

(количество желаемых кластеров)$k = 3$

(коэффициент передискретизации)$\ell = 2$

Я начал вычислять это, но я не уверен, правильно ли я понял, и понятия не имею о шагах 2, 4 или 5.

• Шаг 1: выборка точки случайным образом из $\mathcal{C} \leftarrow$$X$

  Скажем, первый центроид (такой же, как в k-means ++)$(8,0)$

• Шаг 2: $\psi \leftarrow \phi_X(\mathcal{C})$

  без понятия

• Шаг 3:

  • $d^2(x, \mathcal{C}) = [2, 41, 74, 73, 58, 65, 4, 90]$

    Мы рассчитываем квадрат расстояния до ближайшего центра к каждой точке. В этом случае у нас пока только один центр .$(8,0)$

  • $\ell \cdot d^2(x, \mathcal{C}) = [4, 81, 148, 146, 116, 130, 8, 180]$

    (Потому что в этом случае )$\ell = 2$

  • $\text{cumulative } \ell \cdot d^2(x, \mathcal{C}) = [4, 85, 233, 379, 495, 625, 633, 813]$

    Выберите случайных числа в интервале [ 0 , 813 $\ell = 2$$[0, 813)$ . Допустим, вы выбрали и 659,42 . Они попадают в диапазоны [ 379 , 495 ) и [ 633 , 813 ), которые соответствуют 4-му и 8-му пунктам соответственно.$246.90$$659.42$$[379, 495)$$[633, 813)$

  • Повторите это раз, но что такое ψ (рассчитывается на шаге 2) в этом случае? $\mathcal{O}(\log \psi)$$\psi$

• Шаг 4: Для , множество ш й будет число точек в X ближе к й , чем любой другой точке C .$x \in \mathcal{C}$$w_x$$X$$x$$\mathcal{C}$
• Шаг 5: Перегруппируйте взвешенные точки в в k кластеров.$\mathcal{C}$$k$

Любая помощь в целом или в этом конкретном примере будет отличной.

Точки данных: (7,1), (3,4), (1,5), (5,8), (1,3), (7,8), (8,2), (5,9) , (8,0)

l = 2 // коэффициент передискретизации

k = 3 // нет. желаемых кластеров

Шаг 1:

$\mathcal{C}$$\{ c_1\} = \{ (8,0) \}$$X = \{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8\}=\{(7,1),(3,4),(1,5),(5,8),(1,3),(7,8),(8,2),(5,9)\}$

Шаг 2:

$\phi_X(\mathcal{C})$$X$$\mathcal{C}$$X$$\mathcal{C}$$X$

$d^2_{\mathcal{C}}(x_i)$$x_i$$\mathcal{C}$$\psi = \sum_{i=1}^{n}d^2_{\mathcal{C}}(x_i)$

$\mathcal{C}$$X$$d^2_{\mathcal{C}}(x_i)$$\mathcal{C}$$x_i$$\phi = \sum_{i=1}^{n}{||x_i-c||^2}$

$\psi = \sum_{i=1}^nd^2(x_i,c_1) = 1.41+6.4+8.6+8.54+7.61+8.06+2+9.4 = 52.128$ $log(\psi) = log(52.128) = 3.95 = 4 (rounded)$

$\mathcal{C}$

Шаг 3:

$log(\psi)$

$X$$X$$x_i$$p_x = l d^2(x,\mathcal{C})/\phi_X(\mathcal{C})$$l$$d^2(x,\mathcal{C})$$\phi_X(\mathcal{C})$ объясняется на шаге 2.

Алгоритм прост:

• $X$$x_i$
• $x_i$$p_{x_i}$
• $[0, 1]$$p_{x_i}$$\mathcal{C'}$
• $\mathcal{C'}$$\mathcal{C}$

$l$$X$

for(int i=0; i<4; i++) {

  // compute d2 for each x_i
  int[] psi = new int[X.size()];
  for(int i=0; i<X.size(); i++) {
    double min = Double.POSITIVE_INFINITY;
    for(int j=0; j<C.size(); j++) {
      if(min>d2(x[i],c[j])) min = norm2(x[i],c[j]);
    }
    psi[i]=min;
  }

  // compute psi
  double phi_c = 0;
  for(int i=0; i<X.size(); i++) phi_c += psi[i];

  // do the drawings
  for(int i=0; i<X.size(); i++) {
    double p_x = l*psi[i]/phi;
    if(p_x >= Random.nextDouble()) {
      C.add(x[i]);
      X.remove(x[i]);
    }
  }
}
// in the end we have C with all centroid candidates
return C;

Шаг 4:

$w$$\mathcal{C}$$0$$X$$x_i \in X$$j$$\mathcal{C}$$w[j]$$1$$w$ рассчитанный правильно.

double[] w = new double[C.size()]; // by default all are zero
for(int i=0; i<X.size(); i++) {
  double min = norm2(X[i], C[0]);
  double index = 0;
  for(int j=1; j<C.size(); j++) {
    if(min>norm2(X[i],C[j])) {
      min = norm2(X[i],C[j]);
      index = j;
    }
  }
  // we found the minimum index, so we increment corresp. weight
  w[index]++;
}

Шаг 5:

$w$$k$$k$$p(i) = w(i)/\sum_{j=1}^m{w_j}$

for(int k=0; k<K; k++) {
  // select one centroid from candidates, randomly, 
  // weighted by w
  // see kmeans++ and you first idea (which is wrong for step 3)
  ... 
}  

Все предыдущие шаги продолжаются, как в случае с kmeans ++, с нормальным потоком алгоритма кластеризации

Надеюсь, теперь стало понятнее.

[Позже, позже отредактируйте]

Я также нашел презентацию, сделанную авторами, в которой вы не можете ясно, что на каждой итерации может быть выбрано несколько точек. Презентация здесь .

[Позже отредактируйте проблему @ pera]

$log(\psi)$

$C$$log(\psi)$

Еще одна вещь, которую стоит отметить, это следующее примечание на той же странице, где говорится:

На практике наши экспериментальные результаты в разделе 5 показывают, что для достижения хорошего решения достаточно всего нескольких раундов.

$log(\psi)$