Algorytm LBG


Algorytm centroidów w encyklopedii

Z Wikipedii, wolnej encyklopedii (Przekierowano z Algorytm LBG) Przejdź do nawigacji Przejdź do wyszukiwania

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.

Spis treści

Cel algorytmu centroidów | edytuj kod

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

Średni błąd kwantyzacji dany jest wzorem:

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

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

d ( x , r ) = j = 1 n ( x j r j ) 2 . {\displaystyle d(x,r)=\sum _{j=1}^{n}(x_{j}-r_{j})^{2}.}

Przebieg algorytmu centroidów | edytuj kod

Algorytm centroidów przebiega następująco:

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

Bibliografia | edytuj kod

  • 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 | edytuj kod

Na podstawie artykułu: "Algorytm LBG" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy