Algoritmo ID3

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, sí o no, válido o inválido, 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.

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 A 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) está vacío devolver un nodo con el voto mayoritario del
                                                               Atributo objetivo de Ejemplos
               Sino Devolver Id3(Ejemplos(v), Atributo-objetivo, Atributos/{A})

Obsérvese 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.

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 su forma más sencilla es como esta:

Donde p es el conjunto de los ejemplos positivos, n el de los negativos y
d el total de ellos.
Se debe establecer si el logaritmo es positivo o negativo

Un ejemplo 

{| class="wikitable"
|-----
! 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 sería así:

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

Véase también 

 Algoritmo find-s
 Algoritmo de cobertura
 FOIL
 Árbol de decisión alternativo
 Algoritmo C4.5
 Entropía
 Teoría de la información

Bibliografía 

 Mitchell, T.M. Machine Learning (McGraw-Hill, 1997)

Enlaces externos 

 Seminarios - http://www2.cs.uregina.ca/
 Descripción y ejemplos - http://www.cise.ufl.edu/
 Descripción y ejemplos - http://www.cis.temple.edu/

 Machine learning decisión trees 
 ID3 and C4.5
 Implementación del algoritmo ID3 en lenguaje Ruby
 Decision wood

Algoritmos de clasificación