A SVM OSZTÁLYOZÁSI ELJÁRÁS ALKALMAZÁSÁNAK Az SVM osztályozási eljárás alkalmazásának gyakorlati tapasztalatai GYAKORLATI TAPASZTALATAI
Dr. Kozma-Bognár Veronika1- Szilágyi Judit2 - Kőrösy Péter Ernő2 - Dr. Berke József2 1 Pannon
Egyetem, Georgikon Kar,
[email protected] 2 Gábor Dénes Főiskola, Alap- és Műszaki Tudományi Intézet,
[email protected]
Fény-Tér-Kép Konferencia, 2014. szeptember 25-26., Gyöngyös
TARTALOM SVM
KVANTUMSZÁMÍTÓGÉPEK
✓ Bevezetés ✓ Célkitűzések ✓ Anyag és módszer ✓ Kutatási helyszín ✓ Alkalmazott eszközök ✓ Support Vector Machine osztályozó eljárás
✓ Eredmények ✓ Találati pontosságok ✓ Futási idők
✓ Összefoglalás
?
CÉLKITŰZÉSEK Alapvető kutatási célok: - multispektrális légifelvételek elemzése - osztályozási eljárások alkalmazásainak vizsgálata (ENVI programba beépített ellenőrzőtt osztályozási módszerek) KIEMELT CÉL: A Support Vector Machine találati pontosságra és futási időre vonatkozó vizsgálata
+ “majdnem” kvantumszámítógép?
KUTATÁSI HELYSZÍN KIS-BALATON - Kányavári sziget •
Kis-Balaton a Balatonnal együtt világviszonylatban is egyedülálló az ökológiai rendszer.
•
Nemzetközi jelentőségét mutatja, hogy az 1975. decemberében hatályba lépett Ramsari egyezmény alapján Európa fokozottan érzékeny területei közé tartozik.
•
1920-as évek óta a Balaton-felvidéki Nemzeti Park Igazgatóságának fennhatósága alá tartozik.
•
Az 1970-es években merült fel a A Kis-Balaton Vízvédelmi Rendszer (KBVR) megépítésének szüksége, amikor a Balaton vízminősége veszélybe került.
KIS-BALATON
A KBVR I. ütemének a Hídvégi-tónak az üzembehelyezésére 1985-ben került sor. A Kányavári-sziget ezen a területen helyezkedik el. A II. ütem részleges üzembehelyezése 1992-ben valósult meg. A 2012-ben kezdődött beruházás a II. ütem területének ökológiai monitoringját valósítja meg 2014. december 31-ig (Nyugat-dunántúli Vízügyi Igazgatóság honlapja), mely nem érinti a Kányavár-szigetet. A sziget a felszínborítási kategóriák osztályozásához megfelelő tesztterületként alkalamazható, hiszen az itt található növényállományokat tekintve a növényzete igen sokszínű.
ALKALMAZOTT ESZKÖZÖK
Paraméterek
Látható tartományú légifelvételek
Közeli infravörös tartományú légifelvételek
érzékelő típusa
Canon 30D
Canon 30DIR
repülési magasság (m)
400
400
spektrális tartomány (nm)
400-700
720-1150
geometriai felbontás (m2/pixel)
0,1
0,1
adatrögzítés mélysége (bit/pixel)
12
12
MULTISPEKTRÁLIS LÉGIFELVÉTELEK
VIS
NIR
ADATFELDOLGOZÁS ELŐFELDOLGOZÁS DxO 8, ENVI 5 Adobe Photoshop CS6
geometriai korrekció, mozaikolás, maszkolás
FŐFELDOLGOZÁS ENVI 5 Adobe Photoshop CS6
Microsoft Excel 2011
előfeldolgozottsági szint csatornaszám adatmélység
zajcsökkentés, osztályozás, ellenőrzés SVM Maximum Likelihood Mahalanobis
UTÓFELDOLGOZÁS hibamátrix
TEMATIKUSAN OSZTÁLYOZOTT FELVÉTEL
ALKALMAZOTT OSZTÁLYOZÓ ELJÁRÁS Support Vector Machine •
Egy statisztikai (döntéselméleti) alapokon nyugvó ellenőrzött osztályozási eljárás, amelynek alkalmazásával hatékonyan kezelhetőek a magas dimenziószámú, komplex vagy zajos felvételek.
•
Az eljárás az osztályokat döntési fával választja el egymástól, oly módon, hogy maximalizálja az osztályokat elhatároló éleket. Az osztályokat elválasztó felületet gyakran nevezik optimális hipersíknak, és a hipersíkhoz legközelebb álló tér pontjait jellemző-, vagy tartóvektoroknak (support vector).
•
Az eredeti Support Vector Machine eljárást az 1970-es években Vladimir N. Vapnik dolgozta ki, melyet 1982-ben publikált osztályozásra alkalmas algoritmusokkal együtt (Vapnik V.N. 1982).
•
A jelenleg általánosan használt formula Corinna Cortes és Vapnik nevével vált ismerté 1995-ben (Cortes C.-Vapnik V.N., 1995). Módszerei lineárisan elválasztható, lineárisan nem elválasztható és nemlineáris osztályozásra is egyaránt alkalmasak.
SUPPORT VECTOR MACHINE A lineárisan osztályozható esetekben a jellemzők terében az optimális hipersík meghatározása egy linerális függvény felírásával történik. Az N számú tanulóesetből álló (xi, yi) halmazon, ahol (yi) jelöli az osztálycímkét, értéke 1 vagy -1 aszerint, hogy (xi) mely osztályhoz tartozik, a döntési határ a következő egyenletben adható meg:
ahol
•
g az x pont távolsága a hipersíktól
SUPPORT VECTOR MACHINE Az osztályozás értelemszerűen annak figyelembevételével történik, hogy az adott pont a hipersík mely oldalán foglal helyet. Ezzel egyidőben a hipersíkkal párhuzamos síkok is meghatározásra kerülnek pozitív (hipersík fölött), illetve negatív irányban (hipersík alatt), melyek egy margót határolnak be, így megfelelő skálázás (w normálvektor hosszának alkalmas választása) esetén
aszerint, hogy x mely osztálynak eleme, ahol d a margó szélességét jelöli.
Egységes alakban felírva:
SUPPORT VECTOR MACHINE A módszer alkalmazása során bevezetett αi Lagrange szorzók segítségével az elválasztó hipersík egyenlete:
ahol b az alábbi egyenletrendszerből számítható:
SVM - KERNEL TÍPUSOK Az SVM módszertan kiterjeszthető nemlineáris esetekre is úgynevezett kernelek alkalmazásával. Az eredeti koordinátatérből az adatokat áttranszformáljuk egy új térbe, ahol elvégezhetjük a korábban már bemutatott optimalizálási módszert. Az előállított döntési határ a koordináta transzformáció inverzével az eredeti tér nemlineáris döntési felülete lesz.
ahol, • g a gamma értéket jelöli az összes kernel típusnál, kivéve a Linear • d a polynomial degree értéket jelöli a Polynomial kernel típusnál • r a bias értéket jelöli a Polynomial és Sigmoid kernel típusoknál
EREDMÉNYEK Találati pontosságok •
Az SVM osztályozó eljárás találati pontosságait az egyes vizsgálati típusokkal végzett osztályozások eredményképei alapján készített hibamátrixok kiértékelésével határoztuk meg.
•
Hat osztálykategóriát különítettünk el, amelyek a légifelvételeken pixelszám alapján - a következő megosztásban voltak:
• • • • • •
fa (18,4%), víz (7,9%), gyep (26,9%), árnyék (16,7%), út (1,9%) és egyéb (28,3%).
•
Az SVM osztályozó eljárás esetében mind a négy kerneltípusra vonatkozóan elkészítettük a hibamátrixokat.
•
Az egyes kerneltípusok minél megbízhatóbb összehasonlítása érdekében több előfeldolgozottsági szintű felvételeket elemeztünk.
EREDMÉNYEK Találati pontosságok Megvizsgáltuk a légifelvételek osztályozásának találati pontosságát:
•
VIS és a NIR tartományban készített légifelvételekből előállított munltispektrális légifelvételek (6 spektrális sáv)
•
az eredményeket összehasonlítottuk a VIS tartományban készített felvétellel (3-RGB sáv)
•
különböző adatmélységben történő feldolgozások
•
a zajszűrést megelőzően illetve a zajszűrést követően osztályozás
EREDMÉNYEK Találati pontosságok SVM egyes kerneltípusai által végzett osztályozási eljárások találati pontossága
Hiperspektrális osztályozó eljárások összehasonlítása
eredményképeken történt mérés alapján kerültek meghatározásra. Az egyes ROI-kon belül, a ROI intenzítás értéke alapján meghatároztuk a helyesen osztályozott pixelek számát,
melyet az adott ROI teljes képpontjainak számával elosztva, majd százzal szorozva
43. ábra A 21 sáv Maximum likelihood (középs! kép) és SAM (jobb oldali kép) metrika alapján osztályozott eredményképei. A bal oldali kép a 21 sávból választott, osztályozatlan felvétel.
megkaptuk százalékban a találati pontosságot.
Maximium likelihood
SAM
43. ábra A 21 sáv Maximum likelihood (középs! kép) és SAM (jobb oldali kép) metrika alapján osztályozott eredményképei. A bal oldali kép a 21 sávból választott, osztályozatlan felvétel.
Paralellepiped
Minimum distance
Mahalanobis
44. ábra A 21 sáv Parallelepiped (bal oldali kép), Minimum distance (középs! kép) és Mahalanobis (jobb oldali kép) metrika alapján osztályozott eredményképei.
ÁTLAGOS TALÁLATI PONTOSSÁG (%)
Osztályozás típusa
Teljes kép (359 sáv)
Mahalanobis Maximum likelihood SAM Parallelepiped Minimum distance ÁTLAG
96.21 98.16 75.91 65.35 80.61 83.40
SFD Zaj nélkül (300 sáv) 98.61 98.49 76.66 73.45 80.56 85.56
SFD Optimális (6 sáv) 86.09 96.08 75.23 68.00 82.68 81.61
SFD Optimális (21103 sáv) 92.74 97.71 74.40 72.84 79.46 83.43
ÖSSZESEN 93.41 97.61 75.55 69.91 80.83
• Spectral Information Divergence (SID), Binary Encoding (BE) - esetén átlagosan, jelentősen alacsonyabb értékeket kaptunk a
vártnál (SID - 68.73% és BE - 49.64% értékek). 44.•ábra A 21 sávNet Parallelepiped (bal oldali kép), Minimum distance (középs! kép)ugyan és Mahalanobis Neural - NN, Support Vector Machine - SVM jelentősen magasabb értékeket adott (NN - 91.09%, SVM - 95.43 %), (jobb oldali kép) metrika alapján osztályozott eredményképei. ugyanakkor csak 6 vagy 21 optimális sáv esetén volt elfogatható időn belüli a futási idő (3-4 óra). A zaj nélküli (300 sáv) vagy a teljes képre (359 sáv) a mérések alapján becsült futási idő meghaladta volna az 1000 órát (40 napot) egy asztali számítógép esetén (CPU: 2.4 GHz, 4 mag, RAM: 4 GByte), ami nem elfogadható a mai gyakorlati alkalmazások eredményeit illetően, ezért nem kerültek elvégzésre. 103
EREDMÉNYEK Találati pontosságok Suppost Vector Machine összehasonlítása a Mahalanobis Distance és Maximum Likelihood által végzett osztályozási eljárások találati pontosságával: •
Az átlagokat figyelembe véve a Mahalanobis Distance 64,07%, a Maximum Likelihood 67,06% találati pontosságot ért el.
•
Amennyiben összehansonlítottuk az SVM négy kerneltípusával, azt tapasztaltuk, hogy az osztályozások végereménye ennél magasabb találati pontosságot eredményezett (kivétel bizonyos esetekben a Sigmoid).
•
Bár a 6 sáv osztályozása során magasabb találati pontosságokat kaptunk, mint a 3 sáv osztályozása során, elmondható hogy minkét esetben az SVM eljárások teljesítettek a legjobban.
FUTÁSI IDŐK MÉRÉSE Az ENVI az SVM eljárás használatakor egy hierarchikus, felbontáscsökkentő folyamatot hajt végre, mely az elfogadható futási idő érdekében az eredmények megbízhatóságának drasztikus csökkenése nélkül ad nagy pontosságú osztályozási eredményt. Ennek következtében a futási idő szempontjából a nagy felbontású, többsávos felvételeknél az SVM osztályozási eljárás meglehetősen számítás-, és erőforrásigényes.
A futási idők vizsgálatakor a CPU-k kihasználtságát a Mac OS X beépített Activity Monitor 10.7.4, GUI alapon működő alkalmazás segítségével kísértük figyelemmel. A vizsgálati eszköz főbb paraméterei a következőek voltak • Processzor: 2 x 2,66 GHz 6-Core Intel Xeon, • Memoria: 48 GB 1333 MHz DDR3 ECC, • Grafikus kártya: ATI Radeon HD 5770 1024 MB, • Operációs rendszer: Mac OS X Server Lion 10.7.5.
EREDMÉNYEK Futási idők
ÖSSZEFOGLALÓ •
a Support Vector Machine osztályozási eljárás használja a legösszetettebb matematikai reprezentációjú algoritmust az ENVI szoftverben található felügyelt osztályozási eljárások közül.
•
Ebből a komplexitásból adódik, hogy a mérések során tapasztalt feldolgozási idők is magasabbak azok időszükségleténél, valamint az is, hogy a futási idő erősen függ a helyes paraméterezéstől.
•
Azonban a hibamátrixok elemzéseiből kitűnik, hogy az egyes osztálykategóriákra vonatkozó találati pontosság tekintetében kiemelkedőbb eredményeket produkál, amennyiben megfelelő a paraméterezés vagy előfeldolgozás. Jelen publikáció a TÁMOP-4.2.2.A-11/1/KONV-2012-0064 számú "Az éghajlatváltozásból eredő időjárási szélsőségek regionális hatásai és a kárenyhítés lehetőségei a következő évtizedekben" című projekt keretében készült. A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg.
A SVM OSZTÁLYOZÁSI ELJÁRÁS ALKALMAZÁSÁNAK GYAKORLATI TAPASZTALATAI
Dr. Kozma-Bognár Veronika1- Szilágyi Judit2 - Kőrösy Péter Ernő2 - Dr. Berke József2 1 Pannon
Egyetem, Georgikon Kar,
[email protected] 2 Gábor Dénes Főiskola, Alap- és Műszaki Tudományi Intézet,
[email protected]
Fény-Tér-Kép Konferencia, 2014. szeptember 25-26., Gyöngyös