Aprendizaje automático mediante árboles de decisión

Aprendizaje automático mediante árboles de decisión - Page 1
Aprendizaje automático mediante árboles de decisión - Page 2
Aprendizaje automático mediante árboles de decisión - Page 3
Aprendizaje automático mediante árboles de decisión - Page 4
Aprendizaje automático mediante á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 24

Aprendizaje automático mediante árboles de decisión


Documentos relacionados


Aprendizaje automático mediante árboles de decisión Transcripciones

Aprendizaje automático 
mediante árboles de 
decisión
Aprendizaje por inducción 
● Los árboles de decisión son uno de los métodos de aprendizaje inductivo más 
usado.
 Hipótesis de aprendizaje inductivo: cualquier hipótesis encontrada que 
clasifique un número suficientemente grande de ejemplos de entrenamiento 
clasificará otros ejemplos no observados.
 Razonamiento deductivo: partiendo de unas premisas se llega 
necesariamente a una conclusión. No aporta información nueva.
 Razonamiento abductivo: partiendo del conocimiento de unos efectos 
(síntomas) se llega a la causa (enfermedad)
● Se trata de aproximar una función desconocida a patir de ejemplos positivos y 
negativos de esa función. Esos ejemplos serán en realidad pares <x,f(x)>, 
donde x es el valor de entrada y f(x) el valor de la función aplicada a x. 
● Dado un conjunto de ejemplos de f, la inducción consiste en obtener una 
función h que aproxime f. A esta función h se la denomina hipótesis
Arboles de Decisión
● Pueden ser leídas como conjunto de reglas (en el caso de abajo 
tres)
● En un árbol de decisión cada nodo del árbol es un atributo 
(campo) de los ejemplos, y cada rama representa un posible valor 
de ese atributo
Humedad
Pronostico
Viento
No
SI
Si
Lluvioso
Cubierto
DebilFuerte
NoSi
Alta Normal
Soleado
Arboles de Decisión
● Problemas de clasificación apropiados
 Los ejemplos están representados por pares 
<atributo,valor>. Por ejemplo <Temperatura,alta> A 
ser posible los valores deben ser disjuntos <frío, 
caliente, templado>. Aún así se pueden manejar 
valores numéricos <Temperatura, [1º, 20º]
 La función de clasificación tiene valores de salida 
discretos, y a ser posible booleanos.
 Los patrones de ejemplo pueden contener errores, 
tanto por ruido presente en los ejemplos (errores en 
los valores) como errores en la clasificación de los 
ejemplos del conjunto de entrenamiento (recordemos 
que es un aprendizaje supervisado)
 Los ejemplos pueden contener atributos sin valor
Algoritmo ID3
 Propuesto por Quinlan en 1986
 Empieza por responder a la cuastión: ¿qué 
atributo debe ser la raíz del árbol? 
 Para ello se evalúa cada atributo usando un test 
estadístico para determinar cuán bien clasifica 
esos ejemplos (en realidad se determina el más 
representativo o el que mejor describe ese 
conjunto)
Algoritmo ID3
 Las medidas que se usan son:
 Entropía: introducida por Shannon en su teoría de la 
información
siendo p
j
 la proporción de ejemplos de clase C
j
 en el conjunto E
 Efectividad de un atributo para subdividir un conjunto 
de ejemplos en n subconjuntos (uno por cada posible 
valor de X): es el valor esperado de la entropía tras 
efectuar la partición,y se cacula como una suma 
ponderada de cada subconjunto E
i
S E =info E =−∑ j=1
k 
p j log2 p j
S E , X =infoE , X =∑i=1
n ∣E i∣
∣E∣
∗info E i
Algoritmo ID3
 Ganancia de información: propiedead estadística que 
