Algorytm centroidów
Z Wikipedii
Algorytm centroidów jest jednym z algorytmów kwantyzacji wektorowej, nazywany jest także algorytmem klastrowym lub - od nazwisk twórców Linde, Buzo i Graya - algorytmem LBG.
Celem algorytmu jest przypisanie do wektorów kodowych ri (![i \in [1,N]](../../../math/3/2/0/320fc36a1f0930aab2a3db6f3b24429f.png)
) M n-wymiarowych wektorów danych, przy jak najmniejszym średnim błędzie kwantyzacji.
Średni błąd kwantyzacji dany jest wzorem:
gdzie K jest liczbą elementów xi 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 
.
Algorytm centroidów przebiega następująco:
- Wybierz N wektorów kodowych i określ maksymalny błąd kwantyzacji e.
- m: = 0 (iteracja)
(średni błąd kwantyzacji w m-tej iteracji)- Dopóki nie uzyskano zadowalającego rezultatu, powtarzaj:
- Podziel M wektorów danych na N grup. Wektor xj (
![j \in [1,M]](../../../math/a/b/e/abe4e837d8445676a914534ab62432fc.png)
) jest przypisywany do i-tej grupy wtedy i tylko wtedy gdy zachodzi nierówność 
dla wszystkich rk różnych od ri. - Wyznacz średni błąd kwantyzacji:
, przy czym do obliczeń brany jest wektor kodowy r z tej grupy, do której został zakwalifikowany wektor danych xi - Wyznacz centroidy dla wszystkich i grup wektorów i przypisz je do wektorów kodowych ri.
- Jeśli
zakończ (uzyskano wymaganą dokładność), w przeciwnym razie zwiększ m i spróbuj jeszcze raz.
- Podziel M wektorów danych na N grup. Wektor xj (
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ż:
Linki zewnętrzne:
