k-bedeutet || aka Scalable K-Means ++

Bahman Bahmani et al. Einführung von k-means ||, einer schnelleren Version von k-means ++.

Dieser Algorithmus stammt von Seite 4 ihrer Veröffentlichung Bahmani, B., Moseley, B., Vattani, A., Kumar, R. und Vassilvitskii, S. (2012). Skalierbares k-means ++. Verfahren der VLDB-Stiftung , 5 (7), 622-633.

Leider verstehe ich diese ausgefallenen griechischen Buchstaben nicht, daher brauche ich Hilfe, um zu verstehen, wie das funktioniert. Soweit ich weiß, ist dieser Algorithmus eine verbesserte Version von k-means ++ und verwendet Oversampling, um die Anzahl der Iterationen zu verringern: k-means ++ muss mal iterieren , wobei$k$ die Anzahl der gewünschten Cluster ist.$k$

ich habe eine sehr gute Erklärung durch ein konkretes Beispiel bekommen, wie k-means ++ funktioniert, also werde ich dasselbe Beispiel wieder verwenden.

Beispiel

Ich habe folgenden Datensatz:

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

(Anzahl der gewünschten Cluster)$k = 3$

(Überabtastungsfaktor)$\ell = 2$

Ich habe angefangen, es zu berechnen, bin mir aber nicht sicher, ob ich es richtig gemacht habe und habe keine Ahnung von den Schritten 2, 4 oder 5.

• Schritt 1: einen Punkt gleichmäßig zufällig von $\mathcal{C} \leftarrow$$X$

  Angenommen, der erste Schwerpunkt ist (wie in k-means ++).$(8,0)$

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

  keine Ahnung

• Schritt 3:

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

    Wir berechnen die quadratischen Abstände zum nächstgelegenen Zentrum zu jedem Punkt. In diesem Fall haben wir bisher nur ein Zentrum .$(8,0)$

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

    (Weil in diesem Fall ist.)$\ell = 2$

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

    Wählen Sie Zufallszahlen im Intervall [ 0 , 813 ) . Angenommen, Sie wählen 246,90 und 659,42 . Sie fallen in die Bereiche [ 379 , 495 ) und [ 633 , 813 ), die dem 4. bzw. 8. Posten entsprechen.$\ell = 2$$[0, 813)$$246.90$$659.42$$[379, 495)$$[633, 813)$

  • Wiederhole es mal, aber was ist in diesem Fall ψ (berechnet in Schritt 2)? $\mathcal{O}(\log \psi)$$\psi$

• Schritt 4: Für , Set w x die Anzahl der Punkte in seinen X näher an x als jeder anderen Punkt C .$x \in \mathcal{C}$$w_x$$X$$x$$\mathcal{C}$
• Schritt 5: Rekluster der gewichteten Punkte in in k Cluster.$\mathcal{C}$$k$

Jede Hilfe im Allgemeinen oder in diesem speziellen Beispiel wäre großartig.

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

l = 2 // Überabtastungsfaktor

k = 3 // nein. von gewünschten Clustern

Schritt 1:

Angenommen, der erste Schwerpunkt ist ist { 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 ) , ( $\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)\}$

Schritt 2:

ist die Summe aller kleinsten 2-Norm Abstände (euklidische Distanz) von allen Punkten aus dem Satz X auf alle Punkte von C . Mit anderen Worten, ermittle für jeden Punkt in X die Entfernung zum nächsten Punkt in C und berechne am Ende die Summe aller dieser minimalen Entfernungen, eine für jeden Punkt in$\phi_X(\mathcal{C})$$X$$\mathcal{C}$$X$$\mathcal{C}$$X$ .

Bezeichne mit als der Abstand von x i zu dem nächsten Punkt in C . Wir haben dann ψ = ∑ n i = 1 d 2 C ( x i ) .$d^2_{\mathcal{C}}(x_i)$$x_i$$\mathcal{C}$$\psi = \sum_{i=1}^{n}d^2_{\mathcal{C}}(x_i)$

In Schritt 2 enthält ein einzelnes Element (siehe Schritt 1) ​​und X ist die Menge aller Elemente. Somit ist in diesem Schritt d 2 C ( x i ) einfach der Abstand zwischen dem Punkt in C und x i . Also ist ϕ = ∑ n i = 1 | | x i - c | | 2 .$\mathcal{C}$$X$$d^2_{\mathcal{C}}(x_i)$$\mathcal{C}$$x_i$$\phi = \sum_{i=1}^{n}{||x_i-c||^2}$

l o g ( ψ ) = l o g ( 52,128 ) = 3,95 = 4 ( r o u n d e $\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)$

Beachten Sie jedoch, dass in Schritt 3 die allgemeine Formel angewendet wird, da mehr als einen Punkt enthält.$\mathcal{C}$

Schritt 3:

Die for- Schleife wird für zuvor berechnet wurde.$log(\psi)$

Die Zeichnungen sind nicht so, wie Sie es verstanden haben. Die Zeichnungen sind unabhängig, was bedeutet, dass Sie für jeden Punkt in eine Zeichnung ausführen . So wird für jeden Punkt in X , bezeichnet als x i , Berechnen einer Wahrscheinlichkeit von P x = l d 2 ( x , C ) / φ X ( C ) . Hier haben Sie l einen Faktor als Parameter angegeben, d 2 ( x , C ) ist der Abstand zum nächstgelegenen Zentrum, und ϕ X ( C$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})$ wird in Schritt 2 erklärt.

Der Algorithmus ist einfach:

• iterieren Sie in , um alle x i zu finden$X$$x_i$
• für jedes berechnet i p x $x_i$$p_{x_i}$
• eine einheitliche Zahl in generiert , wenn kleiner als ist p x i es auswählen bilden C $[0, 1]$$p_{x_i}$$\mathcal{C'}$
• Nachdem Sie fertig sind, schließen alle Zeichnungen ausgewählte Punkte von nach $\mathcal{C'}$$\mathcal{C}$

Beachten Sie, dass Sie bei jedem Schritt 3, der in der Iteration ausgeführt wird (Zeile 3 des ursprünglichen Algorithmus), erwarten, dass Sie Punkte aus X auswählen (dies wird leicht gezeigt, indem Sie direkt die Formel für die Erwartung schreiben).$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;

Schritt 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]++;
}

Schritt 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)
  ... 
}  

Alle vorherigen Schritte werden wie im Fall von kmeans ++ mit dem normalen Ablauf des Clustering-Algorithmus fortgesetzt

Ich hoffe es ist jetzt klarer.

[Später, später bearbeiten]

Ich habe auch eine Präsentation von Autoren gefunden, bei der man nicht klar erkennen kann, dass bei jeder Iteration mehrere Punkte ausgewählt werden könnten. Die Präsentation ist hier .

[Später bearbeiten @ pera Ausgabe]

$log(\psi)$

$C$$log(\psi)$

Eine andere Anmerkung ist die folgende Anmerkung auf derselben Seite, die besagt:

In der Praxis zeigen unsere experimentellen Ergebnisse in Abschnitt 5, dass nur wenige Runden ausreichen, um eine gute Lösung zu erreichen.

$log(\psi)$