Podręcznik

Zasadniczym celem klasyfikacji jest przyporządkowanie analizowanych obiektów zainteresowania do określonej klasy (kategorii, grupy itp.) znaczeniowej. Skutkiem klasyfikacji jest rozpoznanie treści (na różnym poziomie abstrakcji) przekazu w zakresie zdefiniowanym przez mechanizm klasyfikacji. Klasy mogą mieć ścisłą definicję znaczeniową, jak np. ''kot'' czy ''patologia'', przybliżoną (np. ''obcy obiekt'' w zastosowaniach monitoringu, kiedy to celem jest jedynie wskazanie przedmiotu dalszej analizy) lub też abstrakcyjną (np. wyszukujemy z rysunku wszystkie czworokąty jako obiekty o określonych cechach geometrycznych czy topologicznych, bez funkcji znaczeniowej, celem jedynie uporządkowania posiadanych zasobów).   

Istnieje wiele metod klasyfikacji, od rozwiązujących bezbłędnie problem liniowo separowalnych cech obiektów, rozstrzyganie na podstawie danych a priori rozkładów prawdopodobieństwa rozdzielanych cech metodą największej wiarygodności, aż po metody określające przynależność obiektów w przypadku silnego, wzajemnego wymieszania rozdzielalnych znaczeniowo klas w numerycznej przestrzeni jedynie dostępnych cech. Całe to zagadnienie można uogólnić jako poszukiwanie optymalnej hiperpłaszczyzny czy hiperpowierzchni rozdzielającej klasy przynależności obiektów zainteresowania. 

By jednak lepiej zrozumieć rolę metod klasyfikacji w różnego typu zastosowaniach rozpoznających, trzeba odnieść się do kategorii systemów uczących się  na podstawie danych reprezentujących dany problem. Uczenie to rozumiane jest przede wszystkim jako odkrywanie albo poznawanie specyfiki informacji zawartej w dostępnych danych, aby na tej podstawie można było przeprowadzić różnego typu wnioskowanie w warunkach niepewności. Można więc mówić tutaj o systemach inteligentnej analizy danych, przy czym można je podzielić na uczące się bez nadzoru (czyli tylko na podstawie dostępnych danych, opisanych wektorami cech) oraz pod nadzorem (inaczej z nauczycielem lub - na przykładach). Nadzorowane uczenie wykorzystuje dodatkowy zbiór danych (atrybutów, zmiennych) objaśniających podstawowy wektor danych treningowych (objaśnianych - próba ucząca). W tym przypadku chodzi o okrycie zależności czy reguły wiążącej oba rodzaje danych, służącej wnioskowaniu. 

W przypadku klasyfikacji obiekty $\mathcal{T}_i$ opisane za pomocą wektora cech \\ $\mathbf{x}_i=\mathbf{x}(\mathcal{T}_i)\ \in \ \mathbb{R}^n$ przypisywane są do jednej z wcześniej ustalonych klas decyzyjnych. Danymi objaśniającymi jest w tym przypadku zbiór etykiet (pojedynczych atrybutów jakościowych) $\phi_i=\phi(\mathcal{T}_i)\ \in \ \{1,2,\ldots,k\}$ określających przydział obiektów do jednej z $k$ klas. Próba ucząca składa się więc z ciągu par $(\mathbf{x}_i,\phi_i)$ służących uczeniu -- konstruowaniu klasyfikatora. 

Docelowo klasyfikator powinien poprawnie wskazać (przewidzieć) przynależność obserwowanych obiektów do właściwej klasy na podstawie  wektorów opisujących ich cechy. Ważnym elementem systemu uczącego się jest więc sposób oceny końcowej skuteczności klasyfikacji, jak też szacowanie błędu klasyfikacji na kolejnych etapach procesu uczenia klasyfikatora. Zwykle wykorzystywane miary czułości, specyficzności czy trafności liczone są względem referencyjnego zbioru etykiet zbioru uczącego (na etapie uczenia) czy też zbioru testowego, składającego się z przypadków odmiennych, które nie należą do zbioru uczącego (na etapie weryfikacji klasyfikatora). Problem klasyfikacji pod nadzorem jest często rozwiązywany metodami analizy dyskryminacyjnej. Innym przykładem uczenia się pod nadzorem o charakterze ilościowym jest metoda regresji liniowej, kiedy to na podstawie danych treningowych metoda uczy się wartości parametrów estymowanej funkcji regresji. 

Uczenie bez nadzoru bazuje jedynie na zbiorze przykładowych obiektów opisanych jedynie wektorami cech $\mathbf{x}_i$ nieetykietowanych. System uczący się służy uporządkowaniu i opisaniu obserwowanych danych, wykrycia struktury danych, wzajemnych zależności, regularności, inaczej -- do ich objaśnienia. Klasyfikacja bez nadzoru, nazywana też analizą skupień, klasteryzacją czy grupowaniem, sprowadza się do wyznaczenia zwykle rozłącznych klastrów czy skupień danych, gromadzących w jednej grupie dane o zbliżonych cechach. Niekiedy chodzi o wskazanie obiektów nietypowych, o cechach odbiegających od pozostałych. Ważną rolę w tym przypadku odkrywa kryterium grupowania, sposób inicjalizacji czy też określania aktualnej przynależności danych do skupisk w iterowanym procesie uczenia.  

Projektowanie klasyfikatora pod nadzorem może niekiedy obejmować wstępną fazę grupowania, czy rozdzielenia zbioru danych uczących (treningowych) na rozłączne podzbiory przynależności do określonej liczby klas metodą uczenia bez nadzoru. W metodzie grupowania $k$ średnich następuje grupowanie na  zasadzie iteracyjnego przeplatania metod najbliższego sąsiada (przypisanie do reprezentacyjnego przedstawiciela najbliższej z $k$ klas według przyjętej reguły odległościowej) oraz centroidu (środek ciężkości obiektów aktualnie przypisanych danej klasie staje się nowym reprezentantem klasy). Ustalone według tej procedury, przy określonym kryterium stopu, minimalno-odległościowe granice przedziałów (regionów) poszczególnych klas mogą stanowić definicje klas użytych do klasyfikacji obiektów testowych (rozpoznawanych) metodą najbliższego reprezentanta klas. 

Modyfikacja tej metody, znana jako metoda grupowania $c$ średnich, wykorzystuje rozmyty model przynależności obiektu do poszczególnych klas (prawdopodobna jest przynależność obiektu do każdej z możliwych klas). Procedura grupowania polega na iteracyjnej modyfikacji prawdopodobieństw przynależności obiektów do klas na bazie danych treningowych, a ostateczne przypisanie obiektów do klasy odbywa się na zasadzie największego prawdopodobieństwa (wiarygodności). 

Zasadniczo wśród metod klasyfikacji pod nadzorem można wyróżnić metody należące do kategorii:

• klasyfikatorów bazujących na probabilistycznej teorii decyzji Bayesa, przy zastosowaniu znanych a priori rozkładów prawdopodobieństw (np. normalnych), ale też przy nieznanej postaci rozkładów (naiwny klasyfikator Bayesa, estymacja parametrów metodą największej wiarygodności, estymacja maksymalnej entropii czy mieszanina rozkładów); 
• klasyfikatorów liniowych (zasada perceptronu, liniowy dyskryminator Fishera, metoda najmniejszych kwadratów czy metoda wektorów nośnych i inne); ich zaletą jest prostota koncepcyjna i obliczeniowa, często efektem projektowanych klasyfikatorów są liniowe funkcje dyskryminacyjne;
• klasyfikatorów nieliniowych, będącym zazwyczaj uogólnieniem systemów liniowych (wielowarstwowy perceptron, sieci neuronowe, klasyfikatory wielomianowe, metoda wektorów nośnych z funkcjami jąder, drzewa decyzyjne, klasyfikatory łączone i inne); uogólniające rozszerzenie dotyczy też zwiększenia liczby klas w stosunku do podstawowej metody binarnej.

Liniowe funkcje dyskryminacyjne. Podstawowe zagadnienie klasyfikacji można sprawdzić do problemu przypisania obiektów opisanych wektorami cech ($n$-wymiarowym) do jednej z dwóch możliwych klas (binarny problem klasyfikacji) za pomocą liniowych funkcji dyskryminacyjnych. Przyjmijmy dla uproszczenia, że wartości wektorów cech obiektów obu klas są liniowo separowalne, czyli rozwiązanie za pomocą liniowych funkcji dyskryminacyjnych  pozwoli skutecznie rozwiązać ten problem. Zaprojektowanie klasyfikatora sprawdza się w tym przypadku do wyznaczenia hiperpłaszczyzny decyzyjnej, rozdzielającej wektory obu klas, postaci

