Albero di decisione

Nell'ambito dell'apprendimento automatico e del data mining^[1], in particolare, un albero di decisione è un modello predittivo, dove ogni nodo interno rappresenta una variabile, un arco verso un nodo figlio rappresenta un possibile valore per quella proprietà e una foglia il valore predetto per la variabile obiettivo a partire dai valori delle altre proprietà, che nell'albero è rappresentato dal cammino (path) dal nodo radice (root) al nodo foglia.^[2] Normalmente un albero di decisione viene costruito utilizzando tecniche di apprendimento a partire dall'insieme dei dati iniziali (data set), il quale può essere diviso in due sottoinsiemi: il training set sulla base del quale si crea la struttura dell'albero e il test set che viene utilizzato per testare l'accuratezza del modello predittivo così creato.^[3]^[4]

Un albero di decisione viene utilizzato per classificare le istanze di grandi quantità di dati (per questo viene anche chiamato albero di classificazione). In questo ambito un albero di decisione descrive una struttura ad albero dove i nodi foglia rappresentano le classificazioni e le ramificazioni l'insieme delle proprietà che portano a quelle classificazioni. Di conseguenza ogni nodo interno risulta essere una macro-classe costituita dall'unione delle classi associate ai suoi nodi figli. Il predicato che si associa ad ogni nodo interno (sulla base del quale avviene la ripartizione dei dati) è chiamato condizione di partizionamento (split). In alternativa, quando la variabile-obiettivo da predire è continua si parla di albero di regressione.

Una evoluzione degli alberi di decisione è il modello composito (ensemble) della foresta casuale ^[5](random forest). Altre estensioni multi-output del modello^[6] consentono la predizione strutturata.

Apprendimento

L'apprendimento degli alberi di decisione (binari) si basa generalmente su un algoritmo greedy ricorsivo che, per ogni nodo interno, a partire dalla radice per la quale riceve l'intero insieme degli esempi di training $\{(\mathbf {X} =\mathbf {x} _{t},Y=c_{t})\}_{t=1}^{N}$ :

dati gli esempi a disposizione, partiziona l'insieme di esempi sulla base di un test^[7], che coinvolge una coppia $(i,\theta )$ $(i,\theta )$ , ossia una variabile di input $X_{i}$ $X_{i}$ e uno dei valori $\theta$ del suo dominio, selezionata opportunamente in modo tale da massimizzare l'omogeneità degli esempi nelle partizioni risultanti in termini dei valori della variabile di output $Y$ (etichette delle classi). Il tipo di test dipende dal dominio di $X_{i}$ $X_{i}$ :
- binario/categorico: $X_{i}=\theta$ (ad es. gender in figura);
- ordinale/continuo: $X_{i}\leq \theta$ (ad es. age o sbsp in figura);.

Le partizioni di esempi relative ai diversi esiti del test costituiranno l'input per le chiamate ricorsive che vanno a costruire i sotto-alberi nel medesimo modo.

Ogni chiamata ricorsiva termina quando non è necessario partizionare ancora gli esempi in un dato nodo avendo essi superato una soglia di purezza (omogeneità) minima. In tal caso il nodo sarà una foglia ( ${\hat {Y}}=c^{*}$ ) utile per le successive classificazioni su nuovi esempi.

Grazie alle distribuzioni di esempi di training che raggiungono le diverse foglie, corrispondenti a diversi sottospazio / regioni è anche possibile calcolare diverse distribuzioni $P(Y|\mathbf {X} )$ per fornire predizioni probabilistiche^[4]^[5] (cfr. esempio in figura).

Per apprendere alberi di regressione, per i quali Y da predire è continua, si adotta un diverso criterio di partizionamento e di arresto della ricorsione.

Criteri di split e pruning

È utile definire un criterio di arresto (halting), o anche criterio di potatura (pruning) al fine di determinarne la profondità massima. Questo perché il crescere della profondità di un albero (ovvero della sua dimensione) non influisce direttamente sulla bontà del modello. Infatti, una crescita eccessiva della dimensione dell'albero potrebbe portare solo ad aumento sproporzionato della complessità computazionale rispetto ai benefici riguardanti l'accuratezza delle predizioni/classificazioni, aumentando il rischio di sovradattamento.

I criteri più largamente usati per definire le condizioni di split sono:

Tasso d'errore nella classificazione (misclassification error).
Indice di Gini: utilizzato da CART (Classification and Regression Trees)

I_{G}(i)=1-\sum _{j=1}^{m}f(i,j)^{2}.

L'indice di Gini raggiunge il suo minimo (zero) quando il nodo appartiene ad una singola categoria.

Variazione di entropia (nota anche come entropy deviance): utilizzata da C4.5 e C5.0, è basata sul concetto di entropia definito in teoria dell'informazione

I_{E}(i)=-\sum _{j=1}^{m}f(i,j)\log f(i,j).

In entrambe le formule f rappresenta la frequenza del valore j nel nodo i. L'indice di Gini e la variazione di entropia sono i parametri che vengono usualmente utilizzati per guidare la costruzione dell'albero, mentre la valutazione del tasso di errore nella classificazione viene utilizzato per effettuare una ottimizzazione dell'albero nota come processo di "potatura" (pruning) dei nodi superflui. Poiché, in generale, in un buon albero di decisione i nodi foglia dovrebbero essere il più possibile puri (ovvero contenere solo istanze di dati che appartengono ad una sola classe), un'ottimizzazione dell'albero consiste nel cercare di minimizzare il livello di entropia man mano che si scende dalla radice verso le foglie. In tal senso, la valutazione dell'entropia determina quali sono, fra le varie scelte a disposizione, le condizioni di partizionamento ottimali per l'albero di classificazione.

Si veda anche il criterio di partizionamento detto twoing utilizzato in CART.

Nel caso di alberi di regressione si adottano criteri basati sulla differenza delle varianze prima e dopo il partizionamento, ossia misure di impurità basate sulla deviazione ai minimi quadrati (least squares deviation) simili a quelle utilizzate nel clustering. Un criterio analogo vale anche per l'arresto.

Teoria delle decisioni

Esempio di un albero di decisione (schema)

Nella teoria delle decisioni, un albero di decisione è un sistema di supporto basato su un grafo di decisioni contenente anche le possibili conseguenze (includendo i costi, risorse e rischi relativi) e può essere utilizzato per creare un piano di azioni (plan) che miri a un dato scopo (goal).^[8] Un albero di decisione viene modellato al fine di supportare l'azione decisionale in compiti quali, ad esempio, la gestione dei rischi.^[9]

Note

↑ (EN) Ian H. Witten, Eibe Frank e Mark A. Hall, Data Mining: Practical Machine Learning Tools and Techniques, Elsevier Science, 2025, ISBN 978-0-443-15888-9.
↑ (EN) Leo Breiman, Jerome H. Friedman e Richard A. Olshen, Classification And Regression Trees, 1ª ed., Routledge, 19 ottobre 2017, DOI:10.1201/9781315139470, ISBN 978-1-315-13947-0.
↑ (EN) Trevor Hastie, Robert Tibshirani e Jerome Friedman, Additive Models, Trees, and Related Methods, Springer, 2009, pp. 295–336, DOI:10.1007/978-0-387-84858-7_9, ISBN 978-0-387-84858-7.
1 2 Ethem Alpaydın, Ch. 9: Decision Trees, in Introduction to machine learning, collana Adaptive computation and machine learning, Fourth edition, The MIT Press, 2020, ISBN 978-0-262-35806-4.
1 2 (EN) Kevin P. Murphy, 18. Trees, Forests, Bagging, and Boosting, in Probabilistic machine learning: an introduction, collana Adaptive computation and machine learning, Third printing, The MIT Press, 2025, ISBN 978-0-262-04682-4.
↑ Marie Dumont, Raphaël Marée e Louis Wehenkel, Fast Multi-class Image Annotation with Random Subwindows and Multiple Output Randomized Trees, in Alpesh Ranchordas, Helder Araújo (a cura di), VISAPP 2009 - Proceedings of the Fourth International Conference on Computer Vision Theory and Applications, Lisboa, Portugal, February 5-8, 2009 - Volume 2, INSTICC Press, 2009, pp. 196–203.
↑ Possibili estensioni prevedono test a più vie (multiway) nei nodi interni. È prevista anche la possibilità di test multivariati che coinvolgono più variabili di input.
↑ (EN) Detlof von Winterfeldt e Ward Edwards, Decision analysis and behavioral research, Repr, Cambridge Univ. Press, 1993, ISBN 978-0-521-27304-6.
↑ Analisi del rischio - Enciclopedia, su Treccani. URL consultato il 21 giugno 2026.

Voci correlate

Altri progetti

Wikibooks contiene testi o manuali su albero di decisione
Wikimedia Commons contiene immagini o altri file su albero di decisione

Collegamenti esterni

(EN) 1.10. Decision Trees, su scikit-learn. URL consultato il 25 giugno 2026.
Decisioni, teoria delle - Enciclopedia, su Treccani. URL consultato il 21 giugno 2026.

Controllo di autorità	GND (DE) 4347788-4 · J9U (EN, HE) 987007541962905171

[1] (EN) Ian H. Witten, Eibe Frank e Mark A. Hall, Data Mining: Practical Machine Learning Tools and Techniques, Elsevier Science, 2025, ISBN 978-0-443-15888-9.

[2] (EN) Leo Breiman, Jerome H. Friedman e Richard A. Olshen, Classification And Regression Trees, 1ª ed., Routledge, 19 ottobre 2017, DOI:10.1201/9781315139470, ISBN 978-1-315-13947-0.

[3] (EN) Trevor Hastie, Robert Tibshirani e Jerome Friedman, Additive Models, Trees, and Related Methods, Springer, 2009, pp. 295–336, DOI:10.1007/978-0-387-84858-7_9, ISBN 978-0-387-84858-7.

[:0-4] 1 2 Ethem Alpaydın, Ch. 9: Decision Trees, in Introduction to machine learning, collana Adaptive computation and machine learning, Fourth edition, The MIT Press, 2020, ISBN 978-0-262-35806-4.

[:1-5] 1 2 (EN) Kevin P. Murphy, 18. Trees, Forests, Bagging, and Boosting, in Probabilistic machine learning: an introduction, collana Adaptive computation and machine learning, Third printing, The MIT Press, 2025, ISBN 978-0-262-04682-4.

[6] Marie Dumont, Raphaël Marée e Louis Wehenkel, Fast Multi-class Image Annotation with Random Subwindows and Multiple Output Randomized Trees, in Alpesh Ranchordas, Helder Araújo (a cura di), VISAPP 2009 - Proceedings of the Fourth International Conference on Computer Vision Theory and Applications, Lisboa, Portugal, February 5-8, 2009 - Volume 2, INSTICC Press, 2009, pp. 196–203.

[7] Possibili estensioni prevedono test a più vie (multiway) nei nodi interni. È prevista anche la possibilità di test multivariati che coinvolgono più variabili di input.

[8] (EN) Detlof von Winterfeldt e Ward Edwards, Decision analysis and behavioral research, Repr, Cambridge Univ. Press, 1993, ISBN 978-0-521-27304-6.

[9] Analisi del rischio - Enciclopedia, su Treccani. URL consultato il 21 giugno 2026.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]