Dzisiaj kontynuacja tematu z poprzedniego wpisu na temat algorytmu k-Means. Tym razem sami zaimplementujecie prostą wersję tego algorytmu aby zobaczyć na czym polega uczenie maszynowe.
Dzisiaj samodzielnie napiszemy program, który będzie posiadał zdolność uczenia się, w końcu mowa o uczeniu maszynowym. Będzie to uproszczona, na potrzeby dydaktyczne, wersja algorytmu k-Means, tak aby lepiej zrozumieć jego działanie. Jeżeli nie czytaliście poprzedniego wpisu na temat tego algorytmu, to w tym miejscu koniecznie się z nim zapoznajcie.
Krótko tylko przypomnę, że algorytm k-Means sam rozpoznaje i klasyfikuje elementy o podobnych cechach, bez udziału człowieka. Klasyfikuje on badane elementy w klastry, za kryterium przyjmując „odległość” elementu od „środka” klastra. Przyjmijmy, że miarą odległości jest metryka euklidesowa i dla uproszczenia rozpatrzmy przypadek dwuwymiarowy czyli obiekty, o dwóch cechach (czyli n=2):

Załóżmy ponadto, że mamy zbiór 5 elementów jak na rysunku, przy czym wiemy, że reprezentują one dwie klasy (klastry) obiektów. Jak je rozróżnić?

Ustalmy środki klastrów K1 i K2. O tym jak to zrobić będzie w dalszej części artykułu ale na razie przyjmijmy, że mają one takie położenie jak na rysunku poniżej. Następnie obliczmy odległości pomiędzy każdym obiektem (1, 2, 3, 4, 5), a środkiem klastra K1 i K2 otrzymując zbiór odległości: d1-1, d1-2, d2-1, d2-2, …., itd.

Teraz sprawdźmy, do którego klastra dany element ma bliżej, porównując wyznaczone odległości. Jeżeli dla elementu 1, d1-1 jest mniejsze, niż d1-2, to znaczy, że element ten należy dla klastra K1. Jeżeli dla elementu 4, d4-2 jest mniejsze niż d4-1, to element ten należy do klastra 2. I tak dalej.. Czy widać już zarys algorytmu?
Oczywiście taka klasyfikacja zależy od wyboru punktów K1 i K2 i po sprawdzeniu wszystkich odległości jest zakończona.
Uczenie maszynowe
Ale co gdyby w następnej iteracji na nowo obliczyć współrzędne środków klastrów K1 i K2 biorąc pod uwagę wynik klasyfikacji w poprzedniej iteracji? Spróbujmy napisać program w MATLABie, który zobrazuje nam działanie tego algorytmu. Będzie to bardzo uproszczona wersja algorytmu k-Means, jednak program ten pozwoli, krok po kroku, zrozumieć uczenie maszynowe w tym przypadku.
Przygotowanie danych
Posłużmy się sztucznie wygenerowanym zbiorem danych na potrzeby tej konkretnej symulacji. Utwórzmy dwa klastry o współrzędnych cech elementów K1: (x1,y1) i K2: (x2,y2).
clear all; close all; clc %% Przygowanie danych N = 100; % Liczba elementów w każdym klastrze % Klaster 1 o cechach x1 i y1 x1 = 1 + randn(N,1); y1 = 1 + randn(N,1); % Klaster 2 o cechach x2 i y2 x2 = 4 + randn(N,1); y2 = 4 + randn(N,1); % Jeden zbiór z danymi dane = [[x1; x2], [y1; y2]]; % Zobaczmy jak wyglądają klastry w przestrzeni 2D figure; plot(x1,y1,'x'); hold on; plot(x2,y2,'xr'); title('Dane referencyjne'); xlabel('Cecha 1'); ylabel('Cecha 2'); grid on

