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.

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.

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.

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.