Beslutsträd är en av de mest intuitiva och allmänt använda maskininlärningsalgoritmer för både klassificering och regression. De arbetar genom att dela data i grenar baserat på funktionsvärden, efterlikna hur människor fattar beslut. Medan bibliotek som scikit-learn gör byggnadsbeslutsträd triviala, är genomförandet av en från början ett utmärkt sätt för nybörjare att förstå algoritmens inre arbeten. Denna handledning guidar dig genom teorin och kod, så att du kan bygga ditt eget beslut träd från grunden.
Vad är ett beslutsträde?
Ett beslutsträd är en flödesschema-liknande struktur där varje intern nod representerar ett test på en funktion (t.ex. "Är ålder > 30?"), representerar varje gren resultatet av det testet, och varje bladnod håller en klassetikett eller kontinuerligt värde. Målet är att skapa en modell som förutspår en målvariabel genom att lära sig enkla beslutsregler som härrör från datafunktionerna. Beslutsträd är populära eftersom de är lätta att tolka och kräver lite dataförädling (ing eller normalisering).
Trädet är uppbyggt återkommande: Från roten väljer algoritmen den bästa funktionen och delad punkt som skiljer datan mest rent. Denna process upprepas på varje delmängd tills ett stoppförhållande är uppfyllt. För mer bakgrund väljer Wikipedias inträde på beslutsträdet ger en solid översikt.
Kärnkoncept du måste förstå
Noder, grenar och blad
Rotnoden innehåller hela träningsdataset. Interna noder testar en funktion och delar data i två eller flera barnnoder. Grenar är de anslutningar som representerar resultatet av ett test. Leaf noder (terminella noder) utdata den slutliga förutsägelsen - den vanligaste klassen i klassificering eller medelvärdet i regression.
Splitting Kriterier
För att bygga ett träd behöver du ett sätt att mäta kvaliteten på en potentiell splittring. De vanligaste kriterierna är:
- ]] Gini förorening - som används i klassificering för att mäta hur ofta ett slumpmässigt valt element skulle felaktigt märkas om det var slumpmässigt märkt enligt fördelningen av klasser i undergruppen. Lower Gini är bättre.
- ]Entropi] - mäter mängden oordning eller osäkerhet i en uppsättning. Målet är att minimera entropi efter splittringen (informationsvinsten).
- ]Variance reduktion[] - används för regressionsträd. Det beräknar minskningen av variansen (eller genomsnittet kvadratfelet) som uppnås genom splittringen.
Algoritmen utvärderar varje möjlig splittring på varje funktion och väljer den som ger den största minskningen av orenhet (eller vinst i information).
Information Gain och Gain Ratio
Informationsvinst är skillnaden mellan föroreningen av föräldranoden och den viktade summan av barnföroreningar. Medan det är enkelt tenderar det att gynna funktioner med många värden. Förbättringsförhållandet (används i C4.5) normaliserar detta. För denna handledning kommer vi att hålla fast vid standardinformationsvinst med Gini förorening, vilket är standard i CART (klassificering och regressionsträd).
Bygga ett beslutsträde steg för steg
Förbered dina data
Du behöver en dataset med funktioner och måletiketter. För enkelhet, använd en binär klassificeringsdataset med numeriska funktioner.
- Funktioner: Ålder, Inkomst
- ]] Mål: Godkänd (1) eller inte godkänd (0)
Rengör data: hantera saknade värden, ta bort dubbletter och se till att numeriska typer. Beslutsträd kan hantera blandade datatyper men vi kommer att hålla oss till numeriska för genomförandet.
Definiera en Splitting Criterion Function
Vi kommer att genomföra Gini förorening. Gini index för en uppsättning objekt är:
]
där p i är andelen objekt i klass i. För en binär splittring är den totala Gini det vägda genomsnittet av barnnoderna.
3. Genomföra Split-utvärderingen
För varje funktion, sortera de unika värdena. Testa varje möjlig tröskel (mittpunkt mellan på varandra följande sorterade värden). För varje kandidattröskel, dela data i vänster och höger grupper, beräkna Gini och spåra den bästa split.
Bygg trädet igen
Skapa en funktion som tar en delmängd av data och ett aktuellt djup. Det kontrollerar stoppförhållanden (t.ex. maximalt djup nått, minsta prover per nod eller ingen informationsvinst). Om ett tillstånd är uppfyllt, skapa en bladnod med majoritetsklassen. Annars, hitta den bästa split och skapa en intern nod, sedan upprepande kalla funktionen på vänster och höger delar.
5. Gör förutsägelser
När trädet är byggt är förutsägelse enkelt: börja vid roten, följ grenarna genom att utvärdera funktionstesterna på det nya provet och returnera värdet av bladet du landar på.
Fullt genomförande i Python
Nedan följer ett fullständigt, minimalt genomförande av ett beslutsträd för klassificering med hjälp av Gini förorening. Denna kod är avsedd för lärande - den är inte optimerad för stora datamängder.
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'])
Testa trädet
Använd en enkel datamängd som den klassiska iris datamängden (två funktioner för binär klassificering). ]]]scikit-learn Iris datamängd]] fungerar bra. Jämför ditt träds noggrannhet med scikit-learns för att verifiera korrektheten.
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}')
Avancerade tekniker för att förbättra ditt träd
Beskärning att undvika överfitting
Ett fullt odlat träd kan memorera buller i träningsdata. Pruning tar bort grenar som har liten prediktiv kraft. Vanliga metoder är pre-pruning (stoppning tillväxt tidigt via ] eller ) och efter beskärning (växande hela trädet och sedan avlägsna grenar med hjälp av en validering set eller kostnadskomplexitet beskärning). Vårt genomförande stöder redan pre-pruning.
Hantera kontinuerliga och kategoriska funktioner
För kontinuerliga funktioner använde vi mellanpunkter mellan sorterade värden som trösklar. För kategoriska funktioner (t.ex. "färg = röd / grön") kan varje kategori bli en separat gren (multi-way split) eller du kan binärkoda dem. De flesta moderna implementeringar (som scikit-learn) använder binära delar även för kategoriska funktioner genom att utvärdera alla delmängder.
Hantera saknade värden
Real-världsdata har ofta saknade värden. Ett enkelt tillvägagångssätt är att tilldela saknade värden till den vanligaste grenen bland träningsprover som har funktionen. C4.5 använder en probabilistisk metod. Eftersom detta är en nybörjarhandledning antar vi att data är komplett.
Jämför med bibliotek och vidare läsning
Medan byggandet från början är utbildnings-, använder produktionssystem bibliotek som scikit-learn som ger optimerade C-implementeringar. Du kan lära dig mer från den officiella ] scikit-learn beslutsträd dokumentation ]. För djupare teori, boken "Elements of Statistical Learning" av Hastie, Tibshirani och Friedman är en auktoritativ resurs. En annan utmärkt referens är den ursprungliga CART-boken av Breiman et al.
Slutsats
Att bygga ett beslut träd från grunden avmystifierar en av de mest grundläggande algoritmerna i maskininlärning. Du har lärt dig hur en enkel återkommande uppdelningsprocedur kan producera en kraftfull modell. Genom att skriva koden själv, får du en djupare förståelse för orenhetsåtgärder, delat urval och avvägningar mellan partiskhet och varians. Som ett nästa steg, försök att lägga till regressionsstöd, beskärning eller hantera kategoriska funktioner. De färdigheter du utvecklar här kommer att tjäna dig bra när du går vidare till mer komplexa ensemble metoder som slumpmässiga skogar och gradient öka.