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