Comprendere implementando: albero decisionale

Immagine dell'autore

Molti modelli avanzati di machine learning come random forest o algoritmi di gradient boosting come XGBoost, CatBoost o LightGBM (e persino autoencoder!) si basano su un fondamentale ingrediente comune: il albero decisionale!

Senza comprendere gli alberi decisionali, è impossibile comprendere anche nessuno dei suddetti algoritmi avanzati di insaccamento o potenziamento del gradiente, il che è una vergogna per qualsiasi scienziato di dati! Quindi, cerchiamo di demistificare il funzionamento interno di un albero decisionale implementandone uno in Python.

In questo articolo, imparerai

• perché e come un albero decisionale suddivide i dati,
• il guadagno di informazioni, e
• come implementare alberi decisionali in Python usando NumPy.

Puoi trovare il codice su il mio GitHub.

Per fare previsioni, gli alberi decisionali si basano su scissione il set di dati in parti più piccole in modo ricorsivo.

Immagine dell'autore

Nell'immagine sopra, puoi vedere un esempio di divisione: il set di dati originale viene separato in due parti. Nel passaggio successivo, entrambe queste parti vengono nuovamente divise e così via. Questo continua fino a quando non viene soddisfatto un qualche tipo di criterio di arresto, ad esempio,

• se la divisione risulta in una parte vuota
• se è stata raggiunta una certa profondità di ricorsione
• se (dopo le precedenti suddivisioni) il set di dati è costituito solo da pochi elementi, rendendo superflue ulteriori suddivisioni.

Come troviamo queste divisioni? E perché ci interessa? Scopriamolo.

Motivazione

Supponiamo di voler risolvere a binario problema di classificazione che creiamo noi stessi ora:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

I dati bidimensionali hanno questo aspetto:

Immagine dell'autore

Possiamo vedere che ci sono due diverse classi: viola in circa il 75% e gialla in circa il 25% dei casi. Se fornisci questi dati a un albero decisionale classificatore, questo albero ha inizialmente i seguenti pensieri:

“Ci sono due etichette diverse, il che è troppo disordinato per me. Voglio ripulire questo pasticcio suddividendo i dati in due parti: queste parti dovrebbero essere più pulite rispetto ai dati completi precedenti. — albero che ha preso coscienza

E così fa l'albero.

Immagine dell'autore

L'albero decide di fare una spaccatura approssimativamente lungo il x-asse. Ciò ha l'effetto che la parte superiore dei dati ora è perfettamente pulito, nel senso che trovi solo una sola classe (viola in questo caso) lì.

Tuttavia, la parte inferiore è ancora disordinato, anche più disordinato di prima in un certo senso. Il rapporto di classe era di circa 75:25 nel set di dati completo, ma in questa parte più piccola è di circa 50:50, che è il più confuso possibile

 Nota: Qui, non importa che il viola e il giallo siano ben separati nell'immagine. Solo il quantità grezza di diverse etichette nelle due parti contare.

Immagine dell'autore

Tuttavia, questo è abbastanza buono come primo passo per l'albero, e così va avanti. Anche se non creerebbe un'altra divisione nella parte superiore, cavedano parte più, può creare un'altra divisione nella parte inferiore per ripulirla.

Immagine dell'autore

Et voilà, ciascuna delle tre parti separate è completamente pulita, in quanto troviamo un solo colore (etichetta) per parte.

È davvero facile fare previsioni ora: se arriva un nuovo punto dati, basta controllare in quale dei tre parti mente e dagli il colore corrispondente. Funziona così bene ora perché ogni parte lo è cavedano. Facile, vero?

Immagine dell'autore

Va bene, ne stavamo parlando cavedano ed disordinato dati ma finora queste parole rappresentano solo una vaga idea. Per implementare qualsiasi cosa, dobbiamo trovare un modo per definire pulizia.

Misure per la pulizia

Supponiamo di avere alcune etichette, per esempio

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

Intuitivamente, sì₁ è il set di etichette più pulito, seguito da sì₂ e poi y₃. Fin qui tutto bene, ma come possiamo dare dei numeri a questo comportamento? Forse la cosa più semplice che mi viene in mente è la seguente:

Basta contare la quantità di zeri e la quantità di quelli. Calcola la loro differenza assoluta. Per renderlo più gradevole, normalizzalo dividendo per la lunghezza degli array.

Per esempio, sì₂ ha 8 voci in totale: 6 zeri e 2 uno. Quindi, il nostro file personalizzato punteggio di pulizia sarebbe |6 – 2| /8 = 0.5. È facile calcolare i punteggi di pulizia di sì₁ ed y₃ sono rispettivamente 1.0 e 0.0. Qui possiamo vedere la formula generale:

Immagine dell'autore

Qui, n₀ ed n₁ sono rispettivamente i numeri di zero e uno, n = n₀ + n₁ è la lunghezza dell'array e p₁ = n₁ / n è la quota delle 1 etichette.

Il problema con questa formula è che lo è specificamente adattato al caso di due classi, ma molto spesso siamo interessati alla classificazione multiclasse. Una formula che funziona abbastanza bene è la Misura dell'impurità di Gini:

Immagine dell'autore

o il caso generale:

Immagine dell'autore

Funziona così bene che scikit-learn l'ha adottata come misura di default per la sua DecisionTreeClassifier classe.

Immagine dell'autore

 Nota: Gini misure disordine invece della pulizia. Esempio: se una lista contiene solo una singola classe (= dati molto puliti!), allora tutti i termini nella somma sono zero, quindi la somma è zero. Il caso peggiore è se tutte le classi compaiono il numero esatto di volte, nel qual caso il Gini è 1–1/C where C è il numero di classi.

