Stabla odluka: Kako optimizirati moj postupak donošenja odluka?

Zamislimo da igrate igru ​​Dvadeset pitanja. Vaš je protivnik potajno odabrao temu, a vi morate shvatiti što je odabrao. Na svakom koraku možete postaviti pitanje da ili ne, a vaš protivnik mora odgovoriti istinito. Kako možete saznati tajnu u najmanje broju pitanja?

Treba biti očito da su neka pitanja bolja od drugih. Na primjer, pitati "Može li letjeti?" Jer je vaše prvo pitanje vjerojatno besplodno, dok je pitanje "Je li živ?" Malo korisnije. Intuitivno, želite da svako pitanje značajno suzi prostor moguće tajne, što na kraju vodi do vašeg odgovora.

To je osnovna ideja iza stabala odluka. U svakom trenutku razmotrite skup pitanja koja mogu podijeliti vaš skup podataka. Vi birate pitanje koje omogućuje najbolji podjela i ponovno pronalazite najbolja pitanja za particije. Zaustavite se kad sve točke koje razmislite budu iste klase. Tada je zadatak klasifikacije lagan. Možete jednostavno zgrabiti točku i smjestiti je niz stablo. Pitanja će ga voditi u odgovarajuću klasu.

Važni uvjeti

Stablo odluka je vrsta algoritma nadziranog učenja koji se može koristiti i u regresiji i u klasifikacijskim problemima. Radi i za kategorijske i za kontinuirane ulazne i izlazne varijable.

Identificiramo važne terminologije na stablu odluka gledajući gornju sliku:

  • Korijenski čvor predstavlja cijelu populaciju ili uzorak. Nadalje se dijeli na 2 ili više homogenih skupova.
  • Podijeljenje je proces dijeljenja čvora na 2 ili više pot-čvorova.
  • Kad se pododvor podijeli na daljnje pod-čvorove, to se zove Odlučni čvor.
  • Čvorovi koji se ne dijele nazivaju se terminalnim čvorom ili listom.
  • Kada uklonite pod-čvorove čvora za odlučivanje, ovaj se postupak naziva obrezivanje. Suprotnost obrezivanju je cijepanje.
  • Pododjeljak cijelog stabla naziva se grana.
  • Čvor, koji je podijeljen na pod-čvorove, naziva se nadređeni čvor pod-čvorova; dok se podčvorovi nazivaju dijete nadređenog čvora.

Kako radi

Ovdje samo govorim o klasifikacijskom stablu koje se koristi za predviđanje kvalitativnog odgovora. Regresijsko stablo je ono koje se koristi za predviđanje kvantitativnih vrijednosti.

U klasifikacijskom stablu predviđamo da svako promatranje pripada grupi promatranja s učestalošću u regiji kojoj pripada. Tumačeći rezultate klasifikacijskog stabla često nas zanima ne samo predviđanje klase koje odgovara određenoj regiji terminalnog čvora, već i proporcije klase među opažanjima obuke koja spadaju u tu regiju. Zadatak uzgoja stabla klasifikacije oslanja se na korištenje jedne od ove tri metode kao kriterija za izradu binarnih rascjepa:

1 - Stopa pogrešaka klasifikacije: Možemo definirati "učestalost učitavanja" kao udio promatranja treninga u određenoj regiji koja ne pripada klasi najčešće prisutne. Pogreška je data ovom jednadžbom:

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

u kojoj π̂ mc predstavlja udio podataka o treningu u regiji R_m koji pripadaju razredu c.

2 - Gini indeks: Gini indeks je alternativna metrika pogreške koja je osmišljena da prikaže koliko je "čista" regija. "Čistoća" u ovom slučaju znači koliko podataka o obuci u određenoj regiji pripada jednom razredu. Ako regija R_m sadrži podatke koji su uglavnom iz jedne klase c, tada će vrijednost Gini indeksa biti mala:

3 - Cross-Entropy: Treća alternativa, koja je slična Ginijevom indeksu, poznata je kao Cross-Entropy ili Deviance:

Poprečna entropija će poprimiti vrijednost blizu nule ako su π̂ mc svi blizu 0 ili blizu 1. Stoga će, poput Gini indeksa, poprečna entropija poprimiti malu vrijednost ako je m-ti čvor čist. U stvari, ispada da su Gini indeks i umrežena entropija po brojkama prilično slični.

Pri izgradnji klasifikacijskog stabla za ocjenjivanje kvalitete određenog rascjepa obično se koristi Gini indeks ili umrežena entropija jer su oni osjetljiviji na čistoću čvora nego što je stopa pogreške pogreške u klasifikaciji. Bilo koji od ova tri pristupa može se primijeniti prilikom obrezivanja stabla, ali stopa pogreške klasifikacije je poželjna ako je cilj točnosti predviđanja konačnog obrezanog stabla.

Implementacija od nule

Prolazimo kroz algoritam kreiranja stabla odluka sa svim njegovim detaljima. Da bismo izgradili stablo odluka, moramo donijeti početnu odluku o skupu podataka da bismo diktirali koja se značajka koristi za podjelu podataka. Da bismo to utvrdili, moramo isprobati svaku značajku i mjeriti koji će nam rascjep dati najbolje rezultate. Nakon toga podijelit ćemo skup podataka na podskupove. Podskupovi će tada presjeći grane prvog čvora za odlučivanje. Ako su podaci o granama iste klase, pravilno smo ih klasificirali i ne treba ih dijeliti. Ako podaci nisu isti, tada moramo ponoviti postupak dijeljenja za ovaj podskup. Odluka o podjeli ovog podskupina vrši se na isti način kao u izvornom skupu podataka i ponavljamo ovaj postupak sve dok ne klasificiramo sve podatke.

Kako podijeliti svoj skup podataka? Jedan od načina organiziranja ove nerede je mjerenje informacija. Pomoću teorije informacija možemo izmjeriti podatke prije i nakon rascjepa. Promjena podataka prije i nakon rascjepa poznata je kao informacijski dobitak. Kad znamo kako izračunati informacijski dobitak, možemo podatke podijeliti na sve značajke da bismo vidjeli koji split nam daje najveći dobitak od informacija. Podjela s najvećim dobitkom informacija naša je najbolja opcija.

Da bismo izračunali dobitak od informacija, možemo koristiti Shannonovu entropiju, što je očekivana vrijednost svih informacija svih mogućih vrijednosti naše klase. Pogledajmo Python kod za to:

Kao što vidite, najprije izračunavamo računanje broja instanci u skupu podataka. Tada stvaramo rječnik čiji su ključevi vrijednosti u završnom stupcu. Ako ključ nije prethodno pronađen, stvara se jedan. Za svaki ključ pratimo koliko se puta ova etiketa pojavljuje. Na kraju, za izračunavanje vjerojatnosti te oznake koristimo frekvenciju svih različitih oznaka. Ova vjerojatnost se koristi za izračunavanje Shannonove entropije, i to sumiramo za sve oznake.

Nakon što pronađemo način za mjerenje entropije skupa podataka, moramo podijeliti skup podataka, izmjeriti entropiju na podijeljenim skupovima i vidjeti je li dijeljenje bilo ispravno. Evo kod za to:

Ovaj kôd uzima 3 unosa: podatke koje treba podijeliti, značajku na koju se dijeli i vrijednost značajke koju treba vratiti. Svaki put na početku stvaramo novi popis jer ćemo istu funkciju zvati više puta na istom skupu podataka i ne želimo da se izvorni skup podataka izmijeni. Naš je skup popis popisa; dok ponavljamo svaku stavku na popisu i ako sadrži vrijednost koju tražimo, dodaćemo je na naš novostvoreni popis. Unutar izjave if izrezali smo značajku na koju smo podijeljeni.

Sada ćemo kombinirati dvije funkcije: ShannonEntropy i splitDataset da bi prolazili kroz skup podataka i odlučili na koje je značajke najbolje podijeliti.

Let's brzo ispitati kod:

  • Izračunavamo Shannonovu entropiju cijelog skupa podataka prije bilo kakvog dijeljenja i dodijelimo vrijednost varijabli baseEntropy.
  • Prvi za petlju petlje nad svim značajkama u našim podacima. Koristimo razumijevanja popisa za stvaranje popisa (featList) svih i-tih unosa u podacima ili svih mogućih vrijednosti prisutnih u podacima.
  • Zatim s popisa stvaramo novi skup kako bismo izvadili jedinstvene vrijednosti (uniqueVals).
  • Zatim prolazimo kroz sve jedinstvene vrijednosti ove značajke i dijelimo podatke za svaku značajku (podData). Nova entropija se izračunava (novaEntropy) i zbraja za sve jedinstvene vrijednosti te značajke. Dobitak informacija (infoGain) je smanjenje entropije (baseEntropy - newEntropy).
  • Konačno, uspoređujemo dobivanje informacija među svim značajkama i vraćamo indeks najbolje značajke za podjelu (bestFeature).

Sada kada možemo izmjeriti kako je organiziran skup podataka i možemo podijeliti podatke, vrijeme je da sve to sastavimo i izgradimo stablo odluka. Iz skupa podataka podijelili smo ga na temelju najboljeg atributa split. Kad se podijele, podaci će preći grane stabla do drugog čvora. Nakon toga će čvor ponovno podijeliti podatke. Upotrijebit ćemo rekurziju za rješavanje ovog problema.

Zaustavit ćemo se samo pod sljedećim uvjetima: (1) ponestaje atributa na koje treba podijeliti ili (2) sve su instance u grani iste klase. Ako sve instance imaju istu klasu, tada ćemo stvoriti list čvora. Smatra se da svi podaci koji dopiru do ovog čvorova lista pripadaju klasi tog čvorišta listova.

Evo koda za izgradnju stabala naših odluka:

Naš kod uzima 2 ulaza: podatke i popis naljepnica:

  • Prvo stvaramo popis svih oznaka klase u skupu podataka i zovemo ovaj popis klasa. Prvi uvjet zaustavljanja je da ako su sve oznake klase iste, vraćamo tu oznaku. Drugi uvjet zaustavljanja je slučaj kada nema više mogućnosti za dijeljenje. Ako ne ispunjavamo uvjete zaustavljanja, koristimo funkciju selectBestFeatureToSplit da odaberemo najbolju značajku.
  • Da bismo stvorili stablo, spremit ćemo ga u rječnik (myTree). Tada dobivamo sve jedinstvene vrijednosti iz skupa podataka za našu odabranu značajku (bestFeat). Jedinstveni kod vrijednosti koristi skupove (uniqueVals).
  • Konačno, ponavljamo sve jedinstvene vrijednosti iz naše odabrane značajke i rekurzivno pozivamo createTree () za svaki podijeljeni niz podataka. Ova je vrijednost umetnuta u myTree rječnik, pa na kraju nalazimo s puno ugniježđenih rječnika koji predstavljaju naše stablo.

Implementacija putem Scikit-Learna

Sada kada znamo kako implementirati algoritam od nule, iskoristimo scikit-learn. Konkretno, upotrijebit ćemo klasu DecisionTreeClassifier. Radeći s podacima o irisu, podatke prvo uvezemo i podijelimo u dio za obuku i test. Zatim gradimo model koristeći zadane postavke potpunog razvoja stabla (uzgajanje stabla dok svi listovi ne budu čisti). Popravljamo random_state u stablu koji se koristi za interno lomljenje kravata:

Pokretanje modela trebalo bi nam dati točnost testnog skupa od 95%, što znači da je model ispravno predvidio klasu za 95% uzoraka u testnom skupu podataka.

Prednosti i mane

Glavna prednost korištenja stabala odluka je u tome što ih je intuitivno vrlo lako objasniti. Oni usko zrcale ljudsko odlučivanje u usporedbi s drugim regresijskim i klasifikacijskim pristupima. Mogu se prikazati grafički i mogu lako obraditi kvalitativne prediktore bez potrebe za stvaranjem lažnih varijabli.

Još jedna velika prednost su takvi algoritmi koji su potpuno invarijantni za skaliranje podataka. Kako se svaka značajka obrađuje zasebno, a mogući dijelovi podataka ne ovise o skaliranju, za algoritme stabla odluka nije potrebna prethodna obrada poput normalizacije ili standardizacije značajki. Konkretno, stabla odluka dobro funkcioniraju kada imamo značajke koje su na potpuno različitim mjerilima ili kombinaciju binarnih i kontinuiranih značajki.

Međutim, stabla odluka uglavnom nemaju istu razinu točnosti predviđanja kao i drugi pristupi jer nisu baš čvrsta. Mala promjena podataka može uzrokovati velike promjene u konačnom procijenjenom stablu. Čak i uz uporabu predobrezivanja, oni imaju tendenciju prekomjernog opskrbe i pružaju slabe rezultate generalizacije. Stoga se u većini aplikacija agregiranjem mnogih stabala odlučivanja, primjenom metoda poput vreća, slučajnih šuma i poticanja, predviđajuća svojstva stabala odluka mogu značajno poboljšati.

Referentni izvori:

  • Uvod u statističko učenje Gareth James, Daniela Witten, Trevor Hastie i Robert Tibshirani (2014)
  • Strojno učenje na djelu Peter Harrington (2012)
  • Uvod u strojno učenje s Pythonom Sarah Guido i Andreas Muller (2016)

- -

Ako ste uživali u ovom komadu, volio bih ako pritisnete tipku za pljeskanje kako bi se drugi mogli nataknuti na njega. Moj vlastiti kod možete pronaći na GitHub-u, a više mojih pisanja i projekata na https://jameskle.com/. Možete me pratiti i na Twitteru, direktno me poslati e-poštom ili naći na LinkedInu.