P3200035

4.20

M:

Mclodu k średnich została zaproponowana przez J.B.Mac Queena (1967). SPSS realizuje wersję podaną przez D.N.Sparksa (1973).

()gólny schemat metody jest następujący:

1.    Ustalamy liczbę grup (k)

2.    Wybieramy (w sposób losowy lub ustalony z góry) k punktów przestrzeni

M....., stanowiących tzw. zalążki środków ciężkości skupień (cluster seeds).

3.    Każdy z obiektów O, (i=l,...,/i) przydzielamy do grupy o najbliższym środku ciężkości tzn. 0,e5,, gdy d(o,,M )= min d(o,.M ), gdzie d jest odległością euklidesową.

4 Dla Sj (j=\.....k) obliczamy nowe środki ciężkości jako średnie arytmetyczne

wszystkich obiektów należących do danej grupy.

5. Powtarzamy kroki 3 i 4 aż do chwili, gdy nie następują przesunięcia obiektów między grupami.

Jednocześnie obliczana jest funkcja błędu podziału - ogólna suma kwadratów odległości wewnątrzgrupowych liczonych od środków ciężkości grup:

F = IZ d(o„M,y

7=1 0,eS,

W praktyce proces jest zbieżny po kilku lub kilkunastu iteracjach. Ponieważ w ogólności algorytm nie musi być zbieżny, ustala się maksymalną liczbę iteracji (L). Drugim sposobem zakończenia procesu iteracyjnego jest ustalenie kryterium zbieżności (^£). Proces ite-racyjny jest przerywany, jeżeli zostanie osiągnięta maksymalna liczba iteracji albo jeżeli w dwóch kolejnych iteracjach maksymalna zmiana środków ciężkości jest mniejsza niż ^e

razy minimum odległości między początkowymi środkami ciężkości

Przykład 2

Mamy 8 elementów, które chcemy podzielić na k=2 skupienia

Iteracja 1

Ustalamy zalążki środków ciężkości skupień. Arbitralnie (lub losowo) wybieramy dwa elementy - w przykładzie są to punkty (1; 1) i (2; 1). Pozostałe elementy przyporządkowujemy do najbliższych środków ciężkości skupień - zależności od tego czy znajdują się bliżej punktu (1; I) czy punktu (2; 1).

Rysunek 4.4

1 5 _T

4 a

i ³ i

I 2 a

1 4

o

Iteracja 2 Skupienie tych skup leży bliże

Rysunek 5 -i— 4 |

³ 1 2 \

1 \ °4J

o

Iteracja

Obiekt

menty.

środkó

128