L’algoritmo CART (Classification and Regression Trees) è un algoritmo ampiamente utilizzato per la costruzione di alberi di decisione in machine learning. Gli alberi di decisione sono una forma di modello predittivo che può essere utilizzata sia per problemi di classificazione che per problemi di regressione. Ecco come funziona l’algoritmo CART e come utilizzarlo in Python.
[wpda_org_chart tree_id=21 theme_id=50]
L’algoritmo CART
L’obiettivo dell’algoritmo CART è suddividere ricorsivamente il dataset di addestramento in sottoinsiemi omogenei in modo da massimizzare la purezza delle classi o minimizzare l’errore nella previsione della variabile target, a seconda che si tratti di un problema di classificazione o regressione.
Ecco una panoramica dei passaggi principali dell’algoritmo CART:
- Scelta della variabile predittiva e della soglia di divisione: L’algoritmo CART inizia selezionando la variabile predittiva (caratteristica) e il valore di soglia che massimizzano la purezza delle classi o minimizzano l’errore nella previsione della variabile target. Per le variabili continue, ad esempio, la soglia potrebbe essere un valore come 3.5, mentre per variabili categoriche, potrebbero essere provate tutte le categorie.
- Divisione del dataset: Una volta scelta la variabile e la soglia, il dataset viene diviso in due sottoinsiemi: uno contenente gli esempi che soddisfano il criterio di divisione e l’altro contenente quelli che non lo fanno.
- Calcolo della purezza o dell’errore: Viene calcolata una misura di purezza o di errore per ciascuno dei due sottoinsiemi. Ad esempio, per problemi di classificazione, potrebbe essere utilizzato l’indice di Gini o l’entropia per misurare la purezza. Per problemi di regressione, potrebbe essere utilizzato l’errore quadratico medio (MSE).
- Ripetizione ricorsiva: I passaggi sopra vengono ripetuti ricorsivamente per ciascun sottoinsieme finché non viene soddisfatto un criterio di arresto, ad esempio, quando il numero massimo di suddivisioni è stato raggiunto o quando tutti gli esempi appartengono alla stessa classe (per problemi di classificazione) o quando la variazione target è sotto una certa soglia (per problemi di regressione).
- Costruzione dell’albero: Alla fine del processo ricorsivo, viene costruito un albero di decisione completo, dove i nodi interni rappresentano le divisioni basate sulle variabili predittive e i nodi foglia rappresentano le previsioni.
Un po’ di storia
L’algoritmo CART (Classification and Regression Trees) è stato sviluppato da Leo Breiman, Jerome Friedman, Richard Olshen e Charles Stone ed è stato introdotto negli anni ’80. L’obiettivo principale di CART è quello di costruire alberi di decisione binari che possano essere utilizzati per la classificazione e la regressione.
La storia di CART è legata alla crescente necessità di sviluppare modelli di machine learning che potessero affrontare problemi complessi di classificazione e regressione. L’approccio degli alberi di decisione si è dimostrato attraente per la sua semplicità concettuale e la facilità di interpretazione dei risultati. CART ha rappresentato un passo significativo nell’evoluzione del machine learning e ha aperto la strada a molte varianti e miglioramenti negli algoritmi di alberi di decisione.
Uno degli aspetti chiave di CART è la sua flessibilità nell’affrontare una varietà di problemi, inclusi quelli con variabili continue e categoriche. Inoltre, l’uso di criteri di impurità come l’indice di Gini o l’entropia ha permesso di gestire efficacemente la selezione delle variabili predittive e dei punti di divisione.
Oltre a essere un modello autonomo, l’approccio CART ha anche influenzato lo sviluppo di algoritmi di ensemble come il Random Forest, che si basa sulla combinazione di diversi alberi di decisione per migliorare le prestazioni predittive.
Negli anni successivi, l’uso di alberi di decisione e delle loro varianti si è diffuso in molte applicazioni, compresa l’analisi dei dati, il riconoscimento di modelli, la classificazione di testo e molto altro. CART ha dimostrato di essere una risorsa preziosa nell’arsenale delle tecniche di machine learning e rimane una base importante per lo sviluppo di algoritmi più complessi nel campo dell’apprendimento automatico.
L’algoritmo CART con la libreria scikit-learn
In Python, puoi utilizzare la libreria scikit-learn per implementare l’algoritmo CART nei seguenti approcci:
- Problemi di Classificazione con DecisionTreeClassifier
- Problemi di Regressione con DecisionTreeRegressor
CART per problemi di Classificazione
Il problema di classificazione che affrontiamo è basato sul dataset Iris, dove l’obiettivo è classificare i fiori in una delle tre specie (setosa, versicolor o virginica). Dividiamo il codice in passaggi con descrizioni per una migliore comprensione:
Passo 1: Importa le librerie e carica il dataset:
Iniziamo importando le librerie necessarie, caricando il dataset Iris e suddividendo i dati in set di addestramento e di test.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, confusion_matrix, ConfusionMatrixDisplay
# Load the Iris dataset
iris = load_iris()
X = iris.data
y = iris.target
# Divide the dataset into training and test sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
Passo 2: Crea e addestra un modello CART:
Ora creiamo un modello CART utilizzando il DecisionTreeClassifier di scikit-learn e lo addestriamo sui dati di addestramento.
#Create a CART template
tree_classifier = DecisionTreeClassifier(random_state=42)
#Train the model on the training data
tree_classifier.fit(X_train, y_train)
Passo 3: Effettua previsioni e valuta il modello:
Ora possiamo utilizzare il modello addestrato per effettuare previsioni sui dati di test e valutare le prestazioni del modello.
#Make predictions on test data
y_pred = tree_classifier.predict(X_test)
#Calculate the accuracy of the model<code>
accuracy = accuracy_score(y_test, y_pred)
print("Model accuracy:", accuracy)
#View the confusion matrix
cm = confusion_matrix(y_test, y_pred, labels=tree_classifier.classes_)
disp = ConfusionMatrixDisplay(confusion_matrix=cm,display_labels=tree_classifier.classes_)
disp.plot()
In questo esempio, abbiamo creato un modello CART, effettuato previsioni sui dati di test e calcolato l’accuratezza del modello. Inoltre, abbiamo visualizzato la matrice di confusione per una valutazione più dettagliata delle prestazioni del modello.
Assicurati di aver installato scikit-learn, numpy e matplotlib prima di eseguire il codice. Eseguendolo otterrai i risultati seguenti:
Model accuracy: 1.0
CART per problemi di Regressione
In questo esempio, utilizzeremo il dataset Boston Housing per prevedere il prezzo delle abitazioni in base a diverse caratteristiche. Dividiamo il codice in passaggi con descrizioni per una migliore comprensione:
Passo 1: Importa le librerie e carica il dataset:
Iniziamo importando le librerie necessarie, caricando il dataset Boston Housing e suddividendo i dati in set di addestramento e di test.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_diabetes
from sklearn.tree import DecisionTreeRegressor
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error, r2_score
# Load the Diabetes dataset instead of Boston
diabetes = load_diabetes()
X = diabetes.data
y = diabetes.target
# Split the dataset into training and test sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
Passo 2: Crea e addestra un modello CART per la regressione:
Ora creiamo un modello CART per la regressione utilizzando il DecisionTreeRegressor di scikit-learn e lo addestriamo sui dati di addestramento.
# Create a CART model for regression
tree_regressor = DecisionTreeRegressor(random_state=42)
# Train the model on the training data
tree_regressor.fit(X_train, y_train)
Passo 3: Effettua previsioni e valuta il modello:
Ora possiamo utilizzare il modello addestrato per effettuare previsioni sui dati di test e valutare le prestazioni del modello utilizzando metriche di regressione come l’errore quadratico medio (MSE) e il coefficiente di determinazione (R^2).
# Make predictions on the test data
y_pred = tree_regressor.predict(X_test)
# Calculate the mean squared error (MSE)
mse = mean_squared_error(y_test, y_pred)
print("Mean Squared Error (MSE):", mse)
# Calculate the coefficient of determination (R^2)
r2 = r2_score(y_test, y_pred)
print("Coefficient of Determination (R^2):", r2)
# Display a scatter plot between actual and predicted values
plt.scatter(y_test, y_pred)
plt.xlabel("Actual Values")
plt.ylabel("Predictions")
plt.title("Scatter Plot: Actual Values vs. Predictions")
plt.show()
In questo esempio, abbiamo creato un modello CART per la regressione, effettuato previsioni sui dati di test e valutato il modello utilizzando l’errore quadratico medio (MSE) e il coefficiente di determinazione (R^2). Inoltre, abbiamo visualizzato un grafico di dispersione per esaminare visivamente le previsioni rispetto ai valori effettivi. Eseguendo otterrai i seguenti risultati;
Mean Squared Error (MSE): 4976.797752808989
Coefficient of Determination (R^2): 0.060653981041140725