Algorytm centroidów

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Algorytm centroidów
Linear-svm-scatterplot.svg
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[edytuj | edytuj kod]

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.

Przebieg algorytmu centroidów[edytuj | edytuj kod]

Algorytm centroidów przebiega następująco:

  1. Wybierz N wektorów kodowych i określ maksymalny błąd kwantyzacji e.
  2. m := 0 (iteracja)
  3. D_m := \infty (średni błąd kwantyzacji w m-tej iteracji)
  4. 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).

Bibliografia[edytuj | 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, p100-108.

Linki zewnętrzne[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]