Príklad:

Dvaja bratia vlastnia pozemok s rozlohou 8x8 km. Obaja bratia si na pozemku vysadili stromy. V súbore bratia.mat sa nachádzajú súradnice stromov jedného aj druhého brata. Bratia sa na pozemku rozhodli postaviť rovný plot (priamka), ktorý od seba oddelí stromy vysadené prvým a druhým bratom. Plot navrhli tak, aby čo najmenej stromov pripadlo bratovi, ktorý ich nevysadil.

(Tento príklad bol súčasťou cvičenia č. 10 kurzu Optimalizácia.)

Odkaz na súbor bratia.mat
http://www.kirp.chtf.stuba.sk/moodle/mod/resource/view.php?id=25931

alt

Riešenie:

Matematická formulácia SVM:

alt

Riešením optimalizačného problému je separátor - priamka s predpisom a₁x + a₂y + b = 0. Koeficienty a₁ a a₂ sú prvkami vektora a. Vektory u a v sú tzv. zmäkčovacie premenné. Parameter γ v účelovej funkcii určuje pomer medzi šírkou separačnej medzery a počtom zle klasifikovaných bodov. Tento parameter zvolíme.

M - file:
Prvým krokom je načítanie súboru bratia.mat pomocou príkazu load.

load bratia.mat

Po načítaní súboru môžme vidieť v okne Workspace vektory b1sx, b1sy, b2sx a b2sy (všetky vektory sú rozmeru 1x44 - každý brat vysadil 44 stromov). Vektor b1sx obsahuje x-ové súradnice stromov prvého brata, vektor b1sy y-ové súradnice stromov prvého brata. Vektor b2sx obsahuje x-ové súradnice stromov druhého brata, vektor b2sy y-ové súradnice stromov druhého brata. Vytvoríme matice b1 a b2. Matica b1 bude obsahovať x-ové aj y-ové súradnice stromov prvého brata, matica b2 x-ové aj y-ové súradnice stromov druhého brata.

b1 = [b1sx; b1sy];
b2 = [b2sx; b2sy];

Pomocou príkazu sdpvar zadefinujeme optimalizované premenné - vektor a, u, v a skalár b.

sdpvar b;
a = sdpvar(2,1,'full');
u = sdpvar(44,1,'full');
v = sdpvar(44,1,'full');

Zadefinujeme parameter γ:

gama = 1;

Pomocou funkcie ones vytvoríme jednotkový vektor rozmeru 44x1.

one_vector = ones(44,1);

Vytvoríme účelovú fukciu. Maximalizujeme vzdialenosť separátora od bodov (alebo minimalizujeme prevrátenú hodnotu) a zároveň minimalizujeme počet zle klasifikovaných bodov.

ucelova_funkcia = 1/4*a'*a + gama*(one_vector'*u + one_vector'*v);

Zadefinujeme ohraničenia presne podľa matematickej formulácie. Všetky ohraničenia sú v tvare nerovností. (Pozor na rozmery!)

ohranicenia = [u>=0; v>=0;
               a'*b1 + one_vector'*b >= one_vector' - u';
               a'*b2 + one_vector'*b <= -one_vector' + v'];

Optimalizačný problém vyriešime použitím funkcie optimize. Prvým vstupným argumentom sú ohraničenia, druhým je účelová funkcia.

optimize(ohranicenia,ucelova_funkcia)
opt_a = value(a)
opt_b = value(b)

Výsledky:

Optimization terminated.

ans = 

    yalmiptime: 1.4415
    solvertime: 3.3755
          info: 'Successfully solved (QUADPROG)'
       problem: 0

opt_a =

    1.0060
   -0.2895

opt_b =

   -2.7078

Separátor bude v nasledovnom tvare:
1,0060x - 0,2895y - 2,7078 = 0

alt

Zhrnutie na záver:
Moja prvá testovacia jazda vyšla nad očakávania. Potvrdzujem, že Yalmip šetrí čas aj energiu pri riešení optimalizačných problémov. Keďže vyššie uvedený kód rieši iba jeden konkrétny problém, v nasledujúcich dňoch by som chcela vyzvať svoje mozgové závity na súboj a dať dokopy program, ktorý bude riešiť ľubovoľný klasifikačný problém. Takýto program by som potom vedela využiť vo svojom bakalárskom projekte. Želám si veľa šťastia :).

← OptiBlog

Yalmip test: Support Vector Machine (2D problém)

Príklad:

Riešenie: