średnie k || alias Scalable K-Means ++

Bahman Bahmani i in. wprowadzono k-średnich ||, która jest szybszą wersją k-średnich ++.

Algorytm ten pochodzi ze strony 4 ich pracy , Bahmani, B., Moseley, B., Vattani, A., Kumar, R., i Vassilvitskii, S. (2012). Skalowalne k-średnie ++. Postępowanie z VLDB Endowment , 5 (7), 622-633.

Niestety nie rozumiem tych wymyślnych greckich liter, więc potrzebuję pomocy, aby zrozumieć, jak to działa. O ile rozumiem, ten algorytm jest ulepszoną wersją k-średnich ++ i wykorzystuje nadpróbkowanie, aby zmniejszyć liczbę iteracji: k-średnich ++ musi iterować razy, gdzie jest liczbą pożądanych klastrów.$k$$k$

Dostałem bardzo dobre wyjaśnienie poprzez konkretny przykład działania k-średnich ++, więc użyję tego samego przykładu ponownie.

Przykład

Mam następujący zestaw danych:

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

$k = 3$ (liczba pożądanych klastrów)

$\ell = 2$ (współczynnik nadpróbkowania)

Zacząłem ją obliczać, ale nie jestem pewien, czy wszystko dobrze zrozumiałem i nie mam pojęcia o krokach 2, 4 lub 5.

• Krok 1: próbkuj punkt losowo równomiernie z$\mathcal{C} \leftarrow$$X$

  Powiedzmy, że pierwszym centroidem jest (tak samo jak w k-średnich ++)$(8,0)$

• Krok 2:$\psi \leftarrow \phi_X(\mathcal{C})$

  brak pomysłu

• Krok 3:

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

    Obliczamy kwadratowe odległości do najbliższego środka każdego punktu. W tym przypadku do tej pory mamy tylko jedno centrum .$(8,0)$

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

    (Ponieważ w tym przypadku.)$\ell = 2$

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

    Wybierz liczby losowe w przedziale . Powiedzmy, że i . Obejmują one przedziały i które odpowiadają odpowiednio czwartej i ósmej pozycji.$\ell = 2$$[0, 813)$$246.90$$659.42$$[379, 495)$$[633, 813)$

  • Powtórz to razy, ale co to jest (obliczone w kroku 2) w tym przypadku? $\mathcal{O}(\log \psi)$$\psi$

• Krok 4: Dla ustaw aby była liczbą punktów w bliższą niż jakikolwiek inny punkt w .$x \in \mathcal{C}$$w_x$$X$$x$$\mathcal{C}$
• Krok 5: Ponownie skup ważone punkty w na klastrów.$\mathcal{C}$$k$

Każda pomoc w ogóle lub w tym konkretnym przykładzie byłaby świetna.

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

l = 2 // współczynnik nadpróbkowania

k = 3 // nie. pożądanych klastrów

Krok 1:

Załóżmy, że pierwszym centroidem jest to . $\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)\}$

Krok 2:

$\phi_X(\mathcal{C})$ to suma wszystkich najmniejszych 2-normowych odległości (odległość euklidesowa) od wszystkich punktów ze zbioru do wszystkich punktów z . Innymi słowy, dla każdego punktu znaleźć odległość do najbliższego punktu w w końcowej obliczeniowych suma wszystkich tych minimalnych odległościach, po jednym dla każdego punktu .$X$$\mathcal{C}$$X$$\mathcal{C}$$X$

Oznacz za pomocą jako odległość od do najbliższego punktu w . Mamy wtedy .$d^2_{\mathcal{C}}(x_i)$$x_i$$\mathcal{C}$$\psi = \sum_{i=1}^{n}d^2_{\mathcal{C}}(x_i)$

W kroku 2 zawiera pojedynczy element (patrz krok 1), a jest zbiorem wszystkich elementów. Zatem w tym kroku to po prostu odległość między punktem w i . Zatem .$\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)$

Należy jednak pamiętać, że w kroku 3 stosowana jest ogólna formuła, ponieważ będzie zawierał więcej niż jeden punkt.$\mathcal{C}$

Krok 3:

