Regresia arborelui decizional de la zero: Teorie și practică

Acasă » Piton » Regresia arborelui decizional de la zero: Teorie și practică

Regresia bazată pe arborele decizional de la zero este unul dintre cele mai revelatoare exerciții pe care le poți face dacă vrei să înțelegi cu adevărat cum gândesc modelele bazate pe arbore și de ce sunt atât de populare în învățarea automată. În loc să tratați arborele ca pe o cutie neagră misterioasă, veți vedea cum este aleasă fiecare divizare, cum este măsurată impuritatea și cum sunt produse predicții numerice la nivelul frunzelor, atât pentru problemele de regresie, cât și pentru cele de clasificare.

În acest ghid, vom trece în revistă ideile de bază din spatele arborilor de decizie, funcțiile de cost pe care le utilizează, modul în care aceștia caută cele mai bune divizări și cum să codăm un arbore de bază care să suporte atât regresia, cât și clasificarea, folosind doar concepte fundamentale precum bucle, condiții și statistici simple. Pe parcurs, vom compara arborii de regresie cu cei de clasificare, vom conecta teoria la implementări practice în instrumente precum Python și R (de exemplu, cu rpart și tree) și vom situa pe scurt arborii de decizie în ansambluri mai mari, cum ar fi pădurile aleatorii.

Ce este un arbore decizional și de ce este atât de intuitiv?

Un arbore decizional este, în esență, un flux de întrebări de tip da/nu (sau reguli simple) care te ghidează de la o decizie inițială până la o predicție finală într-un nod frunză. Într-un cadru tipic de învățare supravegheată, scopul este de a prezice o variabilă țintă Y utilizând mai mulți predictori (caracteristici, covariate), iar arborele învață o secvență de întrebări precum „ponderea ≤ 103?” sau „țara este în {SUA, Marea Britanie, California}?”, care împart treptat datele în grupuri mai omogene.

Pentru a avea o intuiție, imaginați-vă că vreți să preziceți dacă cineva este obeză folosind doar înălțimea și greutatea și aveți un set de date etichetat care vă spune cine este obez și cine nu. Un arbore ar putea descoperi o regulă de genul „dacă greutatea > 100 kg, se preconizează obezitatea”, dar acea regulă nu va fi perfectă: unele persoane peste 100 kg nu vor fi obeze, iar altele sub acel prag vor fi. Arborele continuă apoi să adauge mai multe întrebări (subdiviziuni), de exemplu despre înălțime sau un prag de greutate rafinat, pentru a „ajusta fin” acele predicții inițiale aproximative.

Fiecare nod intern din arbore corespunde unei reguli de decizie, fiecare ramură corespunde unui rezultat al acelei reguli, iar fiecare nod frunză corespunde unei regiuni a spațiului de caracteristici unde predicțiile sunt constante. În clasificare, o frunză returnează o etichetă de clasă (sau o distribuție de probabilitate pe etichete); în regresie, o frunză returnează de obicei media valorilor țintă care se încadrează în acea regiune.

Unul dintre principalele puncte forte ale arborilor decizionali este faptul că gestionează atât regresia, cât și clasificarea în mod natural, sunt ușor de interpretat și funcționează atât cu predictori cantitativi, cât și calitativi (categorici) fără a necesita preprocesare complexă. Nu este nevoie să presupuneți nicio distribuție specifică pentru caracteristicile sau ținta dvs., ceea ce face ca arborii să fie foarte atractivi în scenariile din lumea reală în care ipotezele liniare clasice sunt adesea încălcate.

Clasificare vs. arbori de regresie

Deși structura arborilor de clasificare și de regresie este aceeași, natura variabilei de răspuns Y și funcția de cost utilizată pentru divizare diferă între aceste două tipuri. Când Y este cantitativ (de exemplu, vânzări, speranța de viață, consumul de combustibil), vorbim despre un arbore de regresie; când Y este calitativ sau categoric (de exemplu, a supraviețuit vs. nu a supraviețuit, obez vs. nu obez), vorbim despre un arbore de clasificare.

Într-un arbore de regresie, obiectivul obișnuit este de a împărți spațiul caracteristicilor în regiuni în care răspunsul poate fi aproximat printr-o constantă, adesea media observațiilor din acea regiune. Regulile de decizie tipice au forma „este x_k ≤ c?”, unde x_k este una dintre covariabile, iar c este un prag; aceste reguli împart în mod repetat spațiul în hiperdreptunghiuri, iar toate punctele din același hiperdreptunghi au aceeași valoare prezisă ŷ.

