- 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:
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
- 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/
Categoría:- Algoritmos de clasificación
Wikimedia foundation. 2010.
