Algorytm centroidów

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Algorytm centroidów
Ilustracja
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 -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 | edytuj kod]

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).

Zobacz też[edytuj | edytuj kod]

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, s. 100–108.

Linki zewnętrzne[edytuj | edytuj kod]