z wektorem wag $\mathbf{w}=[w_1,w_2,\ldots,w_n]$ określającym kierunek oraz progiem $w_0$ precyzującym lokalizację hiperpłaszczyzny. $\mathbf{w}$ i $w_0$ należy ustalić w procesie uczenia klasyfikatora. Sposoby wyznaczania $\mathbf{w}$ różnicują metody klasyfikacji. Warto zauważyć, że $\mathbf{w}^T$ rzutuje $\mathbf{x}$ na hiperpłaszczyznę, a $|h(\mathbf{x})|$ jest miarą euklidesowej odległości wektora cech od płaszczyzny decyzyjnej. Dla skutecznie wyznaczonej hiperpłaszczyzny z jednej strony mamy dodatnie wartości $h(\mathbf{x})$ - dla wektorów cech  $\mathbf{x}$ obiektów jednej klasy, przyjmijmy $\Phi_1$), zaś z drugiej -- $h(\mathbf{x})$ dla obiektów drugiej klasy $\Phi_2$). Jeśli założymy, że wektor wag dla skutecznie wyznaczonej hiperpłaszczyzny wynosi $\tilde{\mathbf{w}}$, wówczas ogólnie można zapisać (z dokładnością do zawsze możliwej korekty $n$-wymiarowej przestrzeni  cech) 

Wyznaczenie skutecznego $\tilde{\mathbf{w}}$ jest klasycznym problemem optymalizacyjnym, a sposób poszukiwania rozwiązań wymaga zdefiniowania funkcji kosztu oraz algorytmu zmierzającego do minimalizacji wartości kosztu możliwych rozwiązań. I tak w przypadku algorytmów perceptronowych minimalizowana funkcja kosztu ma postać

gdzie $B$ jest zbiorem źle klasyfikowanych, za pomocą aktualnego $\mathbf{w}$, wektorów treningowych. Generalnie na  podstawie (4.76) wyznaczamy wektor wag jako 

Zmienne $\delta_x=-1$ dla $\mathbf{x} \in \Phi_1$ (został zaliczony do $\Phi_2$) oraz $\delta_x=1$ dla $\mathbf{x} \in \Phi_2$ (odwrotnie). Łagodna, iteracyjna zmiana wartości wektora wag odbywa się według zależności $\mathbf{w}(i+1)=\mathbf{w}(i)-\kappa_i\sum_{\mathbf{x} \in B} (\delta_x \mathbf{x})$, startując z losowo dobranej wartości $\mathbf{w}(0)$ oraz odpowiednio korygowanej w kolejnych krokach wartości współczynnika $\kappa_i$ (szybkość vs. dokładność przeszukiwań). Rozwiązanie nie jest jednoznaczne, gdyż hiperpłaszczyn skutecznie rozdzielających liniowo separowane wartości wektorów cech obiektów należących do dwóch klas może być wiele (zobacz rys. 4.26, po lewej). Istnieje wiele modyfikacji algorytmu perceptronu.

W metodzie średniokwadratowej (mean squares) funkcja kosztu ma postać

gdzie pożądany efekt wskazań klasyfikatora $\phi(\mathbf{x})=1$ dla $\mathbf{x} \in \Phi_1$  oraz \$\phi(\mathbf{x})=-1$ dla $\mathbf{x} \in \Phi_2$. Policzenie pochodnych cząstkowych $\mathcal{L}(\mathbf{w})$ po wektorze wag i przyrównanie do zera pozwala wyznaczyć optymalny $\tilde{\mathbf{w}}=E\big[\mathbf{x}\mathbf{x}^T\big]^{-1}E[\mathbf{x}\phi(\mathbf{x})]$ z macierzą autokorelacji $E\big[\mathbf{x}\mathbf{x}^T\big]$ oraz kros-korelacji $E[\mathbf{x}\phi(\mathbf{x})]$ wektorów danych treningowych oraz spodziewanych rezultatów ich klasyfikacji. Liczenie tych macierzy wymaga wstępnej znajomości rozkładów prawdopodobieństwa odpowiednich zmiennych -- uproszczeniem jest metoda najmniejszych kwadratów (least squares) z funkcją kosztu 

gdzie $\phi_i(\mathbf{x}) \in \{-1,1\}$ w przypadku dwóch klas, $t$ -- liczba wektorów treningowych. Rozwiązanie sprowadza się wtedy do rozwiązania układu równań normalnych z $n$ niewiadomymi i macierzą korelacji próbek przybliżającą macierz autokorelacji.

Rys. 4.26 Przykład liniowej separacji obiektów dwóch klas w przestrzeni cech $(x_1,x_2)$ za pomocą  różnych przebiegów prostej separującej (po lewej), przy czym prosta $\mathbf{w}_2$ zapewnia większy margines ''bezpieczeństwa'' $d_2>d_1$, czyli jest bardziej odległa od najbliższych obiektów każdej z klas (po prawej).

