Algorytm centroidów

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.Celem algorytmu jest przypisanie do wektorów kodowych ri () M n-wymiarowych wektorów danych, przy jak najmniejszym średnim błędzie kwantyzacji Średni błąd kwantyzacji dany jest wzorem:gdzie K jest liczbą elementów xi przypisanych do wektora kodowego r natomiast d matematyka .php'>miarą błędu kwantyzacji i najczęściej jest to błąd kwadratowy określany dla wektorów n-wymiarowych jakoAlgorytm centroidów przebiega następująco:Algorytm sukcesywnie dopasowuje wektory kodowe do istniejących danych i w matematyka .php'>miarę potrzeb przesuwa błędnie zakwalifikowane wektory danych do innych grup. Problem stanowi jednak początkowy wybór wektorów kodowych punkt 1 algorytmu).