Attributi con molti valori negli alberi decisionali

Un altro problema frequente nella costruzione di un albero decisionale, è la presenza di attributi con molti valori.

In alcuni casi limite, un attributo assume tanti valori quanti sono gli esempi del training set.

Esempio. Ad esempio, nella scelta di un ristorante un attributo potrebbe essere il nome del ristorante. Ogni ristorante ha un nome diverso dagli altri. Tecnicamente sembra un attributo rilevante... ma non lo è.

Nella scelta dell'attributo più rilevante bisogna considerare questo aspetto.

In caso contrario, si rischia di costruire un albero decisionale complesso e inefficiente.

Come risolvere il problema?

Una soluzione consiste nel calcolare il guadagno informativo di un attributo, tenendo conto del costo necessario per ottenere l'informazione.

Un esempio pratico

In questo training set l'attributo X2 ha molti valori.

Ogni esempio ( riga ) della tabella ha un valore diverso nell'attributo X2.

la tabella del training set con l'attributo X2 con molti valori

Se calcolassi l'indice di Shannon Wiener per trovare l'attributo più rilevante, anche l'attributo X2 verrebbe selezionato.

Gli attributi X2, X6, X9 hanno il guadagno informativo più alto.

l'indice di Shannon Wiener

Nota. Le variabili X2, X6 e X9 hanno un guadagno informativo massimo V=1-H=1 perché l'indice di Shannon Wiener è zero (H=0).

Al momento non si riesce a capire quale attributo scegliere.

Tuttavia, scegliere uno o l'altro non è indifferente perché l'attributo X2 ha un valore differente a ogni esempio. E' quindi meno utile di X6 e X9.

la comparazione tra gli attributi

Viceversa, gli attributi X6 e X9 hanno un'informazione più discriminante perché quando X6 e X9 sono uguali a 1 in tre casi su tre y è uguale a 1.

Esempio pratico. L'attributo X2 potrebbe essere il nome del ristorante. L'attributo X6 la presenza di un parcheggio per i clienti del ristornate. L'attributo X9 un menù con prezzi economici. E' evidente che X6 e X9 influenzino la scelta del cliente di entrare nel ristorante molto più di X2.

Come fare a eliminare gli attributi con molti valori?

Una soluzione è il rapporto tra il valore dell'informazione (V) e la quantità di informazioni contenute nell'attributo.

Il calcolo di questo indice riduce l'importanza degli attributi con molti valori.

Esempio

Il rapporto tra il valore informativo V e la quantità di valori dell'attributo riduce l'importanza dell'attributo X2.

la scelta del valore migliore

Si tratta soltanto di una soluzione semplice (o banale) per rendere l'idea ma già abbastanza efficace.

In realtà, esistono molti altri metodi migliori. Tra questi c'è l'indice di guadagno ( gain ratio ).

Come calcolare l'indice di guadagno ( gain ratio )

Il gain ratio penalizza gli attributi con sottoinsiemi simili.

La formula dell'indice di guadagno di un attributo è la seguente:

l'indice di guadagno

Nota. Il denominatore della formula è detto Split Information. Misura la somiglianza dei sottoinsiemi generati dall'attributo e sfavorisce quelli con molti sottoinsiemi aventi la stessa cardinalità.

Ad esempio, l'attributo X2 ha otto valori diversi V={A,B,C,D,E,F,G,H}.

Il gain ratio di X2 è 0.33.

il calcolo del gain ratio

il gain ratio di X2

L'attributo X6 ha due valori diversi V={0,1}.

Il gain ratio di X6 è uguale a 1.

il calcolo del gain ratio di X6

L'attributo X9 ha due valori {0,1}.

Anche il gain ratio di X9 è uguale a 1.

il gain ratio di X9 è uguale a 1

Calcolando il gain ratio (GR) per tutti gli attributi ottengo la seguente tabella:

l'indice di guadagno degli attributi

Gli attributi X6 e X9 hanno il gain ratio più alto ( 1.00 ).

Pertanto, sono gli migliori attributi nella costruzione di un albero decisionale, quelli da selezionare prima degli altri.

L'attributo X2 si è invece ridimensionato a 0.33 ed è diventato un attributo secondario.

In questo modo si è risolto il problema dell'attributo con molti valori.

Svantaggi del gain ratio. Potrebbe comunque capitare che un attributo con molti valori sia realmente più significativo di altri. Il gain ratio lo penalizza a prescindere. Quindi, il gain ratio non risolve tutti i problemi della selezione dell'attributo ottimale. Ne risolve alcuni, ma ne potrebbe creare altri.

 


 

Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

FacebookTwitterLinkedinLinkedin
knowledge base

Libri di approfondimento

Decision tree

Esempi