Potatura di alberi di decisione

La potatura (o pruning) è una tecnica di compressione utilizzata negli algoritmi di apprendimento automatico e di ricerca che riduce le dimensioni degli alberi di decisione rimuovendo sezioni dell'albero non critiche e ridondanti per classificare le istanze. La potatura riduce la complessità del classificatore finale e, di conseguenza, migliora l'accuratezza predittiva riducendo l'overfitting.

Prima e dopo la potatura

Una delle questioni che si pongono negli algoritmi di costruzione di alberi di decisione è la dimensione ottimale dell'albero finale. Un albero troppo grande rischia sovradattarsi ai dati di addestramento e di generalizzare male rispetto a nuovi esempi che si rendano disponibili. Un albero piccolo potrebbe non catturare informazioni strutturali importanti sullo spazio campionario. Tuttavia, è difficile stabilire quando un algoritmo di costruzione debba fermarsi perché è impossibile dire se l'aggiunta di un singolo nodo in più ridurrà drasticamente l'errore. Tale problema è noto come effetto orizzonte. Una strategia comune consiste nel far crescere l'albero fino a quando ogni nodo non contenga un piccolo numero di istanze per poi utilizzare la potatura per rimuovere nodi che non forniscono informazioni aggiuntive. ^[1]

La potatura dovrebbe ridurre le dimensioni di un albero di decisione senza comprometterne l'accuratezza predittiva misurata su un insieme di esempi usato per la convalida incrociata. Esistono numerose tecniche di potatura degli alberi, che differiscono essenzialmente per misura delle le prestazioni utilizzata per l'ottimizzazione.

Tecniche

I processi di potatura possono essere divisi in due tipi:

• Le procedure di pre-pruning impediscono l'induzione dell'albero sull'intero training set sostituendo il criterio di stop() nell'algoritmo di induzione (ad esempio, con uno basato sulla profondità massima dell'albero o sul guadagno di informazione 'gain(Attr) > minGain'). I metodi di pre-pruning sono considerati più efficienti perché non generalizzano l'intero insieme di esempi di addestramento, ma piuttosto gli alberi rimangono piccoli già in partenza. I metodi di pre-pruning sono soggetti a un problema comune, l'effetto orizzonte. Ciò si manifesta con l'interruzione prematura indesiderata della crescita causata dal criterio stop().

• la procedura di post-pruning (o semplicemente potatura) è il metodo più comune per semplificare gli alberi. In tal caso, nodi e sotto-alberi vengono sostituiti con foglie per ridurne la complessità. La potatura può non solo ridurre significativamente le dimensioni, ma anche migliorare l'accuratezza della classificazione di nuove istanze. Può accadere che l'accuratezza sull'insieme di addestramento peggiori, ma quella complessiva aumenti.

Le procedure si differenziano anche in base al tipo di approccio di lavoro sulla struttura dell'albero (dall'alto verso il basso o dal basso verso l'alto).

Potatura dal basso verso l'alto

Queste procedure iniziano dall'ultimo nodo dell'albero (quello più basso). Procedendo ricorsivamente verso l'alto, si determina la rilevanza di ogni singolo nodo ai fini della classificazione. Se la rilevanza del nodo non può essere apprezzata, esso viene eliminato o sostituito da una foglia. Il vantaggio è che, in tal modo, non si perdono sotto-alberi rilevanti. Tali metodi includono il Reduced Error Pruning (REP), il Minimum Cost Complexity Pruning (MCCP) e il Minimum Error Pruning (MEP).

Potatura dall'alto verso il basso

A differenza dei metodi precedenti, questi metodi iniziano dalla radice dell'albero. Seguendo la struttura sottostante, viene eseguito un controllo di pertinenza che decide se un nodo è rilevante o meno per la classificazione di tutti gli n elementi. Potando l'albero a livello di un nodo interno, può accadere che un intero sotto-albero (indipendentemente dalla sua rilevanza) venga eliminato. Uno dei metodi rappresentativi di questa tipologia il Pessimistic Error Pruning (PEP), che produce risultati piuttosto buoni con nuovi esempi (non considerati nell'addestramento).

Algoritmi di potatura

Riduzione degli errori

Una delle forme più semplici di potatura è la REP. Partendo dalle foglie, ogni nodo viene sostituito con la sua classe più popolare. Se l'accuratezza predittiva non viene compromessa da questa modifica essa viene mantenuta. Sebbene un po' ingenua, questa forma di potatura ha il pregio di essere semplice e veloce.

Riduzione della complessità dei costi

La potatura basata sulla complessità dei costi genera una serie di alberi ${\displaystyle T_{0},\ldots ,T_{m}}$ dove ${\displaystyle T_{0}}$  è l'albero iniziale e ${\displaystyle T_{m}}$ è l'albero formato dalla sola radice. Al passo ${\displaystyle i}$ , viene creato l'albero ${\displaystyle T_{i}}$  rimuovendo un sotto-albero da ${\displaystyle T_{i-1}}$ sostituendolo con un nodo foglia con valore (output) scelto come nell'algoritmo di costruzione dell'albero. Il sotto-albero da rimuovere viene scelto come segue:

1. Definire il tasso di errore dell'albero ${\displaystyle T}$  sui dati ${\displaystyle S}$ , ${\displaystyle \operatorname {err} (T,S)}$ 
2. Si sceglie per la rimozione il sotto-albero ${\displaystyle t}$  che minimizza ${\displaystyle {\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {foglie} (T)\right\vert -\left\vert \operatorname {foglie} (\operatorname {prune} (T,t))\right\vert }}}$ 

La funzione ${\displaystyle \operatorname {prune} (T,t)}$  definisce l'albero ottenuto potando i sotto-alberi ${\displaystyle t}$  da ${\displaystyle T}$  mentre ${\displaystyle \operatorname {foglie} (T)}$  restituisce l'insieme delle foglie di ${\displaystyle T}$ . Una volta creata la serie di alberi, si sceglie l'albero migliore in base all'accuratezza generale misurata da un insieme di ⁠ addestramento o di convalida incrociata.

Esempi

Si può applicare la potatura nello schema di compressione di un algoritmo di apprendimento per rimuovere i dettagli ridondanti senza compromettere le prestazioni del modello. Ad esempio, nel caso delle reti neurali, la potatura rimuove interi neuroni o strati di neuroni.

Vedi anche

• Potatura per problemi di ricerca
• Potatura alfa-beta
• Potatura (reti neurali artificiali)

Ulteriori riferimenti

• Potatura basata su MDL Archiviato il 29 agosto 2017 in Internet Archive.
• Potatura tramite reti neurali di backpropagation

Link esterni

• Algoritmo rapido bottom-up
• Introduzione alla potatura degli alberi decisione

Note

1. ^ Trevor Hastie, Robert Tibshirani e Jerome Friedman, The Elements of Statistical Learning, Springer, 2001, pp. 269–272, ISBN 0-387-95284-5.