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 $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$ . Algorytm centroidów przebiega następująco:

Wybierz $N$ wektorów kodowych i określ maksymalny błąd kwantyzacji $e$ .
$m : = 0$ (iteracja)
$D_m := \infty$ (ś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 $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). Zobacz też:

Linki zewnętrzne: