Algoritmo ID3: differenze tra le versioni

Versione delle 19:50, 19 feb 2019

Versione delle 15:08, 2 apr 2019

Riga 3:

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

== Concetti di baseL'algoritmo ==

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

Riga 13 ⟶ 15:

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|dataoriginale=1 marzo 1997|editore=McGraw-Hill Science|lingua=inglese|ISBN=0070428077}}</ref> dell'algoritmo ID3 per funzioni booleane (i cui valori sono qui indicati semplicemente con "+" e "-").

<syntaxhighlight>

Esempi:= istanze di addestramento.

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

Attributi:= lista di altri attributi.

ID3 (Esempi, Attributo_corrente, 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 della funzione 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 obiettivo più comune tra gli esempi.

Altrimenti

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

Restituisci Radice.

</syntaxhighlight>

=== 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, assegniamo al nodo la distribuzione di probabilità p tale che p(yes)=2/3 e p(no)=1/3.

== Note ==

<references />

== Voci correlate ==