Reprezentacja wzorców¶

Tworzenie reprezentacji obiektów polega na zdefiniowaniu odwzorowania zbioru $O$ obiektów w zbiór ich reprezentacji. Obejmuje ona ustalenie liczebności zbioru uczącego oraz rodzaju cech opisujących każdy jego obiekt. Najpopularniejszym sposobem reprezentacji obiektu jest tzw. reprezentacja wektorowa. W metodzie tej zakłada się, że obiekt jest reprezentowany przez zbiór atrybutów ${{a}_{1}},...,{{a}_{p}}$, zbiór cech ze zbioru $A$, czyli nazwanych kategorii cech nominalnych bądź wielkości mierzalnych wynikających z obserwacji lub przeprowadzonego pomiaru. Atrybuty tworzą tak zwaną przestrzeń cech, zakładamy w tym miejscu, że przestrzeń cech jest podzbiorem ${{R}^{p}}$, a każdy obiekt reprezentowany jest $p$ wymiarowym wektorem cech, czyli poprzez $p$ liczb rzeczywistych. Ostatecznie zatem $p$-wymiarowy wektor cech jest postaci:

\[\begin{split}x_i=\begin{array}{lll} [x_{i1}, & \ldots, & x_{ip}]^T, \end{array}\end{split}\]

Zmierzone, przypisane wartości cech obiektu stanowią jego opis i są źródłem informacji o obiekcie a każdy z wektorów cech jest elementem tak zwanej przestrzeni cech.

Definicja 1

Przestrzenią cech $X$ nazywamy zbiór wszystkich wartości, które może przyjmować wektor cech $x$ obiektu.

Przykład 1

Rozważmy problem uczenia rozpoznawania kwiatów irysa. Obiektem podlegającym rozpoznawaniu jest tutaj zatem kwiat irysa występujący w jednaj z trzech odmian: setosa, virginica, versicolor. Wygląd kwiatów ilustruje rysunek rysunek 1

Rysunek 1: Źródło: wikipedia.org

Na wstępnym etapie rozpoznawania należy wybrać cechy opisujące obiekt, a więc przypisać obiektowi wektor cech, w tym przypadku będą to cztery cechy: długość, szerokość listka kielicha kwiatowego oraz długość, szerokość płatka kwiatu wyrażone w centymetrach. Zbiór $150$ kwiatów irysa z tak wybraną przestrzenią cech rozważany był w [Fisher1950]. Poniżej przedstawiamy skrypt języka Python wczytujący rozważany zbiór. W przykładach wykorzystywać będziemy pakiet scikit-learn dostępny pod adresem http://scikit-learn.org

import numpy as np
from sklearn.datasets import load_iris

#wczytanie zbioru danych
iris_data = load_iris()

#wektory cech
print iris_data.data

#etykiety klasowe - 0,1,2
print iris_data.target

#etykieta i odpowiada i-temu elementowi poniższej listy
labels=list(iris_data.target_names)
print labels

W dalszej części obiekt uczący utożsamiać będziemy z jego wektorem cech.

Przetwarzanie wstępne¶

Do przetwarzania wstępnego danych zaliczamy takie operacje, jak: normalizacja, skalowanie, czy analiza danych odstających. Normalizacja jest częścią wstępnej obróbki danych, jej zadaniem jest zapewnienie bezpośredniej porównywalności cech, które mogą być wyrażone w różnych jednostkach. Najczęściej stosowaną metodą normalizacji jest doprowadzenie danych do takiej postaci, aby wartości każdego z atrybutów miały wartość średnią równą $0$ i odchylenie standardowe równe $1$. Pojęcie normalizacji formalnie definiujemy poniżej:

Definicja 2

Normalizacją nazywamy takie przekształcenie obiektów, które każdy obiekt $x_i$ postaci $x_i=\begin{array}{lll} [x_{i1}, & \ldots, & x_{ip}]^T \end{array}$ przekształca w obiekty o następującej postaci

\[\begin{split}x_i^N=\left[\begin{array}{lll} \frac{x_{i1}-\bar{x}_1}{s_1}, & \ldots, & \frac{x_{ip}-\bar{x}_p}{s_p} \end{array}\right]\!,\end{split}\]

gdzie $\bar{x}_j$ dla każdego $j\leq p$ oznacza wartość średnią $j$-tej cechy w zbiorze danych wejściowych, tzn.

