E2_ML - QuickStart Exercises_Decision Tree.pdf

Definizioni

• Definizione: Definiamo soddisfacibilità quando un esempio $x$ soddisfa un’ipotesi $h$, evento indicato con

  $$ h(x) =1 $$

  a priori sul fatto che $x$ sia un esempio positivo o negativo del target concept. Si ha quindi che i valori $x$ soddisfano i vincoli $h$.

• Definizione: Si dice che $h$ è consistente con il traning set $D$ di concetti target sse:

  $$ \text{Consistent}(h, D) := h(x) = c(x), \ \ \forall (x, c(x)) \in D $$

Algoritmo generale per la costruzione di un albero

Vediamo quindi un algoritmo generale per la costruzione dell’albero:

1. si inizia con un albero vuoto
2. scelgo un attributo opportuno per fare lo split dei dati
3. per ogni split dell’albero:
   1. se non c’è altro da fare si fa la predizione con l’ultimo nodo foglia
   2. altrimenti si torna allo step 2 e si procede con un altro split.

Bisognerà capire:

• come fare in modo ottimizzato lo split
• quando fermare la costruzione (quindi capire quando “non c’è altro da fare”)

Esempio

Posso quindi usare una funzione di costo per fissare quando una distribuzione è omogenea (come nel caso di overcast) o quando no (gli altri due casi).

Lo split, infatti, andrebbe fatto in base ai valori del target, più sono omogenei e meglio è, in quanto nel momento in cui si presenta un nuovo test per la classificazione con outlook pari a overcast saprò già cosa fare (in quanto nello storico delle esperienze ho sempre avuto yer). Le altre due situazioni sono ambigue e quindi, in quei due casi, devo procedere con la costruzione dell’albero per ottenere informazioni cercando di rimuovere l’incertezza.

Gini Index