Zadanie klasyfikacji nadzorowanej

Będziemy zakładać, że na przestrzeni cech obiektów zdefiniowany jest pewien podział na \(L\) rozłącznych klas \(C_1,\ldots,C_L\). Jest to równoznaczne z istnieniem pewnej funkcji \(\psi\) odwzorowującej przestrzeń cech \(X\) w zbiór etykiet klas \(C\). Formalnie funkcję tą nazywamy klasyfikatorem.

Definicja 4

Klasyfikatorem (algorytmem klasyfikacji, regułą decyzyjną) nazywamy funkcję odwzorowującą przestrzeń cech w zbiór numerów klas, to znaczy funkcję:

\[\psi :{{R}^{p}}\to \left\{ 1,...,L \right\}\]

taką, że \(\psi \left( x \right)=i\) gdy wektor \(x\) jest elementem klasy \(i\).

Zauważmy, że w związku z przyjętą definicją dla próbka należy do dokładnie jednej klasy, co oznacza w szczególności, że każda musi zostać zaklasyfikowana. Oczywiście postać funkcji \(\psi\) jest nieznana. W zadaniu klasyfikacji nadzorowanej dany jest jedynie pewien podzbiór zbioru obiektów \(X_{train}\subset X\), który nazywać będziemy zbiorem uczącym. Jest to zbiór następującej postaci

\[X_{train}=\{(x_i,y_i):x_i\in R^p, y_i\in C\}.\]

Każdy element tego zbioru stanowi parę złożoną z wektora cech \(x_i\) obiektu oraz etykiety klasy \(C_i\), której jest elementem. Reguła decyzyjna generuje rozkład przestrzeni cech na ta zwane obszary decyzyjne.

Definicja 5

Obszarem decyzyjnym nazywamy zbiór postaci

\[D_i=\{x\in X : \psi(x)=i\}\textrm{ dla }i=1,\ldots,L\]

W praktyce bardzo wygodnym mechanizmem reprezentacji klasyfikatora są funkcje klasyfikujące

Definicja 6

Funkcją dyskryminacyjną dla \(i\)-tej klasy \(i\in\{1,\ldots,L\}\) nazywamy funkcję

\[g_i\colon X\rightarrow\mathbb{R}\]

odwzorowującą przestrzeń reprezentacji \(X\) w zbiór liczb rzeczywistych \(\mathbb{R}\), tak dobraną by dla każdej reprezentacji \(x\) obiektu z \(C_i\)-tej klasy przyjmowała największą wartość spośród \(L\) wartości wszystkich funkcji dyskryminacyjnych, tzn.

\[\begin{split}\forall_{i=1,\ldots,L}\forall_{j=1,\ldots,L; j\not=i}\forall_{x\in X} \quad g_i(x)>g_j(x).\end{split}\]

Obszary decyzyjne, oddzielone są od siebie tzw. powierzchniami decyzyjnymi.

Definicja 7

Powierzchnia decyzyjna \(g_{ij}\), rozdzielająca od siebie klasy \(C_i\) oraz \(C_j\), dana jest równaniem

\[g_i(x)=g_j(x),\]

gdzie \(g_i, g_j\) są funkcjami dyskryminacyjnymi.

Wprowadzenie pojęcia funkcji klasyfikujących sprowadza zadanie klasyfikacji do przydzielenia wektora cech \(x\) do klasy, dla której odpowiednia funkcja klasyfikująca na wektorze \(x\) osiąga największą wartość, to znaczy zgodnie z poniższą regułą decyzyjną:

\[\psi \left( x \right)=i,\text{ gdy }{{g}_{i}}\left( x \right)=\underset{j\in \left\{ 1,...,k \right\}}{\mathop{\max }}\,{{g}_{j}}\left( x \right)\]

Zgodnie z tą regułą wystarczy więc wyliczyć wartości wszystkich funkcji klasyfikujących, znaleźć wartość największą, a jako wynik działania algorytmu zwrócić indeks funkcji dla której ta wartość została osiągnięta.

Zadanie klasyfikacji nadzorowanej należy rozpatrywać w trybach:

Tryb uczenia

Tryb uczenia jest to proces, w którym następuje wyznaczenie modelu to znaczy znalezienie postaci klasyfikatora wraz z jego parametrami. Tryb uczenia można podzielić na następujące etapy:

  1. akwizycja i etykietowanie.
  2. wytypowanie reprezentacji i jej obliczenie,
  3. wstępne przetwarzanie danych,
  4. ekstrakcję i selekcję cech,
  5. uczenie i walidacja.

Pierwszy ma na celu wyznaczenie obiektów zainteresowania ze zbioru danych wejściowych czyli akwizycję oraz etykietowanie czyli przypisanie przez specjalistę dziedzinowego etykiet określającej przynależność poszczególnych obiektów do konkretnej klasy. Drugi etap to wyznaczenie odpowiedniej reprezentacji obiektu, czyli dziedziny odwzorowania \(\psi\). Etap ten polega na wyznaczeniu wektora cech. Po wyborze sposobu reprezentacji następuje jej obliczenie dla wszystkich wydzielonych obiektów i utworzenie zbioru uczącego. Po wyznaczeniu reprezentacji obiektu następuje etap wstępnego przetwarzania danych a zatem w szczególności normalizacja. Etap selekcji / ekstrakcji cech stosowany jest do wyznaczenia optymalnego podzbioru cech wejściowych bądź do wygenerowania nowych lepiej opisujących dane. Po zakończeniu selekcji cech następuje właściwy etap uczenia i walidacji. Podstawowym celem uczenia i walidacji jest wyznaczenie modelu oraz optymalnych wartości jego parametrów.