Uproszczony algorytm k-Means
Punkt początkowy dla klastra K1 ustalmy na (0,0), a dla klastra K2 na (7,-2). Robimy to arbitralnie tak aby zobrazować działanie algorytmu. W praktyce algorytm k-Means sam dobiera punkty początkowe posługując się innymi algorytmami, jednak to zagadnienie wykracza poza treść tego artykułu. Ustalamy więc punkty początkowe „ręcznie” na K1 i K2.
% Punkt początkowy wybierany arbitralnie przez użytkownika x01 = [0, 0]; % K1 x02 = [7, -2]; % K2
Sercem algorytmu jest sprawdzenie odległości pomiędzy badanym zbiorem elementów o różnych cechach (zmienna dane), a punktem będącym środkiem klastra. Klasyfikację wykonujemy w prostej pętli if .. elseif.. end.
% Wewnętrzna pętla, sprawdzenie "odlegości" element - środek klastra for k = 1 : length(dane) d1 = sqrt((dane(k,1) - x01(1,1)).^2 + (dane(k,2) - x01(1,2)).^2); d2 = sqrt((dane(k,1) - x02(1,1)).^2 + (dane(k,2) - x02(1,2)).^2); % Klasyfikacja if d1 < d2 klasa(k,1) = 1; elseif d1 >= d2 klasa(k,1) = 2; end end
I tu zaczyna się wątek, z uczeniem maszynowym.. Dla tak wyznaczonych klastrów, algorytm oblicza ich nowe środki poprzez uśrednienie współrzędnych elementów:
% Nowy punkt początkowy dla klastra 1 x01(1,1) = mean(dane(klasa == 1,1)); x01(1,2) = mean(dane(klasa == 1,2)); % Nowy punkt początkowy dla klastra 2 x02(1,1) = mean(dane(klasa == 2,1)); x02(1,2) = mean(dane(klasa == 2,2));
Tak wyznaczone środki mogą posłużyć do wykonania kolejnej iteracji algorytmu, potrzebna jest więc zewnętrzna pętla:
max_iter = 10 % Zewnętrzna pętla, liczba iteracji for iter = 1 : max_iter disp(['Iteracja nr: ' num2str(iter)]); disp('Wciśnij dowolny klawisz by kontynuować'); % Wewnętrzna pętla, sprawdzenie "odlegości" element - środek klastra for k = 1 : length(dane) .......... .......... end end
Gotowy program, wraz z dodatkowymi fragmentami rysującymi rysunki, jest na końcu tego artykułu. Po uruchomieniu programu jest wykonywana pojedyncza iteracja algorytmu, przeprowadzana klasyfikacja, rysowany rysunek obrazujący aktualny stan, a następnie algorytm czeka na wciśnięcie klawisza przez użytkownika w celu wykonania kolejnej iteracji. Dzięki temu, krok po kroku, możemy śledzić jak działa algorytm. Poniżej przedstawiono dwa rysunki obrazujące kolejne iteracje.


Program jest prosty, nie zawiera obsługi błędów, warunku stopu algorytmu, itd. Na „sztywno” mamy ustawioną liczbę iteracji. Możecie sami poeksperymentować z programem, żeby go ulepszyć. Powodzenia.!
clear all; close all; clc %% Przygowanie danych N = 100; % Liczba elementów w każdym klastrze % Klaster 1 o cechach x1 i y1 x1 = 1 + randn(N,1); y1 = 1 + randn(N,1); % Klaster 2 o cechach x2 i y2 x2 = 4 + randn(N,1); y2 = 4 + randn(N,1); % Jeden zbiór z danymi dane = [[x1; x2], [y1; y2]]; % Zobaczmy jak wyglądają klastry w przestrzeni 2D figure; plot(x1,y1,'x'); hold on; plot(x2,y2,'xr'); title('Dane referencyjne'); xlabel('Cecha 1'); ylabel('Cecha 2'); grid on %% Algorytm k-Means % Punkt początkowy wybierany arbitralnie przez użytkownika x01 = [0, 0]; % K1 x02 = [7, -2]; % K2 figure; max_iter = 10 % Zewnętrzna pętla, liczba iteracji for iter = 1 : max_iter disp(['Iteracja nr: ' num2str(iter)]); disp('Wciśnij dowolny klawisz by kontynuować'); % Wewnętrzna pętla, sprawdzenie "odlegości" element - środek klastra for k = 1 : length(dane) d1 = sqrt((dane(k,1) - x01(1,1)).^2 + (dane(k,2) - x01(1,2)).^2); d2 = sqrt((dane(k,1) - x02(1,1)).^2 + (dane(k,2) - x02(1,2)).^2); % Klasyfikacja if d1 < d2 klasa(k,1) = 1; elseif d1 >= d2 klasa(k,1) = 2; end end plot(dane(klasa == 1, 1),dane(klasa ==1,2),'bo'); hold on; plot(x01(1), x01(2), 'go', 'LineWidth', 2); % Nowy punkt początkowy dla klastra 1 x01(1,1) = mean(dane(klasa == 1,1)); x01(1,2) = mean(dane(klasa == 1,2)); plot(dane(klasa == 2, 1),dane(klasa ==2,2),'rx'); hold on; plot(x02(1), x02(2), 'go', 'LineWidth', 2) % Nowy punkt początkowy dla klastra 2 x02(1,1) = mean(dane(klasa == 2,1)); x02(1,2) = mean(dane(klasa == 2,2)); axis([-2 8 -4 8]) if iter < max_iter title(['Iteracja nr: ' num2str(iter) '/' num2str(max_iter) '. Wciśnij dowolny klawisz by kontynuować']); xlabel('Cecha 1'); ylabel('Cecha 2'); grid on pause clf end end title(['Iteracja nr: ' num2str(iter) '/' num2str(max_iter) '. Wciśnij dowolny klawisz by kontynuować']); xlabel('Cecha 1'); ylabel('Cecha 2'); grid on