Arboles de decision

A continuación se describe la aplicaciónn del algoritmo de árbol de decisión ID3.

Se utiliza el dataset golf tomando Outlook, Temperature, Humidity, Windy como variables predictoras y PlayGolf como variable objetivo

1- Se calcula la entropia en la variable objetivo PlayGolf \[ E(S)=\sum_{i=1}^{C}-\mathit{p}{i}\log_{2}(p{i}) \] En el caso particular de una clasificación binaria (ejemplos positivos / negativos), la fórmula anterior queda: \[E(S)=-{P}log_{2}(P)-Nlog_{2}(N)\]

Donde:

N= 14

Opción	Cantidad (Q)	Probabilidad (Q/N)
yes	9	0.64
no	5	0.36

Entropy(PlayGolf)
=Entropy(5,9)
=Entropy(0.36,0.64)
=-(0.36*log2(0.36))-(0.64*log2(0.64))

[1] 0.9426832

¿Qué atributo crea las ramas más homogéneas y, por tanto, proporciona una ganancia de información mayor? Respondiendo a esta pregunta obtendríamos cuál sería la mejor pregunta posible en un determinado momento, para ello:

Se calcula la entropía del total. Se divide el conjunto de datos en función de los diferentes atributos. Se calcula la entropía de cada rama y se suman proporcionalmente las ramas para calcular la entropía del total:

E(T,X)=???c???Xp(c)E(Sc)

Se resta este resultado de la entropía original, obteniendo como resultado la Ganancia de Información (descenso de entropía) usando este atributo.

Gain(T,X)=E(T)???E(T,X)Gain(T,X)=E(T)???E(T,X)

El atributo con mayor Ganancia es selecciona como nodo de decisión.

Una rama con entropía 00 se convierte en una hoja (nodo-respuesta), ya que representa una muestra completamente homogénea, en la que todos los ejemplos tienen la misma clasificación. Si no es así, la rama debe seguir subdividiéndose con el fin de clasificar mejor sus nodos.

Atributo Outlook

Outlook	Yes	No	Cantidad (Q)
Sunny	3	2	5
Overcast	4	0	4
Rainy	2	3	5
		Total	14

=E(PlayGolf,Outlook)
=P(Sunny)*E(3,2)+P(Overcast)*E(4,0)+P(Rainy)*E(2,3)
E(3,2)=entropy(2/5,3/5)=-2/5log(2/5)-3/5log(3/5)=0.971
E(4,0)=entropy(1,0)=-1/5log(1)-1log(1)=0 
E(2,3)=entropy(3/5,2/5)=-3/5log(3/5)-2/5log(2/5)=0.971

=(5/14)*0.971 + (4/14)*0.0 +(5/14)* 0.971

[1] 0.6935714

Information gain: information before splitting - information after splitting ???

gain(Outlook ) = info([9,5]) - info([2,3],[4,0],[3,2]) = 0.940 - 0.693 = 0.247 bits

Information gain for attributes from weather data:

gain(Outlook ) = 0.247 bits

gain(Temperature ) = 0.029 bits

gain(Humidity ) = 0.152 bits

gain(Windy ) = 0.048 bits

http://www.cs.us.es/~fsancho/?e=104 http://accelera.uab.cat/help.php?file=advanced_markdown.html https://es.slideshare.net/marinasantini1/lecture-4-decision-trees-2-entropy-information-gain-gain-ratio-55241087