Sdgs

Árboles de decisión
Marta Millán
martha.millan@correounivalle.edu.co

www.eisc.univalle.edu.co/cursos

Árboles de decisión
 

Función aprendida: árbol de decisión Árbol de decisión
Nodos internos: pruebas sobre un atributo  Ramas descendientes: valores del atributo  Nodos hoja: valaores de decisión posibles



Árboles representan: disyunción de conjunciones

Problemasaplicables
  
 

Instancias pares (atributo, valor) Función objetivo: valores discretos Datos de entrenamiento pueden tener errores Datos entrenamiento pueden tener faltantes Problemas declasificación

Algoritmo Básico


 

Buscar el atributo más importante: contribuye más a la clasificación de un ejemplo Busqueda greedy, top-down Entrada
 Conjunto de entrenamiento E  Atributode clase AC  Conjunto de atributos

Algoritmo Básico ID3
ID3(E,AC,Atributos)

Entrada: E, conjunto de ejemplos de entrenamiento Atributo de clase vj Conjunto de atributos A Salida: árbol dedecisión 1. Crear nodo Raíz 2. Si eE e(AC)= vj devuelva el árbol con un único nodo raíz etiquetado con vj
3. Si A=  devuelva un árbol con único nodo etiquetado con el valor más frecuente de V(AC)Algoritmo Básico
4. Calcule el atributo A que mejor clasifica a E y haga Raíz  A 5. Por cada valor posible vj V(A)
(a)Agregar una rama saliendo de la Raíz (b)Sea Ev, el conjunto de ejemplos quetienen valor vj en A (c)Si Ev = agregar a la rama un nodo hoja etiquetado con el valor más común de AC. En caso contrario, crear un subárbol resultado de ejecutar ID3( Ev, AC, Atributos -{A}) 6.Devolver Raíz

Ejemplos e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 e14

Estado soleado soleado nublado lluvioso lluvioso lluvioso nublado soleado soleado lluvioso soleado nublado nublado lluviosoAtributos Temperatura Humedad Caluroso alta Caluroso alta Caluroso alta Templado alta Fresco normal Fresco normal Fresco normal Templado alta Fresco normal Templado normal Templado normal Templado...