InCo2017-Arboles_A4

Vista previa del material en texto

TEMA: Árboles de decisión
Conceptualización
Índice
1. Árboles de Decisión. 1
2. Árboles de Decisión en Clasificación. 2
3. Próxima Clase 4
4. Bibliografía 4
1. Árboles de Decisión.
Árboles de Decisión.
Es una técnica que permite analizar decisiones secuenciales basadas en el uso de resultados y probabilidades
asociadas. Nos ayudan a tomar la decisión más acertada, desde un punto de vista probabilístico, ante un abanico
de posibles decisiones.
Partes del Árbol.
Partes de un árbol de decisión.
Ejemplo de un árbol de decisión: Administrar el fármaco X?
1
Un ejemplo ejemplo de un árbol de decisión.
2. Árboles de Decisión en Clasificación.
Árboles de Decisión en Clasificación.
Los árboles de decisión son ampliamente utilizados en tareas de clasificación.
Son fáciles de comprender.
Se tiende a confiar más en ellos que en otros métodos.
Algoritmo ID3.
Se aplica una estrategia de búsqueda top-down, del tipo greedy en el espacio de búsqueda formado por todos
los árboles de decisión posibles. Al ser voraz, puede que conduzca a una solución óptima local en vez de
global.
Se comienza respondiendo a ¿qué atributo usamos como raíz para el árbol?
Esta cuestión se resuelve aplicando un test estadístico para averiguar cual de los atributos clasifica mejor
las instancias por sí solo. ID3 escoge la cantidad de información mutua como medida de evaluación de cada
atributo (ganancia de informacion).
Algoritmo ID3.
Se desarrolla una rama para cada posible valor.
En los nuevos nodos se vuelve a hacer la misma pregunta. Así hasta desarrollar un árbol completo (en la
versión básica).
Ejemplo de clasificación con el algoritmo ID3.
2
ID3 - Cómo saber qué atributo clasifica mejor?
Calcular la ganancia de información de cada atributo.
Gan(Dv) = Ent(D)−Ent(Dv) (1)
Donde
Ent(D): es la entropía de conjunto D.
Ent(Dv): es la entropía del atributo Dv.
ID3 - Cómo saber qué atributo clasifica mejor?
Entropia del conjunto D.
Ent(D) = Ent(D+)+Ent(D−) (2)
Donde D+ es la entropia de los ejemplos positivos y D− es la entropia de los ejemplos negativos de D.
ID3 - Cómo saber qué atributo clasifica mejor?
Entropia del subconjunto D+
Ent (D+) =−
(
P+
D
)
∗Log2
(
P+
D
)
(3)
Entropia del subconjunto D−
Ent (D−) =−
(
P−
D
)
∗Log2
(
P−
D
)
(4)
Donde P+ y P− son, la cantidad de ejemplos positivos y negativos de D. D: es la cantidad total ejemplos.
ID3 - Cómo saber qué atributo clasifica mejor?
Entropia del atributo Dv
Ent(Dv) = Ent(Dv+)+Ent(Dv−) (5)
Entropia de Dv+ y Dv−
Ent (Dv+) =−
(
Pv+
D
)
∗Log2
(
Pv+
Dv
)
(6)
Ent (Dv−) =−
(
Pv−
D
)
∗Log2
(
Pv−
Dv
)
(7)
Donde Pv+ y Pv− son, la cantidad de ejemplos positivos y negativos de Dv.
3
ID3 - Cómo saber qué atributo clasifica mejor?
Resumiendo: Para seleccionar el atributo ganador debemos calcular la entropía de cada atributo y con ésta
calcular su ganancia.
El atributo ganador será aquel con mayor ganancia de información. Este atributo se convierte en un nodo
del árbol.
ID3 - Cómo saber qué atributo clasifica mejor?
Volviendo a nuestro ejemplo, calculemos la ganancia de COLOR....
3. Próxima Clase
Próxima Clase
1. Formalización.
4. Bibliografía
Bibliografía
Quinlan, J. Ross, Induction of decision trees, Machine learning vol:1, 81-106, Springe 1986.
4