Beslutningstrær er en av de mest intuitive og mye brukte maskinlæring algoritmer for både klassifisering og regresjon. De jobber ved å dele data i grener basert på funksjonsverdier, etterligne måten mennesker tar beslutninger. Mens biblioteker som Scikit -lær å bygge beslutningstrær trivialt, implementere en fra ripe er en utmerket måte for nybegynnere å forstå algoritmens indre arbeid. Denne opplæringen vil veilede deg gjennom teorien og koden, så du kan bygge din egen beslutning tre fra bakken opp.

Hva er et beslutningstre?

Et beslutningstre er en flytskjema - som struktur der hver intern node representerer en test på en funksjon (f.eks. \"Er alder > 30?\"), hver gren representerer utfallet av den testen, og hver bladknute inneholder en klassemerke eller kontinuerlig verdi. Målet er å skape en modell som forutsier en målvariabel ved å lære enkle beslutningsregler som er utledet fra datafunksjonene. Beslutningstrær er populære fordi de er lette å tolke og krever lite dataforbedring (ingen skalering eller normalisering).

Treet er bygget rekursivt: starter fra roten, algoritmen velger den beste funksjonen og splittepunktet som skiller dataene mest rent. Denne prosessen gjentas på hver undergruppe til en stoppetilstand er oppfylt. For mer bakgrunn, Wikipedias ] entry på beslutningstre læring gir en solid oversikt.

Kjernebegreper du må forstå

Noder, grener og blader

Rotnoden inneholder hele treningsdatasettet. Interne noder tester en funksjon og deler dataene i to eller flere barnenoder. Brancher er forbindelsene som representerer utfallet av en test. Leaf noder (terminale noder) produserer den endelige forutsetningen - den vanligste klassen i klassifisering eller gjennomsnittlig verdi i regresjon.

Splittingskriterier

For å bygge et tre, trenger du en måte å måle kvaliteten på en potensiell split. De vanligste kriteriene er:

  • Gini urenhet ⁇ som brukes i klassifisering for å måle hvor ofte et tilfeldig valgt element ville være feilmerket hvis det var tilfeldig merket i henhold til fordelingen av klasser i undergruppen. Nedre Gini er bedre.
  • Entropy ⁇ måler mengden av forstyrrelse eller usikkerhet i et sett. Målet er å minimere entropi etter splittingen (informasjonsgevinst).
  • Variansreduksjon ⁇ brukt til regresjonstrær. Den beregner reduksjonen i varians (eller gjennomsnittlig sifferfeil) oppnådd ved spaltingen.

Algoritmen evaluerer alle mulige splittelser på hver funksjon og velger den som gir den største reduksjonen i urenhet (eller gevinst i informasjon).

Informasjonsgevinst og gevinstforhold

Informasjonsgevinst er forskjellen mellom urenhet av foreldreknuten og vektet summen av barn urenheter. Selv om det er enkelt, har det en tendens til å favorisere funksjoner med mange verdier. Gavinstforholdet (brukt i C4.5) normaliserer dette. For denne opplæringen vil vi holde fast med standard informasjonsgevinst ved hjelp av Gini urenhet, som er standard i CART (klassifikasjon og regression Trees).

Bygge et beslutningstre steg for trinn

1. Forbered dine data

Du trenger et datasett med funksjoner og målmerker. For enkelhet, bruk et binær klassifiseringsdatasett med numeriske funksjoner. For eksempel:

  • Features: Alder, inntekt
  • Target: Godkjent (1) eller ikke godkjent (0)

Rens dataene: håndtere manglende verdier, fjerne dupliserer og sikre numeriske typer. Beslutningstrær kan håndtere blandede datatyper, men vi vil holde oss til numeriske for implementeringen.

2. Definere en splittende kritikkfunksjon

Vi vil implementere Gini urenhet. Gini indeks for et sett med elementer er:

hvor p i er andelen elementer i klasse i. For en binær splitt er den totale Gini det vektede gjennomsnittet av barneknutene.

3. Implementere Split Evaluering

For hver funksjon, sorter de unike verdiene. Test alle mulige terskel (mellompunkt mellom påfølgende sorterte verdier). For hver kandidatgrense, dele dataene i venstre og høyre grupper, beregne Gini, og spore den beste splittelsen.

4. Bygg treet på nytt

Opprett en funksjon som tar en undergruppe av data og en strømdybde. Den kontrollerer stoppeforhold (f.eks. maksimal dybde nådd, minimum prøver per node eller ingen informasjonsgevinst). Hvis en tilstand er oppfylt, oppretter du en bladknute med majoritetsklassen. Ellers finner du den beste splittelsen og opprette en intern node, så ring funksjonen til venstre og høyre splits.

5. Gjør forutsigelser

Når treet er bygget, er prediksjon enkel: start ved roten, følg greinene ved å evaluere funksjonen tester på den nye prøven, og returnere verdien av bladet du lander på.

Full implementering i Python

Nedenfor er en fullstendig, minimal implementering av et beslutningstre for klassifisering ved bruk av Gini urenhet. Denne koden er ment for læring - det er ikke optimalisert for store datasett.

import numpy as np
from collections import Counter

class DecisionTree:
 def __init__(self, max_depth=None, min_samples_split=2):
 self.max_depth = max_depth
 self.min_samples_split = min_samples_split
 self.tree = None

 def fit(self, X, y):
 dataset = np.column_stack((X, y))
 self.tree = self._grow_tree(dataset)

 def _grow_tree(self, dataset, depth=0):
 X, y = dataset[:, :-1], dataset[:, -1]
 n_samples, n_features = X.shape
 n_labels = len(np.unique(y))

 # Stopping conditions
 if (n_labels == 1 or depth == self.max_depth or n_samples < self.min_samples_split):
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 best_feature, best_threshold = self._best_split(dataset, n_features)
 if best_feature is None:
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 left_idx, right_idx = self._split(dataset[:, best_feature], best_threshold)
 left_subtree = self._grow_tree(dataset[left_idx], depth+1)
 right_subtree = self._grow_tree(dataset[right_idx], depth+1)
 return {'leaf': False,
 'feature': best_feature,
 'threshold': best_threshold,
 'left': left_subtree,
 'right': right_subtree}

 def _best_split(self, dataset, n_features):
 best_gini = float('inf')
 best_feature, best_threshold = None, None
 for feature in range(n_features):
 thresholds = np.unique(dataset[:, feature])
 for i in range(len(thresholds)-1):
 thresh = (thresholds[i] + thresholds[i+1]) / 2
 left_idx, right_idx = self._split(dataset[:, feature], thresh)
 if len(left_idx) == 0 or len(right_idx) == 0:
 continue
 gini = self._gini_gain(dataset, left_idx, right_idx)
 if gini < best_gini:
 best_gini = gini
 best_feature = feature
 best_threshold = thresh
 return best_feature, best_threshold

 def _split(self, values, threshold):
 left_idx = np.where(values <= threshold)[0]
 right_idx = np.where(values > threshold)[0]
 return left_idx, right_idx

 def _gini_gain(self, dataset, left_idx, right_idx):
 total = len(left_idx) + len(right_idx)
 gini_left = self._gini(dataset[left_idx, -1])
 gini_right = self._gini(dataset[right_idx, -1])
 return (len(left_idx)/total) * gini_left + (len(right_idx)/total) * gini_right

 def _gini(self, labels):
 _, counts = np.unique(labels, return_counts=True)
 p = counts / np.sum(counts)
 return 1 - np.sum(p**2)

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

 def _predict_row(self, x, node):
 if node['leaf']:
 return node['value']
 if x[node['feature']] <= node['threshold']:
 return self._predict_row(x, node['left'])
 else:
 return self._predict_row(x, node['right'])

Testing av treet

Bruk et enkelt datasett som det klassiske iris datasettet (to funksjoner for binær klassifisering). ]scikit-learn Iris datasett fungerer bra. Sammenlign treets nøyaktighet med Scikit-learns for å verifisere riktigheten.

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

data = load_iris()
X = data.data[:100] # take only first two classes (binary)
y = data.target[:100]

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

tree = DecisionTree(max_depth=3)
tree.fit(X_train, y_train)
preds = tree.predict(X_test)
accuracy = np.mean(preds == y_test)
print(f'Accuracy: {accuracy:.2f}')

Avanserte teknikker for å forbedre treet ditt

Forsøk på å unngå overfitting

Et fullt dyrket tre kan minne om støy i treningsdataene. Prunning fjerner grener som har lite prediktiv kraft. Vanlige metoder er pre-prunking (stopper vekst tidlig via eller ]) og post-prunking (vokser full treet og fjerner deretter grener ved hjelp av et valideringssett eller kostnads-kompleksitetsberegning). Vår implementering støtter allerede pre-prunking.

Håndtering av kontinuerlige og kategoriserte funksjoner

For kontinuerlige funksjoner brukte vi midtpunkt mellom sorterte verdier som terskelverdier. For kategoriske funksjoner (f.eks. «Color = rød/grønn/blå») kan hver kategori bli en egen gren (fleirtyding) eller du kan binær-kode dem. De fleste moderne implementasjoner (som scikit-learn) bruker binære splitter selv for kategoriske funksjoner ved å evaluere alle undergrupper.

⁇ Å håndtere manglende verdier

Real-world data ofte har manglende verdier. En enkel tilnærming er å tildele manglende verdier til den mest vanlige grenen blant treningsprøver som har funksjonen. C4.5 bruker en probabilistisk metode. Siden dette er en nybegynner tutorial, antar vi at dataene er komplette.

Sammenligning med biblioteker og videre lesing

Mens bygning fra ripe er utdanning, bruk produksjonssystemer biblioteker som scikit-learn som gir optimale C-implementasjoner. Du kan lære mer av den offisielle ] scikit-learn beslutningstre dokumentasjon. For dypere teori, boken \"The Elements of Statistical Learning\" av Hastie, Tibshirani, og Friedman er en autoritativ ressurs. En annen utmerket referanse er den originale CART-boken av Breiman et al.

Konklusjon

Bygge et beslutningstre fra ripe demotifiserer en av de mest grunnleggende algoritmene i maskinlæring. Du har lært hvordan en enkel rekursiv splitting kan produsere en kraftig modell. Ved å skrive koden selv, får du en dypere forståelse av urenhetstiltak, splittet utvalg og handel-avbrudd mellom fordommer og varians. Som et neste steg, prøv å legge til regresjonsstøtte, beslaglegg eller håndtering kategoriske funksjoner. Ferdighetene du utvikler her vil tjene deg godt i tillegg til at du går videre til mer komplekse ensemble metoder som tilfeldige skoger og gradientforsterkning.