Otsustusmets

Otsustusmetsa (Inglise keeles random forest) algoritm kuulub ansambelõppe meetodite hulka. Ansambelmeetodi mõte on kasutada koos paljusid "nõrku õppijaid" (siinkohal otsustuspuu), et moodustada nendest üks "tugev õppija". Nagu ka teised masinõppe meetodid, kasutab otsustusmets õppimiseks ja väärtuste ennustamiseks treeningandmeid.^[1]

Klassifikatsiooni algoritmide täpsus suurenes, kui esmakordselt loodi eri puudest koosnev ansambel, sellise algoritmi väljundiks on puude poolt kõige enam ennustatud klass. Selliste ansamblite kasvatamiseks kasutatakse tavaliselt juhuslikke vektoreid, mis juhivad iga puu kasvu ansamblis.^[2]

Varajane näide sellisest algoritmist on bagging-algoritm, mille koostas Breiman aastal 1996. Bagging-meetodi puhul kasutatakse puu kasvatamiseks juhuslikku hulka treeningandmete hulgast.^[2]

Ajalugu

Aastal 1995 pakkus Tin Kam Ho välja meetodi, mis eemaldaks otsustuspuude klassifitseerija keerukuse limitatsiooni.^[3] Sellised klassifitseerijad ei saa meelevaldselt keerukuses kasvada nii, et klassifitseerija ei kaotaks oma üldistamisoskust veel nägemata andmetel. Ho pakutud meetod kasutab kaldus otsustuspuid (ingl oblique decision tree), mis on head treenimisandmete täpsuse optimeerimiseks. Põhiline idee on koostada palju otsustuspuid juhuslikult valitud tunnuste alamruumides.^[1]

Algoritm

Otsustusmetsa algoritmil on kaks staadiumi. Üks on otsustusmetsa loomine ja teine on loodud otsustusmetsa põhjal ennustuste tegemine.

Otsustusmetsa loomise pseudokood:

Vali juhuslikult $k$ tunnust kõikide m tunnuste hulgast, kus $k<=m$ .
k tunnuste seas arvuta puu tipp $d$ , kasutades parimat lahknemispunkti.
Jaota tipp tütartippudeks, kasutades parimat lahknemispunkti.
Korda 1.–3. sammu, kuni otsustuspuus on loodud $l$ arv tippe.
Koosta mets, korrates 1.–4. sammu $n$ korda, et koostada mets, mis koosneb n otsustuspuust.^[4]

Omadused

Muutujate tähtsus

Otsustusmetsa saab kasutada selleks, et hinnata erinevate muutujate tähtsust klassifikatsiooni- või regressiooniprobleemis. Tähtsamad muutujad mõjutavad väljastatavaid väärtuseid rohkem. Seevastu vähetähtsad tunnused avaldavad mudeli ennustustele väiksemat mõju ja seega võib need tunnused otsustusmetsa mudelist välja jätta, tehes nii mudeli lihtsamaks ja kiiremaks.

Muutujate tähtsuse hindamiseks on kaks mõõdet. Esimene mõõde põhineb sellel, kui palju väheneb täpsus, kui tunnus mudelist välja jäetakse. Teine mõõde põhineb sellel, kui palju väheneb andmete ebapuhtus Gini indeksiga, kui muutujat kasutatakse puutipu lahknemiseks.^[5]

Otsustusmetsa eelised ja puudused

Otsustusmetsa eelised:

kasutatav nii regressiooni kui ka klassifikatsiooniprobleemide korral;
oskab eristada tähtsamad tunnused vähetähtsatest;
ülesobitamise oht on minimaalne;
anomaaliad andmetes ei mõjuta algoritmi väljundit;
algoritm oskab hästi ennustada puuduvaid andmeid.

Otsustusmetsa puudused:

algoritm võib muutuda aeglaseks, kui puude arv metsas on väga suur, ja pole seetõttu päriselu probleemide lahendamisel kõige efektiivsem;
ei oska ennustada andmetevahelisi sidemeid;
otsustusmets pole väga hea regressiooniülesande puhul.^[6]

Viited

↑ ^1,0 ^1,1 Tin Kam Ho (1998). "The Random Subspace Method for Constructing Decision Forests" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 20 (8): 832–844. Introduction. Originaali (PDF) arhiivikoopia seisuga 4.03.2016. Vaadatud 06.12.2018.
↑ ^2,0 ^2,1 Leo Breiman (2001). "Random Forests" (PDF). Machine Learning. Introduction. Vaadatud 06.12.2018.
↑ Tin Kam Ho (1995). "Random Decision Forests" (PDF). Introduction. Originaali (PDF) arhiivikoopia seisuga 17. aprill 2016. Vaadatud 06.12.2018.
↑ Shixin Gu (24.10.2017). "How Random Forest Algorithm Works in Machine Learning". Vaadatud 13.11.2018.
↑ Jake Hoare. "How is Variable Importance Calculated for a Random Forest?". Vaadatud 06.12.2018.
↑ Tristan Luminous (2017). Machine Learning For Beginners Guide Algorithms: Supervised & Unsupervised Learning Decision Tree & Random Forest Introduction. Lk 51–52.

[:0-1] 1,0 ^1,1 Tin Kam Ho (1998). "The Random Subspace Method for Constructing Decision Forests" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 20 (8): 832–844. Introduction. Originaali (PDF) arhiivikoopia seisuga 4.03.2016. Vaadatud 06.12.2018.

[:1-2] 2,0 ^2,1 Leo Breiman (2001). "Random Forests" (PDF). Machine Learning. Introduction. Vaadatud 06.12.2018.

[3] Tin Kam Ho (1995). "Random Decision Forests" (PDF). Introduction. Originaali (PDF) arhiivikoopia seisuga 17. aprill 2016. Vaadatud 06.12.2018.

[4] Shixin Gu (24.10.2017). "How Random Forest Algorithm Works in Machine Learning". Vaadatud 13.11.2018.

[5] Jake Hoare. "How is Variable Importance Calculated for a Random Forest?". Vaadatud 06.12.2018.

[6] Tristan Luminous (2017). Machine Learning For Beginners Guide Algorithms: Supervised & Unsupervised Learning Decision Tree & Random Forest Introduction. Lk 51–52.

[1]

[2]

[3]

[4]

[5]

[6]