Strokovni; razprave Odločitvena drevesa in sistemi z večdimenzionalnimi rešitvami Matej Sprogar, Vili Podgorelec, Peter Ko ko I Fakulteta za elektrotehniko, računalništvo in informatiko Univerza v Mariboru, Smetanova 1?, 2000 Maribor rnatej.5pragar@uni-mb.5f Povzetek Pri sprejemanju odločitev je današnjemu strokovnjaku lahko v veliko pomoč sistem za podporo odločanju, ki je sposoben pregledati ogromne količine podatkov. Odločitveni sistem mora biti zanesljiv in tudi dovolj sposoben, da zadosti vsem zahtevam. Članek predstavlja razširitev koncepta odločitvenih dreves na multidimenzionalna - vektorska - drevesa, ki so sposobna dati odgovor na več različnih vprašanj hkrati, in evolucijski pristop h gradnji takšnih dreves. Vektorsko drevo pomeni zlitje več klasičnih odločitvenih dreves, ki delujejo nad isto množico atributov, a dajejo odgovore na različna vprašanja. Takšno drevo je enostavnejše za uporabo, lažje ga je analizirati in izraza možne povezave med končnimi odločitvami, ki drugače niso vidne. Predstavljeno je orodje DecRain, ki gradi vektorska odločitvena drevesa s pomočjo genetskih algoritmov. Abstract In the decision-making process the human expert will always appreciate help from a decision support system, which can examine huge amounts of data. Sucii a decision system should be reliable and should satisfy all the demands it might face. The article presents the extension of a common decision tree concept to a multidimensional - vector decision tree. Contrary to the common decision tree the vector decision tree can answer more than just one question at a time. It has the functionality of many separate decision trees acting on a same set of data and answering different questions. Vector decision tree is simpler in its form, it is easier to use and investigate and can express some relationships between decisions not visible before. DecRain is a special tool for the vector decision tree induction. In the article both the DecRain tool and its evolutionary approach to the vector decision tree induction are presented. Uvod Čeprav smo že krepko v informacijski dobi, so Številne naloge še vedno v domeni človeka. Ko gre za ključne odločitve, kjer ne sme biti napake, so neprecenljive prav izkušnje in osebni občutek posameznika. Informatika v takih primerih naleti na težko oviro, ki bi jo lahko premostila le s pomočjo razvoja inteligentnih programov, sposobnih učenja in razmišljanja na človeku podoben način. Inteligentni sistemi so zaenkrat Se utopična želja, poznamo pa nekaj njihovih lastnosti, ki jih lahko uporabimo pri načrtovanju sistema /.a pomoč pri odločanju. Tak sistem bi se po eni strani naslanjal na rešitve, ki izhajajo iz klasične informacijske teorije, po drugi pa na popolnoma drugačne koncepte programiranja, ki odpirajo nove poglede na problemsko področje. S tem bi premostili določene pomanjkljivosti Obstoječih informacijskih rešitev, ki pomagajo človeku v poplavi podatkov, niso pa sposobne dejansko razumeti obdelanih dejstev in izlušČenih relacij in jih tudi aktivno uporabiti pri novem problemu. Klasični princip torej temelji na programsko kodiranih načelih, ki so nespre- menljiva in absolutna in prav zato tudi močno omejujoča. Da bi premostili to absolutnost, je potrebno spremeniti ne le metodologijo, ampak tudi princip programiranja. Pri velikih problemih namreč ni dovolj le hitro izvajanje ukazov, ampak predvsem način iskanja rešitev. Tako je poglavitna težava največkrat prav velikost problemskega področja in število možnih kombinacij in odvisnosti, ki jih je enostavno nemogoče zajeti v deterministični algoritem. Kot alternativa so se pojavili evolucijski sistemi, ki črpajo ustvarjalno moč iz naravnih načel reprodukcije in selekcije. Kombinacija z določenim odločitvenim modelom nam tako lahko da izredno dober in učinkovit sistem za pomoč pri odločanju. Vloga sistema za pomoč pri odločanju je danes predvsem svetovalna, odločitveni sistem pa bi naj ob predlagani rešitvi nudit tudi razlago oz. utemeljitev odločitve, kar bi dodatno pomagalo strokovnjaku. Tako lahko človek lažje preveri smiselnost odločitve, ugotovi pomanjkljivosti ali nelogičnosti, pa tudi dobi 2000 ■ Številka 2 ■ letnik VIII i ifitvnf >» «H NFORM ATIKA Matej Š praga r. Vili Podgorelec, Peter Ko kol: Odločitvena drevesa in sistemi z večdimenzionalnimi rešitvami nova spoznanja. Področja uporabe takšnih sistemov so seveda izredno široka, predvsem so sistemi za podpori» odločanju primerni tam, kjer morajo biti odločitve sprejete hitro in z določeno stopnjo zanesljivosti. Za takšne naloge so se kot zelo dobra izkazala tudi odločitvena drevesa, saj so konceptualno zelo preprost model z možnostjo avtomatskega učenja [t]. Drugače uspešen klasični način gradnje odločitvenih dreves ima nekaj pomanjkljivosti, ki pa se jih da elegantno odpraviti prav z uporabo evolucijskih tehnik in genetskih algoritmov [3], Ker genetski pristop k izdelavi odločitvenih dreves odpira novo perspektivo in ne postavlja nobenih omejitev za iskano rešitev, je postalo zanimivo tudi hkratno odločanje o več različnih vprašanjih in primerjava takšnih rezultatov z drugimi drevesi in tudi drugimi sistemi odločanja. Klasični načini gradnje dreves so namreč dokaj omejujoči glede obsežnosti rešitve, kar je bii pogosto tudi razlog za izbiro katerega drugega odločitvenega modela, kot so npr. nevronske mreže. Z možnostjo hkratnega odločanja o več vidikih problema pa bi to težavo ne samo odpravili, ampak celo krepko presegli. V ta namen smo razvili sistem za generiranje odločitvenih dreves, ki je sposoben izdelati odločitvena drevesa z izhodom v obliki vektorja več odločitev namesto klasično ene same odločitve. Upali smo, da bo takšen sistem izkazal dodatne lastnosti, kot jih imajo npr. nevronske mreže, in imel hkrati vse prednosti odločitvenih dreves. Prvi rezultati so zelo vzpodbudni. Odločitvena drevesa Odločitvena drevesa spadajo med metode induktivnega učenja, torej avtomatskega učenja iz rešenih primerov. Ciij je odločitvena struktura - drevo, ki temelji na učnih primerih in je sposobno čim bolj uspešno "rešiti" še neznani primer. Sam proces učenja je zajet v oblikovanju dreves, saj odločitvena drevesa hranijo izluščeno znanje prav v svoji obliki. Samo drevo sestoji iz dveh vrst vozlišč - atributna (testna) vozlišča so testi vhodnih vzorcev, končni listi pa so kategorije testiranih vzorcev. Drevo bo vhodni vzorec klasificiralo s sprehodom od začet- , r ( gremo na izlet nega vozlišča do končnega lista ^ pustimo perilo s sprotnim odločanjem v vsakem vozlišču o nadaljnji smeri ^ lahko drevo uvrsti neki vzorec. Sami testi v notranjih vozliščih se lahko izvajajo nad numeričnimi ali diskretnimi vrednostmi in so torej ustrezne oblike, vsak list pa predstavlja možni odgovor na zastavljeno vprašanje. Glavni odliki dreves sta njihova preprostost za uporabo in izraznost rešitve ter naučenega znanja - zgradba drevesa je osnova za napoved, v kateri razred neki vzorec spada in katera vprašanja so pri tej odločitvi pomembna. Sama oblika odločitvenih dreves je zelo preprosta in nedvoumna, vendar pa pri klasični gradnji (učenju) nastopa kar nekaj problemov. Glavni problem je izbira vrstnega reda testov, če pa so testi še nad numeričnimi vrednostmi, je potrebno določili tudi sam test. Za učenje odločitvenih dreves je bilo predlaganih kar nekaj metod in večina od njih je osnovana ali izpeljana iz ideje Quinlanovega 1D3 algortima [6j[7], Ta pri izbiri vrstnega reda testov izbere vedno tisti test, ki maksimalno reducira neko na entropiji osnovano merilo. Takšno hevristično ocenjevalno funkcijo je možno uspešno razširiti iz binarnih atributov tudi na atribute z več vrednostmi [4], problemi pa se pojavijo pri klasifikacijah s širokim naborom razredov [5], Klasična odločitvena drevesa kot vhod sprejmejo nabor vhodnih atributnih vrednosti, kot izhod pa v listu drevesa podajo eno samo odločitev. Zamišljena razširitev pa za razliko od tega kot izhod podaja vektor več ločenih odločitev, od katerih ima vsaka svoj nabor vrednosti. Takšno drevo torej klasificira neki vzorec ne samo po enem, ampak po več kriterijih hkrati. Razlika med vektorskimi in klasičnimi drevesi je torej lc v končnih listih, ki podajajo odločitve, vsa ostala vozlišča pa so funkcionalno enaka. Slika 1 podaja primer preprostega vektorskega odločitvenega drevesa z dvema odločitvama. Atributna vozlišča postavljajo vprašanja o dejstvih, v listih dreves pa imamo naučeno odločitev. Atributi so v tem trivialnem primeru podatki o vremenu, učna množica pa so podatki o preteklih izkušnjah. atrihiitna vozlišče sprehoda. Sama drevesa se ločijo po številu testov, ki jih lahko opravimo v enem vozlišču, po številu možnih odgovorov in tudi po številu razredov, kamor list drevesa Slika 1: preprost primer vektorskega drevesa z dvema odločitvama 80 j jf* fiuIh ml N FOR M ATIKA 2000 ■ številka 2 - letnik Vlll Matej Š praga r. Vili Podgorelec, Peter Ko kol: Odločitvena drevesa in sistemi z večdimenzionalnimi rešitvami Evolucijski model, genetski algoritmi Evolucijski model povzema idejo naravne evolucije. Kot se skozi evolucijo razvijajo, izumirajo in spreminjajo biološke populacije, se tudi naše rešitve razvijajo po načelih »naravne selekcije«. Torej lahko z računalniškim tekom dejansko simuliramo naravne procese selekcije, razmnoževanja, tekmovanja... Z genetskimi algoritmi lahko najdemo rešitve tudi najbolj kompleksnih problemov, saj se za razliko od klasičnih iskalnih strategij problema lotijo na popolnoma svojevrsten način. Genetski algoritem je preslikava iz narave v računalniški svet, kjer prav tako ustvarimo populacijo bolj ali manj dobrih rešitev znotraj iskalnega prostora. Populacijo predstavljajo posamezni osebki, opisani z genetsko kodo, ki določa njihove lastnosti. Tako lahko sprememba genetske kode osebka povzroči spremembo njegovih lastnosti, obnašanja, torej napredek ali tudi nazadovanje glede na iskane lastnosti. S pomočjo genetskih operatorjev selekcije, križanja in mutacije lahko potem razvijamo genetsko sliko osebkov v populaciji. S tem se hkrati premikamo po iskalnem prostoru, dokler ne najdemo točke - osebka, ki predstavlja zadovoljivo rešitev. Osrednjo vlogo v evoluciji imajo genetski operatorji, ki zagotavljajo spreminjanje in v. splošnem napredovanje osebkov skozi Čas. Selekcija je način izbora osebkov za reprodukcijo in s tem tudi preživetje genetskega materiala v produciranih potomcih. Operator križanja proizvede nov osebek iz dveh staršev s pomočjo križanja njune genetske kode. Samo križanje mora glede na obliko osebka zagotavljati tudi logično pravilno končno genetsko sliko, ki bo definirala zdrav osebek, sposoben boja za obstanek. Občasno uporabljen operator mutacij pa zagotavlja vnos potrebnih nenadzorovanih sprememb, ki dajo populaciji nov zagon. Tako kot v naravi tudi tukaj genetski operatorji ne zagotavljajo vedno pridobitve novih kvalitet in imajo lahko tudi dokaj velik destruktiven učinek, kar pa je nujni del evolucije [12]. Združitev odločitvenih dreves in evolucijskih načel Ker za gradnjo odločitvenih dreves obstajajo močne teorije [6\[7\, bi lahko celo opustili nadaljnje raziskave v tej smeri. Vendar je gradnja odločitvenih dreves kompleksen problem, ki ga ni mogoče vedno uspešno opisati in rešiti s statističnimi metodami. Težave lahko nastopijo pri pomanjkljivih ali napačnih podatkih, pri določanju atributov in ustreznih razmejitvenih intervalov. In če že uspemo rešiti te probleme, pa rezultati včasih enostavno niso dovolj dobri. Razlogi so potem lahko ali na strani gradnje dreves ali pa tudi v neprimernosti samih dreves za izbrano nalogo. Ker pa imajo drevesa nekaj izjemnih lastnosti, se je bilo smiselno distancirati od statističnih teorij in poiskati alternativne načine za gradnjo dreves. V skladu z razmišljanji v uvodu smo zato skušali združiti dva svetova preprost koncept odločitvenih dreves in sposobnost evolucijskega pristopa, da se loti še tako kompleksnega problema. Za razliko od klasičnega načina gradnje, ko učenje pomeni gradnjo enega samega drevesa od prvega vozlišča do zadnjega lista, pa evolucijski pristop postopa drugače. Najprej ustvari množico različnih osebkov - v našem primeru so to odločitvena drevesa - in jih nato oceni v skladu z želenimi lastnostmi in s poznanimi podatki. Šele nato pa pride na vrsto iskanje ciljnega drevesa s preoblikovanjem in z razmnoževanjem obstoječih dreves z uporabo genetskih operatorjev. Dejansko torej evolucija išče dobro rešitev na več mestih hkrati, genetski operatorji pa zagotavljajo končno konvergenco k boljši rešitvi. Seveda se lahko v procesu izoblikuje polno slabših dreves in naloga selekcije je, da ohrani in razmnožuje le najboljše. Zanimivo dejstvo je mogoče ravno to, da potomci ne smejo biti vedno absolutno boljši od svojih staršev, saj to vodi v lokalne optimume. Dejanski napredek evolucije pa je zagotovljen prav z raznolikostjo in prenašanjem ter kombiniranjem genetske kode. Gradnja odločitvenih dreves s pomočjo genetskega pristopa je že dala odlične rezultate [3] in pokazala določene prednosti pred klasičnim pristopom. Z razširitvijo odločitvenega drevesa na večdimenzionalno - vektorsko - odločitev pa pridobimo na funkcionalnosti dreves. Takšna razširitev bi bila s klasično metodo težko izvedljiva, izvedba z genetskim pristopom pa ne daje nikakršnih omejitev v obliki in obsegu vhodnih podatkov ali izhodnih odločitev. Orodje Dec Rain Eno trenutno najbolj uporabljanih orodij za gradnjo klasičnih odločitvenih dreves je zagotovo Quinlanpv C4.5 (in izboljšana verzija C5) algoritem [7], tam uporabljeni format pa nekakšna osnova za pripravo podatkov in predstavitev rezultatov. Pri izdelavi orodja Dec-Rain smo zato posnemali preprostost C5 in poskusili narediti gradnjo vektorskih dreves čim bolj enostavno. Ker zahteva priprava podatkov največ časa in lahko količina podatkov krepko preseže pregledne sposobnosti tekstovnega urejevalnika, pa zahteva DecRain podatke iz podatkovne baze, ki podpira ODBC standard, s čimer danes razpolaga večina boljših podatkovnih baz tako pod Windows kot tudi Unix in Linux okolji. Takšna oblika hkrati zagotavlja lažjo obdelavo, spremembe, nadzor in prenosljivost podatkov. Zaradi primerljivosti pa smo naredili tudi možnost pretvorbe v format, kot ga zahtevata orodji C5 in orodje MtDecIt [4], 2000 - Številka 2 - letnik VIII i ipon li» mtNFORM ATI KA Matej Š praga r. Vili Podgorelec, Peter Ko kol: Odločitvena drevesa in sistemi z večdimenzionalnimi rešitvami DeCRain simulira evolucijo odločitvenih dreves, hkrati pa seveda omogoča dinamično nastavitev vseh paramentrov evolucije, popoln nadzor nad njenim potekom in prikaz rezultatov {statistični rezultati na učni in testni množici, prikaz najboljšega zgrajenega drevesa in tabelarični prikaz vseh rezultatov - Klika 2). 1 (T gnllrth M [IncFtainl Efc Vmv t!«t n-u [ia A SPE v |cUJ 139 > Mfctnt ir*li * Jobn. Arii] 13817 C»*'. ! - I'1'! • . -^ |mHR>> &JUo Mm&tonlkbioMin n 7|nt5> IIGdrm dotTCJ deblo liAu 11-iVr: [ntlETI >> HMkjl mnta ttvdta P| t!6l >:■ dti-odct-o l(0t.o dti.o dobo |jf Hl>> tltijiu iXtnr dotro "" ^ ii^dmo IflU» ¡.J* h ti J |1J» iMn ilabo ilttn itat» tM» "-1 iMjCSITMMd !*= |fpai)(>rina?ii>attnvkanb - friflllfl J^flilCP Jirer^ij J * [d«| M 7 duda '' f I :/l >> dotro dobto dobo dobro iMmo » dofcc dobit* dut*o •><"•• dobro ]Ufr»*M>r "I >> dobo dobti M' -t O o dohio i 'i' JI' dobn 'fct* o »t&V! llot^i (c*l>ji«jti >> dotnp dobro dotno dobm Fitittj D i SIKU 26 Nus Slika 2: Okolje DecRain in primer zgrajenega vektorskega odločitvenega drevesa s petimi odločitvami. DecRain uporablja načela genetskih algoritmov. Velikost izhodnega vektorja ustreza številu iskanih odločitev, če je vzorec možno kategorizirati na en sam način (velikost izhodnega vektorja je I), pa bo končno odločitveno drevo funkcionalno enako klasično zgrajenemu drevesu. V splošnem lahko pričakujemo drevo podobnih kvalitet. Alternativa takšnemu pristopu je tudi klasična izgradnja ločenih dreves za vsako od želenih odločitev posebej in nato sestavljanje rezultatov. Medsebojna odvisnost več odločitev sicer ne bo neposredno razvidna iz samega vektorskega drevesa, lahko pa o njej sklepamo na podlagi primerjave velikosti vektorskega drevesa in ustreznega Števila navadnih odločitvenih dreves. Če so odločitve med seboj dokaj povezane in korelirane, potem vektorsko drevo ne bo imelo prevelikega prirastka v Številu vozlišč v primerjavi z ločenimi odločitvenimi drevesi za posamične odločitve. Evolucija odločitvenih dreves Ker se vektorska odločitvena drevesa razlikujejo od klasičnih samo v končnih vozliščih, je evolucija »navadnih« dreves zelo podobna evoluciji »vektorskih« dreves. Do razlike prihaja le pri ocenjevanju, saj moramo pri vektorskem drevesu ocenili njegovo uspešnost v več dimenzijah. Vendar za začetek poglejmo, kako sploh uporabljamo genetske algoritme pri razvoju odločitvenih dreves. Potrebno začetno populacijo dreves lahko enostavno ustvarimo z naključno gradnjo dreves, kar zagotavlja potrebno genetsko raznolikost. Takšna populacija naj vsebuje dovolj veliko število dreves, od zelo dobrih pa tudi do zelo slabih. Evolucija bo namreč poskusila najti tiste dobre veje v posameznih drevesih, ki bi lahko združene sestavljale optimalno drevo. Razvoj načeloma vedno poteka po enem od dveh scenarijev glede na način polnjenja nove populacije [9], povsod pa je pomembna ciklična uporaba genetskih operatorjev selekcije, križanja in mutacije. .Najbolj pomembna je ideja, da optimalnega drevesa ne gradimo s pomočjo determinističnega postopka v enem prehodu, ampak da razvoj prepustimo iterak-tivnemu procesu. Omenili smo že, da osebek v populaciji predstavlja enoodločilveno drevo. Vsak osebek pa mora biti predstavljen v obliki genetske kode. Najenostavnejše kodiranje bi bilo kar znakovno zaporedje, v primeru dreves pa je genotip lahko tudi drevesna struktura, kar pa je tudi končna želena oblika osebka - njegov fenotip. S fenotipom pa je določeno tudi obnašanje drevesa - pretvorba podanega vhoda v izhodni vektor odločitev s pomočjo preprostih vprašanj i f-1 luni. Evolucija nato preoblikuje drevesa v populaciji, genetski operatorji pa spreminjajo že spremenjene oblike. Pomemben faktor v tem postopku je ocena, kdaj je neko drevo dobro in kdaj slabo. Razlika med genetskim generiranjem navadnih, enodimenzionalnih, in vektorskih odločitvenih dreves je tako samo pri odločanju, kako dobro se neko drevo dejansko obnaša, Ker je za ocenjevanje dreves zadolžena posebna funkcija, je tako ta razlika vidna le na enem mestu in to je prav v ocenitveni funkciji drevesa. Operatorja križanja in mutacije delujeta neodvisno od ocene drevesa, le operator selekcije bo upošteval oceno drevesa pri izboru dreves za nadaljnjo reprodukcijo. Ocenjevanje osebkov Ocenitev novo nastalega drevesa poteka vedno s pomočjo učne množice, ocenitvena funkcija pa v oceni pove, kako dobro je neko drevo. Torej moramo drevo uporabiti na vseh učnih vzorcih in dobljene rešitve primerjati z dejanskimi pravilnimi vrednostmi. In lukaj je možnih kar nekaj scenarijev. Najenostavnejše merilo je gotovo odstotni delež pravilnih zadetkov. Pri navadnih, enood ločitve ni h drevesih je pogosta praksa tudi uporaba uteži (stroškov) /.a določanje pomembnosti zadetkov, s čimer lahko uspešno pritisnemo na smer razvoja evolucije, saj tako umetno damo prednost določeni vrsti zadetkov, Tako lahko i ifAimbi MI NFOR M ATI KA 2000-Številka 2-letnik VIII Matej Š praga r. Vili Podgorelec, Peter Ko kol: Odločitvena drevesa in sistemi z večdimenzionalnimi rešitvami npr. prisilimo drevesa, da se usmerijo proti določenim tipom rešitev. To je pomembno predvsem pri klasičnih enodimenzionalnih sistemih, ki imajo več možnih klasifikacij. S tem lahko povečamo zanesljivost oz. pravilnost sprejete klasifikacije. V primerih vektorskih dreves pa je takšen model povezan z mnogimi problemi, saj bi bila stroškovna matrika potrebna za vsako odločitev posebej in bi z njeno uporabo ogrozili ravno želeno iskanje odvisnosti odločitev. Če označimo število odločitev, torej velikost odločitvenega vektorja, z v, potem ima lahko en vektor med 0 in t?pravilnih vrednosti. Poseben primer pa so polni (jnckpot) zadetki, ko je izhodni vektor popolnoma enak pravilnemu vektorju klasifikacij za izbrani vzorec. Če je velikost učne množice u, potem ima lahko drevo največ 11 polnih zadetkov. To sta hkrati tudi prvi dve merili uspešnosti drevesa. Preostali dve merili se podrobneje spustita v vsako od posameznih odločitev. Če ima /'-ta odločitev v vektorju v, možnosti, potem lahko za vsako /-to možnost preverimo, kolikokrat bi se dejansko morala zgoditi in kolikokrat se tudi je (i'/,')- Nato lahko izračunamo povprečje za celotno odločitev in nato še čez vse odločitve vektor j a. Če npr. za vprašanje a velja, da ima 3 klasifikacije, potem ima lahko vsaka od klasifikacij jj, a2 in a3 svoj odstotek zadetkov. Povprečje se nato preračuna čez vse tri klasifikacije in nato še čez vse odločitve v vektorju. Kot zadnje merilo pa lahko uporabimo maksimalno napako (minimalni zadetek), kj jo pri prejšnjem izračunu doprinese posamezna klasifikacija odločitve k skupnemu povprečju. Že prva dva kriterija tvorita enostavno in močno ocenitveno funkcijo, z drugima dvema pa lahko tudi krmilimo tendenco evolucije v enakomernejšo razdelitev zadetkov po odločitvah, odvisno seveda od primera do primera (Enačba I), Ocenitvena funkcija v orodju DecRain vsebuje obteženo (w,) povprečje opisanih ocen. 7. utežmi lahko izboljšamo splošno konvergenco in prilagodimo model specifičnemu problemu. Ker lahko pri razmnoževanju križamo različne veje na različnih globinah, imajo novo nastala drevesa tendenco hitre rasti. Veliko število vozlišč ponavadi povzroči dobre rezultate na učni množici, hkrati pa negativno vpliva na splošne general izacijske sposobnosti drevesa. Da bi preprečili čezmerno rast, smo v oceno drevesa dodali tudi kazenski člen za inlronska vozlišča. Introni so pomemben dejavnik v evoluciji in imajo velik vpliv na efektivno oceno (cffeciive fitness) osebkov v populaciji. Efektivna ocena namreč opisuje sposobnost osebka, da zaščiti svoje potomstvo pred možnimi kvarnimi vplivi genetskih operatorjev, povečuje pa se ravno s seleketjskim pritiskom za ustvarjanje intronov [9]. Introni nastanejo v primerih podvojitve testov v isti veji drevesa. Če npr. vozlišče S testom atributa (ij že razporedi vzorce po izhodnih podvejah, je ponovitev istega testa v neki pod vej i popolnoma nekoristna. Ker pa mora biti drevo logično pravilno, mora takšno vozlišče vsebovali tudi eno ali več nekoristnih pod ve j. Razmerje med velikostjo drevesa in številom intronov lahko uporabimo kot kriterij dodelitve kazenskih točk k skupni oceni drevesa, Pričakujemo namreč lahko, da bodo večja drevesa praviloma vsebovala več intronov kot kompaktnejša, manjša drevesa. Možnih je še nekaj drugih rešitev za omejevanje Čezmerne rasti dreves, npr. razmerje med aktivnim številom listov in številom vseh listov v drevesu, pa tudi med številom aktivnih listov in številom možnih vektorjev. Predlagani kriterij lahko s podobnimi nastavitvami uporabimo za gradnjo odločitvenih dreves pri različnih problemih, torej brez okvirne ocene, kako veliko bo dejansko drevo. Selekcija, križanje in mutacija dreves Operator selekcije ima nalogo odločiti, ali ima nek osebek potencial za nadaljnji razvoj ali pa ga je potrebno zavreči in nadomestiti z drugim osebkom. V našem orodju smo uporabili načelo linearnega razvrščanja (linear rankiu$) [9]. Ta selekcijska shema najprej na podlagi ocene osebka določi njegov položaj v populaciji, vsakemu položaju pa je dodeljena točno določena verjetnost izbora za nadaljnje razmnoževanje. Linearno razvrščanje pogosteje izbira boljša drevesa, nemalokrat pa tudi slabše osebke iz ozadja, l ak pristop ohranja genetsko raznovrstnost in hkrati omogoča kvalitativni napredek, kar je pogoj za uspešen razvoj brez prehitre konvergence k lokalni rešitvi. Ker so vsi parametri dinamično nastavljivi, lahko spreminjamo velikost izbora glede na velikost populacije in s tem spreminjamo selekcijski pritisk. Pri križanju dveh dreves lahko uporabimo več strategij. Najbolj splošna bi bila naključna i/bira dveh vozlišč in nato izmenjava z njima določenih pod-dreves. Takšna rešitev je popolnoma naključna in teži k destruktivnemu delovanju. Tako kot v naravi bi si namreč želeli kriterij, ki bi omogočil križanje dveh dreves samo na določenih točkah. Preprosto pravilo bi hi t s jackpots . ,,, v., fitness = F(w,---,w2--,w3 • t(—•),u'4 • Min{—)) + ws • penalty(\ntrons) v ■ tt % Enačba 1. Occnitvena funkcija v DecRamu 2000 -številka 2 -lelnik VIII Matej Š praga r. Vili Podgorelec, Peter Ko kol: Odločitvena drevesa in sistemi z večdimenzionalnimi rešitvami bilo tudi križanje v točkah z istim atributom, kar pa ne pomeni nujno dveh točk, ki bi odločali o istih vzorcih. Zato smo za izbiro točk križanja izbrali princip prehojene poti - naključno izbran vzorec iz učne množice spustimo skozi obe drevesi in nato na obeh prehojenih poteh izberemo po eno vozlišče. S križanjem v tako izbranih točkah tudi dejansko zamenjamo dve veji, ki /. dosti večjo verjetnostjo sprejemata odločitve o istih vzorcih (Slika 3). Slika 3: Križanje dveh dreves na prehojeni poti istega naključnega vzorca. Genetski operator mutacij vnaša v genetsko kodo -Strukturo drevesa - naključne spremembe. Nenadzorovana sprememba v arhitekturi drevesa je ponavadi destruktivna, saj zelo verjetno poruši ravnotežje, ki se je ustvarilo skozi evolucijski razvoj. Hkrati pa mutacije zagotavljajo nenadne preobrate, potrebne za iskanje globalnih rešitev, in vnašajo sveže spremembe v starejši genetski material osebka [11 j. Mutacija v DecRain lahko nastopi nad katerimkoli vozliščem v drevesu in mu lahko spremeni tako tip kot tudi vsebino. Tako lahko mutacija spremeni list drevesa v notranje vozlišče ali pa enostavno spremeni končno odločitev v listu. Lahko pa deluje nad notranjim vozliščem drevesa, kjer lahko zamenja posamezne veje, določi novo poljubno vprašanje ali spremeni vozlišče v list z odločitvijo. DecRain omogoča dinamično nastavitev verjetnosti posameznih mutacij. Rezultati Vektorska drevesa lahko načeloma uporabimo tudi na klasičnih klasifikacijskih problemih z enim vprašanjem, sam vektorski koncept pa je seveda najprimernejši za naloge, kjer iščemo odgovore na več vprašanj itpombi w\ NFOR M ATI KA hkrati. Za predstavitev ideje in orodja smo izbrali medicinski problem, ki je že bil deloma obdelan s pomočjo klasičnih dreves [3J. Ker je v medicini zelo pomemben dejavnik predvsem preglednost rezultatov in faktorjev, ki so pripeljali do določenih odločitev, smo se omejili izključno na odločitvena drevesa. Sama priprava podatkov ni toliko zahtevna, kot so zahtevne priprave alternativnih metod reševanja. Da bi lahko dobili vse iskane odgovore s pomočjo klasičnih dreves, moramo postopati drugače, kot smo vajeni. Pri iskanju odgovorov na več vprašanj imamo dve možnosti. Prva je intuitivna in zahteva izgradnjo več samostojnih dreves za vsako zastavljeno vprašanje posebej, Osnovno idejo predstavlja slika 4.a, kjer so za tri postavljena vprašanja (QF, in Q j) zgrajena tri neodvisna drevesa. Ce označimo en vzorec kot množico n opisnih atributov (n) in treh pripadajočih rešitev {»¡,a,„ rj,, q2J }, potem je s klasičnimi orodji mogoče enostavno zgraditi drevo za vsako vprašanje s pomočjo p od množice {rtj, ..., a,„ i^f. Idejo je mogoče razširiti tudi na gradnjo odvisnih (povezanih) dreves, kjer bi najprej zgradili npr. Dt in nato še D,, ki bi odgovor^ jemalo kot vbodni atribut a,n t v svoji učni množici. Podobno velja za zadnje - tretje odločitveno drevo. Tak pristop je možen, če vprašanja niso ciklično odvisna in lahko določimo vrstni red gradnje dreves; to pa je redko, saj ponavadi ne poznamo niti vseh odvisnosti posameznih odgovorov od vhodnih atributov. Z vsemi tremi drevesi lahko potem enostavno dobimo vse tri odgovore za vsak vzorec. Problem tega pristopa je v ločenosti odgovorov, saj drevo Dz nima nobene vednosti o zgradbi in znanju drevesa D}. V primeru povezanih dreves pa so rezultati občutljivi na kopičenje napake, saj napačna klasifikacija v prvem drevesu verjetno pomeni tudi napako v vseh naslednjih drevesih. Drugi pristop s pomočjo klasičnih dreves predvideva predhodno združitev vseh treh klasifikacij v eno samo klasifikacijo - Slika 4.h. Torej združitev vprašanj Q1r Q, in Q, v novo vprašanje Q. Če je imelo prvo Vprašanje 3 možne odgovore, drugo 2 in tretje 4, potem ima lahko Q celo 24 možnih odgovorov (toliko je tudi možnih različnih vektorjev v vektorskem drevesu). Slabost tega pristopa je skrita v logiki večine klasičnih algoritmov za gradnjo odločitvenih dreves. Ti predvidevajo, da so vsi odgovori medsebojno ločeni in neodvisni, kar pa tukaj seveda ni res. Algoritem pozna samo pravilne in napačne odgovore, pojma bolj ali manj pravilen nista smiselna. Sta pa pomembna pri vektorskih rešitvah, saj so si posamezne rešitve lahko bolj ali manj podobne. Če bo torej algoritem prisiljen izbirati iz množice napačnih odločitev, se lahko zgodi, da bo izbral popolnoma napačno rešitev, čeprav je imel na voljo optimalni zelo podobno rešitev. Ker pa 2000 - številka 2 - letnik VIII Malej Šprogar. Vili Podgorelec. Peter Kokol: Odločitvena drevesa in sistemi z večdimenzionalnimi rešitvami *-ur