Algoritmo ID3: differenze tra le versioni

Versione delle 15:28, 26 ott 2015

Versione delle 13:25, 9 feb 2016

Riga 1:

ID3 (''Iterative Dichotomiser 3'') risulta essere uno degli algoritmi "storici" per l'induzione di [[albero di decisione|alberi di decisione]].

Risulta un [[algoritmo greedy]] (in ogni momento fa la "mossa" che massimizza la "bontà" dell'albero).

== Concetti di base ==

L'albero è costruito in maniera top-down usando una politica nota come [[divide et impera]] (dividere un problema in sotto-problemi più piccoli).

Algoritmo:

* Si parte con un albero costituito dalla sola radice, alla cui radice sono assegnate tutte le istanze di addestramento.

* Si sceglie un attributo (l'algoritmo ID3 lo sceglie mediante il "guadagno di informazione" e non il gain ratio).

* Si creano tanti nodi (figli della radice) quanti sono i possibili valori dell'attributo scelto. In questo caso le istanze di addestramento sono assegnate al figlio appropriato

* Si procede [[ricorsione|ricorsivamente]] usando come radici i nuovi nodi.

Gli step sopra definiti si adattano alla maggior parte degli algoritmi di induzione di alberi di decisione, cambia il metodo con cui si sceglie l'attributo.