Kaj je drevo odločitev?

Kaj je drevo odločitev?

A odločitveno drevo je uporaben algoritem strojnega učenja, ki se uporablja tako za naloge regresije kot klasifikacije. Ime »odločitveno drevo« izhaja iz dejstva, da algoritem še naprej deli nabor podatkov na manjše in manjše dele, dokler podatki niso razdeljeni na posamezne primerke, ki so nato razvrščeni. Če bi vizualizirali rezultate algoritma, bi način razdelitve kategorij spominjal na drevo in veliko listov.

To je kratka definicija odločitvenega drevesa, vendar se poglobimo v delovanje odločitvenih dreves. Boljše razumevanje delovanja odločitvenih dreves in primerov njihove uporabe vam bo pomagalo vedeti, kdaj jih uporabiti med projekti strojnega učenja.

Oblika odločitvenega drevesa

Odločitveno drevo je zelo podoben diagramu poteka. Če želite uporabiti diagram poteka, začnete na začetni točki ali korenu grafikona in se nato glede na to, kako izpolnjujete kriterije filtriranja tega začetnega vozlišča, premaknete na eno od naslednjih možnih vozlišč. Ta postopek se ponavlja, dokler ni dosežen konec.

Odločitvena drevesa delujejo v bistvu na enak način, pri čemer je vsako notranje vozlišče v drevesu neke vrste merilo za testiranje/filtriranje. Vozlišča na zunanji strani, končne točke drevesa, so oznake za zadevno podatkovno točko in se imenujejo "listi". Veje, ki vodijo od notranjih vozlišč do naslednjega vozlišča, so funkcije ali konjunkcije funkcij. Pravila, ki se uporabljajo za razvrščanje podatkovnih točk, so poti, ki potekajo od korena do listov.

Algoritmi za odločitvena drevesa

Odločitvena drevesa delujejo na podlagi algoritemskega pristopa, ki nabor podatkov razdeli na posamezne podatkovne točke na podlagi različnih meril. Te delitve se izvajajo z različnimi spremenljivkami ali različnimi značilnostmi nabora podatkov. Na primer, če je cilj ugotoviti, ali je pes ali mačka opisan z vhodnimi značilnostmi ali ne, so lahko spremenljivke, na katere so razdeljeni podatki, stvari, kot sta "kremplji" in "lajanje".

Kateri algoritmi se torej uporabljajo za dejansko razdelitev podatkov na veje in liste? Obstajajo različne metode, ki jih je mogoče uporabiti za razdelitev drevesa, vendar je najpogostejša metoda cepitve verjetno tehnika, imenovana "rekurzivna binarna delitev”. Pri izvajanju te metode delitve se postopek začne pri korenu in število funkcij v naboru podatkov predstavlja možno število možnih delitev. Funkcija se uporablja za določitev, koliko natančnosti bo stala vsaka možna delitev, delitev pa se opravi z uporabo meril, ki žrtvujejo najmanjšo natančnost. Ta proces se izvaja rekurzivno in podskupine se oblikujejo z uporabo iste splošne strategije.

Da bi določite stroške delitve, se uporablja stroškovna funkcija. Za naloge regresije in naloge klasifikacije se uporablja drugačna stroškovna funkcija. Cilj obeh stroškovnih funkcij je ugotoviti, katere veje imajo najbolj podobne vrednosti odziva oziroma najbolj homogene veje. Upoštevajte, da želite, da testni podatki določenega razreda sledijo določenim potem in to je intuitivno smiselno.

V smislu regresijske stroškovne funkcije za rekurzivno binarno razdelitev je algoritem, uporabljen za izračun stroškov, naslednji:

vsota(y – napoved)^2

Napoved za določeno skupino podatkovnih točk je povprečje odzivov podatkov o usposabljanju za to skupino. Vse podatkovne točke se izvajajo skozi stroškovno funkcijo, da se določijo stroški za vse možne delitve in izbrana je delitev z najnižjimi stroški.

V zvezi s funkcijo stroškov za klasifikacijo je funkcija naslednja:

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

To je Ginijeva ocena in je merilo učinkovitosti delitve, ki temelji na tem, koliko primerkov različnih razredov je v skupinah, ki izhajajo iz delitve. Z drugimi besedami, kvantificira, kako mešane so skupine po razdelitvi. Optimalna delitev je, ko so vse skupine, ki izhajajo iz delitve, sestavljene samo iz vložkov iz enega razreda. Če je bila ustvarjena optimalna delitev, bo vrednost "pk" 0 ali 1 in G bo enak nič. Morda boste lahko uganili, da je v najslabšem primeru razdelitev tista, kjer obstaja 50-50 predstavitev razredov v razdelitvi, v primeru binarne klasifikacije. V tem primeru bi bila vrednost "pk" 0.5 in G bi bil prav tako 0.5.

Postopek delitve se zaključi, ko so vse podatkovne točke spremenjene v liste in razvrščene. Vendar pa boste morda želeli zgodaj ustaviti rast drevesa. Velika zapletena drevesa so nagnjena k prekomernemu opremljanju, vendar je za boj proti temu mogoče uporabiti več različnih metod. Eden od načinov za zmanjšanje prekomernega opremljanja je določitev najmanjšega števila podatkovnih točk, ki bodo uporabljene za ustvarjanje lista. Druga metoda nadzora nad opremljanjem je omejitev drevesa na določeno največjo globino, ki nadzoruje, kako dolgo se lahko pot razteza od korenine do lista.

Še en proces, ki je vključen v ustvarjanje odločitvenih dreves je obrezovanje. Obrezovanje lahko pomaga povečati učinkovitost odločitvenega drevesa tako, da odstrani veje, ki vsebujejo funkcije, ki imajo majhno napovedno moč/majhen pomen za model. Na ta način se zmanjša kompleksnost drevesa, manjša je verjetnost, da bo preobremenjeno, in poveča se napovedna uporabnost modela.

Pri obrezovanju se lahko postopek začne bodisi na vrhu drevesa bodisi na dnu drevesa. Vendar pa je najlažji način obrezovanja, da začnete z listi in poskušate izpustiti vozlišče, ki vsebuje najpogostejši razred znotraj tega lista. Če se točnost modela ob tem ne poslabša, se sprememba ohrani. Obstajajo tudi druge tehnike, ki se uporabljajo za izvajanje obrezovanja, vendar je zgoraj opisana metoda – obrezovanje z zmanjšano napako – verjetno najpogostejša metoda obrezovanja odločitvenega drevesa.

Premisleki glede uporabe dreves odločanja

Odločitvena drevesa so pogosto uporabni ko je treba izvesti klasifikacijo, vendar je čas izračuna velika omejitev. Odločitvena drevesa lahko pojasnijo, katere funkcije v izbranih naborih podatkov imajo največjo napovedno moč. Poleg tega lahko za razliko od mnogih algoritmov strojnega učenja, kjer je pravila, uporabljena za razvrščanje podatkov, težko razlagati, odločitvena drevesa upodobijo pravila, ki jih je mogoče razlagati. Odločitvena drevesa lahko uporabljajo tako kategorične kot zvezne spremenljivke, kar pomeni, da je potrebna manjša predhodna obdelava v primerjavi z algoritmi, ki lahko obravnavajo samo eno od teh vrst spremenljivk.

Odločitvena drevesa običajno ne delujejo zelo dobro, če se uporabljajo za določanje vrednosti zveznih atributov. Druga omejitev odločitvenih dreves je, da je pri razvrščanju, če je primerov za usposabljanje malo, a veliko razredov, odločitveno drevo ponavadi netočno.