Otsustuspuu

Allikas: Vikipeedia

Otsustuspuu on puud meenutav diagramm, mis esitab probleemi lahendamisel tehtavaid otsuseid. Otsustuspuu on kasulik, sest see annab selge ja dokumenteeritava ülevaate otsuse langetamise loogilise arutluskäigu kohta.[1]

 Sõlmed ja harud[muuda | muuda lähteteksti]

Otsustuspuu graafiline kujutis koosneb sõlmedest ja harudest. Iga sisemine sõlm esindab küsimust mingi tunnuse kohta ja iga haru vastust sellele küsimusele. Selguse mõttes tuleks otsustuspuud ehitada vasakult paremale ajalises järjestuses nii, et vasemal olevad sammud toimuvad ajaliselt varem kui paremal olevad sammud.[1][2]

Otsustuspuudel on kolme tüüpi sõlmi ja kahte tüüpi harusid. Otsustussõlm on punkt, kus tuleb teha valik, ja seda kujutatakse ruuduna. Otsustussõlmest väljuvad harud on otsustusharud ja iga otsustusharu esindab ühte sel hetkel võimalikku alternatiivi või tegevust. Alternatiivid peavad olema üksteist välistavad ja ammendavad (valikus peavad olema kõik võimalikud alternatiivid). Sündmussõlm on punkt, kus otsustaja saab sündmuse toimumisest teada. Sündmussõlmi tähistatakse ringiga. Alternatiivsed sündmused peavad olema üksteist välistavad ja ammendavad. Igale sündmusele määratakse tõenäosus ja tõenäosuste summa peab võrduma ühega. Üldiselt esindavad otsustussõlmed ja -harud otsuse tegemisel kontrollitavaid faktoreid ning sündmussõlmed ja -harud mittekontrollitavaid. Kolmas sõlmetüüp on terminaalne ehk lõppsõlm, mis esindab otsuste ja sündmuste kombinatsiooni lõpptulemust. Terminaalsed sõlmed on otsustuspuu lõpp-punktid ja neid tähistatakse kolmnurkade või vertikaalse joonega.[1][2]

Puu analoogiat kasutades nimetatakse kõige vasakpoolsemat sõlme juureks, sisemisi sõlmi oksteks ja terminaalseid sõlmi lehtedeks. Vasakult paremale liikudes on otsustuspuul ainult laienevad sõlmed, koonduvaid sõlmi ei ole. Seetõttu võivad otsustuspuud väga suureks kasvada ning käsitsi on neid raske täielikult välja joonistada. Tänapäeval kasutatakse palju ka erinevaid otsustuspuude ehitamiseks mõeldud tarkvarasid.[2]

Otsustuspuu sõlmed ja harud

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
Terminaalne sõlm Kolmnurk või joon Lõppväärtus

Otsustuspuu tõlgendamine[muuda | muuda lähteteksti]

Sündmussõlmedest väljuvatele harudele ehk sündmustele määratakse toimumise tõenäosused. Valikute eeldatavate väärtuste arvutamiseks tuleb tulemusi arvuliselt mõõta ning tihti kasutatakse selleks rahalisi väärtusi. Nende andmete alusel on võimalik arvutada tulemuste kasulikkus. Otsustuspuud analüüsitakse alustades terminaalsetest sõlmedest (lehed). Tulemuse oodatav väärtus arvutatakse ja pannakse kirja iga sündmussõlme jaoks. Selleks summeeritakse tulemuse tõenäosuse ja mõõdetava väärtuse korrutis sündmussõlme kõikide tulemuste kohta. Sellel meetodil koondatakse sündmussõlmest väljuvad harud nii, et sündmussõlmele saab anda oodatava väärtuse. Neid väärtusi omakorda kasutatakse vasakule jäävate sündmussõlmede väärtuste hindamiseks. Otsustussõlme korral on valikutest parim see, mille oodatav väärtus on maksimaalne.[1][2]

Otsustuspuude kasutamine[muuda | muuda lähteteksti]

