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