Ora che abbiamo una misura per pulizia/disordine, vediamo come può essere usata per trovare buone divisioni.

Trovare le divisioni

Ci sono molti split tra cui scegliere, ma qual è quello buono? Usiamo di nuovo il nostro set di dati iniziale, insieme alla misura di impurità di Gini.

Immagine dell'autore

Non conteremo i punti ora, ma supponiamo che il 75% sia viola e il 25% giallo. Usando la definizione di Gini, l'impurità del set di dati completo è

Immagine dell'autore

Se dividiamo il set di dati lungo il file x-axis, come fatto prima:

Immagine dell'autore

Il la parte superiore ha un'impurità Gini di 0.0 e la parte inferiore

Immagine dell'autore

In media, le due parti hanno un'impurità Gini di (0.0 + 0.5)/2 = 0.25, che è migliore dello 0.375 dell'intero set di dati di prima. Possiamo anche esprimerlo in termini del cosiddetto guadagno di informazioni:

Il guadagno di informazioni di questa suddivisione è 0.375 – 0.25 = 0.125.

Facile come quello. Maggiore è il guadagno di informazioni (cioè minore è l'impurità di Gini), meglio è.

Nota: Un'altra divisione iniziale altrettanto buona sarebbe lungo l'asse y.

Una cosa importante da tenere a mente è che è utile pesare le impurità Gini delle parti in base alla dimensione delle parti. Ad esempio, supponiamo che

• la parte 1 è composta da 50 punti dati e ha un'impurità Gini di 0.0 e
• la parte 2 è composta da 450 punti dati e ha un'impurità Gini di 0.5,

quindi l'impurità media di Gini non dovrebbe essere (0.0 + 0.5) / 2 = 0.25 ma piuttosto 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Ok, e come troviamo la divisione migliore? La risposta semplice ma che fa riflettere è:

Basta provare tutte le divisioni e scegliere quella con il maggior guadagno di informazioni. È fondamentalmente un approccio di forza bruta.

Per essere più precisi, vengono utilizzati alberi decisionali standard divide lungo gli assi delle coordinate, Cioè xᵢ = c per qualche caratteristica i e soglia c. Ciò significa che

• una parte dei dati suddivisi è costituita da tutti i punti dati x con xᵢ ced
• l'altra parte di tutti i punti x con xᵢ ≥ c.

Queste semplici regole di divisione si sono dimostrate abbastanza valide nella pratica, ma ovviamente puoi anche estendere questa logica per creare altre divisioni (ad esempio linee diagonali come xᵢ + 2xⱼ = 3, per esempio).

Fantastico, questi sono tutti gli ingredienti di cui abbiamo bisogno per iniziare subito!

Ora implementeremo l'albero decisionale. Poiché consiste di nodi, definiamo a Node classe prima.

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

Un nodo conosce la caratteristica che usa per dividere (feature) così come il valore di divisione (value). value viene utilizzato anche come memoria per la previsione finale dell'albero decisionale. Poiché costruiremo un albero binario, ogni nodo deve conoscere i suoi figli sinistro e destro, come memorizzati in left ed right .

Ora, eseguiamo l'effettiva implementazione dell'albero decisionale. Lo sto rendendo compatibile con scikit-learn, quindi utilizzo alcune classi da sklearn.base . Se non lo conosci, dai un'occhiata al mio articolo su come costruire modelli compatibili con scikit-learn.

Implementiamo!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

E questo è tutto! Ora puoi fare tutte le cose che ami di scikit-learn:

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

Poiché l'albero non è regolarizzato, si adatta molto, da qui il punteggio perfetto del treno. L'accuratezza sarebbe peggiore su dati invisibili. Possiamo anche controllare l'aspetto dell'albero tramite

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

Come immagine sarebbe questa:

Immagine dell'autore

In questo articolo, abbiamo visto in dettaglio come funzionano gli alberi decisionali. Abbiamo iniziato con alcune idee vaghe ma intuitive e le abbiamo trasformate in formule e algoritmi. Alla fine, siamo stati in grado di implementare un albero decisionale da zero.

Un avvertimento però: il nostro albero decisionale non può ancora essere regolarizzato. Di solito, vorremmo specificare parametri come

• profondità massima
• dimensione della foglia
• e minimo guadagno di informazioni

tra molti altri. Fortunatamente, queste cose non sono così difficili da implementare, il che lo rende un compito perfetto per te. Ad esempio, se specifichi leaf_size=10 come parametro, i nodi contenenti più di 10 campioni non dovrebbero più essere suddivisi. Inoltre, questa implementazione è non efficiente. Di solito, non vorresti archiviare parti dei set di dati nei nodi, ma solo gli indici. Quindi il tuo set di dati (potenzialmente grande) è in memoria solo una volta.

La cosa buona è che ora puoi impazzire con questo modello di albero decisionale. Puoi:

• implementare divisioni diagonali, ad es xᵢ + 2xⱼ = 3 invece di solo xᵢ = 3,
• cambia la logica che accade all'interno delle foglie, cioè puoi eseguire una regressione logistica all'interno di ogni foglia invece di fare solo un voto di maggioranza, che ti dà un albero lineare
• cambia la procedura di divisione, cioè invece di usare la forza bruta, prova alcune combinazioni casuali e scegli quella migliore, che ti dà un classificatore extra-albero
• e più.

 
 
Dr. Robert Kubler è un Data Scientist presso Publicis Media e Autore presso Towards Data Science.

 
Originale. Ripubblicato con il permesso.
 

• Distribuzione di contenuti basati su SEO e PR. Ricevi amplificazione oggi.
• Platoblockchain. Web3 Metaverse Intelligence. Conoscenza amplificata. Accedi qui.
• Fonte: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree