P3200037

Rysunek 4.6. Algorytm k-średnich - iteracja 3

0    1    2    3    4    5    6

Domyślnie podczas jednej iteracji obiekty są przydzielane do aktualnie najbliższych środków ciężkości obliczonych przed rozpoczęciem iteracji. Dopiero po zakończeniu bieżącej iteracji środki ciężkości są aktualizowane. Można zastosować metodę, w której środki ciężkości są obliczane bezpośrednio po każdej zmianie przyporządkowania obiektu do grupy. Jeżeli jakiś obiekt przechodzi z grupy S do grupy , wymaga to zaktualizowania

dwóch środków ciężkości M_p i M_q .

Przed rozpoczęciem metody ^-średnich badacz musi rozstrzygnąć dwie sprawy: jaka ma być liczba grup (k) i jaki przyjąć początkowy podział obiektów. Pozostałe decyzje: maksymalna liczba iteracji i wybór wartości kryteriów zbieżności są mniej ważne dla problemu.

Na temat ustalania liczby skupień piszemy w punkcie 4.2.6. Tu zajmiemy się ustalaniem początkowych środków ciężkości. Możliwe są różne podejścia:

1.    Arbitralny sposób np. przyjęcie współrzędnych pierwszych k obiektów (nie zawierające braków danych) jako zalążki środków ciężkości.

2.    Losowy wybór środków ciężkości, przy czym może to być losowy wybór k obiektów ze zbioru danych albo losowy wybór k punktów przestrzeni niekoniecznie pokrywających się z położeniem obiektów.

3.    Wykorzystanie algorytmu optymalizującego w pewien sposób {Wożenie początkowych środków ciężkości np. przez uwzględnianie k obiektów leżących daleko względem siebie.

4.    Przyjęcie jako początkowych środków ciężkości uzyskanych na podstawie podziału otrzymanego inna metodą (głównie jedną z metod hierarchicznych).