Ganancia de información (árbol de decisión)

Ganancia al observar otra variable aleatoria

En teoría de la información y aprendizaje automático , la ganancia de información es sinónimo de divergencia de Kullback-Leibler ; la cantidad de información obtenida sobre una variable aleatoria o señal al observar otra variable aleatoria. Sin embargo, en el contexto de los árboles de decisión, el término a veces se usa como sinónimo de información mutua , que es el valor esperado condicional de la divergencia de Kullback-Leibler de la distribución de probabilidad univariante de una variable a partir de la distribución condicional de esta variable dada la otra.

La ganancia de información de una variable aleatoria obtenida a partir de una observación de una variable aleatoria que toma valor se define como: ${\displaystyle X}$ ${\displaystyle A}$ ${\displaystyle A=a}$

$${\displaystyle IG_{X,A}{(X,a)}=D_{\text{KL}}{\left(P_{X}{(x|a)}\|P_{X}{(x|I)}\right)}}$$

es decir, la divergencia de Kullback-Leibler de (la distribución previa para ) de (la distribución posterior para dado ). ${\displaystyle P_{X}{(x|I)}}$ ${\displaystyle x}$ ${\displaystyle P_{X|A}{(x|a)}}$ ${\displaystyle x}$ ${\displaystyle a}$

El valor esperado de la ganancia de información es la información mutua de y ${\displaystyle I(X;A)}$ , es decir, la reducción en la entropía de lograda al aprender el estado de la variable aleatoria . ${\displaystyle X}$ ${\displaystyle A}$ ${\displaystyle X}$ ${\displaystyle A}$

En el aprendizaje automático, este concepto se puede utilizar para definir una secuencia preferida de atributos para investigar con el fin de delimitar más rápidamente el estado de X. Dicha secuencia (que depende del resultado de la investigación de los atributos anteriores en cada etapa) se denomina árbol de decisiones y, cuando se aplica en el área del aprendizaje automático, se conoce como aprendizaje de árboles de decisiones . Por lo general, se debe preferir un atributo con alta información mutua a otros atributos. ^{[ ¿Por qué? ]}

Definición general

En términos generales, la ganancia de información esperada es la reducción de la entropía de información Η desde un estado anterior a un estado que toma cierta información como dada:

${\displaystyle IG(T,a)=\mathrm {H} {(T)}-\mathrm {H} {(T|a)},}$

donde es la entropía condicional de dado el valor del atributo . ${\displaystyle \mathrm {H} {(T|a)}}$ ${\displaystyle T}$ ${\displaystyle a}$

Esto es intuitivamente plausible cuando se interpreta la entropía Η como una medida de incertidumbre de una variable aleatoria : al aprender (o asumir) acerca de , nuestra incertidumbre acerca de se reduce (es decir, es positiva), a menos que, por supuesto , sea independiente de , en cuyo caso , es decir , . ${\displaystyle T}$ ${\displaystyle a}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle IG(T,a)}$ ${\displaystyle T}$ ${\displaystyle a}$ ${\displaystyle \mathrm {H} (T|a)=\mathrm {H} (T)}$ ${\displaystyle IG(T,a)=0}$

Definición formal

Sea T un conjunto de ejemplos de entrenamiento , cada uno de la forma donde es el valor del atributo o característica del ejemplo e y es la etiqueta de clase correspondiente. La ganancia de información para un atributo a se define en términos de la entropía de Shannon de la siguiente manera. Para un valor v tomado por el atributo a , sea definido como el conjunto de entradas de entrenamiento de T para el cual el atributo a es igual a v . Entonces la ganancia de información de T para el atributo a es la diferencia entre la entropía de Shannon a priori del conjunto de entrenamiento y la entropía condicional . ${\displaystyle ({\textbf {x}},y)=(x_{1},x_{2},x_{3},...,x_{k},y)}$ ${\displaystyle x_{a}\in \mathrm {vals} (a)}$ ${\displaystyle a^{\text{th}}}$ ${\displaystyle {\textbf {x}}}$ ${\displaystyle \mathrm {H} (-)}$ $${\displaystyle S_{a}{(v)}=\{{\textbf {x}}\in T|x_{a}=v\}}$$ ${\displaystyle \mathrm {H} (T)}$ ${\displaystyle \mathrm {H} {(T|a)}}$

