- Odločitvena drevesa modelirajo napovedi z rekurzivnimi razdelitvami, izbranimi za zmanjšanje nečistoč, z uporabo mer, kot so Ginijev koeficient, entropija ali varianca.
- Pridobivanje informacij vodi izbiro značilnosti in praga na vsakem vozlišču, kar drevesom omogoča, da obravnavajo tako regresijo kot klasifikacijo.
- Hiperparametri, kot so max_depth, min_samples_split in min_information_gain, nadzorujejo prekomerno prilagajanje in kompleksnost drevesa.
- Razumevanje mehanike posameznih dreves je bistveno, preden se premaknemo k ansamblim, kot so naključni gozdovi, ki stabilizirajo in izboljšujejo zmogljivost.
Regresija odločitvenega drevesa iz nič je ena najbolj poučnih vaj, ki jih lahko naredite, če želite resnično razumeti, kako razmišljajo modeli, ki temeljijo na drevesih, in zakaj so tako priljubljeni v strojnem učenju. Namesto da bi drevo obravnavali kot skrivnostno črno skrinjico, boste videli, kako je izbrana vsaka delitev, kako se meri nečistoča in kako se na listih ustvarjajo numerične napovedi, tako za regresijske kot klasifikacijske probleme.
V tem priročniku si bomo ogledali ključne ideje odločitvenih dreves, stroškovne funkcije, ki jih uporabljajo, kako iščejo najboljše delitve in kako kodirati osnovno drevo, ki podpira tako regresijo kot klasifikacijo, pri čemer bomo uporabili le temeljne koncepte, kot so zanke, pogoji in preprosta statistika. Med potjo bomo primerjali regresijska in klasifikacijska drevesa, povezali teorijo s praktičnimi implementacijami v orodjih, kot sta Python in R (na primer z rpart in tree), ter na kratko umestili odločitvena drevesa znotraj večjih ansamblov, kot so naključni gozdovi.
Kaj je odločitveno drevo in zakaj je tako intuitivno?
Odločitveno drevo je v bistvu tok vprašanj z da/ne (ali preprostih pravil), ki vas vodi od korenske odločitve do končne napovedi v listnem vozlišču. V tipičnem nadzorovanem učenju je cilj napovedati ciljno spremenljivko Y z uporabo več napovedovalcev (značilnosti, kovarijev), drevo pa se nauči zaporedja vprašanj, kot sta »ali je teža ≤ 103?« ali »ali je država v {ZDA, Združeno kraljestvo, Kalifornija}?«, ki postopoma razdeli podatke v bolj homogene skupine.
Da bi dobili nekaj intuicije, si predstavljajte, da želite napovedati, ali je nekdo debel, pri čemer uporabite le višino in težo, in imate označen nabor podatkov, ki vam pove, kdo je debel in kdo ne. Drevo lahko odkrije pravilo, kot je »če je teža > 100 kg, napoveduj debelost«, vendar to pravilo ne bo popolno: nekateri ljudje nad 100 kg ne bodo debeli, nekateri pod tem pragom pa bodo. Drevo nato nenehno dodaja več vprašanj (podvprašanj), na primer o višini ali natančnejšem pragu teže, da bi »izboljšalo« te začetne grobe napovedi.
Vsako notranje vozlišče v drevesu ustreza odločitvenemu pravilu, vsaka veja ustreza enemu izidu tega pravila, vsako listno vozlišče pa ustreza območju prostora značilnosti, kjer so napovedi konstantne. Pri klasifikaciji list vrne oznako razreda (ali porazdelitev verjetnosti po oznakah); pri regresiji list običajno vrne povprečje ciljnih vrednosti, ki spadajo v to območje.
Ena glavnih prednosti odločitvenih dreves je, da naravno obravnavajo tako regresijo kot klasifikacijo, jih je enostavno interpretirati in delujejo tako s kvantitativnimi kot kvalitativnimi (kategoričnimi) napovedovalci brez potrebe po obsežni predobdelavi. Za svoje značilnosti ali cilj vam ni treba predpostavljati nobene specifične porazdelitve, zaradi česar so drevesa zelo privlačna v resničnih scenarijih, kjer so klasične linearne predpostavke pogosto kršene.
Klasifikacijska v primerjavi z regresijskimi drevesi
Čeprav je struktura klasifikacijskih in regresijskih dreves enaka, se narava odzivne spremenljivke Y in stroškovne funkcije, uporabljene za delitev, med tema dvema tipoma razlikujeta. Ko je Y kvantitativen (na primer prodaja, pričakovana življenjska doba, poraba goriva), govorimo o regresijskem drevesu; ko je Y kvalitativen ali kategoričen (na primer preživeli v primerjavi z nepreživetimi, debeli v primerjavi z debelimi), govorimo o klasifikacijskem drevesu.
V regresijskem drevesu je običajni cilj razdeliti prostor značilnosti na območja, kjer je odziv mogoče aproksimirati s konstanto, pogosto s povprečjem opazovanj v tem območju. Tipična odločitvena pravila imajo obliko »je x«k ≤ c?”, kjer je xk je ena od kovariat in c je prag; ta pravila večkrat delijo prostor na hiperpravokotnike in vse točke v istem hiperpravokotniku si delijo isto predvideno vrednost ŷ.
V klasifikacijskem drevesu so razdelitve še vedno »značilnost ≤ prag?« ali »kategorija v množici S?«, vendar se kakovost razdelitve meri s tem, kako čista so nastala podrejena vozlišča glede na oznake razredov. Napoved listov je običajno večinski razred znotraj tega vozlišča, model pa poskuša ustvariti liste, ki so čim bližje temu, da vsebujejo le en razred.
Kljub tem razlikam v tipu cilja lahko z vidika kodiranja implementirate eno samo generično drevesno strukturo in preprosto vstavite različne mere nečistoč ali izgub, odvisno od tega, ali izvajate regresijo ali klasifikacijo. Kasneje, ko bomo izračunali informacijski dobiček, boste videli, da sta formuli za klasifikacijo (na podlagi entropije) in regresijo (na podlagi variance) v duhu vzporedni.
Funkcije nečistoč in stroškov v odločitvenih drevesih
V središču vsakega algoritma odločitvenega drevesa je stroškovna funkcija, ki ocenjuje, kako dobra je določena razdelitev pri ločevanju podatkov v smiselne skupine. Ta stroškovna funkcija je izražena z vidika nečistoč: vozlišče se šteje za čisto, če vsi njegovi vzorci pripadajo istemu razredu (za klasifikacijo) ali imajo skoraj enako številsko vrednost (za regresijo).
Kadar koli izberete kandidata za razdelitev na značilnosti, algoritem pogleda podrejena vozlišča, ki jih ustvari, in vpraša: »Kako mešane so oznake (ali vrednosti) v vsakem podrejenem vozlišču?« Dobra razdelitev je tista, ki ustvari podrejena vozlišča, ki so veliko manj nečista kot nadrejeno, kar pomeni, da so podatki znotraj vsakega podrejenega vozlišča bolj homogeni glede na cilj.
V klasifikacijskih drevesih se nečistost običajno meri z merili, kot sta Ginijev indeks ali entropija, ki oba zajameta verjetnost, da bi bilo naključno izbrano opazovanje v tem vozlišču napačno razvrščeno, če bi preprosto napovedali večinski razred. V regresijskih drevesih se nečistost običajno meri s kvadratno napako ali varianco, ki odraža, kako razpršene so ciljne vrednosti znotraj vozlišča.
Ginijev indeks: merjenje nečistoč v klasifikacijskih drevesih
Ginijev indeks je ena najpogosteje uporabljenih mer nečistoč za klasifikacijska drevesa, ker ga je enostavno izračunati in dobro deluje v praksi. Konceptualno meri verjetnost, da bi bilo naključno izbrano opazovanje iz vozlišča napačno razvrščeno, če bi bila njegova oznaka napovedana glede na porazdelitev oznak v tem vozlišču.
Če vozlišče vsebuje razrede z verjetnostmi P1P2, …, Pn, se Ginijev indeks izračuna kot Gini = 1 − Σ (Pi)². Ko je vozlišče popolnoma čisto (vsa opazovanja pripadajo istemu razredu), je ena od verjetnosti 1, ostale pa 0, zato je vsota kvadratov 1, Ginijev indeks pa 0, kar kaže na popolno čistost.
Po drugi strani pa Ginijev indeks doseže svoj maksimum, ko so razredi znotraj vozlišča enakomerno pomešani, na primer v binarnem problemu s P1 = P2 = 0.5, kar da Gini = 1 − (0.5² + 0.5²) = 0.5. V takšni situaciji je napovedovanje večinskega razreda najslabše, kar jih je mogoče dobiti za to porazdelitev, ker vozlišče vsebuje polovico vsakega razreda.
Ko implementirate Ginijev model v kodi, običajno vzamete vektor oznak za vozlišče, izračunate frekvenco vsakega razreda, pretvorite frekvence v verjetnosti in nato uporabite formulo 1 − Σ p². Če to storite za več kandidatnih razdelitev, lahko primerjate, katera razdelitev ustvari otroke z nižjo tehtano povprečno Ginijevo nečistočo, kar je točno tisto, kar drevo potrebuje, da se odloči za najboljšo razdelitev.
Entropija: drug pogled na klasifikacijsko nečistočo
Entropija je alternativna mera nečistoč, ki se pogosto uporablja v teoriji informacij in v zgodnjih drevesnih algoritmih, kot sta ID3 in C4.5, in zajema količino naključnosti ali negotovosti v porazdelitvi razredov vozlišča. Medtem ko se Gini osredotoča na verjetnost napačne klasifikacije, entropija kvantificira »presenečenje«, povezano z opazovanjem določenega razreda, ko je porazdelitev mešana.
Dane verjetnosti razreda p1, …, str.c Za vozlišče S je njegova entropija definirana kot E(S) = − Σ pi log₂(p)i). Če je vozlišče čisto, je ena od verjetnosti 1, vse ostale pa 0, zaradi česar je vsota nič (ker je log₂(1) = 0), zato je entropija 0, kar pomeni, da ni negotovosti.
Ko vozlišče vsebuje enakomerno porazdelitev razredov, je entropija maksimizirana; za binarni problem s p1 = str2 = 0.5, entropija je 1 bit, kar je najvišja možna vrednost za dva razreda. Ta vrednost ustreza največji negotovosti, kar pomeni, da je vozlišče pri tej porazdelitvi čim bolj nečisto.
Čeprav Ginijeva formula in entropija uporabljata različni formuli in imata različna numerična območja (Ginijeva med 0 in 0.5 za dva razreda, entropija med 0 in 1), oba merita v bistvu isti koncept, zato v praksi običajno vodita do zelo podobnih dreves. Ko oba izračunate na istem vozlišču, boste ugotovili, da visok Ginijev koeficient ustreza visoki entropiji in obratno, zato vam številne knjižnice omogočajo izbiro katerega koli od njih, ne da bi pri tem drastično spremenile zmogljivost.
Pridobivanje informacij in izbira najboljših delitev
Za izbiro najboljše delitve med številnimi kandidati drevesni algoritem uporablja metriko, imenovano Information Gain, ki meri, koliko nečistoč se zmanjša, ko vozlišče razdelimo na njegove podrejene dele. Intuitivno ima razdelitev visok informacijski dobiček, če so podrejeni elementi veliko čistejši od nadrejenega, kar pomeni, da je pravilo uspešno ločilo podatke v bolj smiselne skupine.
Za klasifikacijska drevesa, ki uporabljajo entropijo, je informacijski dobiček razdelitve definiran kot IGRazvrstitev = E(starševski element) − Σ (|Sotrok| / |Sod staršev|) · E(S)otrok). Najprej izračunate entropijo nadrejenega vozlišča, nato pa odštejete tehtano povprečno entropijo podrejenih vozlišč, kjer so uteži njihove relativne velikosti.
Za regresijska drevesa analogen koncept uporablja varianco ali povprečno kvadratno napako kot mero nečistoče, kar daje IGregresija = Var(starševski) − Σ (|Sotrok| / |Sod staršev|) · Var(S)otrok). V tem okolju je dobra delitev tista, ki bistveno zmanjša variabilnost ciljnih vrednosti znotraj vsakega otroka.
Algoritem za učenje drevesa oceni ta informacijski dobiček za vsako možno razdelitev na vsaki značilnosti, nato pa izbere razdelitev z največjim dobičkom, pod pogojem, da presega določen minimalni prag, da se izogne ustvarjanju neuporabnih, drobnih izboljšav. Ta postopek se nato rekurzivno ponavlja na vsakem podrejenem vozlišču, dokler niso doseženi nekateri kriteriji zaustavitve.
Kako poiskati najboljšo razdelitev za vsako značilnost
Iskanje najboljše razdelitve na posamezni značilnosti je odvisno od tega, ali je značilnost numerična ali kategorična, vendar je osnovna ideja vedno enaka: našteti kandidatne particije in izračunati njihov informacijski dobiček. Za numerične značilnosti je particija definirana s pragom; za kategorične značilnosti pa z združevanjem ravni v podmnožice.
Za numerični napovedovalec je običajna strategija ogled vseh edinstvenih vrednosti, ki jih funkcija sprejme v trenutnem vozlišču, njihovo razvrščanje in nato upoštevanje kandidatnih pragov med zaporednimi vrednostmi. Za vsak kandidatni prag c ustvarite dve skupini (x ≤ c in x > c), izračunate nečistočo vsake skupine in nato izračunate informacijski dobiček; prag, ki prinese največji dobiček, je vaša najboljša numerična razdelitev na tej značilnosti.
Pri obravnavanju kategoričnih napovedovalcev je iskalni prostor bolj zapleten, ker bi načeloma lahko katera koli podmnožica kategorij tvorila eno stran razcepa, komplement pa na drugi strani. V značilnosti s kategorijami K obstaja veliko možnih podmnožic (2K−1 − 1 netrivialne particije), zato v praksi implementacije pogosto omejijo to iskanje ali uporabljajo hevristiko, zlasti kadar je K veliko.
Ko izračunate najboljšo delitev za vsako značilko, primerjate njihove informacijske dobitke in izberete značilnost in prag (ali podmnožico kategorij), ki ustreza največjemu dobitku. Ta izbrana razdelitev postane odločitev na trenutnem vozlišču, proces učenja pa se nato ponovi na vsakem otroku z ustrezno podmnožico opazovanj.
Nadzor rasti dreves s hiperparametri
Če odločitvenemu drevesu dovolite, da raste brez omejitev, se bo delilo, dokler vsak list ne bo popolnoma čist ali pa bo vseboval zelo malo opazovanj, kar skoraj vedno vodi do hudega pretiranega prilagajanja (prekomerno prilagajanje v primerjavi s premalo prilagajanjem). Da bi se temu izognili, nastavite zbirko hiperparametrov, ki nadzorujejo globino in kompleksnost drevesa.
Pogost hiperparameter je max_depth, ki omejuje največje število nivojev, ki jih lahko drevo zraste od korena do katerega koli lista. Če je max_depth nastavljen na None (ali na zelo veliko število), lahko drevo raste, dokler so izpolnjene druge omejitve; če je majhna, drevo ostane plitvo in bolj razumljivo, vendar morda ne bo ustrezno prilagojeno.
Drug ključni hiperparameter je min_samples_split, ki določa najmanjše število opazovanj, ki jih mora vozlišče vsebovati, preden ga je mogoče razdeliti. Če ima vozlišče manj vzorcev kot ta prag, se spremeni v list, kar modelu preprečuje, da bi lovil šum v zelo majhnih podmnožicah podatkov.
Prav tako lahko uveljavite minimalni informacijski dobiček (min_information_gain), tako da algoritem izvede delitev le, če ustvari pomembno izboljšanje pri zmanjšanju nečistoč. S tem se izognemo ustvarjanju nepotrebnih vej, ki komajda spremenijo napovedi in zgolj zapletejo drevesno strukturo.
Gradnja odločitvenega drevesa iz nič v kodi
Izvajanje odločitvenega drevesa iz nič se običajno vrti okoli majhnega nabora osnovnih funkcij, ki se kličejo rekurzivno. Medtem ko knjižnice, kot sta scikit-learn ali rpart, vse to počnejo v ozadju, pa logiko veliko bolj jasno naredite, če te korake kodirate sami (programska logika) in vam daje popoln nadzor nad vedenjem.
Najprej potrebujete rutino, ki glede na trenutne podatke na vozlišču oceni vsako značilnost in vsako kandidatno razdelitev, da najde tisto z največjim informacijskim dobitkom. Ta funkcija vrne izbrano značilnost, pravilo razdelitve (prag ali podmnožico kategorij), vrednost ojačanja in logično masko ali nabor indeksov, ki določajo, kateri vzorci gredo levo in kateri desno.
Drugič, potrebujete funkcijo napovedovanja za listna vozlišča, ki pretvori nabor ciljnih vrednosti v tem vozlišču v eno samo napoved. Za regresijo je to običajno povprečje y v tem vozlišču; za klasifikacijo običajno vzamete modus (najpogostejši razred), po možnosti pa shranite tudi verjetnosti razredov, če želite verjetnostne izhode.
Tretjič, ustvarite rekurzivno učno funkcijo, ki preveri kriterije zaustavitve, poišče najboljšo razdelitev, če je dovoljena, in nato zgradi podrejena vozlišča tako, da se pokliče na levi in desni podmnožici. Če pogoji za najmanjšo velikost vzorca, največjo globino ali najmanjši dobiček niso izpolnjeni, funkcija preneha z deljenjem in namesto nadaljnjih vej shrani napoved listov.
Kako deluje napovedovanje v naučenem odločitvenem drevesu
Ko je vaše drevo naučeno in shranite vsa pravila razdelitve in napovedi listov, je napoved za novo opazovanje preprosto stvar sprehoda po drevesu od korena do lista. Na vsakem notranjem vozlišču pregledate zahtevano značilnost in preizkusite, ali opazovanje izpolnjuje pogoj vozlišča.
Če je pravilo razdelitve numerično, preverite, ali je vrednost značilnosti manjša ali enaka pragu; če je pravilo razdelitve kategorično, preverite, ali je kategorija v določeni podmnožici. Glede na izid sledite ustrezni veji (na primer »da« levo, »ne« desno) in ta postopek ponovite na naslednjem vozlišču.
Nadaljujete spuščanje po drevesu, dokler ne dosežete vozlišča brez otrok, ki je list, ki shranjuje konstantno izhodno vrednost ali oznako razreda. Za regresijsko drevo bo napoved število, kot je ocenjena pričakovana življenjska doba ali učinkovitost porabe goriva; za klasifikacijsko drevo bo izhod predvidena kategorija, kot je »preživel« ali »ni preživel«.
Če ta pristop preizkusite na istih podatkih, ki ste jih uporabili za učenje, boste pogosto opazili precej visoko natančnost klasifikacije (na primer okoli 85 % v nekaterih preprostih primerih debelosti ali v slogu Titanika), vendar se lahko ta zmogljivost zmanjša na nevidnih podatkih, če je vaše drevo pregloboko. Prav zato je nadzor nad globino in velikostjo dreves tako pomemben in zato so bili izumljeni ansambli, kot so naključni gozdovi, za stabilizacijo napovedi dreves.
Delo z regresijskimi drevesi v praksi
Regresijska drevesa so še posebej priročna, kadar je razmerje med napovedovalci in odzivom močno nelinearno in vključuje interakcije, ki jih je težko modelirati s klasično linearno regresijo. Namesto da bi poskušalo prilagoditi eno samo globalno enačbo, drevo razdeli prostor značilnosti na regije in znotraj vsake regije prilagodi preprost konstantni model.
V R-ju priljubljeni paketi, kot sta rpart in tree, olajšajo gradnjo regresijskih dreves z enim klicem funkcije, ki določa formulo, kot je y ~ x1 + x2 + … + x11. Na te pakete je vplivala originalna metodologija CART, ki so jo opisali Breiman in sodelavci, in izvajajo številne ideje o deljenju in obrezovanju, ki so standardne v sodobnem modeliranju na osnovi dreves.
Na primer, paket rpart lahko uporabite za modeliranje odziva y na podlagi enajstih spremenljivk od x1 do x11, čiščenje podatkov manjkajočih vrednosti in nato vizualizacijo nastalega drevesa s pomožnimi funkcijami, kot je prp iz paketa rpart.plot. Končna vozlišča prikazujejo predvideni y za vsako regijo, ki ga lahko neposredno uporabite za nova opazovanja.
Glede na naučeno regresijsko drevo lahko v funkcijo napovedovanja vnesete nove vrednosti kovariat, kot so x9 = 70, x2 = 100 ali x9 = 60, x2 = 150, da dobite ocenjene vrednosti ŷ (na primer okoli 20 ali 28 v primeru porabe goriva). Primerjava teh napovedi z opazovanimi vrednostmi, na primer s korelacijo med y in ŷ, vam da hiter občutek, kako dobro drevo zajame osnovni vzorec, tudi če je nabor podatkov precej majhen.
Od posameznih dreves do naključnih gozdov
Eno samo odločitveno drevo je sicer močno, a hkrati znano občutljivo na posebnosti učnih podatkov, kar lahko privede do velike variance (pristranskost in varianca) in prekomerno prilagajanje. Da bi to ublažili, naključni gozdovi zgradijo veliko dreves na vzorcih podatkov, pridobljenih s samodejnim zagonom, in združijo njihove napovedi, kar ustvari stabilnejši in običajno natančnejši model.
V naključnem gozdu se vsako drevo nauči na vzorcu bootstrap, kar pomeni, da se iz prvotnega učnega nabora z zamenjavo izvleče nov nabor podatkov enake velikosti. Zaradi tega postopka vzorčenja vsako drevo vidi nekoliko drugačen nabor podatkov, zato so njihove napake manj korelirane in se lahko pri agregiranju izničijo.
Poleg tega naključni gozdovi uvajajo naključnost v proces izbire značilnosti, saj pri vsaki delitvi upoštevajo le naključno podmnožico napovedovalcev in ne vseh napovedovalcev. To dodatno zmanjša korelacijo med drevesi, poveča raznolikost v gozdu in ponavadi zmanjša varianco, ne da bi preveč povečalo pristranskost.
Kombinacija samodejnega zagonskega vzorca (bootstrapping) in združevanja napovedi je znana kot združevanje (bagging), v naključnih gozdovih pa dobite tudi notranjo oceno napake modela z vrednotenjem vsakega drevesa na podatkovnih točkah, ki niso bile vključene v njegov samodejni vzorec (tako imenovana opazovanja zunaj vreče). Ta napaka »out-of-bag« ponuja priročen način za merjenje učinkovitosti delovanja brez potrebe po ločenem naboru za preverjanje veljavnosti.
Čeprav se ta članek osredotoča na gradnjo enega samega drevesa iz nič, razumevanje delovanja te osnovne komponente veliko olajša razumevanje, kako ansambli, kot so naključni gozdovi, gradientno povečanje in druge metode, ki temeljijo na drevesih, gradijo na istih načelih za doseganje najsodobnejših rezultatov pri številnih uporabnih problemih.
Če vse skupaj sestavimo, vam regresija odločitvenega drevesa iz nič pokaže, kako lahko preprost nabor pravil, stroškovnih funkcij in rekurzivnih delitev modelira kompleksne odnose, ne glede na to, ali napovedujete binarni izid, kot je preživetje, kategorično oznako, kot je stanje debelosti, ali numerični cilj, kot je pričakovana življenjska doba ali poraba goriva, in to poglobljeno razumevanje postane trdna podlaga za uporabo naprednejših tehnik, ki temeljijo na drevesih, v praksi.
