Algorytm centroidów

Algorytm centroidów (k-średnich, ang. k-means) jest jednym z algorytmów stosowanym w analizie skupień, wykorzystywanym m.in. w kwantyzacji wektorowej. Algorytm nazywany jest także algorytmem klastrowym lub - od nazwisk twórców Linde, Buzo i Graya - algorytmem LBG.

Cel algorytmu centroidów

Celem algorytmu jest przypisanie do wektorów kodowych $r_i$ ($i \in [1,N]$) $M$ $n$-wymiarowych wektorów danych, przy jak najmniejszym średnim błędzie kwantyzacji.

Średni błąd kwantyzacji dany jest wzorem:

$D = \frac{1}{K} \sum_{i=1}^{K} d(x_i, r)$

gdzie $K$ jest liczbą elementów $x_i$ przypisanych do wektora kodowego $r$, natomiast $d$ miarą błędu kwantyzacji i najczęściej jest to błąd kwadratowy określany dla wektorów n-wymiarowych jako

$d(x,r) = \sum_{j=1}^{n} (x_j - r_j)^2$.

Przebieg algorytmu centroidów

Algorytm centroidów przebiega następująco:

1. Wybierz $N$ wektorów kodowych i określ maksymalny błąd kwantyzacji $e$.
2. $m := 0$ (iteracja)
3. $D_m := \infty$ (średni błąd kwantyzacji w m-tej iteracji)
4. Dopóki nie uzyskano zadowalającego rezultatu, powtarzaj:
   • Podziel $M$ wektorów danych na $N$ grup. Wektor $x_j$ ($j \in [1,M]$) jest przypisywany do $i$-tej grupy wtedy i tylko wtedy gdy zachodzi nierówność $d(x_j, r_i) \le d(x_j, r_k)$ dla wszystkich $r_k$ różnych od $r_i$.
   • Wyznacz średni błąd kwantyzacji: $D_m = \frac{1}{M} \sum_{i=1}^{M} d(x_i, r)$, przy czym do obliczeń brany jest wektor kodowy $r$ z tej grupy, do której został zakwalifikowany wektor danych $x_i$
   • Wyznacz centroidy dla wszystkich $i$ grup wektorów i przypisz je do wektorów kodowych $r_i$.
   • Jeśli $\frac{D_{m-1} - D_m}{D_m} < e$ zakończ (uzyskano wymaganą dokładność), w przeciwnym razie zwiększ $m$ i spróbuj jeszcze raz.

Algorytm sukcesywnie dopasowuje wektory kodowe do istniejących danych i w miarę potrzeb przesuwa błędnie zakwalifikowane wektory danych do innych grup. Problem stanowi jednak początkowy wybór wektorów kodowych (punkt 1 algorytmu).

Bibliografia

• J. B. MacQueen (1967): "Some Methods for classification and Analysis of Multivariate Observations", Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297
• J. A. Hartigan (1975) "Clustering Algorithms". Wiley.
• J. A. Hartigan and M. A. Wong (1979) "A K-Means Clustering Algorithm", Applied Statistics, Vol. 28, No. 1, p100-108.

Linki zewnętrzne

• Aplet obrazujący działanie algorytmu centroidów dla dwuwymiarowych wektorów
• K-means Java code
• Implementacja algorytmu w języku C

Zobacz też

• centroid
• grupowanie