Algoritmo id3

Algoritmo ID3

Ing. Bruno López Takeyas

ALGORITMO ID3
♦ Desarrollado por J. Ross Quinlan en 1983. ♦ ID3 significa Induction Decision Trees. ♦ Pertenece a la familia TDIDT (TopDown Induction of Decision Trees).

Objetivo
♦ Construir un árbol de decisión que

explique cada instancia de la secuencia de entrada de la manera más compacta posible a partir de una tabla de inducción.http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo ID3

Ing. Bruno López Takeyas

♦ En cada momento elige el mejor atributo dependiendo heurística. ♦ Determinar las variables que portan información relevante para la solución del problema ♦ Establecer la secuencia dentro del árbol de decisión. de una determinada

Inconveniente
♦ Favorece indirectamente aaquellos

atributos con muchos valores, los cuales no tienen que ser los más útiles. ♦ Genera árboles de decisión a partir de ejemplos de partida.

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo ID3

Ing. Bruno López Takeyas

♦ Conflictos en la base de conocimientos donde diferentes soluciones se alcanzan con variables con los mismos valoresasociados. ♦ Manejo discreto de los valores de las variables (rangos para discretizar una variable continua). ♦ Generación de grandes árboles de

decisión que no representan garantía de reglas eficientes. ♦ Aplicables sólo a problemas de

clasificación y diagnóstico. ♦ La generación de conclusiones

intermedias se encuentra implícito en la generación de reglas a partir de la tabla de inducción(no se aprecia discriminación en el árbol de decisión).
http://www.itnuevolaredo.edu.mx/takeyas Email: takeyas@itnuevolaredo.edu.mx

Algoritmo ID3

Ing. Bruno López Takeyas

Características
♦ Crear un árbol de decisión como un método para aproximar una función objetivo de valores discretos, que es resistente al ruido en los datos y que es capaz de hallar o aprender de una disyunción deexpresiones. ♦ El resultado puede expresarse como un conjunto de reglas Si-entonces. ♦ Intenta encontrar el árbol más sencillo que separa mejor los ejemplos. ♦ Es recursivo. ♦ No se realiza “backtracking”. ♦ Utiliza la entropía.

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo ID3

Ing. Bruno López Takeyas

Estructura
Los árboles de decisión estánformados por:

♦ Nodos: Nombres o identificadores de los atributos. ♦ Ramas: Posibles valores del atributo asociado al nodo. ♦ Hojas: Conjuntos ya clasificados de ejemplos y etiquetados con el nombre de una clase.

Un ejemplo de árbol de decisión es el siguiente:

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo ID3

Ing. Bruno López TakeyasDatos
• Atributos: Son los factores que

influencian la clasificación o decisión. • La selección de atributos debe basarse en el conocimiento acumulado por la experiencia. • En este algoritmo cada atributo forma un nodo intermedio en un árbol cuyas hojas o nodos terminales son las clases o decisiones. • Clase: Posibles valores de solución • Ejemplos: Es el conjunto de combinaciones de atributosdados. • Dado el conjunto de ejemplos, el ID3 selecciona el atributo que subdivide los ejemplos de la mejor manera.

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo ID3

Ing. Bruno López Takeyas

♦ Entropía:

Es

la

medida

de

la

incertidumbre que hay en un sistema. Es decir, ante una determinada situación, la probabilidad de queocurra cada uno de los posibles resultados.

http://www.itnuevolaredo.edu.mx/takeyas

Email: takeyas@itnuevolaredo.edu.mx

Algoritmo ID3

Ing. Bruno López Takeyas

♦ La función de entropía más usada es la binaria. Su expresión es con logaritmos base 2:

I(p,n) = -(p/(p + n))*LOG2(p/(p + n))-(n/(p + n))*LOG2(n/(p + n))

Recuerde: Si 10x=1,000 Es decir, si … 10x=y Si 2x=y entonces x=3...