La entropía es el grado de desorden que irremediablemente tiende a crecer. Esta definición es aplicable en distintas disciplinas y se origina como parte del “segundo principio de la termodinámica” enunciado por Nicolas L. Sadi Carnot en 1.824. El término fue usado por primera vez por Rudolf J. E. Clausius en 1.864 en su nueva formulación del principio de Sadi Carnot. Fue formulado matematicamente por Ludwig Boltzmann, en 1.877 y adaptado en 1.948 por Claude E. Shannon en la teoría de la información.
La fórmula de Boltzmann: 
donde:
S es la entropía,
k la constante de Boltzmann
Ω el número de microestados posibles para el sistema
La ecuación asume que todos los microestados tienen la misma probabilidad de aparecer.
Shannon la introduce sugiriendo la siguiente fórmula:
Este índice mide el contenido de información por símbolo de un mensaje compuesto por, S clases de símbolos discretos cuyas probabilidades de ocurrencia son pi … pS. Donde H es la entropía en el sistema que es una medida de aleatoriedad. Habrá una aleatoriedad máxima en nuestro conjunto de datos si los resultados probables tienen la misma probabilidad de ocurrencia.
La entropía calcula la homogeneidad de una muestra. Si la muestra es completamente homogénea, la entropía es cero y si la muestra está dividida en partes iguales, tiene valor uno. En el gráfico se muestra la variación de la entropía con la probabilidad de una clase, la entropía es máxima cuando la probabilidad de cualquiera de las clases es igual. Cuando un algoritmo de decisión intenta dividir los datos, selecciona la variable que nos dará la máxima reducción en la entropía del sistema.
Por ejemplo, tomemos el siguiente conjunto de datos: Piloto, Continente y Circuito donde se corre un gran premio:
Queremos conocer quién es el mejor posicionado para ganar el campeonato del mundo tomando como identificador un solo atributo, en este caso tenemos tres posibilidades, piloto, continente o circuito. La variable piloto es la que nos interesa:
- Tenemos dos atributos y sus probabilidades: PJorge Lorenzo y PMarc Márquez.
- Tenenos un total de 17 carreras en el conjunto de datos, 9 carreras ganadas por Marc y 8 por Jorge
- Los valores de Pi serían, PMarc 9/17 y PJorge 8/17.
| Predictores / Atributo |
Objetivo | ||
| Piloto | Continente | Circuito | S/N |
| Jorge Lorenzo | Europa | Jerez | No |
| Jorge Lorenzo | Europa | Motorland Aragón | No |
| Jorge Lorenzo | Europa | Jerez | Si |
| Jorge Lorenzo | América | Las Américas | No |
| Jorge Lorenzo | Europa | Le Mans | Si |
| Jorge Lorenzo | Europa | Mugello | No |
| Jorge Lorenzo | Asia | Motegui | Si |
| Jorge Lorenzo | Asia | Sepang | No |
| Marc Márquez | Asia | Motegui | Si |
| Marc Márquez | Europa | Mugello | Si |
| Marc Márquez | Europa | Le Mans | No |
| Marc Márquez | Asia | Sepang | No |
| Marc Márquez | América | Termas de Río Hondo | Si |
| Marc Márquez | Europa | Ricardo Tormo | No |
| Marc Márquez | Europa | Jerez | Si |
| Marc Márquez | América | Termas de Río Hondo | No |
| Marc Márquez | Europa | Motorland Aragón | Si |
La tasa de éxito por el atributo piloto en el nodo principal es:
9/17 = 0,529 ≈ 0,53
8/17 = 0,470 ≈ 0,47
Aplicando la fórmula de Shannon tenemos :
– [ (0,53 * ln (0,53) + 0,47 * ln (0,47)] = 0,69 Entropía en el nodo padre.
En la primera división (hijos-hacia la izquierda) tenemos a Marc:
5/9 = 0,55 → Hi = – (0,55*ln(0,55) + 0,45*ln(0,45)) = 0,688
En la primera división (hijos-hacia la derecha) tenemos a Jorge:
3/8 = 0,37 → Hd = – (0,37*ln(0,37) + 0,63*ln(0,63)) = 0,659
La ganancia de información se basa en la disminución de la entropía después de que un conjunto de datos se divide en un atributo.
La ganancia después de dividir los datos por piloto es:
Entropía (padre) – Promedio ponderado de entropía de los hijos
0,69 – (9 * 0,68 + 8 * 0,65) / 17 = 0,015 Ganancia
Ratio de ganancia.
La ganancia está sesgada hacia los atributos con mayor número de valores posibles, para mejorar esta desviación se aplica RG (ratio de ganancia):
Ratio de ganancia = Ganancia / Información de la división
La ID (Información de la división) se puede definir como:
Donde:
- S es el conjunto de ejemplos de aprendizaje
- A es un atributo de los ejemplos
- v los posibles valores se A
Siguiendo con el ejemplo: RG = 0,015 / 0,69 = 0,0217.
Índice de Gini
Es otra métrica que se usa principalmente en CART, mide la impureza de una partición de datos. Originalmente fue un coeficiente desarrollado para medir el nivel de desigualdad entre los habitantes de un territorio, fue propuesto por Corrado Gini. Consiste en un índice entre 0 y 1, donde el 0 hace referencia a la igualdad completa, todos los habitantes disponen de los mismos ingresos, y cuando se registra un valor 1 se alcanza la desigualdad completa, en donde una sola persona cuenta con todos los ingresos.
Donde n es el número de clases y Pi la probabilidad de que una observación en K pertenezca a la clase. El índice de Gini supone una división binaria para cada uno de los atributos en S, digamos T1 y T2 . El índice de Gini de K está dado por:
El índice es la suma ponderada de cada una de las impurezas en los nodos divididos. La reducción de la impureza está dada por:
De manera similar a la relación entre RG y Ganancia, la división nos brinda la máxima reducción de impurezas en la división de nuestros datos.
El índice de Gini para el ejemplo es:
G(k) = 1 – (0,28027+ 0,22145) ≈ 0,49828
Para terminar el ejemplo aplicaríamos:
Ejemplo computacional.
El mayor uso diario que hacemos de la entropía es en la valoración de contraseñas. La fórmula cambia un poco pero es muy similar, el resultado se valora como nº de bits:
Entropía = log2(Ac) donde:
A es el alfabeto utilizado (cantidad de caracteres)
c es el número de caracteres que contiene la palabra.
? Pulsar sobre el gráfico para ampliar.
Es interesante que se observen los dos últimos cálculos. Las contraseñas, para los humanos, son tremendamente diferentes y la última de ellas difícil de memorizar, computacionalmente son idénticas. Tenedlo en cuenta para vuestra elección. No cuenta lo enrevesada que sea, sino la cantidad y el tamaño del alfabeto en el cual se basa.