Separador exacto para la clasificación binaria con atributos numéricos

En esta unidad, explorarás el algoritmo divisor más simple y común, que crea condiciones con la forma $\mathrm{feature}_i \geq t$ en la siguiente configuración:

• Tarea de clasificación binaria
• Sin valores faltantes en los ejemplos
• Sin el índice calculado previamente en los ejemplos

Supón un conjunto de ejemplos de $n$ con un atributo numérico y una etiqueta binaria "naranja" y "azul". De manera formal, describamos el conjunto de datos $D$ de la siguiente manera:

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

Donde:

• $x_i$ es el valor de un atributo numérico en $\mathbb{R}$ (el conjunto de números reales).
• $y_i$ es un valor de etiqueta de clasificación binaria en {orange, blue}.

Nuestro objetivo es encontrar un valor de umbral $t$ (umbral) de tal manera que dividir los ejemplos $D$ en los grupos $T(rue)$ y $F(alse)$ de acuerdo con la condición $x_i \geq t$ mejore la separación de las etiquetas; por ejemplo, más ejemplos de $&$ en color azul.

La entropía de Shannon es una medida del trastorno. Para una etiqueta binaria:

• La entropía de Shannon está al máximo cuando las etiquetas en los ejemplos están equilibradas (50% de azul y 50% de naranja).
• La entropía de Shannon es como mínimo (valor cero) cuando las etiquetas de los ejemplos son puras (100% azul o 100% naranja).

Figura 8: Tres niveles de entropía diferentes.

 

De manera formal, queremos encontrar una condición que disminuya la suma ponderada de la entropía de las distribuciones de etiquetas en $T$ y $F$. La puntuación correspondiente es la ganancia de la información, que es la diferencia entre la entropía de $D$' y la entropía de {$T$,$F$}. Esta diferencia se denomina ganancia de la información.

En la siguiente figura, se muestra una división incorrecta, en la que la entropía permanece alta y la información gana baja:

Figura 9: Una división incorrecta no reduce la entropía de la etiqueta.

 

Por el contrario, la siguiente figura muestra una mejor división, en la que la entropía se vuelve baja (y la información gana alta):

Figura 10: Una buena división reduce la entropía de la etiqueta.

 

De manera formal:

\[\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}\]

Donde:

• $IG(D,T,F)$ es la ganancia de información que se obtiene al dividir $D$ en $T$ y $F$.
• $H(X)$ es la entropía del conjunto de ejemplos $X$.
• $|X|$ es la cantidad de elementos del conjunto $X$.
• $t$ es el valor del umbral.
• $pos$ es el valor de la etiqueta positiva, por ejemplo, "blue" en el ejemplo anterior. Elegir una etiqueta diferente como "etiqueta positiva" no cambia el valor de la entropía o la ganancia de información.
• $R(X)$ es la proporción de valores de etiquetas positivos en los ejemplos $X$.
• $D$ es el conjunto de datos (como se definió anteriormente en esta unidad).

En el siguiente ejemplo, consideramos un conjunto de datos de clasificación binaria con un único atributo numérico $x$. En la siguiente figura, se muestran los diferentes valores $t$ del umbral (eje x):

1. El histograma de la característica $x$.
2. La proporción de ejemplos de “azul” en los conjuntos $D$, $T$ y $F$ según el valor del umbral.
3. La entropía de $D$, $T$ y $F$.
4. La ganancia de información; es decir, el delta de entropía entre $D$ y {$T$,$F$} ponderado por la cantidad de ejemplos.

Figura 11: Cuatro trazados de umbral.

 

Estas representaciones muestran lo siguiente:

• El gráfico de frecuencia muestra que las observaciones están relativamente bien distribuidas con concentraciones entre 18 y 60. Una amplia distribución del valor significa que hay muchas divisiones potenciales, lo que es bueno para entrenar el modelo.

• La proporción de etiquetas &azules en el conjunto de datos es de aproximadamente el 25%. La proporción de la etiqueta azul indica que, para valores de umbral entre 20 y 50, se muestra lo siguiente:

  • El conjunto de $T$ contiene un exceso de ejemplos de etiquetas &azules (hasta el 35% para el umbral 35).
  • El conjunto de $F$ contiene un déficit complementario de ejemplos de etiquetas azules (solo el 8% para el umbral 35).

  Tanto la relación de etiquetas azules como la representación de entropía indican que las etiquetas se pueden separar relativamente bien en este rango de umbral.

• Esta observación se confirma en el trazado de “obtención de información”. Vemos que la ganancia máxima de información se obtiene con t~=28 para un valor de ganancia de información de ~0.074. Por lo tanto, la condición que muestra el divisor será $x \geq 28$.

• La ganancia de información siempre es positiva o nula. Convierte en cero cuando el valor límite converge hacia su valor mínimo / máximo. En esos casos, $F$ o $T$ se vacían mientras que el otro contiene el conjunto de datos completo y muestra una entropía igual a la de $D$. La ganancia de información también puede ser cero cuando $H(T)$ = $H(F)$ = $H(D)$. En el umbral 60, las relaciones de $T$ y cero son la misma información que $T $ y $0.

Los valores candidatos para $t$ en el conjunto de números reales ($\mathbb{R}$) son infinitos. Sin embargo, dada una cantidad finita de ejemplos, solo existe una cantidad finita de divisiones de $D$ en $T$ y $F$. Por lo tanto, solo una cantidad finita de valores de $t$ es significativo para probar.

Un enfoque clásico es ordenar los valores x_i en orden creciente x_s(i) de modo que:

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

Luego, prueba $t$ por cada valor intermedio entre valores consecutivos ordenados de $x_i$. Por ejemplo, supongamos que tienes 1,000 valores de punto flotante de un atributo en particular. Después de ordenar, supongamos que los dos primeros valores son 8.5 y 8.7. En este caso, el primer valor de umbral para probar sería 8.6.

Formalmente, tenemos en cuenta los siguientes valores de candidato para t:

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

La complejidad temporal de este algoritmo es $\mathcal{O} ( n \log n) $ y $n$ es el número de ejemplos en el nodo (debido a la clasificación de los valores de atributo). Cuando se aplica en un árbol de decisión, el algoritmo divisor se aplica a cada nodo y a cada función. Ten en cuenta que cada nodo recibe alrededor de la mitad de sus ejemplos superiores. Por lo tanto, según el teorema principal, la complejidad temporal del entrenamiento de un árbol de decisión con este divisor es la siguiente:

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

Donde:

• $m$ es la cantidad de funciones.
• $n$ es la cantidad de ejemplos de entrenamiento.

En este algoritmo, el valor de los atributos no importa; solo importa el orden. Por este motivo, este algoritmo funciona de forma independiente de la escala o la distribución de los valores de atributos. Es por eso que no necesitamos normalizar ni escalar los atributos numéricos cuando entrenamos un árbol de decisión.