Arbori de decizie și păduri aleatoare

Un arbore de decizie este doar o schemă logică. Însă o pădure de astfel de arbori este unul dintre cele mai puternice instrumente din învățarea automată.

Tip: Construire Limbaj: Python Cerințe preliminare: Faza 1 (lecțiile 09 — Teoria informației și 06 — Probabilități) Durată: ~90 de minute

Obiective de învățare

• Implementarea calculelor pentru impuritatea Gini, entropie și câștig informațional, în vederea găsirii separărilor optime ale unui arbore de decizie
• Construirea de la zero a unui clasificator de tip arbore de decizie, cu mecanisme de pre-tăiere (adâncime maximă, număr minim de eșantioane)
• Construirea unei păduri aleatoare folosind eșantionare bootstrap și selecția aleatoare a caracteristicilor, precum și explicarea motivului pentru care aceasta reduce varianța
• Compararea importanței caracteristicilor prin MDI cu importanța prin permutare și identificarea situațiilor în care MDI este părtinitoare

Problema

Aveți date tabelare. Rândurile sunt eșantioane, coloanele sunt caracteristici, iar una dintre coloane este ținta pe care doriți să o preziceți. Ați putea folosi o rețea neuronală. Însă, pentru datele tabelare, modelele bazate pe arbori — arborii de decizie, pădurile aleatoare și arborii amplificați prin gradient — depășesc adesea învățarea profundă. În competițiile Kaggle cu date structurate sunt frecvent întâlnite XGBoost și LightGBM, nu transformerele.

De ce? Arborii pot modela relații neliniare fără ingineria manuală a caracteristicilor. În funcție de implementare, ei pot lucra cu caracteristici numerice și categoriale direct sau după o codificare adecvată. Un arbore suficient de mic este interpretabil: îi puteți urmări ramurile pentru a vedea cum s-a ajuns la o predicție. Iar pădurile aleatoare, care agregă mai mulți arbori, sunt de regulă mai rezistente la supraînvățare decât un singur arbore pe seturi de date de dimensiune moderată.

Această lecție construiește arbori de decizie de la zero prin separare recursivă, apoi construiește deasupra lor o pădure aleatoare. Veți implementa matematica din spatele criteriilor de separare — impuritatea Gini, entropia și câștigul informațional — și veți înțelege cum un ansamblu de modele individuale instabile poate deveni un predictor robust.

Notă tehnică a traducerii: superioritatea arborilor față de rețelele neuronale pe date tabelare nu este universală, ci depinde de setul de date, bugetul de reglare și implementare. În plus, estimatorii pe arbori din scikit-learn nu acceptă nativ variabile categoriale și necesită codificarea lor; unele biblioteci specializate, precum CatBoost, au suport dedicat. Un singur arbore mic poate fi urmărit integral, dar o pădure cu sute de arbori nu oferă aceeași transparență. A se vedea comparația experimentală Grinsztajn et al. și FAQ-ul scikit-learn despre caracteristicile categoriale.

Conceptul

Ce face un arbore de decizie

Un arbore de decizie împarte spațiul caracteristicilor în regiuni dreptunghiulare adresând o succesiune de întrebări cu răspuns „da” sau „nu”.

Fiecare nod intern compară o caracteristică cu un prag. Fiecare nod-frunză produce o predicție. Pentru a clasifica un punct de date nou, porniți de la rădăcină și urmați ramurile până când ajungeți la o frunză.

Arborele este construit de sus în jos, alegând la fiecare nod caracteristica și pragul care separă cel mai bine datele. Cuvântul „cel mai bine” este definit printr-un criteriu de separare.

Criterii de separare: măsurarea impurității

La fiecare nod avem un set de eșantioane. Dorim să îl separăm astfel încât nodurile-copil rezultate să fie cât mai „pure”, adică fiecare copil să conțină în principal o singură clasă.

