Algorytm centroidów

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi.
Należy w nim poprawić: algorytm centroidów jest stosowany do analizy skupień. Kwantyzacja wektorowa to tylko jedno z zastosowań.
Po wyeliminowaniu wskazanych powyżej niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu.

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.

Spis treści

[edytuj] Cel algorytmu centroidów

Celem algorytmu jest przypisanie do wektorów kodowych $r i$ ( $i \in [1,N]$ ) $M$ $n$ -wymiarowych wektorów danych, przy jak najmniejszym średnim błędzie kwantyzacji.

Średni błąd kwantyzacji dany jest wzorem:

$D = \frac{1}{K} \sum_{i=1}^{K} d(x_i, r)$

gdzie $K$ jest liczbą elementów $x i$ przypisanych do wektora kodowego $r$ , natomiast $d$ miarą błędu kwantyzacji i najczęściej jest to błąd kwadratowy określany dla wektorów n-wymiarowych jako $d(x,r) = \sum_{j=1}^{n} (x_j - r_j)^2$ .

[edytuj] Przebieg algorytmu centroidów

Algorytm centroidów przebiega następująco:

Wybierz $N$ wektorów kodowych i określ maksymalny błąd kwantyzacji $e$ .
$m : = 0$ (iteracja)
$D_m := \infty$ (średni błąd kwantyzacji w m-tej iteracji)
Dopóki nie uzyskano zadowalającego rezultatu, powtarzaj:
- Podziel $M$ wektorów danych na $N$ grup. Wektor $x j$ ( $j \in [1,M]$ ) jest przypisywany do $i$ -tej grupy wtedy i tylko wtedy gdy zachodzi nierówność $d(x_j, r_i) \le d(x_j, r_k)$ dla wszystkich $r k$ różnych od $r i$ .
- Wyznacz średni błąd kwantyzacji: $D_m = \frac{1}{M} \sum_{i=1}^{M} d(x_i, r)$ , przy czym do obliczeń brany jest wektor kodowy $r$ z tej grupy, do której został zakwalifikowany wektor danych $x i$
- Wyznacz centroidy dla wszystkich $i$ grup wektorów i przypisz je do wektorów kodowych $r i$ .
- Jeśli $\frac{D_{m-1} - D_m}{D_m} < e$ zakończ (uzyskano wymaganą dokładność), w przeciwnym razie zwiększ $m$ 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).

[edytuj] 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, p100-108.