Algorytm grupowania danych typu kwantyzacji wektorów

Wst

ę

p

Definicja problemu: Typowe, rozważane dotychczas problemy koncentrowały się na
nauczeniu na podstawie zbioru treningowego i zbioru etykiet klasyfikacji wzorców, które
należały do jednej z kilku kategorii (np. automatyczne przypisywanie odpowiedniego gatunku
kwiatów). Innym typem często spotykanych problemów jest znalezienie w danych
treningowych charakterystycznych grup cechujących się pewnymi podobnymi
właściwościami, przy czym nie mamy wstępnej informacji o przynależności danego wektora
do danej kategorii. Informacje o kategoriach w tym przypadku są niedostępne.
Przykładem zastosowania metod klasteryzacji danych jest problem znajdywania grup
podobnych dokumentów zwracanych przez wyszukiwarkę. (np.

http://clusty.com/

)

Algorytm VQ

Algorytm VQ (Victor quantization) działa podobnie do algorytmu LVQ, w którym pominięto
część odpowiadającą za karanie pozostawiając jedynie część nagradzającą (w zależności od
etykiety klasy). Takie rozwiązanie powoduje że wektory kodujące podążają za jednorodnymi
grupami danych.
Optymalizacja wektorów kodujących odbywa się wg. zależności:

(

)

i

i

j

i

p

p

x

p

α

= +

−

(1)

Gdzie

α

- współczynnik uczenia

p

i

– i-ty wektor kodujący leżący najbliżej wektora treningowego x

j

Wartości

α

powinny być aktualizowane wg. zależności

1

α

α

α

=

+

po każdej iteracji

algorytmu.
Algorytm VQ do działania wymaga zdefiniowania odpowiednich wartości

α

0

oraz liczby

wektorów kodujących

l_w.

Opis algorytmu

Uczenie

1.

Wylosuj położenie

l_w neuronów - w tym celu najlepiej jest wykorzystać istniejące

już wektory danych i losowo wybrać ze zbioru danych wektory których położenie
będzie inicjowało położenie neuronów

2.

Iteracyjnie

l-razy

Dla każdego wektora treningowego

Znajdź najbliższy wektor kodujący (dla danej metryki)
Dokonaj aktualizacji położenia (wag) neuronu zgodnie z zależnością (1)

Dokonaj aktualizacji wsp.

α

wg. zależności (2)

Testowanie (określanie przynależności danego wektora testowego do danej grupy)

1.

Ponumeruj wektory kodujące

2.

Dla każdego wektora testowego

a.

Policz odległości pomiędzy wektorem testowym a wszystkimi neuronami
(wektorami kodującymi)

b.

Znajdź neuron leżący najbliżej wektora testowego (min(odległości(x,y)))

c.

Przypisz numer najbliższego wektora kodującego do danego wektora
testowego

W matlabie

1.

Wczytaj dane

2.

Dokonaj standaryzacji / normalizacji danych

3.

Wywołaj funkcję res=vq(tr);

Funkcja:

function res=vq(tr,l_w,d_t,l_it)
%uczenie
% l_w – wektor opisuj

ą

cy liczb

ę

wektorów koduj

ą

cych

% d_t – typ funkcji odległo

ś

ci

% l_it – liczba iteracji

P=[];
%Inicjowanie poło

ż

enia wektorów koduj

ą

cych

rp = randperm(size(tr,1));
rp = rp(1:l_w);
P=[P ; tr(rp,:)];

%uczenie
for i=1:l_it

%dla ka

ż

dego wektora treningowego

%policz odległo

ś

ci wektora treningowego do wszystkich

wektorów koduj

ą

cych

d = odległo

ść

mi

ę

dzy tr(i,:) a wszystkimi wektorami P

% znajd

ż

najbli

ż

szy wektor koduj

ą

cy

[min_d,min_id] = min(d);
%min_d – minimalna odległo

ść

%min_id – indeks najbli

ż

ej le

żą

cego wektora koduj

ą

cego

%dokonaj aktualizacji najbli

ż

szego wektora koduj

ą

cego

(wekotra o indeksie min_id) wg. zale

ż

no

ś

ci (1)

%zmodyfikuj wsp. uczenia wg. zalezno

ś

ci (2)

end;

%testowanie
res = zeros(size(tr,1),1);
for i=1:size(tr,1)

d = odległo

ś

ci wektora tr(i,:) do wszystkich wektorów

koduj

ą

cych P

%znajd

ź

najbli

ż

ej le

żą

cy wektor do wekora tr(i,:)

[min_d,min_id] = min(d);

%min_d – minimalna odległo

ść

%min_id – indeks najbli

ż

ej le

żą

cego wektora koduj

ą

cego

res(i) = min_id;

end;

Algorytm k-

ś

rtednich (k-means)