Otsustuspuid kasutatakse palju otsuste analüüsimisel, et teha kindlaks strateegia, mis kõige tõenäolisemalt eesmärgini viib. Otsustuspuud on samuti väga populaarsed masinõppimises ja andmekaeves.[3]

Projektijuhtimises[muuda | muuda lähteteksti]

Projektijuhtimises tegelevad projektijuhid muuhulgas riskijuhtimisega, püüdes läbi mõelda, mis võib juhtuda ja kas see on oluline. Projekti riski kohta realistliku info saamisel toetuvad projektijuhid aina enam kvantitatiivsetele meetoditele nagu näiteks otsustuspuude analüüsimine. See tehnika aitab projektijuhtidel teha otsuseid olukorras, kus mõjud ei ole ilmsed.Näiteks võib olla vaja otsustada, millist tarnijat kasutada või kas minna üle uuele tehnoloogiale.[4]

Otsustuspuu kasutamine otsuse tegemiseks:[4]

  1. Tehke kindaks peamised otsused (otsustussõlmed) ja peamised määramatused (sündmussõlmed)
  2. Koostage otsustuspuu alustades otsusest ja kaardistades selle peamised tagajärjed. Juba otsuse analüüsimise ja diagrammi koostamise põhjal on vahel võimalik rohkem informeeritud otsuseid teha, sest projektijuht mõtleb valikud korralikult läbi.
  3. Hinnake iga alternatiivse otsuse kulusid ja kasu. Otsustuspuu analüüsimise lõpptulemus sõltub suuresti nende arvude täpsusest.
  4. Arvutage iga teekonna väärtus alustades esimesest otsusest ja kumuleerides väärtused kuni terminaalse sõlmeni.
  5. Hinnake iga määramata tulemuse tõenäosus. See ei ole alati lihtne, sest informatsiooni saamiseks ei ole tihti sobivaid kasulikke andmebaase. Andmete kogumisel tuleb olla hoolikas, et mitte teha halvasti informeeritud või kallutatud otsust.
  6. Analüüsige otsustuspuud. Alustage lehtede väärtustest paremas ääres ja vasakule liikudes arvutage iga sõlme väärtus. Ratsionaalne organisatsioon valib suurima väärtusega tee.

Riskineutraalne organisatsioon eelistab otsust, mis maksimeerib eeldatava rahalise väärtuse või minimeerib eeldatava kulu. Sellisel organisatsioonil on palju projekte ja keskmine projekt peab õnnestuma. Mõnel juhul on kasulik teha otsuseid riskitundlikust positsioonist lähtuvalt. Riskitundlik organisatsioon maksimeerib eeldatava kasulikkuse (expected utility), mitte eeldatava rahalise väärtuse. See kasulikkuse funktsioon võib anda olulise negatiivse kaalu suurtele võimalikele kaotustele. Riskitundlik organisatsioon väldib otsuseid, mis võiksid ebaõnnestumise korral suuri kahjusid põhjustada, isegi siis, kui need otsused pakuksid võimalust teenida suurt tulu. Riskitundliku organisatsiooni valik võib olla konservatiivsem kui riskineutraalsel organisatsioonil. See ei tähenda, et otsus on ebaratsionaalne, vaid viitab organisatsiooni riskitundlikkusele. Riskitundlikum organisatsioon võib olla väiksem või rohkem sõltuv ühest sissetulekuallikast. Enamik otsustuspuu tarkvarasid võimaldab kasutajal määrata kasulikkuse funktsiooni, mis peegeldab organisatsiooni tundlikkust suurtele kahjudele.[4][5][6] 

Masinõppimises[muuda | muuda lähteteksti]

