arbol de decision
Páginas: 12 (2849 palabras)
Publicado: 11 de diciembre de 2014
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
deuna
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
de
una
determinada
heurística.
♦ Determinar las variables que portan
información relevante para la solución
del problema
♦ Establecer la secuencia dentro del árbolde decisión.
Inconveniente
♦ Favorece
indirectamente
a
aquellos
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
dondediferentes soluciones se alcanzan
con variables con los mismos valores
asociados.
♦ 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
deconclusiones
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
aproximaruna
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 de expresiones.
♦ 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án formados
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 Takeyas
Datos
• 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
unnodo 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 atributos dados.
• 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
♦ Entropía:
Ing. Bruno López Takeyas
Es
la
medida
de
la
incertidumbre que hay en un sistema. Es
decir, ante una determinada situación, la
probabilidad de que ocurra 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...
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
deuna
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
de
una
determinada
heurística.
♦ Determinar las variables que portan
información relevante para la solución
del problema
♦ Establecer la secuencia dentro del árbolde decisión.
Inconveniente
♦ Favorece
indirectamente
a
aquellos
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
dondediferentes soluciones se alcanzan
con variables con los mismos valores
asociados.
♦ 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
deconclusiones
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
aproximaruna
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 de expresiones.
♦ 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án formados
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 Takeyas
Datos
• 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
unnodo 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 atributos dados.
• 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
♦ Entropía:
Ing. Bruno López Takeyas
Es
la
medida
de
la
incertidumbre que hay en un sistema. Es
decir, ante una determinada situación, la
probabilidad de que ocurra 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...
Leer documento completo
Regístrate para leer el documento completo.