\[\bar{x}_j=\frac{1}{n}\sum_{i=1}^nx_{ij},\]

przy czym $n$ oznacza ilość obiektów w zbiorze, natomiast $s_j$ oznacza odchylenie standardowe ze względu na $j$-tą cechę, czyli:

\[s_j=\frac{1}{n}\sum_{i=1}^n\sqrt{\left(x_{ij}-\bar{x}_j\right)^2}.\]

Skalowanie jest szczególnym przypadkiem normalizacji danych. Operację tą stosujemy dla zapewnienia jednakowej istotności i porównywalności każdego z atrybutów w zbiorze uczącym. Polega ona na liniowym, bądź nieliniowym skalowaniu danych do odpowiedniego zakresu. Poprzez skalowanie liniowe rozumiemy liniowe ścieśnienie bądź rozszerzenie każdego z atrybutów na jednakowy przedział wartości. Najczęściej używanym przedziałem jest przedział $\left[ 0,1 \right]$. W takim przypadku operację skalowania liniowego zbioru uczącego $X$ definiujemy następująco:

Definicja 3

Skalowaniem liniowym na przedział math:[0,1], nazywamy liniową transformację obiektu

\[\begin{split}x_i=\begin{array}{lll} [x_{i_1}, & \ldots, & x_{i_p}]^T \end{array}\end{split}\]

zbioru wejściowego do następującej postaci

\[\begin{split}x_i^S=\left[\begin{array}{lll} \frac{\left(x_{i_1}-x_{min_1}\right)}{\max_{i=1,\ldots,n}\{x_{i_1}-x_{min_1}\}}, & \ldots, & \frac{\left(x_{i_p}-x_{min_p}\right)}{\max_{i=1,\ldots,n}\{x_{i_p}-x_{min_p}\}} \end{array}\right]^T\!,\end{split}\]

gdzie $x_{min_j}=\min_{i=1,\ldots,n}\{x_{ij}\}$ jest najmniejszą wartością cechy $j$.

Poprzez dane odstające rozumiemy próbki nietypowe, znajdujące się istotnie daleko od średniej rozkładu próbek w klasach. Ich analiza jest o tyle istotna, iż zaburzać mogą prawidłowy wynik zwracany przez algorytm klasyfikacji. W przypadku stwierdzenia niewielkiej ich ilości, na ogół są one usuwane. Możliwe jest również, że są one wynikiem specjalnej postaci rozkładu. W takich przypadkach zalecanym rozwiązaniem jest stosowanie algorytmów uczenia odpornych na dane odstające.

Podobieństwo między obiektami¶

Większość algorytmów uczenia klasyfikacji zarówno w przypadku nadzorowanym jak i nienadzorowanym wymaga określenia sposobu mierzenia podobieństwa między wektorami cech obiektów. Ustalenie miary odległości, czy inaczej mówiąc miary podobieństwa między obiektami lub grupami obiektów, pozwala na ilościowe określenie stopnia podobieństwa między nimi. Podobieństwo to może być rozumiane wprost, to znaczy wraz z jego wzrostem rośnie podobieństwo rozpatrywanych obiektów. Podobieństwo obiektów jest zatem wprost proporcjonalne do wartości miary podobieństwa. Wśród najczęściej stosowanych są jednak różne miary odległości, dla których im większa wartość tym obiekty są mniej do siebie podobne. Takie miary powinno się zatem nazywać miarami niepodobieństwa (ang. dissimilarity measure). Przyjmując, że każdy z obiektów zbioru uczącego jest reprezentowany w postaci $p$ wymiarowego wektora cech, załóżmy zatem że określamy miarę odległości dla wektorów ${{x}_{i}},{{x}_{j}}\in X\subset {{R}^{p}}$. Miarę tą oznaczamy symbolem $d\left( {{x}_{i}},{{x}_{j}} \right)$. Formalnie poprzez odległość rozumiemy funkcję, która parze obiektów przyporządkowuje liczbę nieujemną, spełniającą warunki metryki, zatem dla dowolnych ${{x}_{i}},{{x}_{j}},{{x}_{k}}\in X$ zachodzi:

\[\left( {{x}_{i}},{{x}_{i}} \right)=0\]

\[\left( {{x}_{i}},{{x}_{j}} \right)=d\left( {{x}_{j}},{{x}_{i}} \right)\]

