Algoritmo ID3: differenze tra le versioni

Versione delle 23:42, 14 giu 2015

Versione attuale delle 23:40, 22 nov 2023

(20 versioni intermedie di 14 utenti non mostrate)

Riga 1:

{{F|matematica|luglio 2017}}

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

Risulta'''ID3''' (''Iterative Dichotomiser 3'') è un [[algoritmo greedy]](in ogniper momentol'induzione fadi la[[albero "mossa"di chedecisione|alberi massimizzadi la "bontà" dell'albero)decisione]].

== Concetti di baseL'algoritmo ==

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

=== 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.

L'obiettivo è comunque sempre quello di ottenere un albero piccolo e preciso.

=== Condizioni di arresto ===

L'algoritmo si arresta se:

* tutte le istanze di un nodo appartengono alla stessa classe, in questo caso il nodo diventa una foglia con la corrispondente classe assegnata.

* non ci sono più attributi sui quali dividere l'albero, in questo caso il nodo diviene una foglia a cui viene assegnata la classe più comune tra le istanze ad esso assegnate.

=== Pseudocodice ===

== Classi o distribuzioni di probabilità ==

Viene qui riportato lo pseudocodice<ref>{{Cita libro|autore=Tom M- Mitchell|titolo=Machine Learning|anno=1997|url=https://archive.org/details/machinelearning0000mitc|dataoriginale=1 marzo 1997|editore=McGraw-Hill Science|lingua=inglese|ISBN=0070428077}}</ref> dell'algoritmo ID3 per [[Funzione booleana|funzioni booleane]].

<pre>

Esempi:= istanze di addestramento.

Attributo_obiettivo:= l'attributo il cui valore viene predetto dall'albero.

Attributi:= lista di altri attributi.

ID3 (Esempi, Attributo_obiettivo, Attributi)

Crea un nodo Radice.

Se tutti gli esempi sono positivi

restituisci un albero con un unico nodo Radice ed etichetta = +

Se tutti gli esempi sono negativi

restituisci un albero con un unico nodo Radice ed etichetta = -

Se Attributi è vuoto

restituisci un albero con un unico nodo Radice ed etichetta = il valore di Attributo_obiettivo più comune tra le istanze di Esempi.

Altrimenti

A ← L'elemento di Attributi che riduce maggiormente l'entropia.

Per ogni valore v di A,

Aggiungi un nuovo ramo sotto Radice corrispondente al test A = v.

Esempi(v) ← sottoinsieme di Esempi che hanno valore v per A.

Se Esempi(v) è vuoto

Aggiungi una foglia con etichetta = valore di Attributo_obiettivo più comune tra gli esempi.

Altrimenti

Aggiungi sotto Radice il sottoalbero ID3 (Esempi(v), Attributo_obiettivo, Attributi – {A}).

Restituisci Radice.

</pre>

=== Classi o distribuzioni di probabilità ===

In alternativa, invece di assegnare una classe a uno nodo, si può assegnare la distribuzione di probabilità dell'attributo classe, relativamente alle istanze a esso assegnate.

Esempio: se all'ultimo nodo sono assegnate 3 istanze, con classi rispettivamente yes, yes e no, assegnamoassegniamo al nodo la distribuzioendistribuzione di probabilità p tale che p(yes)=2/3 e p(no)=1/3.

=== Proprietà e limiti ===

ID3 restituisce un solo albero di decisione, consistente con il [[dataset]] passato in input. Non è garantito che tale soluzione sia l'unica né che sia quella ottima, in quanto ID3 può convergere anche a minimi locali: per ovviare a questo problema si può fare uso della tecnica di [[backtracking]], che tuttavia non compare nella formulazione originale dell'algoritmo.

Per prevenire, invece, il problema dell'[[overfitting]], si dovrebbe arrestare l'algoritmo prima che tutti gli attributi siano processati, preferendo come soluzioni alberi di decisione più piccoli. Un approccio alternativo, utilizzato nell'algoritmo C4.5 (il successore di ID3), è la tecnica del post-pruning: l'algoritmo non viene arrestato durante l'esecuzione, permettendo quindi anche l'overfitting, e solo al suo termine vengono applicate le regole di pruning (potatura) per migliorare la capacità di generalizzazione.

Un'altra difficoltà è data dalla gestione degli attributi a valore continuo, come i [[numero reale|numeri reali]]. ID3 non prevede nemmeno la possibilità di assegnare dei pesi agli attributi, né ammette attributi mancanti.

== Note ==

<references />

== Bibliografia ==

* {{cita pubblicazione|lingua=en|cognome=Quinlan|nome=John Ross|titolo=Semi-autonomous acquisition of pattern-based knowledge|anno=1980|url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=280e86067cad22814681434b559d7b1621fd5bd3|accesso=12 maggio 2023}}

== Voci correlate ==

* [[DataAlbero miningdi e sicurezzadecisione]]

* [[Clustering]]

* [[Data cleaning]]

* [[Data warehouse]]

* [[Geodata warehouse]]

* [[Algoritmo]]

* [[Base di conoscenza]]

* [[Bonifica (informatica)]]

* [[Business intelligence]]

* [[Process mining]]

* [[Elaborazione dati]]

* [[Infografica]]

* [[Information retrieval]]

* [[Intelligenza competitiva]]

* [[Overfitting]]

* [[Qualità dei dati (statistica)]]

{{Controllo di autorità}}

{{Portale|matematica|statistica}}

[[Categoria:Data mining| ]]

[[Categoria:Algoritmi di classificazione|ID3]]

{{categorie qualità}}