En teoría de la información y aprendizaje automático , la ganancia de información es sinónimo de divergencia 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 univariada de una variable de la distribución condicional de esta variable dada la otra. .
La ganancia de información de una variable aleatoria X obtenida a partir de la observación de una variable aleatoria A tomando valor se define
El valor esperado de la ganancia de información es la información mutua de X y A , es decir , la reducción de la entropía de X lograda al conocer el estado de la variable aleatoria A.
En el aprendizaje automático , este concepto se puede utilizar para definir una secuencia preferida de atributos a investigar para reducir más rápidamente el estado de X. Esta secuencia (que depende del resultado de la investigación de atributos previos en cada etapa) se denomina árbol de decisión y se aplica en el área del aprendizaje automático conocido como aprendizaje de árbol de decisión . Por lo general, se debe preferir un atributo con alta información mutua a otros atributos. [ ¿por qué? ]
En términos generales, la ganancia de información esperada es la reducción de la entropía de la información Η desde un estado anterior a un estado que toma cierta información tal como está dada:
¿Dónde está la entropía condicional de dado el valor del atributo ?
Esto es intuitivamente plausible cuando se interpreta la entropía Η como una medida de la incertidumbre de una variable aleatoria : al aprender (o suponer) sobre , nuestra incertidumbre sobre se reduce (es decir, es positiva), a menos que, por supuesto , sea independiente de , en cuyo caso , significa .
Sea T un conjunto de ejemplos de entrenamiento , cada uno de los cuales tiene 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 entropía de Shannon de la siguiente manera. Para un valor v tomado por el atributo a , sea
La información mutua es igual a la entropía total de un atributo si para cada uno de los valores del atributo se puede realizar una clasificación única para el atributo 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 y completos , 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 dada 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 de los valores de a .
Para comprender mejor la obtención de información, analicé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 alta entropía 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.
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 padre y los subnodos t L y t R son nodos secundarios. En este caso, el nodo principal t tiene una colección de muestras cancerosas y no cancerosas 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 decisión. 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 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 indica que se ha confirmado que es cancerosa, mientras que NC significa que no es cancerosa. Con estos datos, se puede crear un árbol de decisión con la ganancia de información utilizada para determinar las divisiones candidatas 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 2 ( p C,t ) + p NC,t log 2 ( 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 información obtenida comenzando con la mutación 1 es el siguiente:
Nota : será el mismo para todas las mutaciones en la raíz.
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 parecerían a 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 conocer los atributos de las mutaciones utilizadas para dividir el nodo. En un determinado nodo, cuando se produce la homogeneidad de los componentes 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.
Continuando, la entropía en los nodos secundarios izquierdo y derecho del árbol de decisión anterior se calcula mediante las fórmulas:
H( t L ) = −[ p C,L log 2 ( p C,L ) + p NC,L log 2 ( p NC,L )] [1]
H( t R ) = −[ p C,R log 2 ( p C,R ) + p NC,R log 2 ( 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 derecho , p C,R = n ( t R , C) / n ( t R ),
probabilidad de seleccionar una muestra de clase 'NC' en el nodo secundario derecho , 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 .
Usando estas fórmulas, H(t L ) y H(t R ) para la mutación 1 se muestran a continuación:
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 hijo correcto, P R = n ( t R ) / n ( t ),
Finalmente, H(s,t) junto con P L y P R para la mutación 1 son los siguientes:
Así, por definición de la ecuación (i):
(Ganancia de información) = H( t ) - H( s , t )
Después de todos los pasos, ganancia( s ), donde s es una división candidata para el ejemplo es:
El uso de este mismo conjunto de fórmulas con las otras tres mutaciones conduce a una tabla de 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 y agregar a los nodos secundarios. A la izquierda se muestra un árbol que describe la división.
Las muestras que están en el nodo izquierdo del árbol serían clasificadas como cancerosas por el árbol, mientras que las del derecho serían no cancerosas. Este árbol es relativamente preciso a la hora de clasificar las muestras que se utilizaron para construirlo (lo cual es un caso de sobreajuste ), pero aun así clasificaría la muestra C2 de forma incorrecta. Para remediar esto, el árbol se puede dividir nuevamente en los nodos secundarios para posiblemente lograr 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 utilizaron para los nodos anteriores. Entonces, 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.
_Example.png/1280px-Info_Gain_Splitting_the_Child_Node(s)_Example.png)
A partir de este nuevo , las divisiones candidatas se pueden calcular usando las mismas fórmulas que el nodo raíz:
Por lo tanto, 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 no la tengan 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, es posible que no sea necesario dividir un nodo en absoluto si es un conjunto puro , donde todas las muestras del nodo son simplemente cancerosas o no cancerosas. Dividir el nodo puede hacer que el árbol sea más inexacto y en este caso no se dividirá.
El árbol ahora alcanzaría una precisión del 100% si se probaran las muestras que se utilizaron para construirlo. Sin embargo, esto no es una buena idea, ya que el árbol sobreajustaría los datos. El mejor curso de acción es intentar probar el árbol en otras muestras, que no forman parte del conjunto original. A continuación se muestran dos muestras exteriores:
Siguiendo el árbol, NC10 se clasificó correctamente, pero C15 se clasificó como NC. Para otras muestras, este árbol ya no sería 100% exacto. Sin embargo, esto podría mejorarse con opciones como aumentar la profundidad del árbol o aumentar el tamaño del conjunto de entrenamiento.
La ganancia de información es el criterio básico para decidir si una característica debe usarse 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:
Aunque la obtención 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 adoptar una gran cantidad de valores distintos. Por ejemplo, supongamos que estamos construyendo un árbol de decisiones para algunos datos que describen a los clientes de una empresa. La obtención de información se utiliza a menudo para decidir cuáles de los atributos son los más relevantes, de modo que puedan probarse cerca de la raíz del árbol. Uno de los atributos de entrada podría ser el número de membresía 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 membresía 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 la de aquellos sin tantos valores distintos.
Para contrarrestar este problema, Ross Quinlan propuso elegir el atributo con mayor índice de ganancia de información entre los atributos cuya ganancia de información es promedio o superior. [5] Esto desvía el árbol de decisión para que no considere atributos con una gran cantidad de valores distintos, sin dar una ventaja injusta a los atributos con un valor de información muy bajo, ya que el valor de la información es mayor o igual a la ganancia de información. [6]
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/531fa7b5f713bf5e00d71c249f6a2e461737d1e7)
