Arboles de decisión

Árboles de Decisión
Tomás Arredondo Vidal 26/3/08

Árboles de Decisión

Contenidos • Árboles de Decisión • Sobreajuste • Recorte (Pruning)

Investigación Relacionada a los Árboles de Decisión
• William of Occam inventa el criterio de Occam’s razor 1320 • Hunt usa el método (CLS) para modelar aprendizaje humano de conceptos - 1960’s. • Quinlan desarrolla ID3 con la heurística de gananciade información para desarrollar sistemas expertos desde ejemplos – 1970s • Breiman, Friedman y otros desarrollan CART (Classification and Regression Trees) similar a ID3 – 1970s • Una variedad de mejorar se introducen para acomodar ruido, características continuas, características incompletas, mejoras en métodos de división – 1980s • Quinlan’s actualiza sistemas de decision (C4.5) -1993. • Wekase incluye una versión en Java de C4.5 llamado J48.

Árboles de Decisión
• Clasificadores basados en árboles para instancias (datos) representados como vectores de características (features). • Nodos prueban características, hay una rama para cada valor de la característica, las hojas especifican la categoría.
color red shape blue green shape red color blue green

pos neg circle squaretriangle neg neg pos

C B circle square triangle B C A

• Pueden representar cualquier conjunción (AND) y disyunción (OR) • Pueden representar cualquier función de clasificación de vectores de características discretas. • Pueden ser rescritas como reglas, i.e. disjunctive normal form (DNF).
– red ∧ circle → pos – red ∧ circle → A blue → B; red ∧ square → B green → C; red ∧ triangle → CPropiedades de Árboles de Decisión
• Características (features) continuas (reales) pueden ser clasificadas al permitir nodos que dividan una característica real en dos rangos basados en umbrales (e.g. largo < 3 and largo ≥3) • Árboles de clasificación tienen valores discretos en las ramas, árboles de regresión permiten outputs reales en las hojas • Algoritmos para encontrar árboles consistentes soneficientes para procesar muchos datos de entrenamiento para tareas de datamining • Pueden manejar ruido en datos de entrenamiento • Ejemplos:
– Diagnostico medico – Análisis de riesgo en crédito – Clasificador de objetos para manipulador de robot (Tan 1993)

Árbol de Decisión para PlayTennis
Outlook Sunny Overcast Rain

Humidity

Yes

Wind

High No

Normal Yes

Strong No

Weak YesÁrbol de Decisión para PlayTennis
Outlook Sunny Overcast Rain

Humidity

Each internal node tests an attribute

High No

Normal Yes

Each branch corresponds to an attribute value node Each leaf node assigns a classification

Árbol de Decisión para Conjunción
Outlook=Sunny ∧ Wind=Weak Outlook Sunny Overcast Rain

Wind

No

No

Strong No

Weak Yes

Árbol de Decisiónpara Disyunción
Outlook=Sunny ∨ Wind=Weak Outlook Sunny Overcast Rain

Yes

Wind

Wind

Strong No

Weak Yes

Strong No

Weak Yes

Árbol de Decisión para XOR
Outlook=Sunny XOR Wind=Weak Outlook Sunny Overcast Rain

Wind

Wind

Wind

Strong Yes

Weak No

Strong No

Weak Yes

Strong No

Weak Yes

Árbol de Decisión
• Árboles de decisión representan disyuncionesde conjunciones Outlook Sunny Humidity High No Normal Yes Overcast Yes Rain Wind Strong No Weak Yes

(Outlook=Sunny ∧ Humidity=Normal) ∨ (Outlook=Overcast) ∨ (Outlook=Rain ∧ Wind=Weak)

Método Top-Down de Construcción
• Construir un árbol Top-Down usando dividir para conquistar.
: + : + : + : − : − : -

color red blue green

: + : + : − : +

Método Top-Down de Construcción
•Construir un árbol Top-Down usando dividir para conquistar.
: + : + : + : − : − : -

color red blue : + : + shape : + neg neg : − : − circle triangle square : + pos : + neg pos : + : − : + green

Pseudocódigo para Construcción de Árbol
DTree(examples, features) returns a tree If all examples are in one category, return a leaf node with that category label. Else if the set of features is empty,...