Inducción de Árboles de Decisión

Inducción de Árboles de Decisión - Page 1
Inducción de Árboles de Decisión - Page 2
Inducción de Árboles de Decisión - Page 3
Inducción de Árboles de Decisión - Page 4
Inducción de Árboles de Decisión - Page 5

Esto es sólo una vista previa del documento.

Descargar el documento original para ver más páginas

Descargar

1 de 62

Inducción de Árboles de Decisión


Documentos relacionados


PowerPoint Presentation Transcripciones

Inducción de Árboles de 
Decisión
ID3, C4.5
Inducción de árboles de decisión 2
Contenido
1. Representación mediante árboles de decisión
2. Algoritmo básico: divide y vencerás
3. Heurística para la selección de atributos
4. Espacio de búsqueda y bias inductivo
5. Sobreajuste
6. Mejoras a ID3
7. Poda de árboles: C4.5
8. Interpretación geométrica aprendizaje con 
árboles
9. Conclusiones y ejemplos de aplicación
Inducción de árboles de decisión 3
1. Representación mediante 
árboles de decisión
 Descripción de instancias: pares 
atributo/valor
 Árbol de decisión
 Nodos no terminales: test
 Arcos: valores
 Nodos terminales: clase de decisión
 Clasificación instancias no vistas
 Recorrer árbol de decisión
Inducción de árboles de decisión 4
Árbol de decisión
Concepto: “Riesgo en la concesión de crédito”
Ingresos
Alto
0 a 2 2 a 5 más de 5
Historia Historia
Deuda Alto Moderado Bajo Moderado Bajo
Desconocida MalaBuena DesconocidaMala Buena
Alto Moderado
Alta Baja
Inducción de árboles de decisión 5
Espacio de hipótesis
 Si clase de decisión binaria
 Cada árbol de decisión representa una 
función booleana
 Espacio de hipótesis:
 Conjunto de todos los árboles de decisión o 
de todas las funciones booleanas
 Tamaño espacio de hipótesis
 Suponiendo atributos binarios
 n atributos
 |H|= 22
n 
funciones booleanas distintas
Inducción de árboles de decisión 6
Tarea inducción de árboles de 
decisión
 Dados
 Descripción de Instancias, X, (atributos, 
valores)
 Descripción de las Hipótesis, H (espacio de 
árboles de decisión)
 Concepto objetivo, c : X  {0,1}
 Ejemplos positivos y negativos, D, pares 
(<x, c(x)>)
 Determinar
 Hipótesis h de H / h(x) = c(x) para todo x
de X
Datos para aplicaciones de 
concesión de créditos
Nº Riesgo Historia Deuda Avales Ingresos
1 alto mala alta no 0 a 2M
2 alto desconocida alta no 2 a 5M
3 moderado desconocida baja no 2 a 5M
4 alto desconocida baja no 0 a 2M
5 bajo desconocida baja no más de 5M
6 bajo desconocida baja adecuados más de 5M
7 alto mala baja no 0 a 2M
8 moderado mala baja adecuados más de 5M
9 bajo buena baja no más de 5M
10 bajo buena alta adecuados más de 5M
11 alto buena alta no 0 a 2M
12 moderado buena alta no 2 a 5M
13 bajo buena alta no más de 5M
14 alto mala alta no 2 a 5M
7Inducción de árboles de decisión
Árbol de decisión
Historia
DeudaDeuda Avales
Desconocida
Mala Buena
Alto Avales
No AdecuadosAlta Baja
Alto Moderado Avales Bajo
Alta Baja
Ingresos Bajo
No Adecuados
Ingresos Bajo
No Adecuados
Alto Moderado Bajo Alto Moderado Bajo
0 a 2 0 a 22 a 5 2 a 5más de 5 más de 5
8Inducción de árboles de decisión
Inducción de árboles de decisión 9
Árbol de decisión “más simple”
Ingresos
Alto
0 a 2 2 a 5 más de 5
Historia Historia
Deuda Alto Moderado Bajo Moderado Bajo
Desconocida MalaBuena DesconocidaMala Buena
Alto Moderado
Alta Baja
2. Algoritmo básico: divide y vencerás
Inducción analítica (top-down) de árboles de decisión
PROCEDIMIENTO Inducir_Arbol(Ejemplos, Atributos)
BEGIN
SI todos los elementos de Ejemplos pertenecen a la misma clase
ENTONCES devolver un nodo hoja con la clase;
SINO SI Atributos está vacío
ENTONCES devolver nodo hoja con disyunción de clases de Ejemplos;
SINO SI Ejemplos está vacío
ENTONCES devolver un nodo hoja etiquetado “desconocido”;
SINO BEGIN
seleccionar un atributo A como raíz del árbol actual;
eliminar A de Atributos;
PARA CADA valor V de A,
BEGIN
crear una rama del árbol etiquetada con V;
sea particion_V elementos de Ejemplos con valor V en atributo A;
colocar rama V resultado de Inducir_Arbol(particion_V, Atributos);
END;
END;
END 10Inducción de árboles de decisión
Inducción de árboles de decisión 11
3. Heurística para la selección de 
atributos
 ¿Atributo más útil para la clasificación?
 Elegir atributo cuyo conocimiento 
aporte mayor información desde la 
perspectiva de clasificación
 Quinlan, ID3 y sucesores: heurística 
basada en teoría de información
Inducción de árboles de decisión 12
Selección de atributos
 ¿Qué atributo es mejor?
atributo A atributo B
6+, 4- 6+, 4-
5+, 1- 1+, 3- 3+, 1- 3+, 3-
Inducción de árboles de decisión 13
Fundamentos teoría información
 Universo mensajes 
M={m1, m2...  ...mn}
con probabilidad p(mi), i=1,2...   ...n
 Información que aporta la recepción de 
un mensaje
I(M)=-
i=1
n
p(mi)log2(p(mi))
Inducción de árboles de decisión 14
Heurística teoría información
 Considerar la clasificación obtenida por un árbol como 
un mensaje
 Estimar el contenido de información a priori, I(D) 
 contenido de información de un mensaje que proporciona la 
clasificación de un ejemplo del conjunto de entrenamiento, D, 
sin conocer el valor de sus atributos
 Estimar el contenido de información a posteriori, o 
resto, Resto(A)
 Como antes, pero una vez conocido el valor del atributo A
 Seleccionar el atributo A que maximice la ganancia de 
información
 Ganancia(D, A) = I(D) – Resto(A)

© 2016 - 2017 Docmia. Todos los derechos reservados.