Algoritmo id3

De Wikipedia, la enciclopedia libre

Tienes mensajes nuevos (Dif. entre las dos últimas versiones).

El algoritmo ID3 es utilizado dentro del ámbito de la inteligencia artificial. Su uso se engloba en la búsqueda de hipótesis o reglas en él dado un conjunto de ejemplos.

El conjunto de ejemplos deberá estar conformado por una serie de tuplas de valores , cada uno de ellos denominados atributos , en el que uno de ellos ( el atributo a clasificar ) es el objetivo el cual es de tipo binario ( positivo o negativo , si o no , valido o invalido , etc )

De esta forma el algoritmo trata de obtener las hipótesis que clasifiquen ante nuevas instancias si dicho ejemplo va a ser positivo o negativo.

ID3 realiza esta labor mediante la construcción de un árbol de decisión.

Los elementos son:

Nodos : Los cuales contendrán atributos
Arcos : Los cuales contienen valores posibles del nodo padre.
Hojas : Nodos que clasifican el ejemplo como positivo o negativo.

[editar] El algoritmo

Id3(Ejemplos, Atributo-objetivo, Atributos )
   Si todos los ejemplos son positivos devolver un nodo positivo
   Si todos los ejemplos son negativos devolver un nodo negativo
   Si Atributos está vacío devolver el voto mayoritario del valor del atributo objetivo en Ejemplos
   En otro caso
        Sea Al Atributo el MEJOR de atributos
        Para cada v valor del atributo hacer
              Sea Ejemplos(v) el subconjunto de ejemplos cuyo valor de atributo A es v 
              Si Ejemplos(v) esta vacío devolver un nodo con el voto mayoritario del Atributo objetivo de Ejemplos
              Sino Devolver Id3(Ejemplos(v), Atributo-objetivo , Atributos/{A})

Observese que la construcción del árbol se hace forma recursiva, siendo las tres primeras líneas y la penúltima los casos base que construyen los nodos hojas.

[editar] Elección del mejor atributo

La elección del mejor atributo se establece mediante la entropía. Eligiendo aquel que proporcione una mejor ganancia de información. La función elegida puede variar , pero en forma más sencilla es como esta:

$- \left ( \frac{\left \vert p \right \vert}{\left \vert d \right \vert} \right ) \log_2 \left ( \frac{\left \vert p \right \vert}{\left \vert d \right \vert} \right ) - \left ( \frac{\left \vert n \right \vert}{\left \vert d \right \vert} \right ) \log_2 \left ( \frac{\left \vert n \right \vert}{\left \vert d \right \vert} \right )$

Donde p es el conjunto de los ejemplos positivos , n el de los negativos y d el total de ellos.

[editar] Un ejemplo

Ej.	Cielo	Temperatura	Humedad	Viento	Jugar tenis
D1	Sol	Alta	Alta	Débil	-
D2	Sol	Alta	Alta	Fuerte	-
D3	Nubes	Alta	Alta	Débil	+
D4	Lluvia	Suave	Alta	Débil	+
D5	Lluvia	Baja	Normal	Débil	+
D6	Lluvia	Baja	Normal	Fuerte	-
D7	Nubes	Baja	Normal	Fuerte	+
D8	Sol	Suave	Alta	Débil	-
D9	Sol	Baja	Normal	Débil	+
D10	Lluvia	Suave	Normal	Débil	+
D11	Sol	Suave	Normal	Fuerte	+
D12	Nubes	Suave	Alta	Fuerte	+
D13	Nubes	Alta	Normal	Débil	+
D14	Lluvia	Suave	Alta	Fuerte	-

En ese caso el árbol finalmente obtenido seriá así:

                           Cielo
                          /   |  \
                         /    |   \
                Soleado /  Nublado \ Lluvia
                       /      |     \
                      /       +      \
               Humedad               Viento
              /    \                  |   \
             /      \                 |    \
        Alta/        \ Normal  Fuerte |     \ Débil
           /          \               |      \
          -           +               -      +