Algorytm centroidów

Szablon:Algorytm infobox 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

Szablon:Dopracować 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:=\mathrm{\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)⩽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).

Zobacz też

• centroid
• DBSCAN
• grupowanie

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, s. 100–108.

Linki zewnętrzne

• Aplet obrazujący działanie algorytmu centroidów dla dwuwymiarowych wektorów
• Szablon:Cytuj stronę