Metoda wektorów nośnych

Opisane wyżej metody, wykorzystujące różne funkcje kosztu pozwalają wykreślać różne hiperpłaszczyzny dając rozwiązania problemu liniowego na zbiorze uczącym. Jednak ze względu na spodziewaną wysoką skuteczność nauczonego klasyfikatora na zbiorze zróżnicowanych przypadków testowych, należałoby dobrać taką jej postać, która zapewni maksymalny margines  rozdzielający obie klasy przypadków. Chodzi o to, by margines błędu był możliwie duży na okoliczność klasyfikacji nieznanych przypadków. Dlatego jako bardziej użyteczną wybieramy hiperpłaszczyznę definiowaną przez kierunek $\mathbf{w}_2$ z rys. 4.26, ze względu na większą wartość symetrycznego (nie ma powodów, żeby uprzywilejowywać jedną z klas), obustronnego marginesu $d_2$. 

Doprecyzowany problem optymalizacji sprowadza się więc do wyznaczenia takiej hiperpłaszczyzny separującej liniowo przypadki dwóch klas, która zapewni maksymalny margines w odniesieniu do przypadków uczących. Rozwiązanie tego zagadnienia,  pozwalające jednoznacznie określić najbardziej użyteczną postać hiperpłaszczyzny zaproponowano w postaci metody (maszyny) wektorów nośnych -- SVM (Support Vector Machine). 

SVM jest przykładem klasyfikatora, który znajduje szerokie zastosowanie w aplikacjach multimedialnych. Koncepcja metody wektorów nośnych (podpierających, wspierających,  podtrzymujących), obejmująca w pierwszym okresie rozwoju rozważania teoretyczne, konstrukcję określonego modelu matematycznego, a następnie rozwijane z czasem realizacje algorytmiczne i atrakcyjne użytkowo  implementacje kształtowała się na przestrzeni kilkudziesięciu lat (pierwsze istotne prace pochodzą z lat 60. zeszłego stulecia). Dziś metoda ta, badana eksperymentalnie w rosnącej skali zastosowań potwierdza swoją użyteczność. 

Podstawą metody jest koncepcja przestrzeni decyzyjnej, która ulega podziałowi poprzez ustalenie granicy separującej obiekty o różnej przynależności klasowej. Na etapie uczenia klasyfikatora wyznaczana (rozpinana) jest hiperpłaszczyzna określonej przestrzeni cech, rozdzielająca z maksymalnym marginesem błędu przypadki uczące. 

Wracając do rozważań bardziej formalnych, symetryczny margines określający ''bezpieczną'' strefę rozdzielającą obie klasy, definiowany jest jako odległość od hiperpłaszczyzny najbliższego punktu danej klasy tak że 

Aby uprościć obliczenia znormalizujmy hiperpłaszczyznę, czyli przeskalujmy wartości wektora wag i progu tak, by wartości bezwględne $h(\mathbf{x})$ w najbliższych hiperpłaszczyźnie punktach każdej z klas wynosiły 1. Wtedy obustronna szerokość marginesu, przy skalowanych wagach, wynosi $\frac{2}{\|\mathbf{w}\|}$. Minimalizowana funkcja kosztu konstruowana jest w taki sposób, by zmaksymalizować margines separacji przy wykorzystaniu normy kwadratowej, czyli 

przy ograniczeniu 

czyli że odległość każdego z obiektów winna być $\geq \frac{1}{\|\mathbf{w}\|}$ oraz że wartości $h(\mathbf{x})$ są dodatnie dla przypadków klasy 1 i ujemne dla klasy 2. 
Przy rozwiązywaniu (4.81) ograniczenie to przyjmuje postać  

dla wartości mnożników Lagrange'a $\lambda_i \geq 0$.
  
Rozwiązaniem jest wektor wag $\tilde{\mathbf{w}}= \sum_{i=1}^t \lambda_i \phi_i \mathbf{x}_i$ wobec $\sum_{i=1}^t \lambda_i \phi_i$. Wartość $w_0$ może być wyznaczona na podstawie dowolnego z warunków (4.83) z niezerową $\lambda_i$ (częściej -- jako średnia po wszystkich takich wektorach). 

