Algorytm centroidów (k-średnich, ang. k-means) – jeden z algorytmów stosowanych w analizie skupień, wykorzystywany 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
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 Algorytm centroidów przebiega następująco:
Wybierz wektorów kodowych i określ maksymalny błąd kwantyzacji (iteracja) (średni błąd kwantyzacji w m-tej iteracji) 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ż centroid DBSCAN grupowanie
Bibliografia 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 Aplet obrazujący działanie algorytmu centroidów dla dwuwymiarowych wektorów
Kategoria:Klasyfikacja statystyczna centroidów