Jest wiele odmian algorytmu k-średnich, jego najczęściej spotykana wersja działa na zasadzie
wsadowej (batch) tzn. że najpierw tworzona jest tablica/macierz przynależności

U o

wymiarach:

l_w x l_n gdzie l_w to liczba klasterów, l_n – to liczba wektorów danych.

Macierz ta ma postać binarną tzn. przyjmuje wartości 1 jeśli dany wektor danych należy do
grupy związanej z danym wektorem kodującym oraz 0 jeśli dany wektor danych nie należy do
danej grupy (danego wektora kodującego).

1

2

3

4

5

x

x

x

x

x

1

2

3

0

1

1

0

0

1

0

0

0

1

0

0

0

1

0

p

p

p





















Każdy wiersz powyższej macierzy powinien spełniać zależność iż suma elementów wiersza

musi być mniejsza od liczby wektorów danych.

[

]

_

,

1, _

1

_

l n

j i

j

l w

i

U

l

n

∈

=

∀

<

∑

Takie ograniczenie pozwala zabezpieczyć się aby pojedynczy klaster nie zagarnął wszystkich
wektorów danych. Drugie ograniczenie służy zapewnieniu by dany wektor przynależał

dokładnie do jednej grupy, a sprowadza się ono do zależności

[

]

_

,

1, _

1

1

l w

j i

i

l n

j

U

∈

=

∀

=

∑

Algorytm k-średnich działa na zasadzie realizacji dwóch kroków 1) wyznaczenia położenia
ś

rodków centrów klasterów P na podstawie macierzy U 2) aktualizacji macierzy U na

podstawie nowych środków centrów P

Opis algorytmu

Uczenie

1.

Zainicjuj położenie centrów P

2.

Dokonaj aktualizacji macierzy U, (przypisz dane do odpowiednich środków klasterów
P)

3.

Wyznacz położenia środków klasterów - oblicz wartość średnią z wszystkich
przypadków należących do danego klastera

4.

Porównaj położenia środków centrów klastra z poprzedniej iteracji i obecnej. Jeśli nie
uległy zmianie to koniec

5.

Idź do 2

W matlabie

4.

Wczytaj dane

5.

Dokonaj standaryzacji / normalizacji danych

6.

Wywołaj funkcję res=ksrednich(tr);

Funkcja:

function res=ksrednich(tr,l_w,d_t)
%uczenie
% l_w – wektor opisuj

ą

cy liczb

ę

wektorów koduj

ą

cych

% d_t – typ funkcji odległo

ś

ci

l_n = size(tr,1);
%zainicjowanie macierzy U
U = false(l_w,l_n); %
%Inicjowanie poło

ż

enia wektorów koduj

ą

cych

rp = randperm(size(tr,1));

rp = rp(1:l_w);
P=[P ; tr(rp,:)];

%uczenie
While false

% policz odległo

ść

pomi

ę

dzy wszystkimi

ś

rodkami klasterów,

a wszystkimi wektorami treningowymi

d = odległo

ść

(P,tr)

%dla ka

ż

dego wektora treningowego znajd

ź

najbli

ż

sze

centrum klastera
[min_d,min_id] = min(d);

%min_d – wektor opisuj

ą

cy minimalna odległo

ść

od

ś

rodka

centrum
%min_id – wektor indeksów najbli

ż

ej le

żą

cych

ś

rodków

centrów klasterów
%Dokonaj aktualizacji macierzy przynale

ż

no

ś

ci

for i=1:l_n

U(min_id(i),i) = 1;

end;
%Dokonaj aktualizacji

ś

rodków centrów P

for i=1:l_w

P(i,:)=mean(tr(U(i,:),:))

end;
%dodaj warunek zako

ń

czenia procesu uczenia

end

%testowanie
res = zeros(size(tr,1),1);
for i=1:size(tr,1)

d = odległo

ś

ci wektora tr(i,:) do wszystkich wektorów

koduj

ą

cych P

%znajd

ź

najbli

ż

ej le

żą

cy wektor do wekora tr(i,:)

[min_d,min_id] = min(d);

%min_d – minimalna odległo

ść

%min_id – indeks najbli

ż

ej le

żą

cego wektora koduj

ą

cego

res(i) = min_id;

end;

Zadanie:

1.

Wczytaj zbiór danych Iris

2.

Pomiń informacje o etykietach (usuń ostatnią kolumnę data(:,end)=[])

3.

Wykonaj obliczenia tylko dla dwóch atrybutów i-tegi i j-tego vq(data(:,[i j],…),
ksrednich(data(:,[i j],…))

4.

Do reprezentacji wyników wykorzystaj funkcję plot_clust(data,res)

Gdzie:

Data – zbiór danych uczących

Res – wynik klasteryzacji

5.

Zbadaj wpływ funkcji odległości na jakość uczenia algorytmu VQ

6.

Zbadaj wpływ liczby wektorów kodujących na jakość klasteryzacji