Selección de atributos relevantes usando la entropía de Shannon

Hoy en día, la detección de amenazas está cada vez más ligada al aprendizaje automático. Si queremos que un IDS o un antivirus pueda lidiar con amenazas nuevas, además de métodos heurísticos, hay que recurrir técnicas de clasificación, una parte importante de la IA. En los problemas de clasificación, una de las tareas a la que nos enfrentamos es seleccionar aquellos atributos que mejor describen la variable objetivo. Esto es, elegir aquellos atributos que aportan más información y tienen mayor correlación con la variable explicada. Por ejemplo, si queremos establecer la probabilidad de que alguien padezca cáncer de pulmón o no, una variable que va a ser muy significativa es si es fumadora. En el otro extremo, el color de los ojos de la persona, por poner un ejemplo muy claro, no aporta información relevante.



Por desgracia, no siempre es tan obvia la cantidad de información que aporta un atributo, así que vamos a ver un método relativamente sencillo de medirlo.

En 1948, Claude Shannon -la fotografía de arriba es un grafitti con su retrato- publicó un artículo llamado A Mathematical Theory of Communication donde introducía el concepto de entropía en el contexto de la teoría de la información (de la que Shannon es padre). Simplificando mucho, la entropía es una medida del desorden de un conjunto datos, y se define como:

\[H(X) = -\sum_{i}^{n} p_i \times \log_2(p_i)\]

Donde pi es la probabilidad relativa de aparición de la propiedad i en el conjunto de datos. Por ejemplo, p1 podría ser la probabilidad de tener cáncer de pulmón y p2 la probabilidad de no tenerlo.

Para entenderlo mejor vamos a ir viéndolo con un ejemplo práctico en R. Vamos a usar el conjunto de datos Titanic incluido en R. Carguemos el conjunto de datos y veamos cuáles son sus atributos:

> data(Titanic)
> dimnames(Titanic)
$Class
[1] "1st"  "2nd"  "3rd"  "Crew"

$Sex
[1] "Male"   "Female"

$Age
[1] "Child" "Adult"

$Survived
[1] "No"  "Yes"

> margin.table(Titanic)
[1] 2201

Así pues, tenemos un conjunto de datos de 2201 pasajeros del Titanic que dispone de tres atributos o variables independientes que son:
- La clase en la que viajaba cada persona que puede tomar los valores: primera, segunda, tercera y tripulación.
- El sexo: Hombre o mujer.
- La edad: Niño o adulto.

Tenemos una cuarta variable, que en este caso será nuestra variable explicada o dependiente, que nos dice si la persona sobrevivió o no al hundimiento del barco.
Así pues, nuestro objetivo es encontrar alguna relación entre los atributos antes mencionados y la probabilidad de que un pasajero sobreviva o no al naufragio.

Intuitivamente podemos pensar que el índice de mujeres y niños supervivientes debe ser mayor que el de los hombres por aquello de "las mujeres y los niños primero". Vemos si es cierto.

> margin.table(Titanic, c(2,4))
Survived
Sex        No  Yes
Male   1364  367
Female  126  344

Parece que, en efecto, las mujeres tenían más tendencia a sobrevivir que los hombres. Veámoslo gráficamente.


A ver los niños:

> margin.table(Titanic,c(3,4))
       Survived
Age       No  Yes
  Child   52   57
  Adult 1438  654


Parece que aquí la cosa ya no está tan clara. ¿Y qué ocurre con la clase en la que viajaba el pasajero?

> margin.table(Titanic,c(1,4))
      Survived
Class   No Yes
  1st  122 203
  2nd  167 118
  3rd  528 178
  Crew 673 212


Se observa también cierta correlación (a los de primera parece que les fue algo mejor) pero no tan clara como con el sexo.

Vamos a tratar de medir, usando el concepto de entropía de Shannon, qué cantidad de información aporta cada una de las tres variables independientes.

Calculamos la entropía del conjunto de datos respecto a la variable explicada Survived.
p1 -> No sobrevive.
p2 -> Sobrevive.

Comenzamos calculando las probabilidades de p1 y p2.

> p<-margin.table(Titanic, c(4))
> p.norm<-p/sum(p)
> p.norm
Survived
No      Yes 
0.676965 0.323035 

Así pues, tenemos que:
p1 = 0.676965
p2 = 0.323035

Con las probabilidades ya calculadas, nos resta hacer el sumatorio según la fórmula de Shannon.

> entropia<-(-sum(log2(p.norm)*p.norm))
> entropia
[1] 0.9076514

Lo que nos dice este valor es la medida de desorden de la variable explicada con un valor que va de 0 a 1. Un valor de 0 indica orden total, o lo que es lo mismo, o todos sobrevivieron o todos murieron, pero todos los valores son iguales. Cuanto más cerca esté de 1, mayor desorden. Un valor 1 querría decir que el 50% de pasajeros murieron y el otro 50% sobrevivió (hay que tener en cuenta que la entropía no es una función lineal).
Usaremos la notación H(survived) para nombrar la entropía producida por la variable survived. También vamos a definir el concepto de entropía condicionada a la entropía generada fijando, a priori, el valor de una segunda variable. Por ejemplo, H(survived | Sex) es la entropía de la variable survived condicionada al valor de la variable sexo. Se calcula con:

