Otsustuspuu

Otsustuspuu on puud meenutav diagramm, mis kujutab otsuseid ja nende võimalikke tagajärgi. Otsustuspuu on kasulik probleemide lahendamisel, sest see annab selge ülevaate otsuse langetamise loogilisest arutluskäigust.
Sõlmed ja harud.
Otsustuspuu graafiline kujutis koosneb sõlmedest ja harudest. Iga sisesõlm märgib küsimust ja iga haru selle küsimuse võimalikku vastust. Selguse huvides tuleks otsustuspuu koostada ajalises järjestuses vasakult paremale nii, et vasakule jääksid varem toimuvad etapid.
Otsustuspuus kasutatakse kolme tüüpi sõlmi ja kahte tüüpi harusid. Otsustussõlm on punkt, kus tuleb teha valik, ja seda tähistatakse ruuduga. Otsustussõlmest väljuvad harud on otsustusharud. Iga otsustusharu märgib üht sel hetkel võimalikku alternatiivi või tegevust. Alternatiivid peavad olema üksteist välistavad ja ammendavad, s.t kõik võimalikud alternatiivid peavad olema kujutatud. Sündmussõlm on punkt, kus toimub sündmus ja selgub tulemus, ning seda tähistatakse ringiga. Alternatiivsed sündmused peavad olema üksteist välistavad ja ammendavad. Igale sündmusele määratakse tõenäosus. Sündmuste tõenäosuste summa peab võrduma ühega. Üldiselt märgivad otsustussõlmed ja -harud juhitavaid tegureid ning sündmussõlmed ja -harud määramatuid. Terminaal- ehk lõppsõlm on punkt, mis märgib otsuste ja sündmuste lõpptulemust. Terminaalsõlmed on otsustuspuu lõpp-punktid ja neid tähistatakse kolmnurga või vertikaalse joonega.
Puu ehituse järgi nimetatakse kõige vasakpoolsemat sõlme juureks, sisesõlmi oksteks ja terminaalsõlmi lehtedeks. Otsustuspuu sõlmed hargnevad vasakult paremale, koonduvaid sõlmi ei ole. Seetõttu võib otsustuspuu väga suureks kasvada, mis raskendab selle käsitsi välja joonistamist. Tänapäeval koostatakse otsustuspuid selleks mõeldud tarkvaraga.
Tabel 1. Otsustuspuu sõlmed ja harud.
Otsustuspuu tõlgendamine.
Sündmusharudele ehk võimalikele sündmustele määratakse toimumise tõenäosus. Valikute eeldatavate väärtuste arvutamiseks peab tulemusi arvuliselt mõõtma. Selleks kasutatakse üldjuhul rahalisi väärtusi, mille alusel arvutatakse tulemuste kasulikkus. Otsustuspuu analüüsi alustatakse terminaalsõlmedest (lehtedest). Tulemuse oodatav väärtus arvutatakse iga sündmussõlme jaoks. Selleks korrutatakse iga sündmusharu tulemuse tõenäosus mõõdetud väärtusega ning liidetakse saadud korrutised kokku. See võimaldab sündmusharud koondada nii, et sündmussõlmele saab anda oodatava väärtuse. Neid väärtusi kasutatakse omakorda eelnevate sündmussõlmede väärtuste arvutamiseks. Otsustusharudest on parim see, mille oodatav väärtus on suurim.
Otsustuspuude kasutamine.
Otsustuspuid kasutatakse palju otsuste analüüsimisel, et teha kindlaks strateegia, mis viib kõige tõenäolisemalt eesmärgini. Otsustuspuud on populaarsed ka masinõppes ja andmekaeves.
Projektijuhtimises.
Projektijuhtimine hõlmab riskijuhtimist, mille eesmärk on läbi mõelda, mis võib projekti käigus juhtuda ja kas see on oluline. Riski hindamisel toetutakse aina enam kvantitatiivsetele meetoditele, sh otsustuspuudele. Need aitavad teha otsuseid olukordades, kus mõju ei ole ilmne. Näiteks võib vaja olla otsustada, mis tarnijat kasutada või kas minna üle uuele tehnoloogiale või mitte.
Otsustuspuu kasutamine otsuse tegemiseks
Riskineutraalne ettevõte või organisatsioon eelistab otsust, mis maksimeerib eeldatavat tulu ja/või minimeerib oodatavat kulu. Sellisel ettevõttel on palju projekte ja tähtis on eelkõige kasumi teenimine. Riskitundlik ettevõte maksimeerib eeldatavat kasulikkust ("expected utility"), mitte tulu, ning väldib otsuseid, mis viiksid ebaõnnestumise korral suure kahjuni, isegi kui need otsused võiksid tuua ka suurt tulu. Riskitundliku ettevõtte otsused on üldjuhul ettevaatlikumad kui riskineutraalse ettevõtte omad. Riskitundlikumad ettevõtted on tihti väiksemad ja/või sõltuvad peamiselt ühest sissetulekuallikast. Suur osa tarkvarast võimaldab otsustuspuus kasutada kasulikkusnäitajat, mis kirjeldab, mil määral suured kahjud ettevõtet mõjutavad.
Masinõppes.
Andmekaeve on automaatne protsess, mille käigus otsitakse andmebaasidest kasulikke ja veel teadmata mustreid. Andmehulk kahekordistub iga kolme aastaga. Andmekaeve aitab andmed muuta informatsiooniks. Andmehulgad on tihti väga suured: need koosnevad miljonitest üksustest, millel on omakorda sadu tunnuseid. Eesmärk on andmed klassifitseerida ehk määrata üksused tunnuste järgi sobivatesse kategooriatesse. Klassifitseerimisel jagatakse andmekogu õpi- ja katseandmeteks. Õpiandmeid kasutatakse klassifitseerimismudeli ehitamiseks ja katseandmeid selle valideerimiseks. Mudelit saab seejärel kasutada uue andmekogu üksuste klassifitseerimiseks. Klassifitseerimisalgoritmidest kasutatakse enim neurovõrke, logistilist regressiooni ja otsustuspuud. Kõige populaarsem on neist otsustuspuu, sest seda on lihtne mõista ja see kergendab klassifitseerimisprotsessi.
Otsustuspuu koostamine.
Otsustuspuud koostatakse üldjuhul sõlmi poolitades. Alustatakse õpiandmetega juursõlmest.
Otsustuspuud koostades tuleb arvestada viit aspekti.
Jagunemiste arv.
Lihtsuse huvides jaotatakse tipp tihti kaheks. Selle tulemusel tekib binaarne ehk kahendpuu. Kahendpuu koostamine nõuab algoritmiliselt vähem ressursse.
Jagunemiste valimine.
Jagunemisi valitakse üldjuhul selle tunnuse põhjal, mis eristab klasse kõige paremini. Klassifitseerimistäpsus paraneb, kui entroopia väheneb. Mida kaugemal asub sõlm otsustuspuu juurest, seda täpsem on klassifikatsioon: igal järgmisel etapil peab andmete jaotus olema selgem. Entroopia mõõtmise kõrval hinnatakse andmete ebapuhtust ka Gini indeksiga. Gini indeks kasvab aeglasemalt kui entroopia ning võimaldab seetõttu paremini eristada halbu ja veidi vähem halbu jagunemisi.
Praktikas ilmneb, et tipu jagunemise kriteeriumid ei ole tõhusa otsustuspuu loomisel esmatähtsad. Nendest relevantsemad on peatumise tingimused ja puu kärpimise meetodid.
Otsustuspuu peatamine.
On võimalik koostada otsustuspuu, mille igale lehele vastab üks õpiobjekt. Selline otsustuspuu kirjeldab hästi õpetamiseks kasutatud andmeid, kuid tundmatute üksuste klassifitseerimiseks on see liiga üksikasjalik. Üleõpetatud puu abil ei saa teha üldistavaid järeldusi nende üksuste kohta, mille tunnuseid õppimisel ei kasutatud.
Andmete ristkontrollis jäetakse väike osa õpiandmetest meetodi katsetamiseks kõrvale ja neid otsustuspuu koostamisel ei kasutata. Valmis otsustuspuud katsetatakse kõrvale jäetud katseandmetega, et kindlaks teha, kas puu abil saab klassifitseerida ka tundmatuid üksusi.
Veel üks võimalus on määrata minimaalne õpiüksuste arv lehe kohta ja/või minimaalne informatiivsuse kasv sõlme jagunemisel. Selle meetodiga on aga keeruline enne otsustuspuu koostamist sobivaid parameetreid leida.
Otsustuspuu kärpimine.
Otsustuspuu suuruse reguleerimiseks on peatamise kõrval võimalik kasutada ka kärpimist. Peatamise puudus on see, et kuna peatumiskriteeriumite järgi ei pruugi järgmine jagunemine olla jätkamiseks piisav, siis ei ole võimalik kasutada ka ülejärgmise sammu tõhusamat jagunemist. Kärpimisel koostatakse kõigepealt otsustuspuu, mille lehtede entroopia on võimalikult väike. Seejärel vaadeldakse altpoolt alustades naaberlehti, ja kui nende ühendamisel tekkiv täpsuse kadu on piisavalt väike, siis sõlmed ühendatakse.
Otsustuspuu optimeerimiseks on kärpimine peatamisest tunduvalt töömahukam, kuid kärbitud otsustuspuuga on võimalik üksusi paremini klassifitseerida.
Müra ja puuduvad tunnused.
Müra all mõistetakse mittesüstemaatilisi vigu õpiandmetes. Müra takistab korrektse otsustuspuu koostamist. Probleem tekib juba näiteks siis, kui õpiandmetesse satub kaks eri klassist, kuid samade tunnustega märgitud üksust. Otsustuspuu väljaõpetamisel tuleb kasutada sellise müratasemega andmeid, mis peegeldavad tegelikkust, sest mürata õpiandmetega treenitud otsustuspuu klassifitseerimistäpsus on tunduvalt kehvem.
Kui õpiandmetes ei ole kõiki vajalikke tunnuseid, tuleb algoritmi kohandada. Kui on õpiüksusi, millel puuduvad mõned tunnused, arvutatakse hinnangud neid üksusi arvesse võtmata. Järgmisel jagunemisel saab puudunud tunnustega üksusi mõne teise tunnuse järgi jälle kasutada.
Algoritmid.
Kuigi enamikus otsustuspuu koostamise algoritmides hinnatakse andmete ebapuhtust entroopianäitajaga, varieerub see, kas valitakse peatamine või kärpimine ning kuidas puuduvate tunnustega toime tullakse.
Andmemaht kasvab pidevalt, mistõttu on vaja algoritme üha kohendada ja täiendada. Näiteks on välja töötatud algoritmid (SPRINT, RandomForest), mis eelsordivad andmeid, et igal sammul ei peaks entroopiat arvutama. See meetod on arvutuslikult tõhusam ja koostatud otsustuspuud on täpsemad.
Enim koostatakse otsustuspuid CART, ID3 ja C4.5 algoritmiga.
ID3.
ID3 ("iterative dichotomized") algoritmi tutvustati esimest korda 1986. aastal. Seda peetakse üheks lihtsaimaks otsustuspuu koostamise algoritmiks. Sõlmede jagunemise kriteeriumina kasutatakse ID3-s informatsioonikasvu. Puu lõpetatakse, kui kõik sõlmed on puhtad või kui informatsioonikasv ei ole suurem nullist. Esialgu ei sisaldanud ID3 algoritm kärpimist ja sellega ei saanud kasutada arvulisi tunnuseid ega töötada puuduvate tunnustega. ID3-ga ei saa täpset tulemust, kui andmetes on liiga palju müra või detaile. Seetõttu on vaja enne otsustuspuu koostamist andmeid töödelda. ID3 algoritmi abil tekitatakse mitu sõlmest väljuvat haru.
C4.5.
C4.5 on ID3 algoritmi edasiarendus. Sõlmede jagunemise kriteeriumina kasutatakse C4.5-s normaliseeritud informatsioonikasvu. Puu lõpetatakse, kui jagatavate üksuste hulk jääb alla kindlaks määratud piiri. Seejärel tehakse vigadepõhine kärpimine, et vähendada klassifitseerimisvigu, mis on müra või liigsete detailide tõttu tekkinud. Erinevalt ID3-st saab C4.5 algoritmiga kasutada arvulisi tunnuseid ja koostada puid ka juhul, kui on üksusi, millel osa tunnuseid puudub. Praktikas on C4.5 asendanud täielikult ID3 algoritmi. C4.5 algoritmi abil tekitatakse mitu sõlmest väljuvat haru.
CART.
CART ("classification and regression trees") algoritmiga koostatakse binaarseid otsustuspuid, mille igast sõlmest väljub kaks haru. Puu kärpimiseks kasutatakse kulukeerukuse meetodit. CART-ga koostatakse regressioonipuid. Regressioonipuud on otsustuspuud, mille lehed ennustavad tegelikku numbrit, mitte klassi. CART võimaldab hõlpsasti koostada eriotstarbelisi otsustuspuid ja aitab leida probleemi jaoks parima lahenduse.
Otsustuspuu eelised ja puudused.
Otsustuspuul on mitmeid eeliseid.
Otsustuspuul on ka puudusi.