Optymalna w sensie (4.81) hiperpłaszczyzna jest więc liniową kombinacją wektorów treningowych z niezerową wartością $\lambda_i$, czyli wektorów aktywnych przy ustalaniu $\tilde{\mathbf{w}}$. Okazuje się, że dla $\lambda_i \neq 0$ warunek (4.83) jest spełniony jedynie przy $h(\mathbf{x}_i)=\pm 1$, czyli dla wektorów uczących leżących na dwóch brzegowych hiperpłaszczyznach stanowiących granicę strefy ''bezpieczeństwa'' (po obu stronach wyznaczanej płaszczyzny decyzji w odległości marginesu - linie przerywane wokół prostej separującej klasy na rys. 4.26, z prawej). Te wektory treningowe noszą nazwę \textbf{wektorów nośnych}. Inne wektory, dla których $\lambda_i = 0$ leżą na zewnątrz tej strefy lub niekiedy mogą także leżeć na jej granicy (czyli na wspomnianych hiperpłaszczynach brzegowych).

Generalnie metoda SVM rozwiązuje binarny (tj. dotyczący rozdzielenia dwóch klas) problem klasyfikacji. Jak pokazano, w najprostszym przypadku liniowo separowalnym wyznaczenie hiperpłaszczyzny separującej jest zadaniem optymalizacji kwadratowej. Określa się ją w iteracyjnym algorytmie uczącym, który minimalizuje dobraną funkcję kosztu. Metoda ta jest jednak nieskuteczna w przypadku, kiedy klasy nie są liniowo separowalne, tj. kiedy nie istnieje liniowa reguła klasyfikacji pozwalające bezbłędnie przyporządkować etykietę klas wszystkim danych treningowym (zobacz rys. 4.27). Uelastycznienie metody wymaga wówczas przedefiniowania funkcji kosztu oraz reguł ograniczających, które są skutkiem modyfikacji zasadniczej koncepcji klasyfikatora SVM, która dopuszcza występowanie przypadków wewnątrz marginesu separacji, a nawet błędne decyzji klasyfikacji.  W nowej sytuacji celem uczenia jest maksymalizacja marginesu separacji klas przy jednoczesnej minimalizacji dopuszczalnych przekroczeń granic tego marginesu.

Rys. 4.27 Przykład liniowo nieseparowalnego rozkładu wartości cech obiektów dwóch w przestrzeni decyzyjnej, kiedy to wewnątrz marginesu separacji pojawiają się przypadki treningowe (punkty szare i czarne), przy czym niektóre z nich są błędnie klasyfikowane za pomocą ustalonej hiperpłaszczyzny decyzyjnej (punkty czarne).

Dopuszczalna możliwość popełnienia błędu przy klasyfikacji wyraża się w osłabieniu ograniczenia (4.82) do postaci

gdzie $\xi_i \geq 0$ są wartościami nowej zmiennej ''rozluźniającej'' (slack) $\mathbf{\xi}$. Wynika z tego, że obserwacja zostanie błędnie sklasyfikowana, jeśli dla danego przypadku wartość $\xi_i > 1$. Na etapie uczenia klasyfikatora minimalizowana jest wtedy zmodyfikowana w stosunku do (4.81) postać funkcji kosztu:

gdzie stała $C$ jest stałą - współczynnikiem kary.  Celem optymalizacji jest ustalenie hiperpłaszczyzny na bazie właściwie dobranych wektorów nośnych, analogicznie jak w problemie liniowo separowalnym, dla której margines separacji będzie maksymalny, przy jednoczesnej minimalizacji liczby przekroczeń marginesu, tj. liczby przypadków, dla których $\xi_i > 0$. 

Problem braku liniowej separowalności klas można zwykle skuteczniej rozwiązać stosując klasyfikatory nieliniowe. Najczęściej stosuje się wówczas nieliniowe przekształcenie -- funkcję mapującą wektory cech obiektów w nową przestrzeń, zwiększając nierzadko jej wymiarowość, gdzie można skuteczniej zastosować metody liniowe i wyznaczyć separowalną hiperpłaszczyznę. Typowe postacie funkcji mapujących (inaczej funkcji jądra)  to funkcje wielomianowe, normalne, sigmoidalne, radialne RBF, tangensa hiperbolicznego nawet falkowe.

Klasyfikację według koncepcji SVM można również rozszerzyć na przypadek większej liczby klas jako zestaw problemów binarnych w konwencji jeden przeciw wszystkim (separacji przypadków danej klasy spośród wszystkich innych) lub też w konwencji jeden na jeden (na podstawie wyznaczonego w ten sposób zestawu hiperpłaszczyzn separujących ustala się ostateczne rozwiązanie metodą głosowania).