Andmekaeve on automaatne protsess, mille abil otsitakse eelnevalt teadmata ja potentsiaalselt kasulikke mustreid andmebaasidest. Andmete arv kahekordistub iga kolme aastaga ja andmekaeve on oluline tööriist muutmaks need andmed informatsiooniks. Andmekaeves kasutatavad kogud on tihti väga suured koosnedes miljonitest objektidest, millel on omakorda sadu tunnuseid. Eesmärk on andmekogude klassifitseerimine ehk objekti määramine tema tunnuste alusel ühte mitmest eeldefineeritud kategooriast. Klassifitseerimisel jagatakse andmekogu õpiandmeteks ja testandmeteks. Õpiandmeid kasutatakse klassifitseerimismudeli ehitamiseks ja testandmeid selle valideerimiseks. Mudelit saab seejärel kasutada uue andmekogu peal sealsete objektide klassifitseerimiseks. Mõned enamkasutatavad klassifitseerimisalgoritmid on neurovõrgud, logistiline regressioon ja otsustuspuud. Neist on kõige levinumad otsustuspuud, sest need on inimestele lihtsasti mõistetavad ja see kergendab klassifitseerimise protsessi.[3] 

Otsustuspuu konstrueerimine[muuda | muuda lähteteksti]

Otsustuspuu tõlgendamine on küllalt arusaadav, kuid selle ehitamine on keerulisem protsess. Enamlevinud meetod on otsustuspuud kasvatada sõlme poolitamise teel, alustades kõikide õpiandmetega juursõlmest.[7]

Otsustuspuude ehitamisel tuleb arvestada järgmisi aspekte:[8]

  • Kas lubada ainult binaarseid jagunemisi või võib küsimusele anda ka rohkem vastuseid?
  • Millise omaduse kohta küsimus esitada?
  • Millal kuulutada sõlm leheks?
  • Kui otsustuspuu kasvab liiga suureks, siis kuidas saab seda väiksemaks ja lihtsamaks teha (puu kärpimine)?
  • Kuidas toimida puuduvate andmete ja müra esinemisel? 

Jagunemiste arv[muuda | muuda lähteteksti]

Lihtsuse mõttes kasutatakse tihti tipu jaotamist kaheks, mille tulemusena tekib binaarne ehk kahendpuu. Kahendpuu ehitamine nõuab algoritmiliselt vähem ressursse.[7]

Küsimuse valimine[muuda | muuda lähteteksti]

Levinumad viisid jagunemiste valimiseks otsivad jagunemist tunnuse baasil, mis eristaks klasse kõige paremini. Klassifitseerimistäpsuse paranemist saab kirjeldada entroopia vähenemise läbi. Mida kaugemale otsustuspuul liigume, seda täpsemaks peab klassifitseerimine muutuma ja andmete jaotamine klassidesse peab pärast järgmist sammu olema puhtam. Alternatiivina entroopia mõõtmisele puu tipus kasutatakse ebapuhtuse hindamiseks Gini indeksit. Gini indeksi funktsioon kasvab aeglasemalt võrreldes entroopiafunktsiooniga ja võimaldab paremini eristada halbasid ja veidi vähem halbasid jagunemisi.[7]

Praktikas on näidatud, et tipu jagunemiste kriteeriumid ei oma hästi töötava otsustuspuu loomisel väga suurt tähtsust. Olulisemad on tingimused peatumiseks ja meetodid puu kärpimiseks.[7][9]

Otsustuspuu kasvatamise lõpetamine[muuda | muuda lähteteksti]

On võimalik koostada täielik otsustuspuu, mille igale lehele vastab üks õpiobjekt. Selline otsustuspuu kirjeldab hästi õpetamiseks kasutatud andmeid, kuid tundmatute objektide klassifitseerimiseks on see liiga spetsiifiline. Üle-õpetatud puu abil ei saa teha üldistavaid järeldusi objektide kohta, mille omaduste kombinatsioone õppimisel ei kasutatud.

Ristkontrolli meetodil jäetakse väike osa õpiandmetest meetodi testimiseks – neid otsustuspuu konstrueerimisel ei kasutata. Valmis otsustuspuud testitakse algselt kõrvale jäetud testandmete peal ning vaadatakse, kas saadud puu suudab klassifitseerida ka tundmatuid objekte.

Teise võimalusena võib määrata minimaalse õpiobjektide arvu lehes ja/või minimaalse informatiivsuse kasvu sõlme jagunemisel. Selle meetodi kasutamisel on keeruline leida sobivad parameetrid enne otsustuspuu konstrueerimist.[7]

