Algorytm centroidów

Algorytm centroidów (k-średnich)

Algorytm centroidów, znany również jako k-średnich (ang. k-means), jest jednym z kluczowych algorytmów w analizie skupień, a jego zastosowanie obejmuje m.in. kwantyzację wektorową. Często określa się go także jako algorytm klastrowy lub, na cześć twórców Linde, Buzo i Graya, jako algorytm LBG.

Cel algorytmu centroidów

Głównym celem algorytmu jest przypisanie wektorów kodowych ri dla N n-wymiarowych wektorów danych, tak aby zminimalizować średni błąd kwantyzacji. Średni błąd kwantyzacji oblicza się za pomocą wzoru:

D = 1/K × ∑i=1Kd(xi, r)

gdzie K to liczba elementów xi przypisanych do wektora kodowego r, a d to miara błędu kwantyzacji, najczęściej wyrażana jako błąd kwadratowy, który dla wektorów n-wymiarowych ma postać:

d(x, r) = ∑j=1n(xj – rj)2.

Przebieg algorytmu centroidów

Algorytm centroidów wykonuje następujące kroki:

  • Wybierz N wektorów kodowych oraz ustal maksymalny błąd kwantyzacji e.
  • Inicjalizuj iterację: m := 0.
  • Ustal Dm := ∞ (średni błąd kwantyzacji w m-tej iteracji).

Dopóki nie uzyskasz satysfakcjonującego wyniku, powtarzaj:

  • Podziel M wektorów danych na N grup. Wektor xj (j ∈ [1, M]) jest przypisywany do i-tej grupy, jeśli zachodzi nierówność:
  • d(xj, ri) ≤ d(xj, rk) dla wszystkich rk różniących się od ri.
  • Oblicz średni błąd kwantyzacji:

    • Dm = 1/M × ∑i=1Md(xi, r)

  • Wyznacz centroidy dla wszystkich grup i przypisz je do wektorów kodowych ri.
  • Jeśli spełniony jest warunek (Dm-1 – Dm)/Dm < e, zakończ działanie (uzyskano wymaganą dokładność), w przeciwnym razie zwiększ m i powtórz proces.

Algorytm dostosowuje wektory kodowe do danych oraz przesuwa błędnie zakwalifikowane wektory do innych grup. Kluczowym zagadnieniem pozostaje początkowy wybór wektorów kodowych (punkt 1 algorytmu).

Zobacz też

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

Przeczytaj u przyjaciół: