Drevesa odločanja: Kako optimizirati postopek odločanja?

Predstavljajmo si, da igrate igro dvajset vprašanj. Vaš nasprotnik je na skrivaj izbral zadevo in morate ugotoviti, kaj je izbral. Na vsakem koraku lahko postavite vprašanje da ali ne, nasprotnik pa mora resnično odgovoriti. Kako v najmanjšem številu vprašanj ugotovite skrivnost?

Očitno je, da so nekatera vprašanja boljša od drugih. Na primer, če vprašate "Ali lahko leti?", Bo vaše prvo vprašanje verjetno neplodno, medtem ko je vprašanje "Ali je živ?" Nekoliko bolj koristno. Intuitivno si želite, da bi vsako vprašanje znatno zožilo prostor morda skrivnosti, kar na koncu privede do vašega odgovora.

To je osnovna ideja za odločitvena drevesa. Na vsaki točki upoštevate niz vprašanj, ki lahko razdelijo vaš nabor podatkov. Izberete vprašanje, ki omogoča najboljši razplet in znova najdete najboljša vprašanja za particije. Ko se vse točke, o katerih razmišljate, ustavijo, so istega razreda. Nato je naloga klasifikacije lahka. Točko lahko preprosto zgrabite in jo odklenete po drevesu. Vprašanja ga bodo usmerila v ustrezen razred.

Pomembni pogoji

Odločilno drevo je vrsta nadzorovanega algoritma učenja, ki ga je mogoče uporabiti tako pri regresiji kot pri klasifikaciji. Deluje tako za kategorične kot za neprekinjene vhodne in izhodne spremenljivke.

Na drevesu odločitev določimo pomembne terminologije in si oglejte zgornjo sliko:

  • Root Node predstavlja celotno populacijo ali vzorec. Nadalje se razdeli na 2 ali več homogenih nizov.
  • Sekanje je postopek delitve vozlišča na 2 ali več pododdelkov.
  • Ko se pododvod razdeli na nadaljnja pododdelka, ga imenujemo odločitveno vozlišče.
  • Vozlišča, ki se ne cepijo, imenujemo terminalsko vozlišče ali list.
  • Ko odstranite pododdelke odločitvenega vozlišča, se ta postopek imenuje obrezovanje. Nasprotno od obrezovanja je cepljenje.
  • Pododdelek celotnega drevesa se imenuje veja.
  • Vozlišče, ki je razdeljeno na pod vozlišča, se imenuje nadrejeno vozlišče pododstavkov; ker se pododreje imenujejo nadrejeno vozlišče.

Kako deluje

Tu govorim samo o klasifikacijskem drevesu, ki se uporablja za napovedovanje kakovostnega odziva. Regresijsko drevo je tisto, ki se uporablja za napovedovanje količinskih vrednosti.

V klasifikacijskem drevesu predvidevamo, da vsako opazovanje spada v najpogostejši razred opazovanj usposabljanja v regiji, v katero spada. Pri razlagi rezultatov klasifikacijskega drevesa nas pogosto zanima ne le napoved razreda, ki ustreza določenemu območju končnega vozlišča, ampak tudi deleži razredov med opazovanji vadbe, ki sodijo v to regijo. Naloga rasti drevesa klasifikacije temelji na uporabi ene od teh treh metod kot merila za izdelavo binarnih ločil:

1 - Stopnja napake pri klasifikaciji: "stopnjo zadetkov" lahko določimo kot del opazovanj pri usposabljanju v določeni regiji, ki ne spada v najbolj razširjen razred. Napaka je podana s to enačbo:

E = 1 - argmax_ {c} (π̂ mc)

v kateri π̂ mc predstavlja del podatkov o usposabljanju v regiji R_m, ki spadajo v razred c.

2 - Ginijev indeks: Ginijev indeks je alternativna meritev napak, ki je zasnovana tako, da prikaže, kako čista je regija. "Čistost" v tem primeru pomeni, koliko podatkov o usposabljanju v določeni regiji pripada enemu razredu. Če regija R_m vsebuje podatke, ki so večinoma iz enega razreda c, bo vrednost indeksa Gini majhna:

3 - Cross-Entropy: Tretja alternativa, ki je podobna Ginijevemu indeksu, je poznana kot Cross-Entropy ali Deviance:

Navzkrižna entropija bo prevzela vrednost blizu nič, če so vrednosti πc mc blizu 0 ali blizu 1. Zato bo podobno kot Gini indeks navzkrižna entropija dobila majhno vrednost, če je m-to vozlišče čisto. Pravzaprav se izkaže, da sta Ginijev indeks in navzkrižna entropija številčno precej podobna.

Pri gradnji klasifikacijskega drevesa se za ocenjevanje kakovosti določenega razcepa običajno uporablja Gini indeks ali navzkrižna entropija, saj so na čistost vozlišč bolj občutljivi, kot je stopnja napake pri klasifikaciji. Pri obrezovanju drevesa je mogoče uporabiti katerega koli od teh treh pristopov, vendar je prednostna stopnja napake pri razvrstitvi, če je cilj natančnost napovedi končnega obrezanega drevesa.

Izvajanje iz nič

Pojdimo po algoritmu gradnje odločitvenega drevesa z vsemi njegovimi podrobnostmi. Za izdelavo odločitvenega drevesa moramo sprejeti začetno odločitev za nabor podatkov, da narekujemo, katera funkcija se uporablja za delitev podatkov. Da bi to določili, moramo poskusiti z vsemi značilnostmi in izmeriti, kateri razcep bo prinesel najboljše rezultate. Po tem bomo nabor podatkov razdelili na podskupine. Podskupine bodo nato prečkale veje prvega odločitvenega vozlišča. Če so podatki o vejah istega razreda, smo jih pravilno razvrstili in nam ni treba nadaljevati z deljenjem. Če podatki niso enaki, moramo ponoviti postopek delitve v tej podskupini. Odločitev o tem, kako razdeliti to podskupino, se izvede na enak način kot prvotni nabor podatkov, in postopek ponavljamo, dokler ne razvrstimo vseh podatkov.

Kako razdelimo svoj nabor podatkov? Eden od načinov za organizacijo tega nereda je merjenje informacij. S pomočjo teorije informacij lahko merimo podatke pred in po razcepu. Sprememba informacij pred in po razcepu je znana kot pridobitev informacij. Ko znamo izračunati informacijski dobiček, lahko svoje podatke razdelimo na vsako funkcijo, da vidimo, kateri delitev nam prinaša največji informacijski dobiček. Razdelitev z največjo pridobitvijo informacij je naša najboljša možnost.

Za izračun pridobljene informacije lahko uporabimo Shannonovo entropijo, ki je pričakovana vrednost vseh informacij vseh možnih vrednosti našega razreda. Oglejmo si kodo Python:

Kot lahko vidite, najprej izračunamo število števila primerkov v naboru podatkov. Nato izdelamo slovar, katerega ključi so vrednosti v zadnjem stolpcu. Če ključa prej niste srečali, ga ustvarite. Za vsak ključ spremljamo, kolikokrat se ta oznaka pojavi. Na koncu uporabimo pogostost vseh različnih nalepk, da izračunamo verjetnost te etikete. To verjetnost uporabljamo za izračun entropije Shannona in to povzemamo za vse oznake.

Potem ko smo ugotovili, kako izmeriti entropijo nabora podatkov, moramo razstaviti nabor podatkov, izmeriti entropijo na razcepljenih nizih in videti, ali je bila delitev prava stvar. Tukaj je koda:

Ta koda ima 3 vhode: podatke, ki jih je treba razdeliti, funkcijo, ki jo je treba razdeliti, in vrednost, ki jo mora vrniti. Vsakič na začetku ustvarimo nov seznam, ker bomo to funkcijo večkrat poklicali na istem naboru podatkov in ne želimo, da se prvotni nabor podatkov spremeni. Naš nabor podatkov je seznam seznamov; ko ponovimo vsak element na seznamu in če vsebuje vrednost, ki jo iščemo, jo bomo dodali na novo ustvarjen seznam. Znotraj izjave if smo izrezali funkcijo, na katero smo se razdelili.

Zdaj bomo združili dve funkciji: ShannonEntropy in splitDataset, da se pomikate po naboru podatkov in se odločite, na katero funkcijo je najbolje razdeliti.

Hitro preučimo kodo:

  • Izračunamo entropijo Shannona celotnega nabora podatkov, preden pride do delitve in dodelimo vrednost spremenljivki baseEntropy.
  • Prva za zanke zanke nad vsemi funkcijami v naših podatkih. Razumevanja seznama uporabljamo za izdelavo seznama (featList) vseh i-tih vnosov v podatke ali vseh možnih vrednosti, ki so prisotne v podatkih.
  • Nato s seznama ustvarimo nov niz, da izvlečemo edinstvene vrednosti (uniqueVals).
  • Nato gremo skozi vse edinstvene vrednosti te funkcije in razdelimo podatke za vsako funkcijo (poddatke). Nova entropija se izračuna (newEntropy) in sešteje za vse edinstvene vrednosti te lastnosti. Dobitek informacij (infoGain) je zmanjšanje entropije (baseEntropy - newEntropy).
  • Na koncu primerjamo pridobljeno informacijo med vsemi funkcijami in vrnemo indeks najboljše lastnosti, da se razdeli na (bestFeature).

Zdaj, ko lahko merimo, kako organiziran je nabor podatkov in lahko podatke razdelimo, je čas, da vse to sestavimo in zgradimo drevo odločitev. Iz nabora podatkov smo ga razdelili na podlagi najboljšega atributa za split. Ko se ločijo, bodo podatki prešli veje drevesa v drugo vozlišče. To vozlišče bo nato podatke ponovno razdelilo. Za to bomo uporabili rekurzijo.

Ustavili se bomo le pod naslednjimi pogoji: (1) zmanjkalo atributov, na katere se lahko delijo, ali (2) vsi primeri v veji so istega razreda. Če imajo vsi primerki isti razred, bomo ustvarili vozlišče listov. Vsi podatki, ki dosežejo to vozlišče listja, veljajo, da pripadajo razredu tega vozlišča listov.

Tukaj je koda za izdelavo naših dreves odločitev:

Naša koda ima 2 vhoda: podatke in seznam nalepk:

  • Najprej ustvarimo seznam vseh oznak razreda v naboru podatkov in pokličemo ta seznam. Prvi pogoj zaustavljanja je, da če so vse oznake razreda enake, to oznako vrnemo. Drugi pogoj za zaustavitev je primer, ko ni več funkcij, ki bi jih lahko razdelili. Če ne izpolnjujemo pogojev ustavljanja, uporabimo funkcijo selectBestFeatureToSplit, da izberemo najboljšo funkcijo.
  • Če želite ustvariti drevo, ga bomo shranili v slovar (myTree). Nato dobimo vse edinstvene vrednosti iz nabora podatkov za našo izbrano funkcijo (bestFeat). Koda edinstvene vrednosti uporablja nabore (uniqueVals).
  • Na koncu ponovimo vse edinstvene vrednosti izbrane funkcije in rekurzivno pokličemo createTree () za vsako delitev nabora podatkov. Ta vrednost je vstavljena v slovar myTree, tako da na koncu dobimo veliko ugnezdenih slovarjev, ki predstavljajo naše drevo.

Izvajanje prek Scikit-Learna

Zdaj, ko vemo, kako algoritem implementirati od začetka, uporabimo učenje scikit. Zlasti bomo uporabili razred DecisionTreeClassifier. Delo s podatkovnim sistemom iris najprej podatke uvozimo in razdelimo na učni in testni del. Nato izdelamo model s privzeto nastavitvijo drevesa v celoti razvijamo (gojimo drevo, dokler vsi listi niso čisti). V drevesu popravimo random_state, ki se uporablja za interno ločevanje vezi:

Zagon modela bi nam moral dati 95-odstotno natančnost testnega niza, kar pomeni, da je model pravilno predvidel razred za 95% vzorcev v testnem naboru podatkov.

Prednosti in slabosti

Glavna prednost uporabe odločitvenih dreves je, da jih je intuitivno zelo enostavno razložiti. Tesno zrcalijo človeško odločanje v primerjavi z drugimi regresijskimi in klasifikacijskimi pristopi. Lahko so prikazani grafično in z lahkoto se spopadajo s kvalitativnimi napovedovalci, ne da bi morali ustvariti navidezne spremenljivke.

Druga velika prednost so taki algoritmi, ki so popolnoma nepomembni za spreminjanje podatkov. Ker se vsaka funkcija obdeluje ločeno in morebitne delitve podatkov niso odvisne od skaliranja, za algoritme drevesa odločanja ni potrebna predhodna obdelava, kot je normalizacija ali standardizacija funkcij. Zlasti drevesa odločanja dobro delujejo, kadar imamo funkcije, ki so na povsem različnih lestvicah, ali kombinacijo dvojiških in neprekinjenih funkcij.

Kljub temu pa drevesa odločanja na splošno nimajo enake ravni napovedne natančnosti kot drugi pristopi, saj niso zelo robustna. Majhna sprememba podatkov lahko povzroči veliko spremembo končnega ocenjenega drevesa. Tudi pri predhodnem obrezovanju ponavadi prekomerno obidejo in zagotavljajo slabo posplošitev. Zato lahko v večini aplikacij z združevanjem številnih dreves odločitev z uporabo metod, kot so zbiranje odpadkov, naključni gozdovi in ​​povečanje, lahko napovedno učinkovitost odločitvenih dreves bistveno izboljšate.

Referenčni viri:

  • Uvod v statistično učenje Gareth James, Daniela Witten, Trevor Hastie in Robert Tibshirani (2014)
  • Strojno učenje v akciji Peter Harrington (2012)
  • Uvod v strojno učenje s Pythonom Sarah Guido in Andreas Muller (2016)

- -

Če ste uživali v tem komadu, bi mi bil všeč, če pritisnete na gumb ploskve, tako da bi se drugi lahko spotaknili ob njem. Mojo lastno kodo najdete na GitHub-u, več mojih pisanj in projektov pa na https://jameskle.com/. Lahko mi sledite tudi na Twitterju, mi neposredno pošljete e-pošto ali pa me najdete na LinkedInu.