Algorytm centroidów (k-średnich)
Algorytm centroidów, znany również jako k-średnich lub algorytm LBG (od nazwisk twórców Linde, Buzo i Graya), jest popularnym narzędziem w analizie skupień, szczególnie w kwantyzacji wektorowej.
Cel algorytmu
Celem algorytmu jest przypisanie n-wymiarowych wektorów danych do wektorów kodowych w taki sposób, aby zminimalizować średni błąd kwantyzacji, określany wzorem:
D = (frac{1}{K} sum_{i=1}^K d(x_i, r)),
gdzie K to liczba elementów przypisanych do wektora kodowego r, a d to miara błędu kwantyzacji, najczęściej definiowana jako:
d(x, r) = (sum_{j=1}^n (x_j – r_j)^2).
Przebieg algorytmu
Algorytm centroidów składa się z kilku kroków:
- Wybierz N wektorów kodowych oraz określ maksymalny błąd kwantyzacji e.
- Inicjalizuj iterację m z wartością 0.
- Ustaw D_m na nieskończoność jako średni błąd kwantyzacji w m-tej iteracji.
- Powtarzaj, aż osiągniesz zadowalający rezultat:
- Podziel M wektorów danych na N grup, przypisując wektor x_j do i-tej grupy, jeśli d(x_j, r_i) ≤ d(x_j, r_k) dla wszystkich k różniących się od i.
- Oblicz średni błąd kwantyzacji: D_m = (frac{1}{M} sum_{i=1}^M d(x_i, r)), gdzie r to wektor kodowy grupy, do której przypisano wektor 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; w przeciwnym razie zwiększ m i powtórz.
Algorytm dostosowuje wektory kodowe do danych, przesuwając błędnie zakwalifikowane wektory do innych grup. Kluczowym wyzwaniem jest jednak wybór początkowych wektorów kodowych.
