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]

Celem algorytmu jest przypisanie do wektorów kodowych () -wymiarowych wektorów danych, przy jak najmniejszym średnim błędzie kwantyzacji.

Średni błąd kwantyzacji dany jest wzorem:

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

.

Przebieg algorytmu centroidów[edytuj]

Algorytm centroidów przebiega następująco:

  1. Wybierz wektorów kodowych i określ maksymalny błąd kwantyzacji .
  2. (iteracja)
  3. (średni błąd kwantyzacji w m-tej iteracji)
  4. Dopóki nie uzyskano zadowalającego rezultatu, powtarzaj:
    • Podziel wektorów danych na grup. Wektor () jest przypisywany do -tej grupy wtedy i tylko wtedy gdy zachodzi nierówność dla wszystkich różnych od .
    • Wyznacz średni błąd kwantyzacji: , przy czym do obliczeń brany jest wektor kodowy z tej grupy, do której został zakwalifikowany wektor danych
    • Wyznacz centroidy dla wszystkich grup wektorów i przypisz je do wektorów kodowych .
    • Jeśli zakończ (uzyskano wymaganą dokładność), w przeciwnym razie zwiększ 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]

  • 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]

Zobacz też[edytuj]