Impuritatea Gini măsoară probabilitatea ca un eșantion ales aleatoriu să fie clasificat greșit dacă i s-ar atribui o etichetă conform distribuției claselor din nodul respectiv.

Gini(S) = 1 - sum(p_k^2)

unde p_k este proporția clasei k în mulțimea S.

Pentru un nod pur, în care toate eșantioanele aparțin aceleiași clase, Gini = 0. Pentru o împărțire binară cu proporții 50/50, Gini = 0,5. O valoare mai mică este mai bună.

Exemplu: 6 pisici, 4 câini

Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48

Entropia măsoară conținutul informațional, adică dezordinea, dintr-un nod. Conceptul a fost tratat în lecția 09 din Faza 1.

Entropy(S) = -sum(p_k * log2(p_k))

Pentru un nod pur, entropia = 0. Pentru o împărțire binară 50/50, entropia = 1,0. O valoare mai mică este mai bună.

Exemplu: 6 pisici, 4 câini

Entropy = -(0.6 * log2(0.6) + 0.4 * log2(0.4))
        = -(0.6 * -0.737 + 0.4 * -1.322)
        = 0.442 + 0.529
        = 0.971 biți

Câștigul informațional este reducerea impurității — entropie sau Gini — după o separare.

IG(S, caracteristică, prag) = Impuritate(S) - media_ponderată(Impuritate(S_stânga), Impuritate(S_dreapta))

unde ponderile sunt proporțiile eșantioanelor din fiecare nod-copil.

Algoritmul greedy aplicat la fiecare nod încearcă fiecare caracteristică și fiecare prag posibil. Apoi alege perechea (caracteristică, prag) care maximizează câștigul informațional.

Cum funcționează separarea

Pentru un set de date cu n caracteristici și m eșantioane în nodul curent:

1. Pentru fiecare caracteristică j (j = 1 până la n):
   • sortați eșantioanele după caracteristica j;
   • încercați ca prag fiecare punct de mijloc dintre două valori distincte consecutive;
   • calculați câștigul informațional pentru fiecare prag.
2. Selectați caracteristica și pragul cu cel mai mare câștig informațional.
3. Împărțiți datele în stânga (caracteristică <= prag) și dreapta (caracteristică > prag).
4. Repetați recursiv procesul pentru fiecare copil.

Această abordare greedy nu garantează arborele optim la nivel global. Găsirea arborelui optim este o problemă NP-dificilă. Totuși, separarea greedy funcționează bine în practică.

Condiții de oprire

Fără condiții de oprire, arborele încearcă să crească până când frunzele nu mai pot fi separate util, iar multe dintre ele pot deveni pure. Aceasta poate memora datele de antrenare și poate generaliza foarte slab.

Pre-tăierea oprește arborele înainte ca acesta să crească integral:

• Adâncime maximă: opriți separarea când arborele ajunge la o adâncime stabilită.
• Număr minim de eșantioane pentru separare: nu mai separați un nod dacă are mai puțin de k eșantioane.
• Număr minim de eșantioane într-o frunză: acceptați numai separările în urma cărora fiecare copil are cel puțin k eșantioane.
• Câștig informațional minim: opriți-vă dacă cea mai bună separare îmbunătățește impuritatea cu mai puțin decât un anumit prag.
• Număr maxim de noduri-frunză: limitați numărul total de frunze.

Post-tăierea crește arborele complet, apoi îl simplifică:

• Tăierea cost-complexitate, folosită de scikit-learn, adaugă o penalizare proporțională cu numărul de frunze. Măriți penalizarea pentru a obține arbori mai mici.
• Tăierea pe baza erorii reduse elimină un subarbore dacă eroarea de validare nu crește.

Pre-tăierea este mai simplă și mai rapidă. Post-tăierea produce adesea arbori mai buni, deoarece nu oprește prematur separări care ar putea conduce ulterior la separări utile.