Tryb testowania

Uzyskany w trybie uczenia model klasyfikatora poddajemy następnie trybowi testowania. Testowanie jest w istocie używaniem klasyfikatora na próbkach, które nie brały udziału w procesie uczenia. Przeprowadzenie tego procesu jest konieczne dla oceny sprawności klasyfikatora a zatem oceny jego możliwości uogólniających. Pod pojęciem tym rozumiemy zdolność klasyfikatora do rozpoznawania próbek nowych a zatem tych, które nie były obserwowane w procesie uczenia. Testowanie odbywa się na niezależnym zbiorze testowym \(X_{test}\) przygotowanym w analogiczny sposób jak zbiór uczący. Klasyfikator którego zdolności uogólniające są niezadowalające nazywać będziemy niedouczonym. Ponowne użycie dla testowania i oceny klasyfikatora zbioru uczącego jest poważnym błędem i prowadzić może do przeuczenia klasyfikatora. Zjawisko to polega na nadmiernym dopasowaniu modelu do zbioru uczącego, poprzez co klasyfikator wykazuje bardzo wysoką sprawność na zbiorze uczącym, jednak jego zdolności uogólniające (do rozpoznawania próbek nowych) są niezadowalające.

Przykłady zadania klasyfikacji nadzorowanej

Poniżej podajemy kilka praktycznych przykładów zadania klasyfikacji nadzorowanej

  • Wspomaganie diagnostyki medycznej - klasyfikacja pacjenta ze względu na występowanie pewnej jednostki chorobowej a zatem klasyfikacja do grupy zdrowych bądź chorych, określenie przynależności pacjenta do grupy o podwyższonym ryzyku
  • Rozpoznawanie cyfr / pisma - przypisanie odpowiedniej etykiety znakom pisma odręcznego
  • Określenie zdolności kredytowej klienta banku
  • Rozpoznawanie niechcianych wiadomości elektronicznych (spamu)
  • Rozpoznawanie twarzy, linii papilarnych itp.

Przykład 3

W tym przykładzie zbudujemy prosty klasyfikator rozróżniający elementy dwóch klas. Faza uczenia klasyfikatora polega na znalezieniu wartości funkcji klasyfikujących, w tym miejscu zakładamy, że funkcje klasyfikacyjne zbudowanego klasyfikatora wyrażają się wzorami \(g_1(x)=x_1+x_2\), \(g_2(x)=-x_1-x_2\). Powierzchnia decyzyjna jest zatem postaci: \(x_2=-x_1\). Poniżej prezentujemy kod języka Python będący implementacją funkcji klasyfikujących oraz w oparciu o nie rozważanego klasyfikatora. Następnie generujemy losowo zbiór danych na którym klasyfikator zostanie przetestowany.

import numpy as np
import matplotlib.pyplot as plt

#definicje funkcji klasyfikujących
def g1(x):
    return x[0]+x[1]

def g2(x):
    return -x[0]-x[1]

#klasyfikator
def klasyfikuj(x):
    if g1(x)>g2(x):
        return 1
    else:
        return 2;

#liczba próbek w klasie
N = 5

#próba losowa z rozkładu jednostajnego na przedziale [1,5]
class1 = np.random.rand(N,2)
class2 = np.random.rand(N,2)-1

data=np.vstack((class1,class2))

#wykres przedstawiający dane do testowania oraz powierzchnię rozdzielającą
#zakres wartości na osiach
plt.ylim(ymax = 1.5, ymin = -1.5)
plt.xlim(xmax = 1.5, xmin = -1.5)
#dane uczące
plt.scatter(data[:,0],data[:,1])
#powierzchnia rozdzielająca
plt.plot([-1.5, 1.5],[1.5, -1.5])
plt.show()

#wartości funkcji klasyfikujących
y1=[g1(data[i,:]) for i in range(2*N)]
y2=[g2(data[i,:]) for i in range(2*N)]
#zaokrąglenie
y1=np.round(y1,2)
y2=np.round(y2,2)
print 'Wartości funkcji klasyfikujacych'
print y1
print y2

#wyznaczamy decyzje klasyfikatora (numer funkcji klasyfikującej zwracającej większą wartość)
labels=np.array([klasyfikuj(data[i,:]) for i in range(2*N)])
print 'Decyzje klasyfikatora:'
print labels

#numery próbek zakalsyfikowane do kazdej z klas
c1 = (labels==1).nonzero()
c2 = (labels==2).nonzero()

#wykres przedstawiający dane oraz powierzchnię rozdzielającą
#klasę w zależności od decyzji klasyfikatora zaznaczamy kolorem
plt.ylim(ymax = 1.5, ymin = -1.5)
plt.xlim(xmax = 1.5, xmin = -1.5)
#dane testowe - klasa1 kolor niebieski, klasa2 kolor czerwony
plt.scatter(data[c1,0],data[c1,1],c='b')
plt.scatter(data[c2,0],data[c2,1],c='r')
#powierzchnia rozdzielająca
plt.plot([-1.5, 1.5],[1.5, -1.5])
plt.show()
Następna część - Test do rozdziału