Hvað er ákvörðunartré?

Hvað er ákvörðunartré?

A ákvörðunartré er gagnlegt vélnámsreiknirit sem notað er fyrir bæði aðhvarfs- og flokkunarverkefni. Nafnið „ákvarðanatré“ kemur frá því að reikniritið heldur áfram að skipta gagnasafninu niður í smærri og smærri hluta þar til gögnunum hefur verið skipt í stök tilvik, sem síðan eru flokkuð. Ef þú myndir sjá fyrir þér niðurstöður reikniritsins myndi skipting flokkanna líkjast tré og mörg laufblöð.

Þetta er fljótleg skilgreining á ákvörðunartré, en við skulum kafa djúpt í hvernig ákvörðunartré virka. Að hafa betri skilning á því hvernig ákvarðanatré starfa, sem og notkunartilvik þeirra, mun hjálpa þér að vita hvenær á að nýta þau í vélanámsverkefnum þínum.

Snið ákvörðunartrés

Ákvörðunartré er mikið eins og flæðirit. Til að nota flæðirit byrjarðu á upphafspunkti, eða rót, myndritsins og byggir síðan á því hvernig þú svarar síuskilyrðum þess upphafshnúts sem þú ferð á einn af næstu mögulegu hnútum. Þetta ferli er endurtekið þar til endi er náð.

Ákvörðunartré starfa í meginatriðum á sama hátt, þar sem hver innri hnútur í trénu er einhvers konar próf-/síuviðmið. Hnútarnir að utan, endapunktar trésins, eru merkimiðar viðkomandi gagnapunkts og þeir eru kallaðir „lauf“. Útibúin sem leiða frá innri hnútum til næsta hnút eru eiginleikar eða samtengingar eiginleika. Reglurnar sem notaðar eru til að flokka gagnapunktana eru slóðirnar sem liggja frá rótinni að laufunum.

Reiknirit fyrir ákvörðunartré

Ákvörðunartré starfa á reikniritfræðilegri nálgun sem skiptir gagnasafninu upp í einstaka gagnapunkta út frá mismunandi forsendum. Þessar skiptingar eru gerðar með mismunandi breytum, eða mismunandi eiginleikum gagnasafnsins. Til dæmis, ef markmiðið er að ákvarða hvort hundi eða kötti sé lýst með inntakseiginleikum eða ekki, gætu breytur sem gögnin skiptast á verið hlutir eins og „klær“ og „gelt“.

Svo hvaða reiknirit eru notuð til að skipta gögnunum í greinar og lauf? Það eru ýmsar aðferðir sem hægt er að nota til að kljúfa tré, en algengasta aðferðin til að kljúfa er líklega aðferð sem vísað er til sem "endurkvæm tvíundarskiptingu“. Þegar þessi aðferð við skiptingu er framkvæmd byrjar ferlið við rótina og fjöldi eiginleika í gagnasafninu táknar mögulegan fjölda mögulegra skiptinga. Fall er notað til að ákvarða hversu mikla nákvæmni sérhver möguleg skipting mun kosta og skiptingin er gerð með þeim forsendum sem fórna minnstu nákvæmni. Þetta ferli er framkvæmt afturkvæmt og undirhópar eru myndaðir með sömu almennu stefnu.

Til þess að ákvarða kostnað við skiptingu, kostnaðarfall er notað. Annað kostnaðarfall er notað fyrir aðhvarfsverkefni og flokkunarverkefni. Markmið beggja kostnaðarfalla er að ákvarða hvaða greinar hafa svipuð svargildi, eða einsleitustu greinarnar. Íhugaðu að þú vilt að prófunargögn ákveðins flokks fylgi ákveðnum slóðum og það er skynsamlegt.

Hvað varðar aðhvarfskostnaðarfallið fyrir endurtekna tvíundarskiptingu er reikniritið sem notað er til að reikna kostnaðinn sem hér segir:

summa(y – spá)^2

Spáin fyrir tiltekinn hóp gagnapunkta er meðaltal svara þjálfunargagna fyrir þann hóp. Allir gagnapunktar eru keyrðir í gegnum kostnaðaraðgerðina til að ákvarða kostnað fyrir allar mögulegar skiptingar og skiptingin með lægsta kostnaðinn er valin.

Varðandi kostnaðarfallið fyrir flokkun er fallið sem hér segir:

G = summa(pk * (1 – pk))

Þetta er Gini stigið og það er mæling á skilvirkni skiptingarinnar, byggt á því hversu mörg tilvik mismunandi flokka eru í hópunum sem verða til vegna skiptingarinnar. Með öðrum orðum, það mælir hversu blandaðir hóparnir eru eftir skiptingu. Ákjósanleg skipting er þegar allir hóparnir sem myndast við skiptinguna samanstanda aðeins af aðföngum frá einum flokki. Ef ákjósanleg skipting hefur verið búin til verður „pk“ gildið annað hvort 0 eða 1 og G verður jafnt og núll. Þú gætir kannski giskað á að versta tilfelli skiptingin sé einn þar sem það er 50-50 framsetning á flokkunum í skiptingunni, ef um er að ræða tvöfalda flokkun. Í þessu tilviki væri „pk“ gildið 0.5 og G væri einnig 0.5.

Klofningsferlinu er hætt þegar öllum gagnapunktum hefur verið breytt í lauf og flokkað. Hins vegar gætirðu viljað stöðva vöxt trésins snemma. Stór flókin tré eru viðkvæm fyrir offitu en hægt er að nota nokkrar mismunandi aðferðir til að berjast gegn þessu. Ein aðferð til að draga úr offitun er að tilgreina lágmarksfjölda gagnapunkta sem verða notaðir til að búa til laufblað. Önnur aðferð til að stjórna fyrir offitun er að takmarka tréð við ákveðna hámarksdýpt, sem stjórnar hversu langan slóð getur teygt sig frá rót til laufblaðs.

Annað ferli sem tekur þátt í gerð ákvörðunartrjáa er að klippa. Pruning getur hjálpað til við að auka árangur ákvörðunartrés með því að fjarlægja greinar sem innihalda eiginleika sem hafa lítinn forspárkraft/lítið mikilvægi fyrir líkanið. Þannig minnkar flókið tréð, það minnkar líkur á offitun og forspárgildi líkansins eykst.

Þegar klipping er framkvæmd getur ferlið byrjað annað hvort efst á trénu eða neðst á trénu. Hins vegar er auðveldasta aðferðin til að klippa er að byrja á laufunum og reyna að sleppa hnútnum sem inniheldur algengasta flokkinn innan þess blaðs. Ef nákvæmni líkansins versnar ekki þegar þetta er gert, þá er breytingin varðveitt. Það eru aðrar aðferðir sem notaðar eru til að framkvæma klippingu, en aðferðin sem lýst er hér að ofan - minni skekkjuklipping - er líklega algengasta aðferðin við ákvörðunartrésklippingu.

Íhuganir fyrir notkun ákvörðunartrés

Ákvörðun tré eru oft gagnlegar þegar flokkun þarf að fara fram en reiknitími er mikil þvingun. Ákvörðunartré geta gert það ljóst hvaða eiginleikar í völdum gagnasettum hafa mesta forspárkraftinn. Ennfremur, ólíkt mörgum vélrænum reikniritum þar sem reglurnar sem notaðar eru til að flokka gögnin geta verið erfiðar að túlka, geta ákvörðunartré gert túlkanlegar reglur. Ákvörðunartré geta einnig nýtt sér bæði flokkaðar og samfelldar breytur sem þýðir að minni forvinnslu er þörf, samanborið við reiknirit sem ráða aðeins við eina af þessum breytutegundum.

Ákvörðunartré hafa tilhneigingu til að standa sig ekki mjög vel þegar þau eru notuð til að ákvarða gildi samfelldra eiginleika. Önnur takmörkun á ákvörðunartrjám er að þegar flokkun er gerð, ef það eru fá dæmi um þjálfun en margir flokkar, hefur ákvörðunartréð tilhneigingu til að vera ónákvæmt.