Algoritmo Id3

ALGORITMO ID3 (Induction Decision Trees) En español "Inducción mediante árboles de
decisión" fue desarrollado por J. Ross Quinlan y pertenece a la familia TDIDT (TopDown
Induction of Decision Trees). Su uso se engloba en la búsqueda de hipótesis o reglas en él,
dado un conjunto de ejemplos.
Las métricas usadas en ID3
Entropía
Es una medida de la cantidad de incertidumbre en el conjunto (de datos) S (es decir, la

entropía caracteriza el conjunto (de datos) S).
Dónde,
S- El conjunto de datos actual para el que se calcula la entropía.
Esto cambia en cada paso del algoritmo ID3, ya sea a un subconjunto del conjunto anterior en
el caso de dividir en un atributo o a una partición "hermana" del padre en caso de que la
recursión haya terminado previamente.
X - El conjunto de clases en S
p(x)- La proporción del número de elementos en clase.x al número de elementos del conjunto
S
Cuándo {\displaystyle \mathrm {H} {(S)}=0}, el conjunto S está perfectamente clasificado (es
decir, todos los elementos en S son de la misma clase).
En ID3, la entropía se calcula para cada atributo restante. El atributo con la entropía más
pequeña se usa para dividir el conjuntoSen esta iteración. La entropía en la teoría de la
información mide cuánta información se espera obtener al medir una variable aleatoria ; como
tal, también se puede utilizar para cuantificar la cantidad a la que se desconoce la distribución
de los valores de la cantidad. Una cantidad constante tiene entropía cero, ya que su
distribución se conoce perfectamente . En contraste, una variable aleatoria distribuida
uniformemente ( discreta o continuamente uniforme) maximiza la entropía. Por lo tanto,
cuanto mayor es la entropía en un nodo, menos información se conoce sobre la clasificación
de los datos en esta etapa del árbol; y por lo tanto, mayor es el potencial para mejorar la
clasificación aquí.
Como tal, ID3 es una heurística codiciosa que realiza una búsqueda del mejor primero para los
valores de entropía óptimos localmente . Su precisión se puede mejorar procesando
previamente los datos.
Ganancia de información
Ganancia de información IG(A) es la medida de la diferencia en entropía desde antes hasta

después del conjunto S se divide en un atributo A. En otras palabras, ¿cuánta incertidumbre
enS se redujo después de dividir el conjunto S en atributo A.
{\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\
mathrm {H} {(S|A)}.}
Dónde,
{\displaystyle \mathrm {H} (S)} - Entropía de conjunto S
T - Los subconjuntos creados a partir del conjunto de división S por atributo A tal que S=\
bigcup _{{t\in T}}t
p(t) - La proporción del número de elementos en t al número de elementos del conjunto S
{\displaystyle \mathrm {H} (t)} - Entropía de subconjunto t
En ID3, la ganancia de información se puede calcular (en lugar de la entropía) para cada
atributo restante. El atributo con la mayor ganancia de información se utiliza para dividir el
conjunto.S en esta iteración.
General
Soleado Nublado Lluvioso
? P ?
General
Soleado Nublado Lluvioso
Humedad P Viento
Alta Normal No Si
N P P N
Primero analizamos el nodo raíz. Dado que hay ejemplos pertenecientes a clases, no es un
nodo terminal por lo cual se debe hallar el mejor atributo.
Calculamos primero a la entropía global sobre todos los ejemplos del nodo. Hay 9 P y 5 N
(Total = 14). Por lo tante aplicando la fórmula de la entropía seria.
Ahora*analizamos*los*difer
entes*atributos*disponibles:
**
Dado este resultado, el mejor atributo (el de mayor ganancia) es el atributo General y por ello
se elige como atributo para el nodo raíz del árbol. Ahora analizaremos los diferentes atributos
disponibles:
Dado este resultado, el*mejor*atributo*(el de mayor ganancia) es
el*atributo*General*y*por*ello*se*elige*como*atributo*para*el*nodo*raíz*del*árbol.
Primero*analizamos*el*nod
o*raíz.*Dado*que*hay*ejem
plos*pertenecientes*clases,*
no*es*nodo*
terminal*y*hay*que*encontr
ar*el*mejor*atributo
no*es*nodo*
no*es*nodo*
H globavl&= (−6/10 log26/10)*+*(−4/10*∗ log24/10)*=*0,*97*

Algoritmo Id3

Cargado por

Copyright:

Formatos disponibles

Algoritmo Id3

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Algoritmo Id3

Cargado por

Copyright:

Formatos disponibles

ALGORITMO ID3 (Induction Decision Trees) En español "Inducción mediante árboles de

Las métricas usadas en ID3

Es una medida de la cantidad de incertidumbre en el conjunto (de datos) S (es decir, la

S- El conjunto de datos actual para el que se calcula la entropía.

Ganancia de información IG(A) es la medida de la diferencia en entropía desde antes hasta

{\displaystyle \mathrm {H} (S)} - Entropía de conjunto S

p(t) - La proporción del número de elementos en t al número de elementos del conjunto S

{\displaystyle \mathrm {H} (t)} - Entropía de subconjunto t

Soleado Nublado Lluvioso

Soleado Nublado Lluvioso

También podría gustarte