Algorytm centroidów

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)

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

Ten artykuł wymaga uzupełnienia informacji. Artykuł należy uzupełnić o istotne informacje: algorytm centroidów jest stosowany do analizy skupień. Kwantyzacja wektorowa to tylko jedno z zastosowań. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

Średni błąd kwantyzacji dany jest wzorem:

${\displaystyle D={\frac {1}{K}}\sum _{i=1}^{K}d(x_{i},r),}$

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

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