$${\displaystyle \mathrm {H} (T|a)=\sum _{v\in \mathrm {vals} (a)}{{\frac {|S_{a}{(v)}|}{|T|}}\cdot \mathrm {H} \left(S_{a}{\left(v\right)}\right)}.}$$

${\displaystyle IG(T,a)=\mathrm {H} (T)-\mathrm {H} (T|a)}$

La información mutua es igual a la entropía total para un atributo si para cada uno de los valores del atributo se puede hacer una clasificación única para el atributo de resultado. En este caso, las entropías relativas restadas de la entropía total son 0. En particular, los valores definen una partición de los datos del conjunto de entrenamiento T en subconjuntos mutuamente excluyentes e inclusivos , lo que induce una distribución de probabilidad categórica en los valores del atributo a . La distribución está dada . En esta representación, la ganancia de información de T dado a se puede definir como la diferencia entre la entropía de Shannon incondicional de T y la entropía esperada de T condicionada a a , donde el valor esperado se toma con respecto a la distribución inducida en los valores de a . ${\displaystyle v\in vals(a)}$ ${\textstyle P_{a}{(v)}}$ ${\textstyle v\in vals(a)}$ ${\textstyle P_{a}{(v)}:={\frac {|S_{a}{(v)}|}{|T|}}}$ $${\displaystyle {\begin{alignedat}{2}IG(T,a)&=\mathrm {H} (T)-\sum _{v\in \mathrm {vals} (a)}{P_{a}{(v)}\mathrm {H} \left(S_{a}{(v)}\right)}\\&=\mathrm {H} (T)-\mathbb {E} _{P_{a}}{\left[\mathrm {H} {(S_{a}{(v)})}\right]}\\&=\mathrm {H} (T)-\mathrm {H} {(T|a)}.\end{alignedat}}}$$

Otra perspectiva sobre la obtención de información, con un ejemplo

Para comprender mejor la ganancia de información, desglosémosla. Como sabemos, la ganancia de información es la reducción de la entropía de la información. ¿Qué es la entropía? Básicamente, la entropía es la medida de impureza o incertidumbre en un grupo de observaciones. En aplicaciones de ingeniería, la información es análoga a la señal y la entropía es análoga al ruido. Determina cómo un árbol de decisión elige dividir los datos. ^[1] La figura más a la izquierda a continuación es muy impura y tiene una entropía alta que corresponde a un mayor desorden y un menor valor de información. A medida que avanzamos hacia la derecha, la entropía disminuye y el valor de la información aumenta.

Diagrama de entropía ^[2]

Un árbol de decisiones simple

Ahora bien, está claro que la ganancia de información es la medida de cuánta información proporciona una característica sobre una clase. Visualicemos la ganancia de información en un árbol de decisión como se muestra a la derecha:

El nodo t es el nodo principal y los nodos secundarios t _L y t _R son nodos secundarios. En este caso, el nodo principal t tiene una colección de muestras de cáncer y de no cáncer denominadas C y NC respectivamente. Podemos utilizar la ganancia de información para determinar qué tan buena es la división de nodos en un árbol de decisiones. En términos de entropía, la ganancia de información se define como:

Para entender esta idea, comencemos con un ejemplo en el que creamos un conjunto de datos simple y queremos ver si las mutaciones genéticas podrían estar relacionadas con los pacientes con cáncer. Dadas cuatro mutaciones genéticas diferentes, así como siete muestras, el conjunto de entrenamiento para una decisión se puede crear de la siguiente manera:

En este conjunto de datos, un 1 significa que la muestra tiene la mutación (Verdadero), mientras que un 0 significa que la muestra no la tiene (Falso). Una muestra con C denota que se ha confirmado que es cancerosa, mientras que NC significa que no es cancerosa. Con estos datos, se puede crear un árbol de decisiones con ganancia de información utilizada para determinar las divisiones de candidatos para cada nodo.

Para el siguiente paso, la entropía en el nodo padre t del árbol de decisión simple anterior se calcula como:

H( t ) = −[ p _C,t log ₂ ( p _C,t ) + p _NC,t log ₂ ( p _NC,t )] ^[3]