\[d\left( {{x}_{i}},{{x}_{j}} \right)\le d\left( {{x}_{i}},{{x}_{k}} \right)+d\left( {{x}_{k}},{{x}_{j}} \right)\]

Powyższe warunki nazywamy odpowiednio warunkami zwrotności, symetryczności oraz warunkiem trójkąta.

Wśród najczęściej spotykanych miar odległości wyróżniamy:

Odległość euklidesową

\[{{d}^{2}}\left( {x}_{i},{x}_{j} \right)={{\left( {x}_{i}-{x}_{j} \right)}^{T}}\left( {x}_{i}-{x}_{j} \right)\]
Odległość Minkowskiego (norma ${{L}_{p}}$)

\[{{d}_{p}}\left( {{x}_{i}},{{x}_{j}} \right)=\sqrt[p]{\sum\limits_{k=1}^{m}{{{\left| {{x}_{ik}}-{{x}_{jk}} \right|}^{p}}}}\]
Odległość Mahalanobisa

\[{{d}_{M}}\left( {{x}_{i}},{{x}_{j}} \right)={{\left( {{x}_{i}}-{{x}_{j}} \right)}^{T}}{{\sum }^{-1}}\left( {{x}_{i}}-{{x}_{j}} \right)\]
Odległość Sebestyena

\[{{d}_{S}}\left( {{x}_{i}},{{x}_{j}} \right)={{\left( {{x}_{i}}-{{x}_{j}} \right)}^{T}}W\left( {{x}_{i}}-{{x}_{j}} \right)\]

Zauważmy, że odległość euklidesowa jest szczególnym przypadkiem odległości Minkowskiego dla $p=2$. W przypadku jej stosowania zaleca się znormalizowanie danych, bowiem skala atrybutów ma tutaj istotny wpływ na wartość tej odległości.

Przykład 2

W tym przykładzie zilustrujemy działanie operacji normalizacji oraz skalowania liniowego. Wygenerujemy losowo zbiór uczący dla dwóch atrybutów: pierwszy z rozkładu jednostajnego na $[1,5]$, drugi z rozkładu normalnego $N(3,2)$ (z wartością oczekiwaną równą 3 i odchyleniem standardowym równym 2). Wygenerowany zbiór 10 przykładów zilustrujemy wykresem, następnie poddamy normalizacji oraz skalowaniu. Obliczymy również odległości pomiędzy każdą parą wektorów tego zbioru.

from sklearn import preprocessing
from sklearn import metrics
import numpy as np
import matplotlib.pyplot as plt

#liczba próbek
N = 10

#próba losowa z rozkładu jednostajnego na przedziale [1,5]
x1 = 4*np.random.rand(N)+1

#próba losowa z rozkładu N(3,2)
x2 = 2*np.random.randn(N)+3

#umieszczany oba atrybuty w jednej macierzy
data=np.vstack((x1,x2))
#transpozycja - wartości atrybutu reprezentujemy w kolumnie
data=data.conj().transpose()

#wartości pierwszego atrybutu:
print data[:,0]

#wartości pierwszej próbki
print data[0,:]

#wykres ilustrujący próbki w przestrzeni cech
plt.scatter(data[:,0], data[:,1])
plt.show()

#wartości średnie dla atrybutów
print 'wartości średnie:'
print data.mean(0)
#odchylenia standardowe dla atrybutów
print 'odchylenia standardowe:'
print data.std(0)

#normalizacja
data_norm = preprocessing.scale(data)

print 'wartości średnie i odchylenia po normalizacji:'
print data_norm.mean(0)
print data_norm.std(0)

#przedział, na który dokonywane jest skalowanie
skalowanie = preprocessing.MinMaxScaler((0,1))
#operacja skalowania
data_skal = skalowanie.fit_transform(data)
print 'wartości minimalne i maksymalne atrybutów po przeskalowaniu:'
print data_skal.min(0)
print data_skal.max(0)

#macierz odległości euklidesowych między obiektami zbioru uczącego
odl_eukl=metrics.pairwise.pairwise_distances(data, metric='euclidean')
print 'Macierz odległości euklidesowych między elementami zbioru uczącego'
print odl_eukl

#macierz odległości euklidesowych między obiektami zbioru uczącego
print 'Macierz odległości Mahalanobisa między elementami zbioru uczącego'
odl_mah=metrics.pairwise.pairwise_distances(data, metric='mahalanobis')
print odl_mah

Następna część - Zadanie klasyfikacji nadzorowanej