Într-un arbore de clasificare, divizările sunt încă de tip „caracteristică ≤ prag?” sau „categorie în mulțimea S?”, dar calitatea unei divizări este măsurată prin cât de pure sunt nodurile copil rezultate în termeni de etichete de clasă. Predicția frunzei este de obicei clasa majoritară din interiorul acelui nod, iar modelul încearcă să creeze frunze care să fie cât mai aproape posibil de a conține o singură clasă.

În ciuda acestor diferențe în ceea ce privește tipul țintă, din perspectiva codării, puteți implementa o singură structură arborescentă generică și pur și simplu să introduceți diferite măsuri de impuritate sau pierdere, în funcție de cum faceți regresie sau clasificare. Mai târziu, când vom calcula Câștigul Informațional, veți vedea că formulele pentru clasificare (bazată pe entropie) și regresie (bazată pe varianță) sunt paralele în spirit.

Funcții de impuritate și cost în arbori de decizie

În centrul oricărui algoritm de tip arbore decizional se află o funcție de cost care evaluează cât de bună este o anumită divizare la separarea datelor în grupuri semnificative. Această funcție de cost este exprimată în termeni de impuritate: un nod este considerat pur dacă toate eșantioanele sale aparțin aceleiași clase (pentru clasificare) sau au aproape aceeași valoare numerică (pentru regresie).

Ori de câte ori selectați o divizare candidată pe o caracteristică, algoritmul analizează nodurile copil pe care le produce și întreabă: „cât de amestecate sunt etichetele (sau valorile) din fiecare copil?” O divizare bună este una care produce noduri copil mult mai puțin impure decât părintele, ceea ce înseamnă că datele din fiecare copil sunt mai omogene în raport cu ținta.

În arborii de clasificare, impuritatea este de obicei măsurată prin criterii precum indicele Gini sau entropia, ambele surprinzând cât de probabil este ca o observație aleasă aleatoriu în acel nod să fie clasificată greșit dacă am prezice pur și simplu clasa majoritară. În arborii de regresie, impuritatea este de obicei măsurată cu eroarea pătratică sau varianța, reflectând cât de răspândite sunt valorile țintă în cadrul nodului.

Indicele Gini: măsurarea impurității în arborii de clasificare

Indicele Gini este una dintre cele mai frecvent utilizate măsuri de impuritate pentru arborii de clasificare, deoarece este simplu de calculat și funcționează bine în practică. Conceptual, aceasta măsoară probabilitatea ca o observație selectată aleatoriu din nod să fie clasificată incorect dacă eticheta sa ar fi prezisă în funcție de distribuția etichetelor din acel nod.

Dacă un nod conține clase cu probabilități P₁, P₂, …, P_n, indicele Gini se calculează ca Gini = 1 − Σ (P_i)². Când un nod este perfect pur (toate observațiile aparțin aceleiași clase), una dintre probabilități este 1, iar restul sunt 0, deci suma pătratelor este 1, iar indicele Gini este 0, indicând puritate deplină.

Pe de altă parte, indicele Gini atinge maximul atunci când clasele sunt amestecate uniform în interiorul nodului, de exemplu într-o problemă binară cu P₁ = P₂ = 0.5, ceea ce dă coeficientul Gini = 1 − (0.5² + 0.5²) = 0.5. În această situație, prezicerea clasei majoritare este cea mai rea posibilă pentru acea distribuție, deoarece nodul conține jumătate din fiecare clasă.

Când implementați Gini în cod, de obicei luați vectorul de etichete pentru nod, calculați frecvența fiecărei clase, convertiți frecvențele în probabilități și apoi aplicați formula 1 − Σ p². Dacă faceți acest lucru pentru mai multe divizări candidate, puteți compara care divizare produce copii cu o impuritate Gini medie ponderată mai mică, ceea ce este exact ceea ce arborele are nevoie pentru a decide asupra celei mai bune partiții.

Entropia: o altă perspectivă asupra impurității clasificării

Entropia este o măsură alternativă a impurității utilizată pe scară largă în teoria informației și în algoritmii arborescenți timpurii, cum ar fi ID3 și C4.5, și surprinde cantitatea de aleatoriu sau incertitudine din distribuția de clase a nodului. În timp ce Gini se concentrează pe probabilitatea de clasificare greșită, entropia cuantifică „surpriza” asociată cu observarea unei anumite clase atunci când distribuția este mixtă.

