Beslissingsbomen zijn een van de meest intuïtieve en veelgebruikte machine learning algoritmen voor zowel classificatie als regressie. Ze werken door gegevens te splitsen in branches op basis van functiewaarden, het nabootsen van de manier waarop mensen beslissingen nemen. Terwijl bibliotheken zoals scikit-leer maken bouwbeslissing bomen triviaal, het implementeren van een van nul is een uitstekende manier voor beginners om het algoritme te begrijpen . Deze tutorial zal u leiden door de theorie en code, zodat u uw eigen beslissing boom van de grond omhoog te bouwen.

Wat is een Beslissingsboom?

Een beslissingsboom is een flowchart-achtige structuur waarbij elke interne knoop een test op een functie vertegenwoordigt (bijv., . .Is leeftijd > 30?), elke tak vertegenwoordigt het resultaat van die test, en elke bladknoop heeft een klasse label of continue waarde. Het doel is om een model te creëren dat een doel variabele voorspelt door het leren van eenvoudige beslissingsregels afgeleid uit de gegevensfuncties. Beslissingsbomen zijn populair omdat ze gemakkelijk te interpreteren en weinig gegevens voorverwerking vereisen (geen schaalvergroting of normalisatie).

De boom wordt recursief gebouwd: vanaf de root selecteert het algoritme de beste functie en split point die de gegevens het meest proper scheidt. Dit proces wordt herhaald op elke subset totdat een stoppende voorwaarde is voldaan. Voor meer achtergrond biedt Wikipedias entry on decision tree learning een solide overzicht.

Kernbegrippen die je moet begrijpen

Knodes, takken en bladeren

De root knooppunt bevat de gehele training dataset. Interne knooppunten testen een functie en splitsen de gegevens in twee of meer kind knooppunten. Takken zijn de verbindingen die het resultaat van een test vertegenwoordigen. Bladknooppunten (terminal nodes) geven de uiteindelijke voorspelling . . de meest voorkomende klasse in classificatie of de gemiddelde waarde in regressie.

Splitsingscriteria

Om een boom te bouwen, heb je een manier nodig om de kwaliteit van een potentiële splitsing te meten. De meest voorkomende criteria zijn:

  • Gini onzuiver
  • Entropie
  • Variantiereductie

Het algoritme evalueert elke mogelijke splitsing op elke functie en kiest degene die de grootste vermindering van onzuiverheid (of winst in informatie) oplevert.

Informatie Gain and Gain Ratio

Informatiewinst is het verschil tussen de onzuiverheid van de ouderknoop en de gewogen som van kinder onzuiverheden. Hoewel het eenvoudig is, is het de neiging om functies met veel waarden te bevorderen. De winstverhouding (gebruikt in C4.5) normaliseert dit. Voor deze tutorial zullen we vasthouden aan standaard informatiewinst met behulp van Gini onzuiverheid, wat de standaard is in CART (Classification and Regression Trees).

Een beslissingsboom bouwen Stap voor stap

1. Bereid uw gegevens voor

U heeft een dataset nodig met functies en doellabels. Voor eenvoud kunt u een binaire classificatiedataset gebruiken met numerieke functies. Bijvoorbeeld:

  • Kenmerken: Leeftijd, inkomen
  • Target: Goedgekeurd (1) of niet goedgekeurd (0)

Reinig de gegevens: omgaan met ontbrekende waarden, verwijder duplicaten, en zorg voor numerieke types. Beslissing bomen kunnen omgaan met gemengde gegevens types, maar we zullen vasthouden aan numeriek voor de implementatie.

2. Definieer een splitsende criteriumfunctie

We zullen Gini onzuiverheid implementeren. De Gini index voor een set items is:

waarbij p i het aandeel van de items in klasse i is. Voor een binaire splitsing is de totale Gini het gewogen gemiddelde van de kindknooppunten.

3. De gesplitste evaluatie uitvoeren

Voor elke functie sorteert u de unieke waarden. Test elke mogelijke drempel (tussen opeenvolgende gesorteerde waarden). Voor elke kandidaatdrempel, splitst u de gegevens in links en rechts groepen, berekent u de Gini en volgt u de beste verdeling.

4. Bouw de boom recursief

Maak een functie aan die een deelverzameling van gegevens en een huidige diepte nodig heeft. Het controleert de stopcondities (bijv. maximale diepte bereikt, minimum monsters per knoop, of geen informatiewinst). Als een voorwaarde wordt vervuld, maak een bladknooppunt met de meerderheidsklasse. Anders, vind de beste splitsing en maak een interne knoop, dan recursief de functie aan de linker- en rechterkant splits.

5. Voorspellingen maken

Zodra de boom is gebouwd, is de voorspelling eenvoudig: begin bij de wortel, volg de takken door de functietesten op het nieuwe monster te evalueren en geef de waarde van het blad waarop je landt terug.

Volledige implementatie in Python

Hieronder vindt u een volledige, minimale implementatie van een beslissingsboom voor classificatie met behulp van Gini onzuiverheid. Deze code is bedoeld voor het leren .. het is niet geoptimaliseerd voor grote datasets.

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'])

Testen van de boom

Gebruik een eenvoudige dataset zoals de klassieke irisset (twee functies voor binaire classificatie). De scikit-leer Iris-set werkt goed. Vergelijk uw nauwkeurigheid van de boom met scikit-learn

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}')

Geavanceerde technieken om uw boom te verbeteren

Overbouwen voorkomen

Een volgroeide boom kan geluid in de trainingsgegevens onthouden. Snoeien verwijdert takken die weinig voorspellende kracht hebben. Gemeenschappelijke methoden zijn aan het voor-prenen (het stoppen van groei vroeg via of ) en na-prunnen (het kweken van de volledige boom vervolgens verwijderen van takken met behulp van een validatie-set of kosten-complexiteit snoeien). Onze implementatie ondersteunt reeds pre-prunnen.

Handling Continue en categorische functies

Voor continue functies gebruikten we tussen gesorteerde waarden als drempels. Voor categorische kenmerken (bijv. .Color = rood/groen/blauwe

Omgaan met ontbrekende waarden

Real-world gegevens ontbreken vaak waarden. Een eenvoudige aanpak is om ontbrekende waarden toe te wijzen aan de meest voorkomende tak van training monsters die de functie hebben. C4.5 maakt gebruik van een probabilistische methode. Aangezien dit een beginner tutorial is, gaan we ervan uit dat de gegevens zijn voltooid.

Vergelijken met bibliotheken en verder lezen

Terwijl bouwen vanaf nul educatief is, maken productiesystemen gebruik van bibliotheken zoals scikit-leer die geoptimaliseerde C-implementaties bieden. U kunt meer leren van de officiële scikit-leer beslissingsbomen documentatie. Voor diepere theorie, het boek .De Elementen van Statistisch Leren . door Hasty, Tibshirani en Friedman is een gezaghebbende bron. Een andere uitstekende referentie is het originele CART boek van Breiman et al.

Conclusie

Het bouwen van een beslissingsboom vanaf nul demystiseert een van de meest fundamentele algoritmen in machine learning. Je hebt geleerd hoe een eenvoudige recursieve splitsingsprocedure een krachtig model kan produceren. Door zelf de code te schrijven, krijg je een dieper begrip van onzuiverheidsmaatregelen, split selectie en de afwegingen tussen vooroordeel en variantie. Als volgende stap, probeer regressieondersteuning toe te voegen, snoeien of om categorische kenmerken te hanteren. De vaardigheden die je hier ontwikkelt zullen je goed dienen als je verder gaat met complexe ensemble methoden zoals willekeurige bossen en gradiënt stimuleren.