mide cómo clasifica ese atributo a los ejemplos. 
• Elijo como nodo del árbol aquél que tenga mayor ganancia de 
información.
• Después expando sus ramas y sigo igual, pero considerando la 
nuava partición formada por el subconjunto de ejemplos que 
tienen ese valor para el atributo elegido.
ganancia E , X =info E −infoatribE , X 
Algoritmo ID3
● Interpretación de los parámetros
 Entropia: nº de bits necesarios para codificar un 
suceso. Cuanto más bits más información menos 
probable es un suceso. Es decir, al aparecer más 
cuando aparece aporta menos información al 
conjunto que cuando aparece un suceso más raro.
 Ganancia: Información del conjunto menos la que 
aporta el atributo X. Cuanto mayor sea menor es la 
cantidad de información que aporta X, es decir, es 
un suceso muy probable lo que implica que sea un 
buen candidato como atributo representativo del 
conjunto.
Ejemplo del algoritmo ID3
Pronóstico Temperatura Humedad Viento ¿Adecuado?
Soleado Alta Alta Flojo No
Soleado Alta Alta Fuerte No
Nublado Alta Alta Flojo Si
Lluvia Moderada Alta Flojo Si
Lluvia Baja Normal Flojo Si
Lluvia Baja Normal Fuerte No
Nublado Baja Normal Fuerte Si
Soleado Moderada Alta Flojo No
Soleado Baja Normal Flojo Si
Lluvia Moderada Normal Flojo Si
Soleado Moderada Normal Fuerte Si
Nublado Moderada Alta Fuerte Si
Nublado Alta Normal Flojo Si
Soleado Moderada Alta Fuerte No
Mejoras del ID3
● Mejoras de ID3 (1)
 Manejo de atributos de gran número de valores.
 Manejo de atributos con valores continuos.
 Manejo de valores desconocidos en algunos de los Atributos.
 El coste de conocer el valor de un atributo no es cte.:
 Ejemplo: Presión arterial v.s. Biopsia.
 Cuándo se debe parar de subdividir el árbol:
 Sobreajuste v.s. Poda.
 Los ejemplos vienen dados incrementalmente:
 Solución: Algoritmos incrementales ID4 e ID5.
● (1) La solución a muchas de estas cuestiones la incorpora el algoritmo C4.5 que constituye 
una extensión del algoritmo ID3.
Algoritmo C4.5
● Modificación propuesta por Quinlan para mejorar el 
algoritmo ID3
● Se basa en introducir una medida alternativa, el ratio de 
ganancia, definido por:
Donde
 El sistema C4.5 selecciona en cada nodo el 
atributo con mayor ratio de ganancia de 
información 
ratioE , X = ganancia E , X 
info part E , X 
info part E , X =−∑i=1
n ∣E i∣
E
∗log2
∣E i∣
E
Manejo de atributos con 
valores continuos
● Se ordenan los valores del atributo y se especifica la clase a la 
que pertenecen:
 Temperatura 40 48 60 72 80 90
 Adecuado No No Si Si Si No
● El objetivo es definir atributos discretos dividiendo el atributo 
continuo en intervalos, y dando valores booleanos.
● La división del intervalo se realiza basándose en un punto 
umbral, dividiéndolo así en 2 intervalos.
Manejo de atributos con 
valores continuos
● Otras posibilidades:
 Dividir en tantos subintervalos como puntos de corte tengamos.
 T<54, 54<T<85, T>85
Manejo de atributos con 
valores continuos
● Candidatos a valor umbral: valores para los cuales la clase 
cambia:
 (48+60)/2=54 -> T>54
 (80+90)/2=85 -> T>85
● Computo la ganancia respecto a cada valor y escojo el de 
mayor ganancia:
 G(T>54)=E([3+,3-])-4/6E([3+,1-])-2/6E([0+,2-])
 G(T>85)=E([3+,3-])-1/6E([0+,1-])-5/6E([3+,2-])
● Como el valor mayor es 54, los posibles valores del atributo 
pasan a ser: T>54={Verdadero, Falso}

© 2016 - 2017 Docmia. Todos los derechos reservados.