P

P

P

P

ROJEK

ROJEK

ROJEK

ROJEKT

T

T

T

C

C

C

C

YFRO

YFRO

YFRO

YFROWE

WE

WE

WE

P

P

P

P

RZETW

RZETW

RZETW

RZETWARZANIE

ARZANIE

ARZANIE

ARZANIE

S

S

S

S

YGNAŁ

YGNAŁ

YGNAŁ

YGNAŁÓW

ÓW

ÓW

ÓW

„Grupowanie metod

ą k-środków

oraz

algorytm k-

środków”

Wykonali:

Rachwał Marek

ID 7.1

Stachyra Przemysław

ID 7.2

Tomiło Zbigniew ID 7.2

Metoda k-środków jest jedną z najbardziej popularnych metod grupowania.

Nazwa jej pochodzi

od reprezentacji klastra poprzez środek ciężkości c

j

(średnią) jego punktów. Do obliczania rozbieżności

pomiędzy dowolnym punktem a odpowiadającym mu środkiem wykorzystuje się funkcję odległości
(zazwyczaj normę L

2

). Dla normy L

2

suma kwadratów wszystkich rozbieżności pomiędzy punktami a

odpowiadającymi im środkami ciężkości równa się całkowitej wewnątrz klastrowej wariancji:

( )

∑ ∑

=

∈

−

=

k

j

C

x

j

i

j

i

c

x

C

E

...

1

2

Rozróżnia się dwie wersje metody k-środków:

Metoda 1 – algorytm Forgy'a

dzielimy zbiór danych na k losowych klastrów

dla każdego klastra obliczamy środek ciężkości

każdy obiekt przypisujemy do klastra reprezentowanego przez najbliższy środek ciężkości

powtarzaj cykl od punktu drugiego do momentu, gdy kryteria stopu zostaną spełnione (np. gdy
nie dokonano żadnej realokacji)

Własności metody 1:



dobra dla dowolnej L

p

normy



pozwala na łatwą paralelizację (równoległość)



niewrażliwa na kolejność (porządek) obiektów

Przykład:

Metoda 2



dzielimy zbiór danych na k losowych klastrów



dla każdego klastra obliczamy środek ciężkości



przesuwamy jeden obiekt do potencjalnie nowegoklastra



jeśli przesunięcie daje pozytywny efekt, obiekt jest realokowany i obliczamy środki ciężkości dla
zmienionych klastrów



powtarzamy cykl od kroku trzeciego do momentu, gdy krytaria stopu zostaną spełnione

Własności metody 2:

•

obliczalnie możliwa tylko dla normy L

2

•

daje lepsze rezultaty niż algorytm Forgy'a

Zalety



relatywnie efektywna: O (tkn), gdzie n to # obiektów, k to # klastrów, t to # iteracji – zazwyczaj
k, t << n



często zatrzymuje się na lokalnym maksimum. Globalne maksimum można znaleźć stosując
techniki takie jak: deterministyczne wyżarzanie, algorytmy genetyczne

Słabości

o

środek ciężkości musi zostać zdefiniowany – a co się dzieje z atrybutami symbolicznymi

o

liczba klastrów k musi zostać ustalona na początku

o

niezdolna do uchwycenia szumu oraz obiektów oddalonych

o

niezdolna do budowy klastrów o niewypukłych kształtach

Podstawową zaletą algorytmu k-środków jest szybkość działania. Algorytm ten jest podstawą dla
algorytmów grupowania dużych zbiorów danych, np. opisywany jest algorytm grupowania oparty na
k-środkach i działający na danych nie mieszczących się w pamięci RAM. K-środki mają małe wymagania
pamięciowe, ponieważ przechowują tylko listę przykładów, przypisań przykład-klaster i środków
klastrów.


Kod programu:

a=rand(1,100);
plot(a,zeros(1,100),'*');
b=rand(1,6);
for iter=1:1:10
hold off
M=[(a-b(1)).^2;(a-b(2)).^2;(a-b(3)).^2;(a-b(4)).^2;(a-b(5)).^2;(a-b(6)).^2;];
[P,CLUSTERNO]=min(M);
u=['r','g','b','c','m','y'];
figure
for i=1:1:6
[x,y]=find(CLUSTERNO==i);
col=[];
for k=1:1:length(x)
col=[col a(x(k),y(k))];
end
plot(col,zeros(1,length(col)),strcat(u(i),'*'))
hold on
b(i)=mean(col);
end
pause(0.01)
end

Otrzymane wyniki po pierwszym uruchomieniu programu:

Name

Size Bytes Class

******************************************************************
CLUSTERNO

1x100 800 double array

M

6x100 4800 double array

P

1x100 800 double array

a

1x100 800 double array

b

1x6 48 double array

col

1x14 112 double array

i

1x1 8 double array

iter

1x1 8 double array

k

1x1 8 double array

u

1x6 12 char array

x

1x14 112 double array

y

1x14 112 double array

Materiały:

Algorithm Collections for Digital Signal Processing Applications using Matlab – E.S. Gopi
skrypt Politechniki Warszawskiej oraz Poznańskiej
Sztuczna inteligencja i systemy doradcze
http://www.ise.pw.edu.pl/~cichosz/mow/wyklad/mow-w7/mow-w7.html
http://www.users.pjwstk.edu.pl/~krz/research/magister/node22.html