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.