dónde,

probabilidad de seleccionar una muestra de clase 'C' en el nodo t, p _C,t = n ( t, C) / n ( t ),

probabilidad de seleccionar una muestra de clase 'NC' en el nodo t, p _NC,t = n ( t, NC) / n ( t ),

n ( t ), n ( t, C) y n ( t, NC) son el número de muestras totales, muestras 'C' y muestras 'NC' en el nodo t respectivamente .

Usando esto con el conjunto de entrenamiento de ejemplo, el proceso para encontrar la ganancia de información comenzando con la mutación 1 es el siguiente: ${\displaystyle \mathrm {H} {(t)}}$

p _{C, t} = 4/7

pNC _{, t} = 3/7

${\displaystyle \mathrm {H} {(t)}}$= −(4/7  ×  logaritmo ₂ (4/7) + 3/7  ×  logaritmo ₂ (3/7)) = 0,985

Nota : será lo mismo para todas las mutaciones en la raíz. ${\displaystyle \mathrm {H} {(t)}}$

El valor relativamente alto de entropía (1 es el valor óptimo) sugiere que el nodo raíz es altamente impuro y los constituyentes de la entrada en el nodo raíz se verían como la figura más a la izquierda en el Diagrama de Entropía anterior . Sin embargo, un conjunto de datos de este tipo es bueno para aprender los atributos de las mutaciones utilizadas para dividir el nodo. En un nodo determinado, cuando se produce la homogeneidad de los constituyentes de la entrada (como se muestra en la figura más a la derecha en el Diagrama de Entropía anterior), el conjunto de datos ya no sería bueno para el aprendizaje. ${\displaystyle \mathrm {H} {(t)}=0.985}$

Continuando, la entropía en los nodos secundarios izquierdo y derecho del árbol de decisión anterior se calcula utilizando las fórmulas:

H( t _L ) = −[ p _{C, L} log ₂ ( p _{C, L} ) + p _{NC, L} log ₂ ( p _{NC, L} )] ^[1]

H( t _R ) = −[ p _{C, R} log ₂ ( p _{C, R} ) + p _{NC, R} log ₂ ( p _{NC, R} )] ^[1]

dónde,

probabilidad de seleccionar una muestra de clase 'C' en el nodo secundario izquierdo , p _C,L = n ( t _L , C) / n ( t _L ),

probabilidad de seleccionar una muestra de clase 'NC' en el nodo secundario izquierdo , p _NC,L = n ( t _L , NC) / n ( t _L ),

probabilidad de seleccionar una muestra de clase 'C' en el nodo secundario correcto , p _C,R = n ( t _R , C) / n ( t _R ),

probabilidad de seleccionar una muestra de clase 'NC' en el nodo secundario correcto , p _NC,R = n ( t _R , NC) / n ( t _R ),

n ( t _L ), n ( t _L , C) y n ( t _L , NC) son el número total de muestras, muestras 'C' y muestras 'NC' en el nodo secundario izquierdo respectivamente,

n ( t _R ), n ( t _R , C) y n ( t _R , NC) son el número total de muestras, muestras 'C' y muestras 'NC' en el nodo secundario derecho respectivamente .

Utilizando estas fórmulas, los valores H(t _L ) y H(t _R ) para la mutación 1 se muestran a continuación:

