MATLAB - UCZENIE MASZYNOWE #5 - ALGORYTM c-MEans

W poprzednich artykułach skupiłem na algorytmie k-Means, samouczącym się algorytmie automatycznej klasyfikacji. Tym razem przyglądniemy się bardziej rozbudowanemu bratu tej metody czyli bazującemu na rozmytych funkcjach przynależności algorytmowi c-means.

Algorytm k-Means opisywałem w kilku poprzednich postach. Zachęcam do zaznajomienia się z nimi tu i tutaj. Ponadto w kolejnym poście TU opisywałem przewagę logiki rozmytej nad logiką klasyczną binarną i korzyściach jakie mogą płynąć z jej zastosowania w kontekście automatycznej klasyfikacji obiektów o określonych cechach. Czas połączyć te elementy, a więc zastosować algorytm k-Means z elementami logiki rozmytej.

Algorytm k-Means a logika rozmyta

Algorytm k-Means, klasyfikował obiekty w oparciu o ocenę ich „odległości” od środka klastrów, przy czym środki te w każdej iteracji były obliczane w sposób adaptacyjny. Jakkolwiek algorytm miał zdolność uczenia się, to decyzja do którego klastra należy dany obiekt była podejmowana na gruncie logiki klasycznej: element był przypisywany do tego klastra do którego miał „bliżej” i nie należał do żadnego innego. To ostre kryterium powodowało, że granice między klastrami były jednoznacznie zdefiniowane.

Wiemy jednak, że granice pomiędzy klastrami nie muszą być ostre. Wręcz przeciwnie w praktyce często grupy elementów o określonych cechach „nachodzą” na siebie. Możemy ocenić przecież, że jakiś element należy „bardziej” do zbioru A, choć wydaje się, że częściowo ma cechy elementów ze zbioru B. Weźmy na przykład jabłka - nie mają one tylko jednolitego koloru czerwonego lub zielonego. Często zdarza się, że kolory te są wymieszane. Klasyfikacja takiego kolorowego jabłka do zbioru, na przykład „czerwone”, byłaby błędem. Takie zielono – czerwone jabłko jest przecież gdzieś „pomiędzy”.

Algorytm c-means

I tu do algorytmu k-Means wkracza logika rozmyta. Efektem takiego połączenia jest algorytm c-means. Co do zasady działa on bardzo podobnie do k-Means (jeszcze raz polecam post na ten temat). Jednak klasyfikacja jest podejmowana na podstawie oceny „rozmytej” funkcji przynależności. Algorytm ocenia w jakim stopniu dany element pasuje do wszystkich rozpatrywanych klastrów, a liczbową miarą przynależności jest wartość wspomnianej funkcji. Funkcja przyjmuje wartości od zera (brak przynależności) do jeden (przynależność) czyli również wszystkie pośrednie wartości.

MATLAB

W MATLABie algorytm c-means jest zaimplementowany we funkcji fcm. Zwraca ona, oprócz środków klastrów, wartości funkcji przynależności. Na tej podstawie można ocenić, do którego zbioru dany element pasuje lepiej. Mamy więc dodatkową informację, która była niedostępna w przypadku algorytmu k-Means.

Najlepiej prześledzić to na przykładzie, który znacie z poprzednich postów:

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 = 3 + randn(N,1);
y2 = 3 + 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

% Klasyfikacja
[srodki,U] = fcm(dane,2,5);
maxU = max(U);
roznica = diff(U);

indx0 = find(abs(roznica)<0.15);
indx1 = find(U(1,:) == maxU);
indx2 = find(U(2,:) == maxU);

figure;
plot(dane(indx0,1),dane(indx0,2),'*');
hold on; 
plot(dane(indx1,1),dane(indx1,2),'o');
hold on
plot(dane(indx2,1),dane(indx2,2),'x');
plot(srodki(1,1),srodki(1,2),'x','MarkerSize',15,'LineWidth',3);
plot(srodki(2,1),srodki(2,2),'x','MarkerSize',15,'LineWidth',3);
xlabel('Cecha 1'); ylabel('Cecha 2'); grid on

legend('Klaster 1/Klaster 2?', 'Klaster 1', 'Klaster 2')

Zwróćmy uwagę, że funkcja fcm zwróciła wektor U, zawierający dla każdego elementu wartości funkcji przynależności dla dwóch klastrów. Większa wartość, wskazuje ten klaster, do którego element „lepiej pasuje”, ale nie znaczy to, że całkowicie wykluczona jest jego przynależność do drugiego klastra. Daje to więc możliwość „rozmytej” klasyfikacji elementów, co jest szczególnie cenne w sytuacji kiedy klastry „zachodzą na siebie”.

W MATLABIE jest również dostępne demonstracyjne narzędzie obrazujące działanie algorytmu. Wystarczy w ‘command window’ wpisać fcmdemo.  Polecam się tym „pobawić”. Rozgryzienie znaczenia parametru ‘exponent’ zostawiam już Wam. Ma on wpływ na „rozmycie” algorytmu..

(Visited 181 times, 1 visits today)

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *