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.^[1]

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.^[1]^[2]

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.^[1]^[2]

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.^[2]

Tabel 1. Otsustuspuu sõlmed ja harud.^[1]

Sõlmetüüp	Sümbol	Sõlmele järgneb
Otsustussõlm	Ruut	Otsustusharu
Sündmussõlm	Ring	Sündmusharu
Terminaalsõlm	Kolmnurk või vertikaalne joon	Lõpptulemus

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.^[1]^[2]

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.^[3]

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.^[4]

Otsustuspuu kasutamine otsuse tegemiseks^[4]

Määrake kindlaks peamised otsused (otsustussõlmed) ja peamised määramatused (sündmussõlmed).
Koostage otsustuspuu. Alustage otsustest ja fikseerige nende peamised tagajärjed. Võimaluste analüüsimine ja diagrammi koostamine aitavad projektijuhil informeeritumaid otsuseid teha, sest kõik valikud on põhjalikult läbi mõeldud.
Hinnake iga alternatiivse otsuse kulu ja tulu. Otsustuspuu analüüsi lõpptulemus sõltub suuresti kalkuleerimise täpsusest.
Arvutage iga teekonna väärtus, summeerides sõlmede väärtused esimesest otsustussõlmest kuni terminaalsõlmeni.
Määrake iga tulemuse tõenäosus. See ei ole alati lihtne, sest tihti puuduvad sobivad andmebaasid, mis vajalikku infot sisaldavad. Andmete kogumisel tuleb olla hoolikas, et vältida informeerimata või ekslikku otsust.
Analüüsige otsustuspuud. Alustage lehtede väärtustest ja arvutage iga eelneva sõlme väärtus. Mõistlik on valida suurima väärtusega tee.

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.^[4]^[5]^[6]

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.^[3]

Otsustuspuu koostamine

Otsustuspuud koostatakse üldjuhul sõlmi poolitades. Alustatakse õpiandmetega juursõlmest.^[7]

Otsustuspuud koostades tuleb arvestada viit aspekti.^[8]

Kas lubada ainult binaarseid jagunemisi või võib küsimusel olla ka rohkem vastuseid?
Millise omaduse kohta küsimus esitada?
Millal määrata sõlm leheks?
Kui otsustuspuu on liiga suur, siis kuidas saaks seda väiksemaks ja lihtsamaks teha (puu kärpimine)?
Kuidas toimida, kui andmed puuduvad ja/või on segavat müra?

Jagunemiste arv

Lihtsuse huvides jaotatakse tipp tihti kaheks. Selle tulemusel tekib binaarne ehk kahendpuu. Kahendpuu koostamine nõuab algoritmiliselt vähem ressursse.^[7]

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.^[7]

Praktikas ilmneb, et tipu jagunemise kriteeriumid ei ole tõhusa otsustuspuu loomisel esmatähtsad. Nendest relevantsemad on peatumise tingimused ja puu kärpimise meetodid.^[7]^[9]

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.^[7]

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.^[7]

Otsustuspuu optimeerimiseks on kärpimine peatamisest tunduvalt töömahukam, kuid kärbitud otsustuspuuga on võimalik üksusi paremini klassifitseerida.^[8]

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.^[7] Otsustuspuu väljaõpetamisel tuleb kasutada sellise müratasemega andmeid, mis peegeldavad tegelikkust, sest mürata õpiandmetega treenitud otsustuspuu klassifitseerimistäpsus on tunduvalt kehvem.^[10]

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.^[7]

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.^[8]

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.^[3]

Enim koostatakse otsustuspuid CART, ID3 ja C4.5 algoritmiga.^[11]

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.^[7]^[8]^[12] 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.^[3]

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.^[3] Erinevalt ID3-st saab C4.5 algoritmiga kasutada arvulisi tunnuseid ja koostada puid ka juhul, kui on üksusi, millel osa tunnuseid puudub.^[12] Praktikas on C4.5 asendanud täielikult ID3 algoritmi.^[7] C4.5 algoritmi abil tekitatakse mitu sõlmest väljuvat haru.^[3]

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.^[12] CART võimaldab hõlpsasti koostada eriotstarbelisi otsustuspuid ja aitab leida probleemi jaoks parima lahenduse.^[7]

Otsustuspuu eelised ja puudused

Otsustuspuul on mitmeid eeliseid.^[7]^[12]

Otsustuspuu on intuitiivselt arusaadav: seda on lihtne jälgida ja tõlgendada. Mõistliku suurusega otsustuspuust saab aru ka tavakasutaja ja selle tööpõhimõtet on võimalik reeglistikuna fikseerida.
Väljaõpetatud otsustuspuu kasutamine on algoritmiliselt lihtne ja seda on võimalik täiendada eksperditeadmistega.
Otsustuspuus saab kasutada nii nominaalseid kui ka arvulisi sisendtunnuseid.
Otsustuspuus saab kasutada vigaseid andmekogusid.
Otsustuspuus saab kasutada puuduvate tunnustega andmekogusid.
Otsustuspuu klassifitseerimistäpsus ei ole alternatiivsetest meetoditest halvem: arvutused on piisavalt tõhusad.
Otsustuspuu võeti kasutusele 1986. aastal. Seda on pikka aega praktiliselt kasutatud ja ekspertidel on olnud võimalik seda edasi arendada.

Otsustuspuul on ka puudusi.^[12]

Enamiku algoritmide (nagu ID3 ja C4.5) kasutamiseks peavad tunnustel olema ainult diskreetsed väärtused.
Otsustuspuu töötab hästi, kui esineb väike hulk tähtsaid tunnuseid, kuid selle tõhusus väheneb, kui tunnuste vahel on palju keerulisi seoseid.
Otsustuspuu kipub olema liiga tundlik õpiandmete, ebaoluliste tunnuste ja müra suhtes.

Viited

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 Eriksen, S., Huynh, C., Keller, L.R (2001). "Decision trees" (PDF). Kluwer Academic Publishers. Originaali (PDF) arhiivikoopia seisuga 17. aprill 2016.{{netiviide}}: CS1 hooldus: mitu nime: autorite loend (link)
↑ ^2,0 ^2,1 ^2,2 ^2,3 Schuyler, J. R. (1993). Decision analysis in projects: decision trees. PM Network, 7(7), 31–34.
↑ ^3,0 ^3,1 ^3,2 ^3,3 ^3,4 ^3,5 Venkatadri, M., Lokanatha, C.R (2010). A Comparative Study on Decision Tree Classification Algorithms in Data Mining. ISSN: 0974-3596
↑ ^4,0 ^4,1 ^4,2 Hulett, D. T. & Hillson, D. (2006). Branching out. PM Network, 20(5), 36–40.
↑ Cohen, M.-D. (1990). Decision analysis in project management. PM Network, 4(3), 37–40.
↑ Hulett, D. T. (2006). Decision tree analysis for the risk averse organization. Paper presented at PMI® Global Congress 2006–EMEA, Madrid, Spain. Newtown Square, PA: Project Management Institute.
↑ ^7,00 ^7,01 ^7,02 ^7,03 ^7,04 ^7,05 ^7,06 ^7,07 ^7,08 ^7,09 ^7,10 ^7,11 Käärmann, K. (2003). "Otsustuspuudega klassifitseerimine (andmekaevandamise uurimisseminar)" (PDF). Arvutiteaduse instituut, Tartu Ülikool. Originaali (PDF) arhiivikoopia seisuga 1. detsember 2017.
↑ ^8,0 ^8,1 ^8,2 ^8,3 Duda, R.O., Hart, P.E., Stork, D.G. (2001). Non-metric Methods. In: Pattern Classification, Second Edition. John Wiley &Sons, Inc. ISBN 978-0471056690.{{raamatuviide}}: CS1 hooldus: mitu nime: autorite loend (link)
↑ Murthy, S.K. (1998). "Automatic Construction of Decision Trees from Data: A Multidisciplinary Survey" (PDF). Kluwer Academic Publishers.
↑ Quinlan, J.R. "Induction of Decision Trees" (PDF). Machine Learning 1: 81–106, 1986. Kluwer Academic Publishers.
↑ Lakshmi, T.M,. Martin, A., Mumtaj Begum, R., Prasanna Venkatesan, V. (2013) An analysis on Performance of Decision Tree Algorithms using Student’s Qualitative Data. I.J.Modern Education and Computer Science, 2013, 5, 18–27
↑ ^12,0 ^12,1 ^12,2 ^12,3 ^12,4 Rokach L., Maimon O. (2005). Decision Trees. In: Maimon O., Rokach L. (eds) Data Mining and Knowledge Discovery Handbook. Boston, MA: Springer.

[:0-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 Eriksen, S., Huynh, C., Keller, L.R (2001). "Decision trees" (PDF). Kluwer Academic Publishers. Originaali (PDF) arhiivikoopia seisuga 17. aprill 2016.{{netiviide}}: CS1 hooldus: mitu nime: autorite loend (link)

[:1-2] 2,0 ^2,1 ^2,2 ^2,3 Schuyler, J. R. (1993). Decision analysis in projects: decision trees. PM Network, 7(7), 31–34.

[:2-3] 3,0 ^3,1 ^3,2 ^3,3 ^3,4 ^3,5 Venkatadri, M., Lokanatha, C.R (2010). A Comparative Study on Decision Tree Classification Algorithms in Data Mining. ISSN: 0974-3596

[:3-4] 4,0 ^4,1 ^4,2 Hulett, D. T. & Hillson, D. (2006). Branching out. PM Network, 20(5), 36–40.

[WhWgo-5] Cohen, M.-D. (1990). Decision analysis in project management. PM Network, 4(3), 37–40.

[X977X-6] Hulett, D. T. (2006). Decision tree analysis for the risk averse organization. Paper presented at PMI® Global Congress 2006–EMEA, Madrid, Spain. Newtown Square, PA: Project Management Institute.

[:4-7] 7,00 ^7,01 ^7,02 ^7,03 ^7,04 ^7,05 ^7,06 ^7,07 ^7,08 ^7,09 ^7,10 ^7,11 Käärmann, K. (2003). "Otsustuspuudega klassifitseerimine (andmekaevandamise uurimisseminar)" (PDF). Arvutiteaduse instituut, Tartu Ülikool. Originaali (PDF) arhiivikoopia seisuga 1. detsember 2017.

[:5-8] 8,0 ^8,1 ^8,2 ^8,3 Duda, R.O., Hart, P.E., Stork, D.G. (2001). Non-metric Methods. In: Pattern Classification, Second Edition. John Wiley &Sons, Inc. ISBN 978-0471056690.{{raamatuviide}}: CS1 hooldus: mitu nime: autorite loend (link)

[elXpn-9] Murthy, S.K. (1998). "Automatic Construction of Decision Trees from Data: A Multidisciplinary Survey" (PDF). Kluwer Academic Publishers.

[XZxrI-10] Quinlan, J.R. "Induction of Decision Trees" (PDF). Machine Learning 1: 81–106, 1986. Kluwer Academic Publishers.

[z5EA8-11] Lakshmi, T.M,. Martin, A., Mumtaj Begum, R., Prasanna Venkatesan, V. (2013) An analysis on Performance of Decision Tree Algorithms using Student’s Qualitative Data. I.J.Modern Education and Computer Science, 2013, 5, 18–27

[:6-12] 12,0 ^12,1 ^12,2 ^12,3 ^12,4 Rokach L., Maimon O. (2005). Decision Trees. In: Maimon O., Rokach L. (eds) Data Mining and Knowledge Discovery Handbook. Boston, MA: Springer.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]