Otsustuspuu kärpimine[muuda | muuda lähteteksti]

Kärpimine on peatumise kõrval teine viis otsustuspuu kõrguse reguleerimiseks. Peatumise meetodite puuduseks on see, et ei saa ära kasutada ülejärgmisel sammul võimalikuks saavat head jagunemist, sest järgmise sammu võimalik parim jagunemine ei ole seatud kriteeriumitest lähtudes jätkamiseks piisav. Kärpimise meetodil ehitatakse esiteks täielik otsustuspuu, mille lehtede entroopia on minimaalne. Seejärel kontrollitakse suunaga alt üles naaberlehti ja kui nende ühendamisel tekkiv täpsuse kadu on piisavalt väike, siis sõlmed ühendatakse.[7]

Kärpimise teel otsustuspuu optimeerimine on tunduvalt töömahukam kui õigel hetkel peatumine, kuid annab paremini klassifitseerivaid otsustuspuid.[8]

 Puuduvad tunnused ja müra[muuda | muuda lähteteksti]

Müra tähendab mittesüstemaatilisi vigu õpiandmetes ning takistab täielikult korrektse otsustuspuu konstrueerimist. Näiteks võib õpiandmetes olla kaks erinevast klassist, kuid samade tunnustega kirjeldatud objekti.[7] Otsustuspuu õpetamiseks tuleb kasutada  reaalsusega sarnase müratasemega andmeid. Ilma mürata õpiandmete kasutamisel on otsustuspuu hilisem klassifitseerimistäpsus reaalsete andmete kasutamisel tunduvalt kehvem kui otsustuspuul, mis ehitati tõepärase müraga õpiandmete alusel.[10]

Kui õpiandmetes esineb puuduvaid tunnuseid tuleb otsustuspuu konstrueerimise algoritmi kohandada. Täielike tunnuste korral saab käituda tavalisel viisil, kuid tunnuste puhul, mis mõnel õpiobjektil puuduvad, tuleb arvutada hinnangud neid objekte arvestamata. Järgmisel jagunemisel saab puudunud tunnustega objekte mõne teise tunnuse järgi jälle kasutada.[7] 

Algoritmid[muuda | muuda lähteteksti]

Kuigi enamus otsustuspuu koostamise algoritmidest kasutavad ebapuhtuse hindamiseks entroopiafunktsiooni, on erinevatel algoritmidel erinevad valikud peatumise ja kärpimise meetodite osas ja puuduvate tunnustega toimetulemiseks.[8]

Andmemahud kasvavad pidevalt ja see esitab uusi nõudmisi ka klassifitseerimiseks kasutatavatele algoritmidele. Näiteks on välja töötatud algoritmid, mis kasutavad andmete eelsorteerimist selle asemel, et igal sammul entroopiat arvutada (nt SPRINT, RandomForest). Selline lähenemine on arvutuslikult efektiivsem ja saadavate otsustuspuude täpsus on parem.[3]

Enamkasutatavad otsustuspuu koostamise algoritmid on CART, ID3 ja C4.5.[11]

ID3[muuda | muuda lähteteksti]

ID3 (Iterative Dichotomized) algoritmi tutvustati 1986. aastal ning seda loetakse väga lihtsaks otsustuspuu konstrueerimise algoritmiks. Jagunemise kriteeriumina sõlmedes kasutatakse informatsioonikasvu. Puu kasvatamine lõpetatakse kui kõik sõlmed on puhtad või kui parim informatsioonikasv ei ole suurem nullist. Algne ID3 algoritm ei sisaldanud kärpimist, ei suutnud kasutada arvulisi tunnuseid ega tegeleda puuduvate tunnustega.[7][8][12] ID3 ei anna täpset tulemust kui andmetes on liiga palju müra või detaile, seega on enne otsustuspuu koostamist ID3 algoritmi abil vajalik andmete korralik eeltöötlemine. See algoritm tekitab mitu sõlmest väljuvat haru.[3]

C4.5[muuda | muuda lähteteksti]

