Atraminių vektorių klasifikatorius

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Jump to navigation Jump to search
 Broom icon.svg  Šį puslapį ar jo dalį reikia sutvarkyti pagal Vikipedijos standartus.
Jei galite, sutvarkykite.

Atraminių vektorių klasifikatorius (ang. support vector machine, SVM) [1] - sistemos mokymosi (machine learning) algoritmas skirtas klasifikuoti duomenims. Tai prižiūrimo mokymosi (supervised learning) metodas, kuomet siekiama suklasifikuoti jau pažymėtus (t. y. skirtingų, iš anksto žinomų klasių) duomenis.

Duomenų klasifikavimo problema[redaguoti | redaguoti vikitekstą]

Skirtingi būdai nubrėžti sprendimo ribą tarp dviejų klasių. Intuityviai, tiesė padalija duomenis geriau, nei tiesė .

Dažnai duomenų analizėje sutinkama problema − žinant dvi skirtingas klases kurioms priklauso turimi duomenys, priskirti naują duomenų tašką kažkuriai iš klasių. Šią problemą galima nesunkiai išspręsti, jeigu duomenys yra vienmačiai arba dvimačiai. Tačiau esant daugiau matmenų bei siekiant automatizuoti procesą reikalingi sudėtingesni algoritmai. Šie algoritmai kiekvieną turimų duomenų tašką priskiria kuriai nors (prižiūrimo mokymosi atveju žinomai) klasei. Tarp skirtingų klasių atsiranda taip vadinama sprendimo riba (decision boundary), kuri visus duomenis suskaido į sritis, priklausančias skirtingoms klasėms (žr. paveikslą dešinėje).

Apibrėžimas[redaguoti | redaguoti vikitekstą]

Klasifikavimas atraminiais vektoriais. Algoritmas maksimizuoja atstumą tarp punktyrinių linijų. Taškai, per kuriuos eina šios linijos vadinami atraminiais vektoriais.

Atraminių vektorių klasifikatorius (AVK) siekia surasti tiesę (sprendimo ribą) tokią, kad atstumas nuo jos iki dviejų taškų (tiesių einančių per juos), priklausančių skirtingoms klasėms būtų didžiausias (esant daugiau matmenų ši tiesė pavirsta hiperplokštuma). Šie ypatingi taškai nusako vektorius, vadinamus atraminiais vektoriais, nes jie vieninteliai daro įtaką sprendimo ribai. Formaliai sprendimo riba nusakoma vektoriumi ir skaliaru taip, jog galioja nelygybė

i-ajam duomenų taškui.

Čia yra i-ojo taško klasė ( arba ), yra vektorius nukreiptas į i-ąjį tašką. Pagal šią formuluotę, kiekvienas naujas taškas nusakomas vektoriumi yra klasifikuojamas surandant šio vektoriaus projekciją į ir pridedant skaliarą . Jei , taškas priskiriamas klasei , jei , taškas priskiriamas klasei .

Žinoma, norint taikyti AVK, reikia nustatyti vektoriaus ir skaliaro reikšmes. Tam pasinaudojama jau turimais duomenimis, žinant kuriai klasei priklauso kiekvienas taškas. Atstumas tarp tiesių, einančių per atraminius vektorius (punktyrinės linijos paveiksle dešinėje) išreiškiamas dydžiu Atraminių vektorių nustatymas susiveda į dydžio minimizavimą. Šis uždavinys sprendžiamas Lagranžo daugiklių metodu, kuomet ieškoma funkcijos ekstremumo daugiklių atžvilgiu. Ši funkcija lygi

čia - Lagranžo daugikliai lygūs 0 visiems i, išskyrus kai yra atraminis vektorius. Šią išraišką įprasta perrašyti (remiantis Karush-Kuhn-Tucker sąlygomis) kaip [2]

Apskaičiavus Lagranžo daugiklius , vektorius ir skaliaras išreiškiami pagal ir kur yra atraminiai vektoriai.

Netiesinis klasifikavimas transformacijos branduolių metodu[redaguoti | redaguoti vikitekstą]

Tiesiškai neatskiriami taškai paveikus juos transformacija tampa tiesiškai atskiriamais naujame atvaizdavime.

Dažnai neįmanoma nubrėžti tiesės (hiperplokštumos) taip, kad visi taškai būtų padalinti į dvi atskiras grupes. Tokiu atveju AVK metodas modifikuojamas, įvedant transformacijos funkciją , kuri kiekvieną tašką (nusakomą vektoriumi) transformuoja pagal . Tinkamai parinkus šią funkciją visi tiesiškai neatskiriami taškai įprastame atvaizdavime, taps tiesiškai atskiriamais funkcijos atvaizdavime. Dažnai įvedama taip vadinama transformacijos branduolio funkcija , kuria pakeičiamos visos vektorių skaliarinės sandaugos Lagranžiane . Šis virsta

Transformacijos branduolio funkcijos gali būtų įvairių formų ir parenkamos pagal situaciją. Keletas pavyzdžių [3]:

kur yra tam tikra matrica.

kur ir yra tam tikri skaičiai.

Šaltiniai[redaguoti | redaguoti vikitekstą]

  1. http://web.vu.lt/mii/j.zilinskas/DzemydaKurasovaZilinskasDDVM.pdf
  2. http://www.cogsys.wiai.uni-bamberg.de/teaching/ss06/hs_svm/slides/SVM_Seminarbericht_Hofmann.pdf
  3. Bishop, Christopher M. (2006). Pattern Recognition and Machine Learning