Notă tehnică a traducerii: o frunză pură nu conține neapărat un singur eșantion; poate conține mai multe eșantioane din aceeași clasă. De asemenea, valori identice ale caracteristicilor cu etichete contradictorii pot împiedica obținerea purității perfecte. Parametrii min_samples_split și min_samples_leaf au roluri distincte: primul limitează separarea nodului, iar al doilea impune dimensiunea minimă a fiecărui copil rezultat.

Arbori de decizie pentru regresie

În regresie, predicția unei frunze este media valorilor-țintă din acea frunză. Se modifică și criteriul de separare.

Reducerea varianței înlocuiește câștigul informațional:

VR(S, caracteristică, prag) = Var(S) - media_ponderată(Var(S_stânga), Var(S_dreapta))

Alegeți separarea care reduce cel mai mult varianța. Arborele împarte spațiul de intrare în regiuni și prezice în fiecare regiune o constantă, adică media.

Pădurile aleatoare: puterea ansamblurilor

Un singur arbore de decizie are varianță ridicată. Schimbări mici în date pot produce arbori complet diferiți. Pădurile aleatoare remediază această instabilitate prin agregarea mai multor arbori.

Două surse de aleatoriu fac arborii mai diverși:

Bagging (agregare bootstrap): fiecare arbore este antrenat pe un eșantion bootstrap, adică un eșantion aleatoriu cu înlocuire extras din datele de antrenare. Aproximativ 63% dintre eșantioanele originale apar cel puțin o dată în fiecare eșantion bootstrap; restul sunt eșantioane din afara sacului, numite out-of-bag, care pot fi folosite pentru validare.

Selecția aleatoare a caracteristicilor: la fiecare separare este luată în considerare numai o submulțime aleatoare de caracteristici. Pentru clasificare, o alegere implicită uzuală este sqrt(n_features). Pentru regresie, valoarea implicită depinde de implementare. Astfel se împiedică separarea tuturor arborilor pe aceeași caracteristică dominantă.

Notă tehnică a traducerii: regula istorică n_features/3 pentru regresie nu este valoarea implicită actuală din RandomForestRegressor al scikit-learn; documentația curentă folosește max_features=1.0, adică toate caracteristicile. Pentru clasificare, valoarea implicită este "sqrt". Consultați documentația scikit-learn pentru ansambluri și RandomForestClassifier.

Ideea esențială este că agregarea mai multor arbori slab corelați reduce varianța ansamblului. Fiecare arbore poate fi un predictor mediocru, dar ansamblul poate fi robust.

Notă tehnică a traducerii: dacă arborii individuali au aceeași distribuție, simpla lor mediere nu modifică valoarea așteptată și, implicit, păstrează componenta de părtinire a acelui predictor. Totuși, bootstrap-ul, limitarea aleatoare a caracteristicilor și alte constrângeri pot schimba și părtinirea arborilor individuali. Prin urmare, formularea „reduce varianța fără să crească părtinirea” este o intuiție utilă, nu o garanție absolută pentru orice configurație.

Importanța caracteristicilor

Pădurile aleatoare furnizează în mod natural scoruri de importanță a caracteristicilor. Cea mai răspândită metodă este:

Scăderea medie a impurității (MDI): pentru fiecare caracteristică, însumați reducerea totală a impurității din toți arborii și toate nodurile în care este folosită caracteristica respectivă. Caracteristicile care produc reduceri mai mari ale impurității în separările timpurii sunt considerate mai importante.

importanță(caracteristica_j) = suma peste toate nodurile în care este folosită caracteristica_j:
    (nr_eșantioane_în_nod / nr_total_eșantioane) * scăderea_impurității

Metoda este rapidă, deoarece scorul este calculat în timpul antrenării, dar este părtinitoare în favoarea caracteristicilor cu cardinalitate ridicată și a celor care permit multe puncte de separare.

Importanța prin permutare este alternativa: amestecați aleatoriu valorile unei caracteristici și măsurați cât scade scorul modelului. Metoda este adesea mai informativă, dar mai lentă.

Notă tehnică a traducerii: importanța prin permutare ar trebui evaluată de preferință pe date de validare sau test, după ce s-a confirmat că modelul are putere predictivă. Nici ea nu este infailibilă: dacă mai multe caracteristici sunt puternic corelate, permutarea uneia singure poate sugera o importanță mică deoarece celelalte păstrează aceeași informație. Consultați ghidul scikit-learn despre importanța prin permutare.

Când arborii depășesc rețelele neuronale

Arborii și pădurile sunt adesea foarte competitivi pe date tabelare. Iată câteva motive frecvente:

Factor	Arbori	Rețele neuronale
Tipuri mixte (numerice + categoriale)	Unele implementări oferă suport nativ; altele necesită codificare	Necesită de regulă codificare sau reprezentări învățate
Seturi de date mici (< 10.000 de rânduri)	Funcționează adesea bine	Pot supraînvăța fără regularizare atentă
Interacțiuni între caracteristici	Sunt descoperite prin separări	Sunt învățate prin arhitectură și optimizare
Interpretabilitate	Ridicată pentru un arbore mic; mai redusă pentru ansambluri	De regulă necesită metode explicative
Timp de antrenare	Adesea minute	Poate varia de la minute la ore
Sensibilitate la hiperparametri	De regulă moderată	Poate fi ridicată

Rețelele neuronale excelează atunci când datele au structură spațială sau secvențială, precum imaginile, textul și semnalul audio. Pentru tabele cu caracteristici eterogene, modelele bazate pe arbori reprezintă un punct de plecare foarte bun, dar alegerea finală trebuie făcută prin validare pe problema concretă.

decision-tree-depth

Construiți

Pasul 1: impuritatea Gini și entropia

Construiți de la zero ambele criterii de separare și verificați că acestea sunt de acord asupra separărilor bune.

import math

def gini_impurity(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return 1.0 - sum((c / n) ** 2 for c in counts.values())

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum(
        (c / n) * math.log2(c / n) for c in counts.values() if c > 0
    )

Pasul 2: găsiți cea mai bună separare

Încercați fiecare caracteristică și fiecare prag. Returnați perechea care produce cel mai mare câștig informațional.

def information_gain(parent_labels, left_labels, right_labels, criterion="gini"):
    measure = gini_impurity if criterion == "gini" else entropy
    n = len(parent_labels)
    n_left = len(left_labels)
    n_right = len(right_labels)
    if n_left == 0 or n_right == 0:
        return 0.0
    parent_impurity = measure(parent_labels)
    child_impurity = (
        (n_left / n) * measure(left_labels) +
        (n_right / n) * measure(right_labels)
    )
    return parent_impurity - child_impurity

Pasul 3: construiți clasa DecisionTree

Separare recursivă, predicție și urmărirea importanței caracteristicilor.

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1, criterion="gini",
                 max_features=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.criterion = criterion
        self.max_features = max_features
        self.tree = None
        self.feature_importances_ = None

    def fit(self, X, y):
        self.n_features = len(X[0])
        self.feature_importances_ = [0.0] * self.n_features
        self.n_samples = len(X)
        self.tree = self._build(X, y, depth=0)
        total = sum(self.feature_importances_)
        if total > 0:
            self.feature_importances_ = [
                fi / total for fi in self.feature_importances_
            ]

    def predict(self, X):
        return [self._predict_one(x, self.tree) for x in X]

Pasul 4: construiți clasa RandomForest

Eșantionare bootstrap, selecție aleatoare a caracteristicilor și vot majoritar.

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None,
                 min_samples_split=2, max_features="sqrt",
                 criterion="gini"):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.criterion = criterion
        self.trees = []

    def fit(self, X, y):
        n = len(X)
        for _ in range(self.n_trees):
            indices = [random.randint(0, n - 1) for _ in range(n)]
            X_boot = [X[i] for i in indices]
            y_boot = [y[i] for i in indices]
            tree = DecisionTree(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                max_features=self.max_features,
                criterion=self.criterion,
            )
            tree.fit(X_boot, y_boot)
            self.trees.append(tree)

    def predict(self, X):
        all_preds = [tree.predict(X) for tree in self.trees]
        predictions = []
        for i in range(len(X)):
            votes = {}
            for preds in all_preds:
                v = preds[i]
                votes[v] = votes.get(v, 0) + 1
            predictions.append(max(votes, key=votes.get))
        return predictions

Consultați code/trees.py pentru implementarea completă, care include toate metodele auxiliare.

Notă tehnică a traducerii: fragmentele de mai sus sunt didactice, nu o implementare autonomă completă. Clasa DecisionTree apelează metodele _build și _predict_one, care nu sunt definite în fragment, iar RandomForest folosește modulul random fără instrucțiunea import random. În plus, apelurile repetate ale metodei RandomForest.fit adaugă arbori la lista existentă în loc să o reinițializeze. Pentru rulare este necesară completarea codului indicată de materialul-sursă.

Folosiți

Cu scikit-learn, antrenarea unei păduri aleatoare necesită trei linii:

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
print(f"Accuracy: {rf.score(X_test, y_test):.4f}")
print(f"Feature importances: {rf.feature_importances_}")

În practică, arborii amplificați prin gradient — XGBoost, LightGBM și CatBoost — sunt adesea mai puternici decât pădurile aleatoare, deoarece construiesc arborii secvențial, fiecare arbore corectând erorile celor anteriori. Pădurile aleatoare sunt însă mai greu de configurat într-un mod complet nepotrivit și necesită adesea mai puțină reglare a hiperparametrilor.

Livrați

Această lecție produce outputs/prompt-tree-interpreter.md — un prompt care interpretează separările unui arbore de decizie pentru părțile interesate din mediul de afaceri. Furnizați-i structura unui arbore antrenat — adâncime, caracteristici, praguri de separare și acuratețe — iar acesta traduce modelul în reguli exprimate în limbaj obișnuit, ordonează importanța caracteristicilor, semnalează supraînvățarea sau scurgerea de informații și recomandă pașii următori. Folosiți-l ori de câte ori trebuie să explicați un model bazat pe arbori unei persoane care nu citește cod.

Exerciții

1. Antrenați un singur arbore de decizie pe un set de date bidimensional cu 3 clase. Urmăriți manual separările și desenați frontierele de decizie dreptunghiulare. Comparați frontierele pentru max_depth=2 și max_depth=10.

2. Implementați separarea prin reducerea varianței pentru arbori de regresie. Generați y = sin(x) + zgomot pentru 200 de puncte și ajustați arborele dumneavoastră de regresie. Reprezentați grafic predicțiile constante pe porțiuni ale arborelui și curba reală.

3. Construiți o pădure aleatoare cu 1, 5, 10, 50 și 200 de arbori. Reprezentați grafic acuratețea pe datele de antrenare și pe cele de test în funcție de numărul de arbori. Observați tendința de stabilizare a acurateței de test pe măsură ce ansamblul crește.

Notă tehnică a traducerii: rezultatul de convergență pentru pădurile aleatoare arată că eroarea de generalizare a ansamblului tinde către o limită când numărul de arbori crește; nu garantează că acuratețea măsurată pe un set finit de test crește monoton la fiecare dimensiune a pădurii. Valorile observate pot fluctua. Consultați lucrarea originală Breiman, „Random Forests” (2001).

4. Comparați impuritatea Gini și entropia drept criterii de separare pe 5 seturi de date diferite. Măsurați acuratețea și adâncimea arborelui. În majoritatea cazurilor, ele produc rezultate aproape identice. Explicați de ce.

5. Implementați importanța prin permutare. Comparați-o cu importanța MDI pe un set de date în care o caracteristică este zgomot aleatoriu, dar are cardinalitate ridicată. Verificați experimental dacă MDI acordă caracteristicii de zgomot o importanță artificial de mare și dacă importanța prin permutare evită acest efect.

Notă tehnică a traducerii: părtinirea MDI face ca acest rezultat să fie probabil în anumite construcții, nu garantat în orice eșantion aleatoriu. Importanța prin permutare poate fi și ea înșelătoare în prezența caracteristicilor corelate și ar trebui calculată pe date nefolosite la ajustarea modelului.

Termeni-cheie

Termen	Cum i se spune	Ce înseamnă de fapt
Arbore de decizie	„O schemă logică pentru predicții”	Un model care împarte spațiul caracteristicilor în regiuni dreptunghiulare învățând o succesiune de separări if/else
Impuritate Gini	„Cât de amestecat este nodul”	Probabilitatea clasificării greșite a unui eșantion aleatoriu într-un nod. 0 = pur, 0,5 = impuritate maximă în cazul binar
Entropie	„Dezordinea dintr-un nod”	Conținutul informațional al unui nod. 0 = pur, 1,0 = incertitudine maximă în cazul binar. Provine din teoria informației
Câștig informațional	„Cât de bună este o separare”	Reducerea impurității după o separare. Criteriul greedy pentru alegerea separărilor
Pre-tăiere	„Oprirea timpurie a arborelui”	Oprirea timpurie a creșterii arborelui prin stabilirea adâncimii maxime ori a pragurilor pentru numărul minim de eșantioane sau câștigul minim
Post-tăiere	„Scurtarea ulterioară a arborelui”	Creșterea arborelui complet, urmată de eliminarea subarborilor care nu îmbunătățesc performanța de validare
Bagging	„Antrenare pe submulțimi aleatoare”	Agregare bootstrap. Fiecare model este antrenat pe alt eșantion aleatoriu cu înlocuire
Pădure aleatoare	„O mulțime de arbori”	Un ansamblu de arbori de decizie, fiecare antrenat pe un eșantion bootstrap și cu submulțimi aleatoare de caracteristici la fiecare separare
Importanța caracteristicilor (MDI)	„Care caracteristici contează”	Reducerea totală a impurității datorată fiecărei caracteristici, însumată peste toți arborii și toate nodurile
Importanță prin permutare	„Amestecați și verificați”	Scăderea scorului când valorile unei caracteristici sunt amestecate aleatoriu. Evită unele părtiniri ale MDI, dar are propriile limitări
Reducerea varianței	„Versiunea pentru regresie a câștigului informațional”	Analogul câștigului informațional pentru arborii de regresie. Alege separarea care reduce cel mai mult varianța țintei
Eșantion bootstrap	„Eșantion aleatoriu cu repetări”	Un eșantion aleatoriu extras cu înlocuire din setul de date original. Are aceeași dimensiune, dar conține duplicate

Lecturi suplimentare

• Breiman: Random Forests (2001) — lucrarea originală despre pădurile aleatoare
• Grinsztajn et al.: Why do tree-based models still outperform deep learning on tabular data? (2022) — comparație riguroasă între arbori și rețele neuronale pentru sarcini pe date tabelare
• Documentația scikit-learn despre arborii de decizie — ghid practic cu instrumente de vizualizare
• XGBoost: A Scalable Tree Boosting System (Chen & Guestrin, 2016) — lucrarea despre amplificarea prin gradient care a popularizat XGBoost în competițiile Kaggle

---

Sursă: Decision Trees and Random Forests — original

Navigare: înapoi: 02.03 — Regresie logistică · Faza 2 — Bazele învățării automate · Catalog complet · în continuare: 02.05 — Mașini cu vectori suport.