W pętli wykonywane w uprzednio obliczonej.$log(\psi)$

Rysunki nie są takie, jak zrozumiałeś. Rysunki są niezależne, co oznacza, że będzie wykonywać losowanie dla każdego punktu . Zatem dla każdego punktu w , oznaczonego jako , oblicz prawdopodobieństwo z . Tutaj masz współczynnik podany jako parametr, to odległość do najbliższego centrum, a wyjaśniono w kroku 2.$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})$

Algorytm jest po prostu:

• iteruj w aby znaleźć wszystkie$X$$x_i$
• dla każdego obliczenia$x_i$$p_{x_i}$
• wygeneruj jednolitą liczbę w , jeśli jest mniejsza niż wybierz ją, aby utworzyć$[0, 1]$$p_{x_i}$$\mathcal{C'}$
• po zakończeniu wszystkich losowań uwzględnij wybrane punkty z do$\mathcal{C'}$$\mathcal{C}$

Zauważ, że na każdym kroku 3 wykonanym w iteracji (linia 3 oryginalnego algorytmu) spodziewasz się wybrać punktów z (można to łatwo pokazać, pisząc bezpośrednio wzór na oczekiwanie).$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;

Krok 4:

Prostym algorytmem jest utworzenie wektora o wielkości równej liczbie elementów w i zainicjowanie wszystkich jego wartości za pomocą . Teraz iteruj w (elementy nie wybrane jako centroidy), a dla każdego znajdź indeks najbliższego środka ciężkości (element z ) i zwiększ o . W końcu trzeba będzie wektor obliczone prawidłowo.$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]++;
}

Krok 5:

Biorąc pod uwagę wagi obliczone w poprzednim kroku, postępujesz zgodnie z algorytmem kmeans ++, aby wybrać tylko punktów jako początkowe centroidy. W ten sposób wykonasz dla pętli, w każdej pętli wybierając pojedynczy element, losowany losowo z prawdopodobieństwem, że każdy element jest . Na każdym kroku wybierasz jeden element i usuwasz go z kandydatów, usuwając również odpowiadającą mu wagę.$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)
  ... 
}  

Wszystkie poprzednie kroki są kontynuowane, podobnie jak w przypadku kmeans ++, przy normalnym przepływie algorytmu klastrowania

Mam nadzieję, że teraz jest jaśniej.

[Później, później edytuj]

Znalazłem także prezentację autorów, w której nie można jednoznacznie stwierdzić, że przy każdej iteracji można wybrać wiele punktów. Prezentacja jest tutaj .

[Późniejsza edycja wydania @ pera]

Oczywiste jest, że zależy od danych, a podniesiony przez ciebie problem byłby prawdziwym problemem, gdyby algorytm był wykonywany na jednym hoście / maszynie / komputerze. Należy jednak pamiętać, że ten wariant klastrowania kmeans jest dedykowany dużym problemom i działa na systemach rozproszonych. Co więcej, autorzy w poniższych akapitach powyżej opisu algorytmu stwierdzają, co następuje:$log(\psi)$

Zauważ, że rozmiar jest znacznie mniejszy niż rozmiar wejściowy; przekierowanie można zatem wykonać szybko. Na przykład w MapReduce, ponieważ liczba centrów jest niewielka, można je wszystkie przypisać do pojedynczej maszyny, a dowolny algorytm przybliżenia (taki jak k-średnia ++) może zostać użyty do grupowania punktów w celu uzyskania k centrów. Implementacja algorytmu MapReduce 2 została omówiona w rozdziale 3.5. Chociaż nasz algorytm jest bardzo prosty i nadaje się do naturalnej równoległej implementacji (w rundach ), wyzwaniem jest wykazanie, że ma on możliwe do udowodnienia gwarancje.$C$$log(\psi)$

Kolejną rzeczą do odnotowania jest następująca uwaga na tej samej stronie, która stwierdza:

W praktyce nasze wyniki eksperymentalne w rozdziale 5 pokazują, że wystarczy kilka rund, aby znaleźć dobre rozwiązanie.

Co oznacza, że ​​możesz uruchomić algorytm nie dla czasów , ale dla danego stałego czasu.$log(\psi)$