Splitter esatto per classificazione binari con caratteristiche numeriche

In questa unità esplorerai l'algoritmo dello splitter più semplice e comune, che crea condizioni nel formato $\mathrm{feature}_i \geq t$ 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 $n$ con una caratteristica numerica e un'etichetta binaria"arancione" e "blu". Descrivi in modo formale il set di dati $D$ come:

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

dove:

• $x_i$ è il valore di una caratteristica numerica in $\mathbb{R}$ (l'insieme di numeri reali).
• $y_i$ è un valore etichetta di classificazione binaria in {orange, blue}.

Il nostro obiettivo è trovare una soglia di valore $t$ (soglia) che dividendo gli esempi $D$ nei gruppi $T(rue)$ e $F(alse)$ secondo la condizione $x_i \geq t$ migliora la separazione delle etichette; ad esempio, più "arancia" esempi in $T$ 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 $T$ e $F$. Il punteggio corrispondente è l'incremento delle informazioni, che è la differenza tra l'entropia di $D$'s e l'entropia di $$T$,$F$}. 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:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

dove:

• $IG(D,T,F)$ è l'incremento delle informazioni dovuto alla suddivisione di $D$ in $T$ e $F$.
• $H(X)$ è l'entropia dell'insieme di esempi $X$.
• $|X|$ rappresenta il numero di elementi nell'insieme $X$.
• $t$ è il valore della soglia.
• $pos$ è 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.
• $R(X)$ è il rapporto tra i valori dell'etichetta positiva negli esempi $X$.
• $D$ è 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 $x$. La figura seguente mostra valori di soglia $t$ (asse x) diversi:

1. L'istogramma dell'elemento $x$.
2. Il rapporto di "blu" esempi nei set $D$, $T$ e $F$ si basa sul valore di soglia.
3. L'entropia in $D$, $T$ e $F$.
4. Le informazioni guadagnano, ovvero il delta entropia tra $D$ e {$T$,$F$} 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 $T$ contiene un eccesso di esempi di etichette "blu" (fino al 35% per la soglia di 35).
  • L'insieme di $F$ 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à $x \geq 28$.

• 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, $F$ o $T$ diventano vuoti mentre l'altro contiene l'intero set di dati e mostra un'entropia uguale a quella in $D$. Anche l'incremento delle informazioni può essere pari a zero quando $H(T)$ = $H(F)$ = $H(D)$. A soglia 60, i rapporti di "blu" le etichette di $$ corrispondono a $T

I valori candidati per $t$ nella serie di numeri reali ($\mathbb{R}$) sono infiniti. Tuttavia, a fronte di un numero finito di esempi, ne esiste solo un numero limitato di divisioni da D$ a $T$ e $F$. Pertanto, solo un numero finito di valori di $t$ è significativo per il test.

Un approccio classico consiste nell'ordinare i valori x_i in ordine crescente x_s(i) in modo che:

$$ x_{s(i)} \leq x_{s(i+1)} $$

Poi, prova $t$ per ogni valore a metà strada tra valori ordinati consecutivi di $x_i$. 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:

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

La complessità temporale di questo algoritmo è $\mathcal{O} ( n \log n) $ con $n$ 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 è:

$$ \mathcal{O} ( m n \log^2 n ) $$

dove:

• $m$ indica il numero di elementi.
• $n$ è 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.