Disminución de Gini e impureza de Gini de los nodos hijos

Question

Estoy trabajando en la medida de importancia de la característica Gini para el bosque aleatorio. Por lo tanto, necesito calcular la disminución de Gini en la impureza del nodo. Aquí está la forma en que lo hago, lo que conduce a un conflicto con la definición, lo que sugiere que debo estar equivocado en alguna parte ... :)

Para un árbol binario, y dadas las probabilidades de los hijos de la izquierda y de la derecha, puedo calcular la impureza de Gini de un nodo $n$ :

$$ i(n) = 1 - p_l^2 - p_r^2$$

Y la disminución del Gini:

$$ \Delta i(n) = i(n) - p_li(n_l) - p_ri(n_r) $$

---

Así, para este ejemplo con 110 observaciones en un nodo:

- node (110)
   - left (100)
      - left_left (60)
      - left_right (40)
   - right (10)
      - right_left (5)
      - right_right (5)

Calcularía la disminución de Gini para nodo así :

\begin {align} i({ \rm izquierda}) &= 1 - (60/100)^² - (40/100)^²& &= 0,48 \\ i({ \rm derecha}) &= 1 - (5/10)^² - (5/10)^²& &= 0,50 \\ i({ \rm nodo}) &= 1 - (100/110)^² - (10/110)^²& &= 0,16 \end {align}

Pero siguiendo la definición de Breiman (o esta respuesta en CV: Cómo medir/clasificar la "importancia de las variables" cuando se utiliza CART pero no tengo acceso al libro de referencia), el criterio de impureza del descendiente debe ser menos que el nodo padre:

Importancia de Gini
Cada vez que se realiza una división de un nodo en la variable m, el criterio de impureza de gini para los dos nodos descendientes es menor que el del nodo padre. Sumando las disminuciones de gini para cada variable individual sobre todos los árboles del bosque se obtiene una importancia rápida de la variable que suele ser muy coherente con la medida de importancia de la permutación.

Porque de lo contrario, conduce a una disminución negativa de Gini...

$$\Delta i({\rm node}) = i({\rm node}) - (100/110)*i({\rm left}) - (10/110)*i({\rm right}) = -0.32$$

Así que, si alguien pudiera decir en qué me equivoco, se lo agradecería mucho porque parece que me falta algo evidente aquí...

Answer 1

Simplemente no se utiliza la variable de clase de destino en absoluto. La impureza de Gini, como todas las demás funciones de impureza, mide la impureza de los resultados después de una división. Lo que ha hecho es medir algo utilizando sólo el tamaño de la muestra.

Intento derivar la fórmula para su caso.

Supongamos, para simplificar, que tenemos un clasificador binario. Denotemos con $A$ el atributo de prueba, con $C$ el atributo de clase que tiene $c_+, c_-$ valores.

El índice de gini inicial antes de la división viene dada por $$I(A) = 1 - P(A_+)^2 - P(A_-)^2$$ donde $P(A_+)$ es la proporción de puntos de datos que tienen $c_+$ valor para la variable de clase.

Ahora, la impureza para el nodo izquierdo sería $$I(Al) = 1 - P(Al_+)^2-P(Al_-)^2$$ $$I(Ar) = 1 - P(Ar_+)^2-P(Ar_-)^2$$ donde $P(Al_+)$ es la proporción de puntos de datos del subconjunto izquierdo de $A$ que tienen valor $c_+$ en la variable de clase, etc.

Ahora la fórmula final de GiniGain sería

$$GiniGain(A) = I(A) - p_{left}I(Al) - p_{right}I(Ar)$$ donde $p_{left}$ es la proporción de instancias para el subconjunto de la izquierda, o $\frac{\#|Al|}{\#|Al|+\#|Ar|}$ (cuántas instancias hay en el subconjunto izquierdo dividido por el número total de instancias de $A$ .

Creo que mi anotación podría ser mejorada, lo miraré más tarde cuando tenga más tiempo.

Conclusión:

Utilizar sólo el número de puntos de datos no es suficiente, la impureza significa lo bien que una característica (característica de prueba) es capaz de reproducir la distribución de otra característica (característica de clase). La distribución de la característica de prueba produce el número que ha utilizado (cómo a la izquierda, cómo a la derecha), pero la distribución de la característica de la clase no se utiliza en sus fórmulas.

Edición posterior - demostrar por qué disminuye

Ahora me he dado cuenta de que me faltaba la parte que demuestra por qué siempre el índice de gini en el nodo hijo es menor que en el nodo padre. No tengo una prueba completa o verificada, pero creo que es una prueba válida. Para otras cosas interesantes relacionadas con el tema se puede comprobar Nota técnica: Algunas propiedades de los criterios de división - Leo Breiman . Ahora seguirá mi prueba.

Supongamos que estamos en el caso binario, y que todos los valores de un nodo pueden ser descritos completamente por un par $(a,b)$ con el significado de $a$ instancias de la primera clase, y $b$ instancias de la segunda clase. Podemos afirmar que en el nodo padre tenemos $(a,b)$ instancias.

Para encontrar la mejor división, ordenamos las instancias según una característica de prueba y probamos todas las divisiones binarias posibles. La ordenación por una característica determinada es en realidad una permutación de instancias, en la que las clases comienzan con una instancia de la primera clase o de la segunda. Sin perder la generalidad, supondremos que empieza con una instancia de la primera clase (si no es el caso tenemos una prueba espejo con el mismo cálculo).

La primera división que hay que intentar es la de la izquierda $(1,0)$ y en el derecho $(a-1,b)$ instancias. ¿Cómo se compara el índice de gini de esos posibles candidatos a nodos hijos de la izquierda y de la derecha con el nodo padre? Obviamente en el izquierdo tenemos $h(left) = 1 - (1/1)^2 - (0/1)^2 = 0$ . Así que en el lado izquierdo tenemos un valor de índice de Gini más pequeño. ¿Y el nodo de la derecha?

$$h(parent) = 1 - (\frac{a}{a+b})^2 - (\frac{b}{a+b})^2$$ $$h(right) = 1 - (\frac{a-1}{a+b})^2 - (\frac{b}{a+b})^2$$

Teniendo en cuenta que $a$ es mayor o igual que $0$ (ya que si no, ¿cómo podríamos separar una instancia de la primera clase en el nodo de la izquierda?) y después de la simplificación es sencillo ver que el índice de gini para el nodo de la derecha tiene un valor menor que para el nodo padre.

Ahora la etapa final de la prueba es nodo que al considerar todos los posibles puntos de división dictados por los datos que tenemos, nos quedamos con el que tiene el menor índice de gini agregado, lo que significa que el óptimo que elegimos es menor o igual que el trivial que probé que es menor. Lo que concluye que al final el índice de gini disminuirá.

Como conclusión final hay que señalar que aunque varios splits pueden dar valores mayores que el nodo padre, el que elijamos será el más pequeño entre ellos y también menor que el valor del índice de gini padre.

Espero que sea de ayuda.