\[H(X|Y) = \sum_{i}^{n} p_x \times H(X|Y=y)\]

Px es la probabilidad relativa de aparición de la propiedad x en el conjunto de los datos en los que Y=y y H(X|Y=y) es la entropía de la propiedad y en el conjunto de los datos en los que Y=y.

Por ejemplo, tomemos el caso del sexo y calculemos H(Survived|Sex=Male) y H(Survived|Sex=Female).

La entropía para el caso de las mujeres la calculamos de la forma que ya conocemos.

> p<-margin.table(Titanic,c(2,4))
> p
Survived
Sex        No  Yes
Male   1364  367
Female  126  344

> p.male<-p[1,]
> p.female<-p[2,]

> p.female.norm<-p.female/sum(p.female)
> p.female.norm
       No       Yes 
0.2680851 0.7319149 
> entropia.female<-(-sum(log2(p.female.norm)*p.female.norm))
> entropia.female
[1] 0.8387034

Ahora calculamos la entropía para el caso de los hombres.

> p.male.norm<-p.male/sum(p.male)
> p.male.norm
       No       Yes 
0.7879838 0.2120162 
> entropia.male<-(-sum(log2(p.male.norm)*p.male.norm))
> entropia.male
[1] 0.745319

Finalmente, calculamos la entropía H(Survived|Sex) aplicando la fórmula de la entropía condicionada que acabamos de ver.

> p.sex<-margin.table(Titanic,2)
> p.norm.sex<-p.sex/sum(p.sex)
> p.norm.sex
Sex
     Male    Female 
0.7864607 0.2135393 
> entropia.sex<-entropia.male*as.numeric(p.norm.sex[1])+
   entropia.female*as.numeric(p.norm.sex[2])
> entropia.sex 
[1] 0.7652602

Así pues, ya podemos calcular la entropía, pero este valor por sí mismo tampoco nos aclara del todo el asunto de qué atributo aporta más información.

Vamos a definir, basándonos en la entropía, un nuevo concepto al que llamaremos ganancia de información como:

\[GI(X|Y) = H(X) - H(X|Y)\]

En este caso H(X) es la entropía de la variable explicada y H(X|Y) la entropía condicionada que acabamos de calcular.

La ganancia de información nos dice cómo se reduce la entropía cuando añadimos la nueva variable. Una mayor reducción implica una correlación mayor con la variable explicada. Calculémosla con los datos que ya tenemos:

> gi.sex=entropia-entropia.sex
> gi.sex
[1] 0.1423912

Analicemos qué ocurre con los otros dos atributos. Hacemos el cálculo para el atributo edad:

> p<-margin.table(Titanic,c(3,4))
> p.child<-p[1,]
> p.adult<-p[2,]
> p.child.norm<-p.child/sum(p.child)
> p.adult.norm<-p.adult/sum(p.adult)
> entropia.child<-(-sum(log2(p.child.norm)*p.child.norm))
> entropia.adult<-(-sum(log2(p.adult.norm)*p.adult.norm))
> p.age<-margin.table(Titanic,3)
> p.norm.age<-p.age/sum(p.age)
> entropia.age<-entropia.child*as.numeric(p.norm.age[1])+
   entropia.adult*as.numeric(p.norm.age[2])
> gi.age<-entropia-entropia.age
> gi.age
[1] 0.006410718

Y finalmente hacemos el cálculo para el atributo clase:

> p<-margin.table(Titanic,c(1,4))
> p.1st<-p[1,]
> p.2nd<-p[2,]
> p.3rd<-p[3,]
> p.crew<-p[4,]
> p.1st.norm<-p.1st/sum(p.1st)
> p.2nd.norm<-p.2nd/sum(p.2nd)
> p.3rd.norm<-p.3rd/sum(p.3rd)
> p.crew.norm<-p.crew/sum(p.crew)
> entropia.1st<-(-sum(log2(p.1st.norm)*p.1st.norm))
> entropia.2nd<-(-sum(log2(p.2nd.norm)*p.2nd.norm))
> entropia.3rd<-(-sum(log2(p.3rd.norm)*p.3rd.norm))
> entropia.crew<-(-sum(log2(p.crew.norm)*p.crew.norm))
> p.class<-margin.table(Titanic,1)
> p.norm.class<-p.class/sum(p.class)
> entropia.class<-entropia.1st*as.numeric(p.norm.class[1])+
   entropia.2nd*as.numeric(p.norm.class[2])+
   entropia.3rd*as.numeric(p.norm.class[3])+
   entropia.crew*as.numeric(p.norm.class[4])
> gi.class<-entropia-entropia.class
> gi.class
[1] 0.05928794

En resumen:
Ganancia de información para el sexo: 0.1423912
Ganancia de información para la edad: 0.006410718
Ganancia de información para la clase: 0.05928794

Esto significa que el atributo que más información aporta, con diferencia, es el sexo. La clase aporta bastante menos información, y la edad apenas nada.
En la práctica, esto significa que al construir nuestro modelo predictivo, podríamos descartar tranquilamente el atributo edad sin miedo a peder capacidad predictiva.

Me ha parecido más didáctico desarrollar manualmente los cálculos, sin embargo R ya dispone de un paquete para el cálculo de la entropía de Shannon que nos facilitará sin duda la vida.

No hay comentarios:

Publicar un comentario