Algoritmo ID3

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, si 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.

Contenido

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) esta 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:


- \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. se debe establecer si el logaritmo es positivo o negativo

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
           /          \               |      \
          -           +               -       +

Véase también

Bibliografía

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

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • ID3 — Para otros usos de este término, véase Algoritmo ID3. ID3 es un estándar de facto para incluir metadatos (etiquetas) en un archivo contenedor audiovisual, tales como álbum, título o artista. Se utiliza principalmente en ficheros sonoros como MP3 …   Wikipedia Español

  • Algoritmo de eliminación de candidatos — El algoritmo de eliminación de candidatos es utilizado dentro del ámbito de la inteligencia artificial. Su uso se engloba en la búsqueda de hipótesis o conceptos en él dado un conjunto de ejemplos de entrenamiento. Este algoritmo se puede… …   Wikipedia Español

  • Algoritmo de cobertura — El algoritmo de cobertura es utilizado dentro del ámbito de la inteligencia artificial. Su uso se engloba en la búsqueda de reglas en él dado un conjunto de ejemplos de entrenamiento. El objetivo del algoritmo de cobertura es la obtención de una… …   Wikipedia Español

  • Algoritmo find-s — El algoritmo find s es utilizado dentro del ámbito de la inteligencia artificial. Su uso se engloba en la búsqueda de hipótesis o conceptos en él dado un conjunto de ejemplos. El conjunto de ejemplos deberá estar conformado por una serie de… …   Wikipedia Español

  • Minería de datos — La minería de datos (DM, Data Mining) consiste en la extracción no trivial de información que reside de manera implícita en los datos. Dicha información era previamente desconocida y podrá resultar útil para algún proceso. En otras palabras, la… …   Wikipedia Español

  • Espacio de versiones — Saltar a navegación, búsqueda El espacio de versiones es un concepto del aprendizaje automático que representa el subconjunto de todas la hipótesis que son consistentes con los ejemplos de entrenamiento (Tom M. Mitchell 1997). Este conjunto… …   Wikipedia Español

  • Árbol de decisión — Un árbol de decisión es un modelo de predicción utilizado en el ámbito de la inteligencia artificial. Dada una base de datos se construyen diagramas de construcciones lógicas, muy similares a los sistemas de predicción basados en reglas, que… …   Wikipedia Español

  • Proceso de traducción de programas — Saltar a navegación, búsqueda Además de un traductor, se pueden necesitar otros programas para crear un programa objeto ejecutable. Un programa fuente se puede dividir en módulos almacenados en archivos distintos. La tarea de reunir el programa… …   Wikipedia Español

  • Compilador — «Compilación» redirige aquí. Para otras acepciones, véase recopilación. Diagrama a bloques de la operación de un buen compilador. Un compilador es un programa informático que traduce un programa escrito en un lenguaje de programación a otro… …   Wikipedia Español

  • ITunes — Saltar a navegación, búsqueda iTunes Desarrollador Apple Inc. www.apple.com Información general …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”