In questa unità esplorerai l'algoritmo dello splitter più semplice e comune, che crea condizioni nel formato nella seguente impostazione:
- Attività di classificazione binaria
- Senza valori mancanti negli esempi
- Senza indice precalcolato negli esempi
Supponiamo di avere un insieme di esempi di con una caratteristica numerica e un'etichetta binaria"arancione" e "blu". Descrivi in modo formale il set di dati come:
dove:
- è il valore di una caratteristica numerica in (l'insieme di numeri reali).
- è un valore etichetta di classificazione binaria in {orange, blue}.
Il nostro obiettivo è trovare una soglia di valore (soglia) che dividendo gli esempi nei gruppi e secondo la condizione migliora la separazione delle etichette; ad esempio, più "arancia" esempi in e altri.
L'entropia di Shangon è una misura di disturbo. Per un'etichetta binaria:
- L'entropia Shannon è al massimo quando le etichette negli esempi sono bilanciate (50% blu e 50% arancione).
- L'entropia Shannon è minima (valore zero) quando le etichette negli esempi sono pure (100% blu o 100% arancione).
Figura 8. Tre diversi livelli di entropia.
Formalmente, vogliamo trovare una condizione che riduca la somma ponderata dell'entropia delle distribuzioni delle etichette in e . Il punteggio corrispondente è l'incremento delle informazioni, che è la differenza tra l'entropia di 's e l'entropia di $$TF$}. Questa differenza è chiamata aumento delle informazioni.
La figura seguente mostra una suddivisione errata, in cui l'entropia rimane alta e l'informazione diventa bassa:
Figura 9. Una suddivisione errata non riduce l'entropia dell'etichetta.
Al contrario, la figura seguente mostra una suddivisione migliore in cui l'entropia diventa bassa (e le informazioni diventano elevate):
Figura 10. Una buona suddivisione riduce l'entropia dell'etichetta.
Formalmente:
dove:
- è l'incremento delle informazioni dovuto alla suddivisione di in e .
- è l'entropia dell'insieme di esempi .
- rappresenta il numero di elementi nell'insieme .
- è il valore della soglia.
- è il valore dell'etichetta positiva, ad esempio ""blu". La scelta di un'etichetta diversa come "etichetta positiva" non cambia il valore dell'entropia o il guadagno relativo alle informazioni.
- è il rapporto tra i valori dell'etichetta positiva negli esempi .
- è il set di dati (come definito in precedenza in questa unità).
Nell'esempio seguente, consideriamo un set di dati di classificazione binari con una singola caratteristica numerica . La figura seguente mostra valori di soglia (asse x) diversi:
- L'istogramma dell'elemento .
- Il rapporto di "blu" esempi nei set , e si basa sul valore di soglia.
- L'entropia in , e .
- Le informazioni guadagnano, ovvero il delta entropia tra e {,} ponderato in base al numero di esempi.
Figura 11. Quattro grafici delle soglie.
Questi grafici mostrano quanto segue:
- La trama "Frequenza" mostra che le osservazioni sono relativamente ben distribuite con concentrazioni comprese tra 18 e 60. Un'ampia distribuzione dei valori significa che sono presenti molte suddivisioni potenziali, il che è utile per addestrare il modello.
Il rapporto di etichette "blu" nel set di dati è di circa il 25%. Il "rapporto di etichetta blu" indica che per valori di soglia compresi tra 20 e 50:
- Il set contiene un eccesso di esempi di etichette "blu" (fino al 35% per la soglia di 35).
- L'insieme di contiene un deficit complementare di "esempi" di colore blu (solo l'8% per la soglia 35).
Sia il "rapporto di etichette blu" che il "entropy" grafici indicano che le etichette possono essere relativamente ben separate in questo intervallo di soglia.
Questa osservazione è confermata nel grafico "Utili informazioni". Vediamo che il massimo guadagno di informazioni si ottiene con t~=28 per un valore di guadagno delle informazioni di circa 0,074. Pertanto, la condizione restituita dallo splitter sarà .
Le informazioni sono sempre positive o nulle. Converge a zero quando il valore della soglia converge verso il suo valore massimo / minimo. In questi casi, o diventano vuoti mentre l'altro contiene l'intero set di dati e mostra un'entropia uguale a quella in . Anche l'incremento delle informazioni può essere pari a zero quando = = . A soglia 60, i rapporti di "blu" le etichette di $$ corrispondono a $T
I valori candidati per nella serie di numeri reali () sono infiniti. Tuttavia, a fronte di un numero finito di esempi, ne esiste solo un numero limitato di divisioni da DTFt$ è significativo per il test.
Un approccio classico consiste nell'ordinare i valori xi in ordine crescente xs(i) in modo che:
Poi, prova per ogni valore a metà strada tra valori ordinati consecutivi di . Supponi, ad esempio,di avere 1000 valori in virgola mobile per una determinata caratteristica. Dopo l'ordinamento, supponiamo che i primi due valori siano 8,5 e 8,7. In questo caso, il primo valore di soglia da testare sarebbe 8,6.
Consideriamo formalmente i seguenti valori candidati per t:
La complessità temporale di questo algoritmo è con il numero di esempi nel nodo (a causa dell'ordinamento dei valori delle funzionalità). Se applicato a un albero decisionale, l'algoritmo Splitter viene applicato a ogni nodo e a ogni funzionalità. Tieni presente che ogni nodo riceve circa 1/2 degli esempi principali. Pertanto, secondo il teorema master, la complessità temporale dell'addestramento di un albero decisionale con questo splitter è:
dove:
- indica il numero di elementi.
- è il numero di esempi di addestramento.
In questo algoritmo, il valore delle caratteristiche non è determinante, è determinante solo l'ordine. Per questo motivo, questo algoritmo funziona indipendentemente dalla scalabilità o dalla distribuzione dei valori delle funzionalità. Questo è il motivo per cui non è necessario normalizzare o scalare le funzionalità numeriche durante l'addestramento di un albero decisionale.