Gli alberi di decisione sono uno degli algoritmi di machine learning più intuitivi e ampiamente utilizzati sia per la classificazione che per la regressione. Essi lavorano dividendo i dati in rami basati su valori di caratteristica, mimicking il modo in cui gli esseri umani prendono decisioni. Mentre le librerie come scikit-learn fanno costruire alberi di decisione triviale, l'attuazione di uno da zero è un ottimo modo per i principianti di afferrare le funzioni interne dell'algoritmo.

Cos'è un albero della decisione?

Un albero di decisione è una struttura simile a quella del diagramma di flusso, dove ogni nodo interno rappresenta un test su una funzione (ad esempio, “È l’età > 30?”), ogni ramo rappresenta il risultato di tale prova, e ogni nodo foglia contiene un’etichetta di classe o un valore continuo. L’obiettivo è quello di creare un modello che prevede una variabile di destinazione, imparando regole di decisione semplici inferrate dalle caratteristiche dei dati.

L’albero è costruito in modo ricorsivo: a partire dalla radice, l’algoritmo seleziona la migliore funzionalità e il punto di divisione che separa i dati più in modo pulito. Questo processo viene ripetuto su ogni sottoinsieme fino a quando non viene soddisfatta una condizione di arresto.

Concetti core che devi capire

Nodi, rami e foglie

I nodi interni testano una funzione e distinguono i dati in due o più nodi di bambino. I rami sono i collegamenti che rappresentano l'esito di un test. I nodi di foglia (nodi terminali) emettono la previsione finale – la classe più comune nella classificazione o il valore medio nella regressione.

Criteri di divisione

Per costruire un albero, è necessario un modo per misurare la qualità di una potenziale divisione.

  • Gini impurity[[[] – usato in classificazione per misurare quanto spesso un elemento scelto casualmente sarebbe etichettato in modo errato se fosse etichettato casualmente secondo la distribuzione delle classi nel sottoset.
  • L'introduzione[[] – misura la quantità di disordine o di incertezza in un insieme. L'obiettivo è quello di ridurre l'entropia dopo la divisione (aumento di informazioni).
  • Riduzione della varianza[[[]] – utilizzata per gli alberi di regressione.

L'algoritmo valuta ogni possibile spaccatura su ogni caratteristica e sceglie quella che produce la più grande riduzione dell'impurità (o guadagno in informazioni).

Informazioni Gain e Gain Ratio

Il guadagno di informazioni è la differenza tra l'impurità del nodo genitore e la somma ponderata delle impurità dei bambini. Mentre è semplice, tende a favorire le caratteristiche con molti valori. Il rapporto di guadagno (utilizzato in C4.5) normalizza questo. Per questo tutorial ci appiccheremo con il guadagno di informazioni standard utilizzando l'impurità di Gini, che è il default in CART (Classificazione e alberi di regressione).

Costruire un albero decisione Passo dopo Passo

1. Prepara i tuoi dati

Per semplicità, utilizzare un set di dati di classificazione binaria con funzioni numeriche. Ad esempio:

  • Caratteristiche:[ Età, reddito
  • Grande:[] Approvato (1) o non approvato (0)

Pulire i dati: gestire i valori mancanti, rimuovere i duplicati e garantire i tipi numerici. Gli alberi di decisione possono gestire i tipi di dati misti, ma ci atteniamo a numerici per l'implementazione.

2. Definire una funzione di calcolo dei criteri di divisione

Realizzeremo l'impurità di Gini. L'indice Gini per un insieme di elementi è:

dove p i è la proporzione di elementi in classe i. Per una divisione binaria, il Gini generale è la media ponderata dei nodi del bambino.

3. Implementare la valutazione di Spalato

Per ogni funzione, ordinare i valori unici. Testare ogni possibile soglia (in mezzo a valori ordinati consecutivi). Per ogni soglia candidato, dividere i dati in gruppi di sinistra e di destra, calcolare il Gini, e monitorare la migliore divisione.

4. Costruisci l'albero in modo ricorsivo

Creare una funzione che richiede un sottoinsieme di dati e una profondità corrente. Controlla le condizioni di arresto (ad esempio, la massima profondità raggiunta, campioni minimi per nodo, o nessun guadagno di informazione). Se una condizione viene soddisfatta, creare un nodo foglia con la classe di maggioranza. Altrimenti, trovare la migliore scissione e creare un nodo interno, quindi chiamare ricorsivamente la funzione sulla divisione sinistra e destra.

5. Fare le preddizioni

Una volta che l'albero è costruito, la previsione è semplice: iniziare alla radice, seguire i rami valutando i test di funzionalità sul nuovo campione, e restituire il valore della foglia che si atterra.

Attuazione completa in Python

Di seguito è riportata una completa e minima implementazione di un albero di decisione per la classificazione utilizzando l'impurità di Gini.Questo codice è destinato all'apprendimento – non è ottimizzato per grandi dataset.

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

Testare l'albero

Utilizzare un semplice set di dati come il classico set di dati iris (due caratteristiche per la classificazione binaria). Scikit-learn Iris dataset[] funziona bene.

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

Tecniche avanzate per migliorare il tuo albero

Pruning per evitare sovrapposti

Un albero completamente coltivato può memorizzare il rumore nei dati di allenamento. Pruning rimuove i rami che hanno poca potenza predittiva. I metodi comuni sono pre-pruning (che blocca la crescita presto via [[] o ]) e post-pruning (crescere l'albero completo quindi rimuovere i rami utilizzando un set di convalida o una potatura di complessità dei costi).

Maneggiare funzioni continue e categoriche

Per le caratteristiche categoriche (ad esempio, “Colore = rosso/verde/blu”), ogni categoria può diventare un ramo separato (divisi a più vie) o è possibile codificarli in binario. La maggior parte delle implementazioni moderne (come la scikit-learn) utilizzano le divisioni binarie anche per le caratteristiche categoriche valutando tutti i sottoinsiemi.

Trattare con valori mancanti

I dati del mondo reale spesso hanno valori mancanti. Un approccio semplice è quello di assegnare valori mancanti al ramo più frequente tra i campioni di formazione che hanno la funzione. C4.5 utilizza un metodo probabilistico. Poiché questo è un tutorial principiante, presumiamo che i dati siano completi.

Confrontare con le biblioteche e leggere

Mentre la costruzione da zero è educativa, i sistemi di produzione utilizzano librerie come la scikit-learn che forniscono implementazioni C ottimizzate. È possibile saperne di più dalla documentazione ufficiale scikit-learn decision tree. Per la teoria più profonda, il libro “Gli elementi di apprendimento statistico” di Hastie, Tibshirani e Friedman è una risorsa autorevole.

Conclusioni

Costruire un albero di decisione da zero demystify uno degli algoritmi più fondamentali nell'apprendimento automatico. Hai imparato come una semplice procedura di scissione ricorsiva può produrre un modello potente. Scrivendo il codice stesso, si ottiene una più profonda comprensione delle misure di impurità, selezione divisa, e le offerte commerciali tra bias e varianza. Come passo successivo, cercare di aggiungere supporto di regressione, potatura, o gestire caratteristiche di categoria.