H( _t L ₎ = −(3/4  ×  log2 ( _3/4 ) + 1/4  ×  log2 (1/4)) = 0,811

H( _tR ) = −(1/3 _× log2 ( _1/3 ) + 2/3  ×  log2 (2/3)) =  0,918 

A continuación, la entropía promedio de los nodos secundarios debido a la división en el nodo t del árbol de decisión anterior se calcula como:

H( s , t ) = P _L H ( t _L ) + P _R H ( t _R )

dónde,

probabilidad de muestras en el hijo izquierdo, P _L = n ( t _L ) / n ( t ),

probabilidad de muestras en el niño correcto, P _R = n ( t _R ) / n ( t ),

Finalmente, H(s,t) junto con P _L y P _R para la mutación 1 es como sigue:

PL ₌ 4/7

PR ₌ 3/7

H( s, t ) = (4/7  ×  0,811) + (3/7  ×  0,918) = 0,857

Así, por definición de la ecuación (i):

(Ganancia de información) = H( t ) - H( s , t )

Después de todos los pasos, la ganancia ( s ), donde s es un candidato a dividir para el ejemplo es:

ganancia( s ) = 0,985 – 0,857 = 0,128

El árbol recién creado con el nodo raíz dividido en función de la mutación 3. La mutación 3 tuvo la mayor ganancia de información, por lo que se seleccionó como división.

El uso de este mismo conjunto de fórmulas con las otras tres mutaciones conduce a una tabla de las divisiones candidatas, clasificadas según su ganancia de información:

La mutación que proporciona la información más útil sería la mutación 3, por lo que se utilizará para dividir el nodo raíz del árbol de decisión. La raíz se puede dividir y todas las muestras se pueden pasar a través de ella y anexarlas a los nodos secundarios. A la izquierda se muestra un árbol que describe la división.

Las muestras que se encuentran en el nodo izquierdo del árbol se clasificarían como cancerosas por el árbol, mientras que las que se encuentran en el derecho no serían cancerosas. Este árbol es relativamente preciso a la hora de clasificar las muestras que se utilizaron para construirlo (lo que es un caso de sobreajuste ), pero seguiría clasificando incorrectamente la muestra C2. Para solucionar esto, el árbol se puede dividir de nuevo en los nodos secundarios para lograr posiblemente algo aún más preciso.

Para dividir el nodo correcto, se debe calcular nuevamente la ganancia de información para todas las posibles divisiones candidatas que no se usaron para los nodos anteriores. Por lo tanto, las únicas opciones esta vez son las mutaciones 1, 2 y 4.

Nota : esta vez es diferente, ya que solo hay cuatro muestras del niño correcto. ${\displaystyle \mathrm {H} {(t)}}$

PC _{, t} = 1/4

PNC _{, t} = 3/4

${\displaystyle \mathrm {H} {(t)}}$= -(1/4  ×  logaritmo ₂ (1/4) + 3/4  ×  logaritmo ₂ (3/4)) = 0,811

El árbol actualizado con el nodo secundario correcto dividido según la mutación 4.

A partir de este nuevo , las divisiones de candidatos se pueden calcular utilizando las mismas fórmulas que el nodo raíz: ${\displaystyle \mathrm {H} {(t)}}$

De esta forma, el hijo derecho se dividirá con la mutación 4. Todas las muestras que tengan la mutación se pasarán al hijo izquierdo y las que carezcan de ella se pasarán al hijo derecho.

Para dividir el nodo izquierdo, el proceso sería el mismo, excepto que solo habría 3 muestras para verificar. A veces, puede que no sea necesario dividir un nodo si es un conjunto puro , donde todas las muestras del nodo son cancerosas o no cancerosas. Dividir el nodo puede hacer que el árbol sea más impreciso y, en este caso, no se dividirá.

El árbol alcanzaría ahora una precisión del 100 % si se probaran las muestras que se usaron para construirlo. Sin embargo, esto no es una buena idea, ya que el árbol se ajustaría en exceso a los datos. La mejor opción es intentar probar el árbol con otras muestras que no formen parte del conjunto original. A continuación se muestran dos muestras externas:

Probando el árbol de decisión con dos nuevas muestras.

Siguiendo el árbol, NC10 se clasificó correctamente, pero C15 se clasificó como NC. Para otras muestras, este árbol ya no sería 100% preciso. Sin embargo, podría ser posible mejorar esto con opciones como aumentar la profundidad del árbol o aumentar el tamaño del conjunto de entrenamiento.

Ventajas

La ganancia de información es el criterio básico para decidir si se debe utilizar una característica para dividir un nodo o no. La característica con la división óptima , es decir, el valor más alto de ganancia de información en un nodo de un árbol de decisión, se utiliza como característica para dividir el nodo.

El concepto de función de ganancia de información se incluye en el algoritmo C4.5 para generar árboles de decisión y seleccionar la división óptima para un nodo del árbol de decisión. ^[1] Algunas de sus ventajas incluyen:

• Puede trabajar con variables continuas y discretas .
• Debido al factor –[p ∗ log(p)] en la definición de entropía que se indica más arriba, a los nodos de hoja con una pequeña cantidad de instancias se les asigna un peso menor y esto favorece la división del resto de los datos en grupos más grandes pero homogéneos. Y, por lo tanto, a medida que profundizamos en la profundidad del árbol, el conjunto de datos se vuelve más homogéneo. Este enfoque suele ser más estable y elige las características más impactantes en los nodos. ^[4]

Desventajas y soluciones

Aunque la ganancia de información suele ser una buena medida para decidir la relevancia de un atributo, no es perfecta. Un problema notable ocurre cuando la ganancia de información se aplica a atributos que pueden tomar una gran cantidad de valores distintos. Por ejemplo, supongamos que uno está construyendo un árbol de decisión para algunos datos que describen a los clientes de una empresa. La ganancia de información se utiliza a menudo para decidir cuáles de los atributos son los más relevantes, de modo que se puedan probar cerca de la raíz del árbol. Uno de los atributos de entrada podría ser el número de miembro del cliente, si es miembro del programa de membresía de la empresa. Este atributo tiene una alta información mutua, porque identifica de forma única a cada cliente, pero no queremos incluirlo en el árbol de decisión. Es poco probable que decidir cómo tratar a un cliente en función de su número de miembro se generalice a clientes que no hemos visto antes ( sobreajuste ). Este problema también puede ocurrir si las muestras que se están probando tienen múltiples atributos con muchos valores distintos. En este caso, puede provocar que la ganancia de información de cada uno de estos atributos sea mucho mayor que aquellos sin tantos valores distintos.

Para contrarrestar este problema, Ross Quinlan propuso elegir en cambio el atributo con la mayor tasa de ganancia de información entre los atributos cuya ganancia de información es promedio o superior. ^[5] Esto sesga el árbol de decisión en contra de considerar atributos con una gran cantidad de valores distintos, mientras que no da una ventaja injusta a los atributos con un valor de información muy bajo, ya que el valor de información es mayor o igual a la ganancia de información. ^[6]

Véase también

• Obtener información de manera más amplia
• Aprendizaje mediante árboles de decisión
• Contenido de la información , punto de partida de la teoría de la información y base de la entropía de Shannon
• Relación de ganancia de información
• Algoritmo ID3
  • Algoritmo C4.5
• Análisis sorprendente

Referencias

1. Larose, Daniel T. (2014). Descubrimiento de conocimiento en los datos: Introducción a la minería de datos . Hoboken, Nueva Jersey: Wiley . Págs. 174-179. ISBN. 9780470908747.
2. Gopalan, Bhuvaneswari (10 de diciembre de 2020). "¿Qué son la entropía y la ganancia de información? ¿Cómo se utilizan para construir árboles de decisión?". Numpy Ninja . Consultado el 28 de noviembre de 2021 .
3. Jothikumar, R. (2018). "Predicción de la longevidad de un paciente con ataque cardíaco mediante un algoritmo de clasificación C4.5 mejorado". Revista de investigación de farmacia y tecnología . 11 (5): 1951–1956. doi :10.5958/0974-360X.2018.00362.1.
4. "Aprendizaje automático: ¿Por qué usamos la ganancia de información en lugar de la precisión como criterio de división en el árbol de decisiones?". Data Science Stack Exchange . Consultado el 9 de diciembre de 2021 .
5. Quinlan, J. Ross (1986). "Inducción de árboles de decisión". Aprendizaje automático . 1 (1): 81–106. doi : 10.1007/BF00116251 .
6. Milman, Oren (6 de agosto de 2018). "¿Cuál es el rango de la relación de ganancia de información?". Stack Exchange . Consultado el 9 de octubre de 2018 .

Lectura adicional

• Nowozin, Sebastion (18 de junio de 2012). "Estimaciones mejoradas de ganancia de información para la inducción de árboles de decisión". arXiv : 1206.4620v1 .
• Shouman, Mai (2011). "Uso de árboles de decisión para diagnosticar pacientes con enfermedades cardíacas" (PDF) . Actas de la Novena Conferencia de Minería de Datos de Australasia . 121 : 23–30.
• Mitchell, Tom M. (1997). Aprendizaje automático. The Mc-Graw-Hill Companies, Inc. ISBN 978-0070428072.