PROJEKT

CYFROWE PRZETWARZANIE SYGNAŁÓ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₂). Dla normy L₂ 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:

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₂

• 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

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

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

• niezdolna do uchwycenia szumu oraz obiektów oddalonych

• 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

---