¿Cómo se tratan exactamente los valores perdidos en los árboles de decisión?

Question

Cito las palabras de Tom M. Mitchell sobre este tema:

" Un segundo procedimiento, más complejo, consiste en asignar una probabilidad a cada uno de los posibles valores de A en lugar de limitarse a asignar el valor más común a A(x). Estas probabilidades pueden estimarse de nuevo a partir de las frecuencias observadas de los distintos valores de A entre los ejemplos del nodo n. Por ejemplo, dado un atributo booleano A, si el nodo n contiene seis ejemplos conocidos con A = 1 y cuatro con A = 0, entonces diríamos que la probabilidad de que A(x) = 1 es 0,6, y la probabilidad de que A(x) = 0 es 0,4. Un 0,6 fraccionario de la instancia x se distribuye ahora por la rama para A = 1, y un 0,4 fraccionario de x por la otra rama del árbol. Estos ejemplos fraccionarios se utilizan para calcular la ganancia de información y se subdividen en las siguientes ramas del árbol si hay que comprobar un segundo valor que falta. Este mismo fraccionamiento de ejemplos también puede aplicarse después del aprendizaje, para clasificar nuevas instancias cuyos valores de atributo se desconocen. En este caso, la clasificación de la nueva instancia es simplemente la clasificación más probable, calculada sumando los pesos de los fragmentos de instancia clasificados de diferentes maneras en los nodos hoja del árbol. Este método para tratar los valores de atributos que faltan se utiliza en el C4.5 (Quinlan 1993). "

Ahora, mis preguntas son:

1. ¿Cómo se utilizan estas fracciones de 0,6 y 0,4 para calcular la ganancia de información en los nodos situados más abajo en el árbol?
2. ¿Cómo se realizaría la subdivisión si faltara un segundo valor?
3. ¿Cómo se utilizaría exactamente este fraccionamiento para clasificar los nuevos ejemplos?

Answer 1

1. No encuentro la referencia, pero lo único sensato para mí es que funciona igual que cualquier ponderación de muestras: en la definición de entropía de la información $ -\sum_i p_i \log(p_i) $ donde normalmente $p_i=|C_i|/|C|$ tomamos los pesos totales en lugar de sólo los cardinales.

2. Lo único sensato de nuevo: los pesos son multiplicativos. Si un nodo tiene 0,4 de una fila, y esa fila necesita subdividirse de nuevo en una división 0,7 vs 0,3, entonces los hijos tienen esa fila con pesos 0,28 y 0,12.

3. Este parece bastante claro por su cita. Si la fila termina en cuatro hojas con pesos de 0,1, 0,2, 0,3, y 0,4, y esas hojas se clasifican como clase 1, 2, 3, 1, respectivamente, entonces la fila recibe un peso total para la clase 1 de 0,1 + 0,4, el peso de la clase 2 de 0,2, y el peso de la clase 3 de 0,3, y la clasificación final es la clase 1. (Hay otro enfoque razonable, creo, si usted toma el árbol para ser un clasificador suave en el primer lugar. En ese caso, tomarías las medias ponderadas de las probabilidades de las hojas).

---

He ejecutado un ejemplo a través de la implementación de weka de C4.5. No creo que conserve los cálculos de ganancia de información, así que no puedo confirmar (1), pero (2) y (3) son correctos. Estoy utilizando el conjunto de datos de cáncer de mama incorporado, con sólo las dos características node-caps et breast-quad (los dos únicos con valores ausentes). He desactivado la poda, pero sólo he aplicado divisiones binarias y he fijado en 10 el número mínimo de muestras de nodos de hoja para que el árbol sea pequeño. Para comprobar (2), también he tomado una fila con node-caps=missing , breast-quad=right_low y class=1 y eliminó su breast_quad ahora es la única fila que carece de ambas características. Configuro el modelo para evaluarlo en el conjunto de entrenamiento.

La primera división es en node-caps : hay 222 filas con esta característica =no, 56 =sí, y 8=falta. Las ponderaciones son las siguientes $56/278\approx 0.201$ et $0.799$ .
node-caps=no informa de la clase 0, 228,39 / 53,4. Que $228.39 \approx 222 + 8*0.799$ .
En cuanto a la $53.4$ tenemos que comprobar cuántos no y cuántos missing son de clase 1. Son 51 y 3, respectivamente, y de hecho $53.4 \approx 51 + 3*0.799$ .

Utilizando cálculos similares para el resto del árbol podremos comprobar (2). El nodo node-caps=yes no da un informe desde que se dividió, pero podemos calcular que mostraría $286-228.39=57.61$ et $85-53.4=31.6$ . Valdrá la pena comprobar más tarde que el 57,61 se compone de 18 muestras completas con breast-quad=left_up 38 muestras completas con breast-quad!=left_up y 8 muestras con peso 0,201 (de las cuales 3 tienen left_up , 4 no left_up y falta 1).
Ahora la segunda división de esta rama; me centraré en la de la derecha ya que informa de la clase positiva:
breast-quad!=left_up informa de la clase 1, 38,94 / 13,54. Hay 38 filas sin faltas en esta rama, 4 con node-caps falta pero breast-quad!=left_up y 1 con ambos rasgos ausentes. Por lo tanto, el peso total de las muestras que no faltan breast-quad es de 38,804; del mismo modo, en el lado izquierdo de la división, el peso es de 18,603. La fila a la que le faltan ambas características debería tener ahora el peso $0.201 * 38.804 / (38.804 + 18.603) \approx 0.136$ . Y de hecho $38.94 = 38.804+0.136$ .

Es más difícil de escribir de lo que esperaba.

Para (3) miramos la matriz de confusión para ver que 38 filas se clasificaron como clase positiva. Son las 38 filas sin ninguna falta en la hoja que acabamos de discutir. La fila a la que le faltan ambas características tiene un peso de 0,799 en la hoja de primer nivel, de 0,065 en la otra hoja de clase 0 y de 0,136 en la única hoja de clase 1. Las filas a las que sólo les falta node-caps también tienen un peso de 0,799 en la hoja de primer nivel y de 0,201 en alguna de las hojas de segundo nivel. Pero en cualquier caso domina el 0,799 y se asignan a la clase 0. Bueno, eso no ha sido convincente.

Vale, lo siento, pero ahora mismo no quiero volver a hacer los cálculos anteriores. Vamos a mantener todo eso, pero ahora cambiar la única fila que tiene breast-quad que faltan en el conjunto de datos original de node-caps=no a yes . Ahora las divisiones elegidas son las mismas, pero esta fila baja por la rama izquierda y su peso se divide entre las dos hojas de nivel dos. Aún así, el peso del hijo derecho es mayor, y ahora esta fila se clasifica como clase 1 (el total de la matriz de confusión es 39).