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.

Algorytm centroidów

Rodzaj	heurystyczny
Złożoność
Czasowa	w ogólności NP trudny. Dla stałych k i d: O(ndk+1 log n)

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})\leqslant 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
• K-means Java code. algorithm-code.com. [zarchiwizowane z tego adresu (2009-03-29)].