C4.5 algoritm on ID3 järglane ja edasiarendus sama autori poolt. Selle algoritmi puhul on jagunemise kriteeriumiks normaliseeritud informatsioonikasv. Jagunemine lõpetatakse kui jagatavate objektide hulk jääb alla kindlaksmääratud piiri. Pärast kasvamise faasi viiakse läbi vigade-põhine kärpimine. Kärpimise abil saab vähendada klassifitseerimisvigu, mis tekivad müra või liigsete detailide tõttu andmekogus.[3] C4.5 suudab kasutada arvulisi tunnuseid ning hakkama saada puuduvate tunnustega.[12] Praktikas on C4.5 täielikult asendanud ID3 algoritmi.[7] See algoritm tekitab mitu sõlmest väljuvat haru.[3]

CART[muuda | muuda lähteteksti]

CART (Classification and Regression Trees) algoritmi iseloomustab binaarsete otsustuspuude koostamine, milles igal sõlmel on täpselt kaks väljuvat haru. Puu kärbitakse kulu-keerukuse meetodil. CART suudab koostada regressioonipuid. Regressioonipuud on sellised otsustuspuud, milles lehed ennustavad reaalset numbrit ja mitte klassi.[12] CART raamistikus saab lihtsa vaevaga ehitada erinevatel alustel otsustuspuid ning seega leida oma probleemi jaoks parim lahendus.[7] 

Otsustuspuude eelised ja puudused[muuda | muuda lähteteksti]

Kirjanduses on toodud otsustuspuude kasutamisele mitmeid eeliseid:[12][7]

  • Otsustuspuu tööpõhimõte on intuitiivne ja seda on lihtne jälgida. Mõistliku suurusega otsustuspuust saab aru ka mitteprofessionaalne kasutaja ja selle saab välja kirjutada reeglite kogumina.
  • Väljaõpetatud otsustuspuu kasutamine on algoritmiliselt lihtne ja seda on võimalik täiendada ekspertteadmistega.
  • Otsustuspuu suudab kasutada nii nominaalseid kui arvulisi sisendtunnuseid.
  • Otsustuspuu suudab kasutada andmekogusid, milles on vigu.
  • Otsustuspuu suudab kasutada andmekogusid, milles on puuduvaid tunnuseid.
  • Otsustuspuud ei jää klassifitseerimistäpsuselt alla teistele meetoditele ja meetodid nende konstrueerimiseks on piisavalt arvutusefektiivsed.
  • Otsustuspuude meetod võeti kasutusele 1986. aastal, seega on meetod olnud piisavalt pikaajaliselt praktilises kasutuses ja ekspertidel on olnud võimalusi seda edasi arendada.

Otsustuspuudel on ka puudusi:[12]

  • Enamus algoritme (nagu ID3 ja C4.5) vajavad, et tunnustel oleksid ainult diskreetsed väärtused.
  • Otsustuspuu meetod töötab hästi kui esineb väike hulk väga olulisi tunnuseid, kuid mitte nii hästi, kui tunnuste vahel on palju keerulisi seoseid.
  • Otsustuspuud kipuvad olema õpiandmete, ebaoluliste tunnuste ja müra suhtes liigtundlikud.

Viited[muuda | muuda lähteteksti]

  1. 1,0 1,1 1,2 1,3 1,4 Eriksen, S., Huynh, C., Keller, L.R. "Decision trees". Kluwer Academic Publishers, 2001.
  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.
  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
  4. 4,0 4,1 4,2 Hulett, D. T. & Hillson, D. (2006). Branching out. PM Network, 20(5), 36–40.
  5. Cohen, M.-D. (1990). Decision analysis in project management. PM Network, 4(3), 37–40.
  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.
  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.. "Otsustuspuudega klassifitseerimine (andmekaevandamise uurimisseminar)". Arvutiteaduse instituut, Tartu Ülikool, 2003.
  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
  9. Murthy, S.K.. "Automatic Construction of Decision Trees from Data: A Multidisciplinary Survey.". Kluwer Academic Publishers, 1998.
  10. Quinlan, J.R.. "Induction of Decision Trees". Machine Learning 1: 81–106, 1986. Kluwer Academic Publishers..
  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
  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.