1 Cel ćwiczenia. 1
POLITECHNIKA ÅšL
SKA
w Gliwicach
WYDZIAA
AUTOMATYKI, ELEKTRONIKI i INFORMATYKI
Instytut Elektroniki
Zakład Elektroniki Biomedycznej
LABORATORIUM
BIOCYBERNETYKI
SVM
Maszyna wektorów podpierających
Opracowała: mgr inż. Joanna Czajkowska
1 Cel ćwiczenia.
Celem ćwiczenia jest zapoznanie studentów z zasadą działania oraz wykorzystaniem klasyfikatora SVM. Przeba-
dane zostanie działanie narzędzia w zastosowaniu do klasyfikacji różnego typu danych, między innymi pacjentów
z dwoma odmianami białaczki, na podstawie obrazu ekspresji ich genów.
2 SVM - Maszyna wektorów podpierających
Maszyna wektorów podpierających (ang. Support Vectors Machine) została wprowadzona przez V. Vapnika i jego
współpracowników w 1995 roku. Inną często spotykaną nazwą dla tego narzędzia jest sformułowanie  klasyfikator
maksymalnoodległościowy , co oddaje po części istotę jego działania, czyli maksymalizację odległości granic
marginesu. Ogólnie rzecz ujmując celem metody jest separacja danych przy zachowaniu dość ostrych wymagań
statystycznych.
Zasadniczym celem klasyfikacji metodą SVM jest rozdzielenie danych na dwie grupy za pomocą hiperpłasz-
czyzny
wT x + b = 0 (1)
w oparciu o decyzje podejmowane na podstawie
d(x) = sign[wT x + b]. (2)
Wygodnie jest przyjąć zgodnie z [1], że dobór parametrów (w, b) odbywa się wedle propozycji Rosenblatta
metodÄ…
wp+1 = wp + ypxp, (3)
2 SVM - Maszyna wektorów podpierających 2
gdzie p oznacza bieżący numer przykładu uczącego, w oznacza wektor wag, x oznacza przykłady uczące, a y
wyjścia przykładów uczących y " {ą1}.
Początkowy wektor wag jest zerowy. Podczas iteracji są dodawane lub odejmowane aktualne dane w zależności
od ich bieżącej klasyfikacji, stąd ostatecznie wektor wag będzie liniową kombinacją tych danych
P
w = Ä…pypxp = 0. (4)
p=1
Współczynniki ąp są liczbami całkowitymi, mówiącymi ile razy punkt został niepoprawnie sklasyfikowany. Funk-
cja decyzyjna przyjmie zatem postać
P
d(x) = sign( Ä…pyp[xp]T x + b), (5)
p=1
a uczenie odbywa się przez modyfikację wartości współczynników ą i b. Przy czym wcześniej nie opisane b " R
jest wyrażeniem błędu, odchylenia (ang. bias).
Posługując się przykładem z Rys. 1 można dowieść, że istnieje nieskończenie wiele różnych sposobów separacji
danych. W metodzie SVM, proponuje się, żeby optymalną hiperpłaszczyzną była ta, która zapewni największy
(symetryczny względem płaszczyzny rozdzielającej) margines separacji danych uczących. Płaszczyzna ta jest
zaznaczona na Rys. 2 kolorem niebieskim. Optymalną hiperpłaszczyzną separującą jest ta, dla której
max min{ x - xp : x " F, wT x + b = 0, p = 1, 2, ..., P }, w " F, b " R. (6)
w,b
Rys. 1: Hiperpłaszczyzny separujące dwa zbiory [4]
Oprócz hiperpłaszczyzny separującej wyróżnia się również tzw. hiperpłaszczyzny kanoniczne (ang. canonical
hyperplanes), na których dla każdego punktu uczącego xp spełniony jest warunek
min |wT xp + b| = 1. (7)
xp
Dane uczące, dla których
|wT xp + b| = 1 (8)
nazywane są wektorami podpierającymi (ang. support vectors)[3]. Odległość oznaczona na Rys. 2 jako ł jest
szukaną maksymalną szerokością marginesu separacji, obiekty uczące leżące na prostych w kolorze zielonym są
2 SVM - Maszyna wektorów podpierających 3
wspominanymi wektorami podpierającymi. Szerokość marginesu wynosi [1]
2
Å‚ = . (9)
w
Rys. 2: Maksymalna odległość marginesu separacji [4]
Drogą prowadzącą do maksymalizacji marginesu ł jest minimalizacja normy wektora wag w , co jest rów-
noznaczne z minimalizacjÄ…
2
wT w = wi (10)
przy ograniczeniach
yp(wT xp + b) d" 1. (11)
Zadanie to jest w teorii optymalizacji znane jako problem optymalizacji kwadratowej z ograniczeniami nierów-
nościowymi. Problem taki rozwiązuje się wprowadzając nieujemne parametry ąp zwane mnożnikami Lagrange a
i funkcjÄ™ Lagrange a postaci
p
1
L(w, b, Ä…) = wT w - Ä…p[yp(wT xp + b) - 1] (12)
2
p=1
przy Ä… e" 0.
Funkcję tę należy minimalizować względem parametrów w i b, natomiast maksymalizować względem ąp, za-
tem poszukiwany jest punkt siodłowy. Zgodnie z warunkami Kuhna-Truckera w punkcie siodłowym pochodne
cząstkowe L względem w i b zerują się
P
"L(w, b, Ä…)
"
|w=w ,b=b" = w" - Ä…pypxp = 0 (13)
"w
p=1
P
"L(w, b, Ä…)
"
|w=w ,b=b" = Ä…pyp = 0 (14)
"w
p=1
stÄ…d
P
w" = Ä…pypxp (15)
p=1
Ä…pyp = 0 (16)
2 SVM - Maszyna wektorów podpierających 4
w", b" i ą" spełniać muszą także uzupełniające warunki Karusha-Kuhna-Truckera szerzej opisane w [1]:
Ä…p[yp(wT xp + b) - 1] = 0 dla p = 1, ..., P. (17)
Z powyższych rozważań można wnioskować, że optymalny wektor w" zależy tylko od danych uczących x",
których mnożniki ąp są niezerowe. Są to wektory podpierające.
Wstawiając powyższe wyrażenie do wzoru (12), po przekształceniach, z którymi można się zapoznać w [1]
otrzymujemy
1
L(w", b", Ä…) = 1T Ä… - Ä…T H Ä… (18)
2
gdzie 1 - wektor jednostkowy; ą - wektor współczynników ąp, H - Hesjan o elementach hpq = ypyq[xp]T xq.
RozwiÄ…zujÄ…c zadanie
1
max L(w", b", Ä…) = 1T Ä… - Ä…T H Ä… (19)
Ä…
2
przy ograniczeniach
yT Ä… = 0 (20)
oraz warunku
Ä… e" 0 (21)
otrzymujemy optymalny wektor ą", co pozwala już obliczyć wartości parametrów w", b" [1].
W praktyce oprócz klasyfikatorów liniowych istnieje także bardzo często potrzeba zastosowania klasyfikato-
rów nieliniowych. W takich wypadkach zastosowanie metody SVM wymaga odwzorowania przestrzeni danych
wejściowych X, w której dane nie są liniowo separowalne, w taką przestrzeń F , w której liniowa separacja będzie
już możliwa (Rys. 3).
Rys. 3: Transformacja [4]
Funkcję odwzorowującą K taką, że dla wszystkich u, v " X
K(x, xp) = Ć(x), Ć(xp) (22)
gdzie Ć jest przekształceniem z przestrzeni danych X w przestrzeń cech F , nazywamy jądrem (ang. kernel).
Od odwzorowania ½ = Ć(x) wymaga siÄ™, aby umożliwiaÅ‚o podejmowanie decyzji klasyfikujÄ…cych dane w oparciu o
sign[(wT ½(xp) + b)]. (23)
3 Podział na wiele klas 5
Przydziału punktów do klas dokonuje się w oparciu o funkcję
P
d(x; Ä…", b") = sign{ Ä…"pypK(x, xp) + bp}. (24)
p=1
Istnieje wiele rodzajów funkcji jądra. Poniżej przedstawione zostały najczęściej używane [3]:
" Liniowa (ang. Linear)
K(x, xp) = x " xp (25)
" Wielomianowa (ang. Polynominal)
K(x, xp) = ( x, xp + 1)n (26)
gdzie n - stopień wielomianu
" RBF (ang. Gaussian Radial Basis Function)
x - xp
K(x, xp) = exp(- ) (27)
2Ã2
gdzie à - odlegÅ‚ość punktu przegiÄ™cia krzywej Gaussa wzglÄ™dem argumentu odpowiadajÄ…cego jej wartoÅ›ci
szczytowej
" Wielowarstwowy perceptron (ang. Multi-Layer Perceptron)
K(x, xp) = tgh(Á x, xp + ) (28)
gdzie Á - wartość skali, - przesuniÄ™cie
3 Podział na wiele klas
Metoda SVM w sposób naturalny przystosowana została do zadań podziału na dwie klasy. Można jednak
z łatwością przystosować ją do traktowania problemów podziału na wiele klas. Istnieją dwa podstawowe sposoby
takiego przystosowania [1]:
" rozwiązanie N (ilość klas) zadań podziału na dwie klasy
" przeprowadzenie klasyfikacji parami.
Zamiana problemu wielu klas na N zadań podziału na dwie klasy sprowadza się do uczenia N klasyfikatorów
systemem jeden przeciw wszystkim albo inaczej mówiąc systemem klasa-reszta. Co oznacza, że rozwiązując
poszczególne zadania dokonujemy separacji i-tej (i = 1, ..., N) klasy od klas pozostałych. Za każdym razem
powstaje nowa hiperpłaszczyzna:
T
y(x; wi, bi) = wi x + bi = 0. (29)
Wektory wspierające należące do klasy i spełniają równanie y(x; wi, bi) = 1, pozostałe natomiast - równanie
y(x; wi, bi) = -1. Jeżeli dla nowego wektora
d(x) = sign[y(x; wi, bi)] = 1, (30)
to jest on przydzielany do i-tej klasy.
Zdarza się jednak, że w wyniku powyższych działań, warunek klasyfikacji spełniony jest dla wielu klas, albo nie
jest spełniony dla żadnej. Obszary o niejednoznacznej klasyfikacji przedstawia Rys. 4 (zostały one zakreskowane).
3 Podział na wiele klas 6
Rys. 4: Wynik podziału na 3 klasy metodą SVM, klasa-reszta [6].
Przeprowadzając klasyfikację parami problem o N klasach zamieniany jest na N(N - 1)/2 zadań podziału
na dwie klasy. Hiperpłaszczyzna, która rozdziela parę klas i,j jest postaci
T
y(x; wij, bij) = wijx + bij = 0, (31)
przy czym y(x; wij, bij) = y(x; wji, bji). Klasyfikacji nowego wektora x dokonuje siÄ™ w oparciu o
arg max di(x), (32)
i=1,...,N
gdzie
N
di(x) = sign[y(x; wij, bij)]. (33)
i=1
Ponieważ może się zdarzyć kilka takich samych wartości di(x), również tutaj nie zawsze możliwa jest jed-
Rys. 5: Wynik klasyfikacji parami [6].
noznaczna klasyfikacja. Wynik klasyfikacji parami przedstawia Rys. 5. Wartości Dij odpowiadają funkcjom
y(x; wij, bij). W obszarze zakreskowanym mamy do czynienia z niejednoznacznÄ… klasyfikacjÄ….
4 SVM w Matlabie 7
4 SVM w Matlabie
Istnieje wiele implementacji klasyfikatora SVM opisywanych w literaturze i udostępnionych w sieci [5]. Na la-
boratorium wykorzystana zostanie implementacja stworzona w środowisku Matlab.
Opis funkcji:
SVMStruct = svmtrain(Training, Group)
Uczenie klasyfikatora SVM.
SVMStruct = svmtrain(..., Kernel_Function , Kernel_FunctionValue,...)
SVMStruct = svmtrain(...,  RBF_Sigma , RBFSigmaValue, ...)
SVMStruct = svmtrain(...,  Polyorder , PolyorderValue, ...)
SVMStruct = svmtrain(...,  Mlp_Params , Mlp_ParamsValue, ...)
SVMStruct = svmtrain(...,  Method , MethodValue, ...)
SVMStruct = svmtrain(...,  QuadProg_Opts , QuadProg_OptsValue, ...)
SVMStruct = svmtrain(...,  SMO_Opts , SMO_OptsValue, ...)
SVMStruct = svmtrain(...,  BoxConstraint , BoxConstraintValue, ...)
SVMStruct = svmtrain(...,  Autoscale , AutoscaleValue, ...)
SVMStruct = svmtrain(...,  Showplot , ShowplotValue, ...)
Parametry:
Training - zbiór danych uczących, wiersze odpowiadają poszczególnym przypadkom (osobnikom), a kolumny
opisujÄ… odpowiednie cechy.
Group - wektor bÄ…dz
macierz opisująca przynależność danych uczących do jednej z dwóch grup. Wiersze tego
wektora odpowiadajÄ… wierszom wektora opisujÄ…cego cechy.
Kernel_FunctionValue - łańcuch opisujący wykorzystywaną funkcję jądra.
" linear - funkcja liniowa (parametr domyślny)
" quadratic - funkcja kwadratowa
" rbf - radialna funkcja bazowa Gaussa
" mlp - perceptron wielowarstwowy
" polynomial - wielomian
RBFSigmaValue - liczba dodatnia okreÅ›lajÄ…ca wartość à dla funkcji jÄ…dra rbf. DomyÅ›lnie wartość 1.
PolyorderValue - liczba dodatnia określająca stopień wielomianowej funkcji jądra. Domyślnie wartość 3.
Mlp_ParamsValue - wektor dwuelementowy [p1, p2], określający parametry perceptronu. K = tanh(p1 " U "
V + p2). p1 musi być > 0, oraz p2 musi być < 0. Domyślnie [1, -1].
MethodValue - metoda optymalizacji:
" QP - programowanie kwadratowe
" SMO - algorytm minimalnej optymalizacji sekwencyjnej
" LS - metoda najmniejszych kwadratów
SMO_OptsValue - parametry określające metodę SMO.
BoxConstraintValue - ograniczenia separacji (Ä…i)
AutoscaleValue - parametr odpowiedzialny za przeskalowanie danych.
ShowplotValue - wybór graficznego wyświetlania wyniku uczenia (false, true).
4 SVM w Matlabie 8
SVMStruct - struktura opisujÄ…ca nauczony klasyfikator.
Group = svmclassify(SVMStruct, Sample)
Klasyfikacja z wykorzystaniem nauczonego wcześniej narzędzia SVM.
Group = svmclassify(SVMStruct, Sample,  Showplot , ShowplotValue)
Parametry:
SVMStruct - struktura opisujÄ…ca nauczony klasyfikator (svmtrain).
Sample - dane do klasyfikacji. Macierz danych testujących musi posiadać tyle samo kolumn (cech) co macierz
danych uczÄ…cych.
ShowplotValue - wybór graficznego wyświetlania wyniku klasyfikacji (false, true).
Group - wskazuje grupę, do której dany przykład został zaklasyfikowany.
CP = classperf(truelabels)
Obliczanie skuteczności klasyfikatora.
CP = classperf(truelabels, classout)
CP = classperf(...,  Positive , PositiveValue,  Negative , NegativeValue)
classperf(CP, classout)
classperf(CP, classout, testidx)
Parametry:
truelabels - postać etykiet klas:
" wektor danych numerycznych
" tablica komórkowa.
classout - określenie wyjścia klasyfikatora, jego rozmiar powinien pokrywać się z rozmiarem wektora (tablicy)
etykiet klas:
" wektor danych numerycznych
" tablica celi.
PositiveValue - wektor lub tablica zawierająca przewidywane wyjścia klasyfikatora.
NegativeValue - wektor lub tablica zawierająca przewidywane wyjścia klasy uczącej.
testidx - wektor zawierajÄ…cy obserwacje dotyczÄ…ce konkretnego testu.
CP - struktura opisująca jakość klasyfikacji.
Przykładowe pola struktury:
cp.CorrectRate - prawidłowo zaklasyfikowane przykłady.
tf = ismember(A, S)
Elementy tablicy opisane zbiorem.
tf = ismember(A, S,  rows )
[tf, loc] = ismember(A, S, ...)
Parametry:
A - macierz wejściowa, w której szukane są wartości (komórki) opisane za pomocą macierzy S
4 SVM w Matlabie 9
S - macierz wejściowa określająca szukane wartości
rows - parametr wskazujący na to, czy w przypadku gdy macierze A i S mają jednakową ilość kolumn, przy
porównywaniu zawartości, pod uwagę należy wziąć cały wiersz.
tf - macierz o rozmiarach macierzy A, w której komórki odpowiadające komórkom macierzy A, o wartościach
podanych przez S zawierają wartość 1, pozostałe natomiast 0. loc - wskazuje najwyższy indeks elementu ma-
cierzy S, który zawarty jest w macierzy A.
Przykład zastosowani klasyfikatora SVM do klasyfikacji danych fisheriris
1 load fisheriris; %wczytanie danych
2 data = [meas(:,1), meas(:,2)]; %wybór cech do klasyfikacji
3 groups = ismember(species, setosa ); %wyodrębnienie grupy  stetosa
4 [train, test] = crossvalind( holdOut ,groups); %wylosowanie grupy danych
5 %uczÄ…cych i testujÄ…cych
6 cp = classperf(groups);
7 svmStruct = svmtrain(data(train,:),groups(train), showplot ,true,...
8  Kernel_Function , linear , boxconstraint ,1000); %uczenie klasyfikatora Rys.6
9 pause;
10 classes = svmclassify(svmStruct,data(test,:), showplot ,true); %klasyfikacja Rys.7
11 classperf(cp,classes,test); %oszacowanie skuteczności klasyfikatora
12 cp.CorrectRate
13 pause;
14 hold on;
15 gr1=data(groups==1,:); %zaznaczenie wejściowych zbiorów danych Rys.8
16 gr=data(groups==0,:);
17 plot(gr1(:,1),gr1(:,2), b. );
18 plot(gr(:,1),gr(:,2), r. );
19 hold off
Rys. 6: Rezultat uczenia klasyfikatora SVM
5 Zadania do wykonania na laboratorium 10
Rys. 7: Rezultat klasyfikacji z wykorzystaniem nauczonego klasyfikatora SVM
Rys. 8: Nałożenie wejściowych zbiorów danych
5 Zadania do wykonania na laboratorium
1. Przetestować działanie klasyfikatora na danych syntetycznych (wartości wybrane losowo), dwuwymiaro-
wych. Sprawdzić działanie narzędzia wykorzystując różne płaszczyzny separujące.
2. Przetestować działanie klasyfikatora na danych fisheriris (przykład z Matlaba), dwuwymiarowych. Spraw-
dzić wpływ doboru cech oraz płaszczyzny separującej.
3. Przetestować działanie klasyfikatora na danych fisheriris, pełnowymiarowych. Sprawdzić wpływ doboru
cech oraz płaszczyzny separującej.
4. Stworzyć klasyfikator umożliwiający podział przestrzeni danych na 3 klasy, dowolnie wybraną metodą
(klasa-reszta, klasyfikacja parami). Przetestować działanie stworzonego narzędzia na danych iris, dla dwóch
dowolnie wybranych oraz dla wszystkich cech.
6 Zadania do wykonania w domu 11
6 Zadania do wykonania w domu
1. Powtórzyć podpunkty 2-4 z laboratorium na danych dotyczących ekspresji genów w konfiguracji podanej
przez prowadzącego. Opisać przeprowadzone eksperymenty numeryczne.
2. Odpowiedzieć na pytania podane przez prowadzącego.
7 Uwaga!
Ze względu na fakt, iż klasyfikator SVM nie jest omawiany na wykładzie, wymagana jest dobra
znajomość instrukcji do laboratorium.
Literatura
[1] P. S. Szczepaniak, Obliczenia inteligentne, szybkie przekształcenia i klasyfikatory, Akademicka Oficyna
Wydawnicza EXIT, Warszawa 2004.
[2] S. R. Gunn, Support Vector Machines for Classification and Regression. University of Southampton,10 May
1998.
[3] R. Meir, Support Vector Machines - an Introduction. Department of Electrical Engineering Technion, Israel.
[4] W. Kozłowski, Maszyny wektorów podpierajacych-Support Vector Machines (SVM),9 V 2006
[5] http://www.support-vector.net/software.html
[6] T. Inoue and S. Abe, Fuzzy Support Vector Maciner for Pattern Classification. Graduate School of Science
and Technology, Kobe University,Japan.