Având în vedere probabilitățile de clasă p₁, … , p._c pentru un nod S, entropia sa este definită ca E(S) = − Σ p_i log₂(p_i). Dacă nodul este pur, una dintre probabilități este 1 și toate celelalte sunt 0, ceea ce face ca suma să fie zero (deoarece log₂(1) = 0), deci entropia este 0, indicând lipsa incertitudinii.

Când nodul conține o distribuție uniformă de clase, entropia este maximizată; pentru o problemă binară cu p₁ =p₂ = 0.5, entropia este de 1 bit, care este cea mai mare valoare posibilă pentru două clase. Această valoare corespunde incertitudinii maxime, ceea ce înseamnă că nodul este cât se poate de impur în cadrul acelei distribuții.

Chiar dacă indicele Gini și entropia utilizează formule diferite și au intervale numerice diferite (Gini între 0 și 0.5 pentru două clase, entropia între 0 și 1), ambele măsoară în esență același concept, așa că, de obicei, în practică, duc la arbori foarte similari. Când calculați ambele pe același nod, veți constata că un coeficient Gini ridicat corespunde unei entropii ridicate și invers, motiv pentru care multe biblioteci vă permit să alegeți oricare dintre ele fără a schimba drastic performanța.

Obținerea de informații și alegerea celor mai bune diviziuni

Pentru a alege cea mai bună împărțire dintre mai mulți candidați, algoritmul arborelui folosește o metrică numită Câștig de informații, care măsoară cât de mult scade impuritatea atunci când împărțim un nod în copiii săi. Intuitiv, o divizare are un câștig informațional ridicat dacă copiii sunt mult mai puri decât părintele, ceea ce înseamnă că regula a separat cu succes datele în grupuri mai semnificative.

Pentru arborii de clasificare care utilizează entropia, Câștigul Informațional al unei divizări este definit ca IG_clasificare = E(părinte) − Σ (|S_copil| / |S_mamă|) · E(S_copil). Mai întâi calculați entropia nodului părinte, apoi scădeți entropia medie ponderată a nodurilor copil, unde ponderile sunt dimensiunile lor relative.

Pentru arborii de regresie, un concept analog folosește varianța sau eroarea medie pătratică ca măsură a impurității, dând IG_regres = Var(părinte) − Σ (|S_copil| / |S_mamă|) · Var(S_copil). În acest context, o divizare bună este una care reduce substanțial variabilitatea valorilor țintă în cadrul fiecărui copil.

Algoritmul de antrenament al arborelui evaluează acest Câștig de Informație pentru fiecare posibilă divizare candidată pe fiecare caracteristică, apoi alege divizarea cu cel mai mare câștig, cu condiția să depășească un anumit prag minim pentru a evita crearea de îmbunătățiri inutile și minuscule. Acest proces este apoi repetat recursiv pe fiecare nod copil până când sunt atinse anumite criterii de oprire.

Cum să cauți cea mai bună divizare pentru fiecare caracteristică

Găsirea celei mai bune divizări pentru o singură caracteristică depinde de caracterul numeric sau categorial al caracteristicii, dar ideea de bază este întotdeauna aceeași: enumerarea partițiilor candidate și calcularea câștigului lor informațional. Pentru caracteristicile numerice, o partiție este definită de un prag; pentru caracteristicile categorice, aceasta este definită prin gruparea nivelurilor în subseturi.

Pentru un predictor numeric, strategia obișnuită este de a analiza toate valorile unice pe care le ia caracteristica în nodul curent, de a le sorta și apoi de a lua în considerare pragurile candidate dintre valorile consecutive. Pentru fiecare prag candidat c, creați două grupuri (x ≤ c și x > c), calculați impuritatea fiecărui grup și apoi calculați câștigul informațional; pragul care produce cel mai mare câștig este cea mai bună divizare numerică pe acea caracteristică.

Când se lucrează cu predictori categorici, spațiul de căutare este mai complex deoarece, în principiu, orice subset de categorii ar putea forma o parte a diviziunii, cu complementul pe cealaltă parte. Într-o caracteristică cu K categorii, există multe subseturi posibile (2^K−1 − 1 partiții netriviale), așa că în practică implementările restricționează adesea această căutare sau utilizează euristici, în special atunci când K este mare.

După ce ați calculat cea mai bună divizare pentru fiecare caracteristică, comparați câștigurile informaționale ale acestora și selectați caracteristica și pragul (sau subsetul de categorii) corespunzător câștigului maxim. Această divizare aleasă devine decizia la nodul curent, iar procesul de antrenament se repetă apoi pentru fiecare copil cu subsetul corespunzător de observații.

Controlul creșterii arborilor cu hiperparametri

