Príklad:

Dvaja bratia vlastnia pozemok s rozlohou 8×8 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

Riešenie:

Matematická formulácia SVM:

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 1×44 – 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 44×1.

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.2895opt_b =   -2.7078

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

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 :).