Dacă permiteți unui arbore decizional să crească fără nicio constrângere, acesta va continua să se divizeze până când fiecare frunză este fie perfect pură, fie conține foarte puține observații, ceea ce duce aproape întotdeauna la o supraadaptare severă (supraajustare vs montare insuficientă). Pentru a evita acest lucru, setați o colecție de hiperparametri care controlează adâncimea și complexitatea arborelui.

Un hiperparametru comun este max_depth, care limitează numărul maxim de niveluri pe care arborele le poate crește de la rădăcină până la orice frunză. Dacă max_depth este setat la None (sau la un număr foarte mare), arborele poate continua să crească atâta timp cât sunt îndeplinite celelalte constrângeri; dacă este mic, arborele rămâne superficial și mai ușor de interpretat, dar s-ar putea să nu fie suficient de potrivit.

Un alt hiperparametru cheie este min_samples_split, care specifică numărul minim de observații pe care un nod trebuie să le conțină înainte de a putea fi divizat. Dacă un nod are mai puține eșantioane decât acest prag, acesta se transformă într-o frunză, împiedicând modelul să urmărească zgomotul în subseturi foarte mici de date.

De asemenea, puteți impune un câștig minim de informație (min_information_gain), astfel încât algoritmul să efectueze o divizare doar dacă produce o îmbunătățire semnificativă în reducerea impurităților. Acest lucru evită crearea de ramificații inutile care modifică abia predicțiile și doar complică structura arborescentă.

Construirea unui arbore decizional de la zero în cod

Implementarea unui arbore decizional de la zero se învârte de obicei în jurul unui set mic de funcții de bază care sunt apelate recursiv. În timp ce biblioteci precum scikit-learn sau rpart fac toate acestea în secret, programarea acestor pași pe cont propriu face logica mult mai clară (logica de programare) și vă oferă control deplin asupra comportamentului.

În primul rând, aveți nevoie de o rutină care, având în vedere datele actuale de la un nod, evaluează fiecare caracteristică și fiecare divizare candidată pentru a o găsi pe cea cu cel mai mare câștig de informație. Această funcție returnează caracteristica aleasă, regula de divizare (pragul sau subsetul de categorii), valoarea amplificării și masca booleană sau seturile de index care identifică ce eșantioane merg la stânga și care merg la dreapta.

În al doilea rând, aveți nevoie de o funcție de predicție pentru nodurile frunză care să convertească setul de valori țintă din acel nod într-o singură predicție. Pentru regresie, aceasta este de obicei media lui y în acel nod; pentru clasificare, se ia de obicei modul (clasa cea mai frecventă), eventual stocând și probabilitățile clasei dacă se doresc rezultate probabilistice.

În al treilea rând, creați o funcție de antrenament recursivă care verifică criteriile de oprire, caută cea mai bună divizare dacă este permisă și apoi construiește noduri copil apelându-se singură pe subseturile din stânga și din dreapta. Dacă nu sunt îndeplinite condițiile de dimensiune minimă a eșantionului, adâncimea maximă sau amplificare minimă, funcția oprește divizarea și stochează o predicție a frunzei în loc de ramificări suplimentare.

Cum funcționează predicția într-un arbore decizional antrenat

Odată ce arborele tău a fost antrenat și ai stocat toate regulile de divizare și predicțiile frunzelor, efectuarea unei predicții pentru o nouă observație este pur și simplu o chestiune de a parcurge arborele de la rădăcină la o frunză. La fiecare nod intern, inspectați caracteristica necesară și testați dacă observația îndeplinește condiția nodului.

Dacă regula de divizare este numerică, verificați dacă valoarea caracteristicii este mai mică sau egală cu pragul; dacă regula de divizare este categorială, verificați dacă categoria se află într-un anumit subset. În funcție de rezultat, urmați ramura corespunzătoare (de exemplu, „da” la stânga, „nu” la dreapta) și repetați acest proces la următorul nod.

Continui să cobori în arbore până ajungi la un nod fără copii, care este o frunză ce stochează o valoare constantă de ieșire sau o etichetă de clasă. Pentru un arbore de regresie, predicția va fi un număr precum o durată de viață estimată sau o eficiență a consumului de combustibil; pentru un arbore de clasificare, rezultatul va fi o categorie prezisă, cum ar fi „a supraviețuit” sau „nu a supraviețuit”.

Dacă testezi această abordare pe aceleași date pe care le-ai folosit pentru antrenament, vei observa adesea o precizie destul de mare pentru clasificare (de exemplu, în jur de 85% în unele exemple simple de obezitate sau în stilul Titanic), dar această performanță ar putea scădea pe date nevăzute dacă arborele tău este prea adânc. Tocmai de aceea este atât de important să controlezi adâncimea și dimensiunea copacilor și de ce au fost inventate ansambluri precum pădurile aleatorii pentru a stabiliza predicțiile privind copacii.

Lucrul cu arbori de regresie în practică

Arborii de regresie sunt deosebit de utili atunci când relația dintre predictori și răspuns este puternic neliniară și implică interacțiuni greu de modelat cu regresia liniară clasică. În loc să încerce să potrivească o singură ecuație globală, arborele împarte spațiul caracteristicilor în regiuni și potrivește un model constant simplu în fiecare regiune.

În R, pachete populare precum rpart și tree facilitează construirea arborilor de regresie cu un singur apel de funcție, specificând o formulă precum y ~ x1 + x2 + … + x11. Aceste pachete au fost influențate de metodologia CART originală descrisă de Breiman și colegii săi și implementează multe dintre ideile standard de divizare și tăiere în modelarea modernă bazată pe arbori.

De exemplu, puteți utiliza pachetul rpart pentru a modela un răspuns y bazat pe unsprezece covariabile x1 până la x11, curățați datele de valorile lipsă și apoi vizualizați arborele rezultat cu funcții auxiliare precum prp din pachetul rpart.plot. Nodurile terminale arată axei y prezise pentru fiecare regiune, pe care o puteți utiliza direct pentru observații noi.

Având în vedere un arbore de regresie antrenat, puteți introduce în funcția de predicție noi valori ale covariabilelor, cum ar fi x9 = 70, x2 = 100 sau x9 = 60, x2 = 150, pentru a obține valori estimate ŷ (de exemplu, în jur de 20 sau 28 într-un exemplu de consum de combustibil). Compararea acestor predicții cu valorile observate, de exemplu prin corelația dintre y și ŷ, vă oferă o idee rapidă despre cât de bine surprinde arborele modelul subiacent, chiar și atunci când setul de date este destul de mic.

De la copaci singulari la păduri aleatorii

Un singur arbore decizional este puternic, dar și notoriu de sensibil la particularitățile datelor de antrenament, ceea ce poate duce la o varianță ridicată (părtinire și varianță) și supraadaptare. Pentru a atenua acest lucru, pădurile aleatorii construiesc mulți arbori pe eșantioane de date bootstrapate și își agregă predicțiile, producând un model mai stabil și, de obicei, mai precis.

Într-o pădure aleatoare, fiecare arbore este antrenat pe un eșantion bootstrap, ceea ce înseamnă că un nou set de date de aceeași dimensiune este extras din setul original de antrenament cu înlocuire. Acest proces de eșantionare face ca fiecare arbore să vadă un set de date ușor diferit, astfel încât erorile lor sunt mai puțin corelate și se pot anula atunci când sunt agregate.

În plus, pădurile aleatorii introduc caracter aleatoriu în procesul de selecție a caracteristicilor, luând în considerare doar un subset aleatoriu de predictori la fiecare divizare, mai degrabă decât toți predictorii. Acest lucru reduce și mai mult corelația dintre copaci, sporește diversitatea din pădure și tinde să reducă varianța fără a crește prea mult prejudecățile.

Combinarea dintre bootstrapping și agregarea predicțiilor este cunoscută sub numele de bagging, iar în pădurile aleatorii se obține și o estimare internă a erorii modelului prin evaluarea fiecărui arbore pe baza punctelor de date care nu au fost incluse în eșantionul său bootstrap (așa-numitele observații out-of-bag). Această eroare out-of-bag oferă o modalitate convenabilă de a evalua performanța fără a fi nevoie de un set separat de validare.

Deși acest articol se concentrează pe construirea unui singur arbore de la zero, înțelegerea modului în care funcționează acea componentă de bază face mult mai ușoară înțelegerea modului în care ansambluri precum pădurile aleatorii, amplificarea gradienților și alte metode bazate pe arbori se bazează pe aceleași principii pentru a obține rezultate de ultimă generație în multe probleme aplicate.

Punând totul cap la cap, regresia arborelui decizional de la zero vă arată cum un set simplu de reguli, funcții de cost și divizări recursive pot modela relații complexe, indiferent dacă preziceți un rezultat binar, cum ar fi supraviețuirea, o etichetă categorială precum obezitatea sau o țintă numerică, cum ar fi speranța de viață sau consumul de combustibil, iar această înțelegere profundă devine o bază solidă pentru utilizarea în practică a unor tehnici mai avansate bazate pe arbori.