Modelos

de árbol
Universidad Politécnica de Madrid
Objetivos

En este tema se presentan modelos de árbol básicos para toma

de decisiones. Además, cubriremos algunos detalles sobre cómo
se entrenan estos modelos.
Al final del tema, se deben conocer:
▣ Varios modelos de árbol
□ Árboles de decisión y regresión
□ Métodos de combinación (Ensembles)
▣ Aprendizaje/Generación de un árbol de decisión paso a paso
□ Conceptos de entropía y ganancia de información
□ Selección de variables del árbol

2
 1. Tipos de
Introducción modelos

3
4
¿Qué es un modelo de árbol?

Los modelos de árbol utilizan un árbol de decisión como un

modelo predictivo que enlaza determinadas variables observables
sobre un hecho concreto y genera conclusiones sobre una
determinada variable.

El objetivo es crear un modelo que predice el valor de una variable

de destino en función de diversas variables de entrada.

Principalmente se engloban en dos categorías: árboles de

decisión y métodos de combinación o “ensembles”.

5
Familias de modelos de árbol

ÁRBOLES DE DECISIÓN MÉTODOS DE COMBINACIÓN

(ensembles)

ID3 Random Forest

C4.5 ExtraTrees
C5.0 GBM (Gradient
CART Boosting Machine)

6
Perspectiva histórica

Árboles de decisión Bosques aleatorios

▣ J. R. Quinlan, ▣ T.K. Ho, “Random
“Induction of Decision Forests”.
Decision Trees”, Proc. ICDAR, 1995.
1979 ▣ L. Breiman,
▣ L. Breiman et al., "Random Forests".
Classification and Machine Learning.
regression trees. 45 (1): 5–32, 2001.
T&F, 1984.
▣ J. R. Quinlan, “C4.5:
Programs for
Machine Learning”.
MK Publishers, 1993. 7
 Usos prácticos: Microsoft Kinect

▣ Usa Random Forest para predecir la posición del cuerpo

▣ Implementado eficientemente sobre una GPU (Unidad de
Procesamiento Gráfico)

8
http://www.i-programmer.info/news/105-artificial-intelligence/2176-kinects-ai-breakthrough-explained.html
Tipos de algoritmos

▣ Árboles de decisión ▣ Modelos de

□ Binaria combinación
■ CART □ Random Forest
□ No-Binaria □ Extratrees
■ ID3
■ C4.5
■ C5.0

9
 2.
Modelos de
árboles de Tipos de
modelos de
decisión árbol

10
Tipos de algoritmos

▣ Árboles de ▣ Árboles de
clasificación regresión
□ Tipos: □ Salida numérica
■ Binario
■ No-Binario
□ Salida categórica
para clasificación

11
Árboles de clasificación

▣ Clasificación basada en el criterio de binario donde cada

nodo tiene dos hijos, conocidos como hijo izquierdo e hijo
derecho.
▣ Se suele utilizar variables lógica (booleanas) con dos únicas
opciones.
▣ Sus nodos se definen como: root
□ Nodo raíz (root)
□ Nodo de decisión (split node) split
□ Nodo hoja (leaf node) node

leaf
node

12
Árbol de clasificación binario

¿Más de 5
patas?
NO SI

¿Se esconde
¿Delicioso? bajo tu
cama?

NO SI NO SI

¿En las
¿Aparece en ¿Aparece en
monedas de
la Telaraña ¿Hace miel? la Telaraña
5 cent.
de Charlotte? de Charlotte?
australianas?

NO SI NO SI NO SI NO SI

Gato Equidna Bisonte Cerdo Mosquito Abeja Chinche Araña

Traducido de la fuente original: http://apprize.info/python/scratch/17.html 13

 Árbol de clasificación no-binario

▣ De manera más genérica, los árboles de decisión no tiene por

qué restringirse a variable binarias.
▣ Así se convierte un árbol binario a una estructura de árbol
más general. Para ello se pueden usar dos alternativas: nodos
multimodo (multiway) y división en nodos binarios (binary
splitting). Como se muestra respectivamente en los
siguientes ejemplos:

¿color =
¿color? verde?
SI NO

rojo verde amarillo ¿color =

rojo?
SI NO
14
Árbol de clasificación no-binario

¿Trabajo por
hacer?
SI
NO

Quedarse en ¿Previsión
casa del tiempo?

Soleado Nublado Lluvioso

¿Amigos
Ir a la playa Ir a correr
ocupados?

NO SI

Quedarse en
Ir al cine
casa

Traducido de la fuente original: Python Machine Learning

15
Árbol de regresión

▣ Cuando se utilizan árboles de decisión para obtener una

salida continua (numérica), se pueden utilizar árboles
aleatorios.
▣ De esta manera, se obtienen heurísticos de los datos para
llevar a cabo la toma de decisiones.
▣ En la siguiente página se muestra un árbol aleatorio que
ofrece como salida una estimación del valor de una variable
(y) en función de otras dos variables (x1 y x2).
▣ En la figura izquierda se muestra el árbol usado para predecir
el valor de la variable y basándose en los datos de la figura
derecha siendo los círculos rojos valores cercanos a cero y los
círculos azules valores cercanos a uno.
▣ Además, la figura derecha muestra las regiones delimitadas
por determinados valores de x1 (eje vertical) y x2 (eje
horizontal) con los valores medios de los datos de dicha
región (dichos valores son la salida del árbol).
Árbol de regresión

17
Métodos de combinación (Ensembles)

▣ Los métodos de combinación (o ensemble) utilizan múltiples

algoritmos de aprendizaje para conseguir un mejor
rendimiento predictivo del que pudiera alcanzar alguno de los
algoritmos de manera individual.
▣ A diferencia de otros métodos de combinación estadística, un
método de combinación (ensemble) consiste en la
combinación de un conjunto finito de modelos alternativos
para conseguir una predicción sobre la misma variable.
▣ En el ámbito de árboles de decisión, se suelen utilizar
algoritmos rápidos para crear multitud de árboles de decisión
que luego son agrupados (por ejemplo, con el algoritmo de
bosques aleatorios, o random forest) para conseguir una
mejor predicción.
Métodos de combinación (Ensembles)

▣ Al igual que los árboles de decisión en los que se basan, estos

métodos pueden usarse tanto para clasificación como para
regresión.
▣ El método Random Forest consiste en generar multitud de
árboles de decisión que predigan una clase (clasificación) o
un valor (regresión) y ofrecer como salida final la moda (en
clasificación) o la media (en regresión).
▣ Existen variaciones sobre el algoritmo Random Forest original
como el ExtraTrees (Extremely Randomized Trees) que
incluye un proceso aleatorizado en la selección de variables
durante el proceso de aprendizaje de los árboles.
▣ También existen otras métricas para entrenar/ajustar el
método de combinación (ensemble) correctamente, como el
GBM (Gradient Boosting Machine) que ajusta de manera
iterativa el resultado minimizando el error cuadrático medio.

19
 3.
Aprendizaje de
árboles de
Generación de
decisión un árbol

20
Algoritmo básico

▣ Seleccionar los mejores atributos para

dividir las instancias restantes y hacer que ese
atributo sea un nodo de decisión
▣ Repetir este proceso de manera recursiva
para cada nodo hijo
▣ Parar cuando:
□ Todas las instancias tienen el mismo valor del
atributo objetivo
□ No hay más atributos
□ No hay más instancias

21
Caso práctico: ¿Jugará Nadal el partido?

22
Introducción de los datos

▣ previsión: {soleado, nublado, lluvioso}

▣ temperatura: {frío, templado, caliente}
▣ humedad: {alto, normal}
▣ ventoso: {cierto, falso}

Induction of Decision Trees, J. R. Quinlan,

Machine Learning, 1: 81-106, 1986, Kluwer
23
Datos

Día Previsión Temperatura Humedad Viento PartidoTenis

D1 Soleado Caliente Alto Débil NO
D2 Soleado Caliente Alto Fuerte NO
D3 Nublado Caliente Alto Débil SI
D4 Lluvioso Templado Alto Débil SI
D5 Lluvioso Frío Normal Débil SI
D6 Lluvioso Frío Normal Fuerte NO
D7 Nublado Frío Normal Fuerte SI
D8 Soleado Templado Alto Débil NO
D9 Soleado Frío Normal Débil SI
D10 Lluvioso Templado Normal Débil SI
D11 Soleado Templado Normal Fuerte SI
D12 Nublado Templado Alto Fuerte SI
D13 Nublado Caliente Normal Débil SI
D14 Lluvioso Templado Alto Fuerte NO

24
 ¿Qué atributo da más información?
Variable objetivo

Día Previsión Temp. Humedad Viento PartidoTenis

D1 Soleado Caliente Alto Débil NO
D2 Soleado Caliente Alto Fuerte NO
partidotenis D3 Nublado Caliente Alto Débil SI
(9P, 5N) D4 Lluvioso Templado Alto Débil SI
D5 Lluvioso Frío Normal Débil SI
previsión D6 Lluvioso Frío Normal Fuerte NO
D7 Nublado Frío Normal Fuerte SI
D8 Soleado Templado Alto Débil NO
D9 Soleado Frío Normal Débil SI
D10 Lluvioso Templado Normal Débil SI
soleado nublado lluvioso D11 Soleado Templado Normal Fuerte SI
(2P, 3N) D12 Nublado Templado Alto Fuerte SI
D13 Nublado Caliente Normal Débil SI
D14 Lluvioso Templado Alto Fuerte NO

25
 ¿Qué atributo da más información?

▣ Se calculan todas
previsión las distribuciones
con respecto a la
variable objetivo
para después
soleado nublado lluvioso seleccionar el
(2P, 3N) (4P, 0N) (3P, 2N)
mejor atributo (el
que aporta más
información al
decisión “pura” (split “pure”): proceso de
todos los de una clase y
ninguno del resto, no se clasificación).
necesita decisión/división 26
 ¿Qué atributo da más información?

previsión temperatura

soleado nublado lluvioso caliente templado frío

(2P, 3N) (4P, 0N) (3 P, 2N) (2P, 2N) (4P, 2N) (3P, 1N)

humedad viento

alto normal débil fuerte

(3P, 4N) (6P, 1N) (6P, 2N) (3P, 3N) 27
Seleccionar el mejor atributo

▣ Se prefieren nodos con distribuciones de clase

homogéneas
▣ Ej.
□ viento fuerte (3P, 3N)
■ → no homogénea, alta impureza
□ previsión nublado (4P, 0N)
■ → homogénea, baja impureza

28
 (9P, 5N)

previsión
Entropía: Atributo previsión
soleado nublado lluvioso
(2P, 3N) (4P, 0N) (3P, 2N)

▣ Entropía: nivel de ‘desorden’ o ‘impureza’ o

‘diversidad’. Se mide en ‘bits’.
▣ Entropía(S) = E(S) = -∑pilog2pi
□ S = conjunto de ejemplos (instancias)
□ pi = proporción de ejemplos de la clase i en S
□ Ej: 2/3

▣ E(inicial) = - 9/14log29/14 - 5/14log25/14 = 0.940 bits

▣ E(soleado) = -2/5log22/5 -3/5log23/5 = 0.971 bits
▣ E(nublado) = 0 bits
▣ E(lluvioso) = -3/5log23/5 -2/5log22/5 = 0.971 bits

Entropía: https://en.wikipedia.org/wiki/Entropy_(information_theory) 29
 (9P, 5N)
previsió
n
Ganancia de información (IG)
soleado nublado lluvioso
(2P, 3N) (4P, 0N) (3P, 2N)

▣ IG(S,A) : reducción esperada de la entropía en S

por la selección del atributo A.
▣ IG(S, A) = E(S) - ∑|Sv|/|S| E(SA), v: valores de A

▣ E(S) = 0.940 bits

▣ E(previsión) = 5/14 E(soleado) + 4/14 E(nublado) +
5 /14 E(lluvioso) = 5/14 * 0.971 + 4/14 *0 + 5/14* 0.971 = 0.694
bits

▣ IG(S, previsión) = E(S) - E(previsión) = 0.246 bits

30
 (9P, 5N)

IG temperatura temperatura

caliente templado frío

▣ E(S) = 0.940 bits (2P, 2N) (4P, 2N) (3P, 1N)

▣ E(caliente) = 1
▣ E(templado)= -4/6log2(4/6)-2/6log2(2/6) = 0.918
bits
▣ E(frío) = -3/4log2(3/4) - 1/4log2(1/4) = 0.811 bits

▣ E(temperatura) = 4/14 * 1 + 6/14 * 0.918 + 4/14 * 0.811

= 0.911 bits
▣ IG(S, temperatura) = 0.94 - 0.911 = 0,029 bits

31
 (9P, 5N)

IG humedad humedad

alto Normal
▣ E(S) = 0.94 bits (3P, 4N) (6P, 1N)

▣ E(alto) = -3/7log2(3/7)-4/7log2(4/7) = 0.985 bits

▣ E(normal) = -6/7log2(6/7) - 1/7log2(1/7) = 0.591 bits

▣ IG(S, humedad) = 0.94 - 7/14 * 0.984 - 7/14 * 0.591 =

0,151 bits

32
 (9P, 5N)

IG viento viento

débil fuerte
▣ E(S) = 0.94 bits (6P, 2N) (3P, 3N)

▣ E(débil) = -6/8* log2(6/8) - 2/8*log2(2/8) = 0.811 bits

▣ E(fuerte) = 1 bits

▣ IG(S, viento) = 0.94 - 8/14 * 0.811 - 6/14 * 1

= 0,048 bits

33
Seleccionar el mejor atributo

▣ IG(S, previsión) = 0,246 bits

▣ IG(S, temperatura) = 0,029 bits
▣ IG(S, humedad) = 0,151 bits
▣ IG(S, viento) = 0,048 bits
Se selecciona como nodo raíz (root) el que tenga
mayor Ganancia de Información (IG)

previsión

soleado nublado lluvioso

(2P, 3N) (4P, 0N) (3 P, 2N)
34
Seleccionar siguiente atributo:
soleado (I)

Día Previsión Temp. Humedad Viento PartidoTenis

previsión D1 Soleado Caliente Alto Débil NO
D2 Soleado Caliente Alto Fuerte NO

(2P, 3N) soleado D3 Nublado Caliente Alto Débil SI

D4 Lluvioso Templado Alto Débil SI

... ...
D5 Lluvioso Frío Normal Débil SI
temperatura D6 Lluvioso Frío Normal Fuerte NO
D7 Nublado Frío Normal Fuerte SI
caliente templado frío D8 Soleado Templado Alto Débil NO
D9 Soleado Frío Normal Débil SI
D10 Lluvioso Templado Normal Débil SI
(0P, 2N) (1P, 1N) (1P, 0N) D11 Soleado Templado Normal Fuerte SI
D12 Nublado Templado Alto Fuerte SI
D13 Nublado Caliente Normal Débil SI
D14 Lluvioso Templado Alto Fuerte NO

35
Seleccionar siguiente atributo:
soleado (II)

previsión ▣ E(previsión=soleado) = 0.971

bits
(2P, 3N) soleado ▣ E(caliente|soleado) = 0 bits
E(templado|soleado) = 1 bit
... ...
temperatura E(frío|soleado) = 0 bit
▣ E(temperatura | soleado) =
caliente templado frío
2/5 E(caliente|soleado) +
2/5 E(templado|soleado) +
(0P, 2N) (1P, 1N) (1P, 0N) 1/5 E(frío|soleado)
= 2/5 * 0 + 2/5 *1 + 1/5* 0 = 0.4
bits
▣ IG(temperatura) = 0.971 - 0.4 =
0.571 bits

36
 Seleccionar siguiente atributo:
soleado (III)

previsión previsión

(2P, 3N) soleado soleado

... ... ... ...

humedad viento

alto normal débil fuerte

(0P, 3N) (2P, 0N) (1P, 2N) (1P, 1N)

▣ E(previsión=soleado) = 0.971 bits

▣ E(humedad|soleado) = 0 bits
▣ IG(humedad) = 0.971 - 0 = 0.971 bits
▣ E(débil|soleado) = -⅓ * log2(⅓)-⅔*log2(⅔) = 0.918 bits
▣ E(viento|soleado) = ⅗ * 0.918 + ⅖ * 1 = 0.951 bits
▣ IG(viento) = 0.971 - 0.951 = 0.020 bits 37
 Seleccionar el siguiente atributo

(9P, 5N)

previsión

(2P, 3N) soleado nublado lluvioso (3P, 2N)

(4P, 0N)
humedad ?

alto normal

(0P, 3N) (2P, 0N)

38
Seleccionar el siguiente atributo:
lluvioso (I)
(9 P, 5N) Día Previsión Temp. Humedad Viento PartidoTenis
D1 Soleado Caliente Alto Débil NO
D2 Soleado Caliente Alto Fuerte NO
previsión
D3 Nublado Caliente Alto Débil SI
D4 Lluvioso Templado Alto Débil SI
(3 P, 2N) lluvioso D5 Lluvioso Frío Normal Débil SI
D6 Lluvioso Frío Normal Fuerte NO
D7 Nublado Frío Normal Fuerte SI
temperatura
D8 Soleado Templado Alto Débil NO
D9 Soleado Frío Normal Débil SI
calie templ cold
D10 Lluvioso Templado Normal Débil SI
nte ado
D11 Soleado Templado Normal Fuerte SI
D12 Nublado Templado Alto Fuerte SI
(0 P, 0N) (2P, 1N) (1P, 1N) D13 Nublado Caliente Normal Débil SI
D14 Lluvioso Templado Alto Fuerte NO

39
Seleccionar el siguiente atributo:
lluvioso (II)
(9 P, 5N)

previsión

(3 P, 2N) lluvioso ▣ E(previsión=lluvioso) = 0.971

bits
temperatura E(caliente) = 0 bits
E(templado) = 0.918 bits
caliente frío
templado E(frío) = 1 bit
▣ E(temperatura | lluvioso)
(0 P, 0N) (2P, 1N) (1P, 1N) = 3/5 * 0.918 + 2/5 * 1 = 0,951 bits
▣ IG(temperatura) = 0.971 - 0.951
= 0.02 bits

40
 Seleccionar el siguiente atributo:
lluvioso (III)

previsión previsión

(3 P, 2N) lluvioso lluvioso

... ... ... ...

humedad viento

alto normal débil fuerte

(1 P, 1N) (2 P, 1N) (3 P, 0N) (0P, 2N)

▣ E(previsión=lluvioso) = 0.971 bits

▣ E(humedad | lluvioso) = ⅖ * 1 + ⅗ * 0,918 = 0,951 bits
▣ IG(humedad|lluvioso) = 0.971 - 0,951 = 0.02 bits
▣ E(viento|lluvioso) = 0 bits
▣ IG(viento|lluvioso) = 0.971 bits 41
 Árbol de decisión resultante

(9P, 5N)

previsión

(2P, 3N) soleado nublado lluvioso (3P, 2N)

(4P, 0N)
humedad viento

alta normal débil fuerte

(0P, 3N) (2P, 0N) (3P, 0N) (0P, 2N)

42
Árbol resultante como reglas de
decisión

previsión

soleado nublado lluvioso

SI
humedad viento

alta normal débil fuerte

NO SI NO SI

43
 4. Resumen y
Conclusiones puntos clave

44
Conclusiones

▣ Los árboles de decisión (Decision Trees-DT) pueden ser vistos

como reglas y así comprender más fácilmente la salida del
algoritmo de aprendizaje (Machine Learning-ML)
▣ Los árboles de decisión pueden ser usados para clasificación y
regresión
▣ Los principales algoritmos son CART, ID3 and C4.5
▣ Los métodos de combinación (Ensemble), como los árboles
aleatorios (Random Forest) ofrecen un enfoque muy robusto
para combinar árboles

45
Referencias

▣ Machine Learning: The Art and Science of Algorithms

that Make Sense of Data, by Peter Flach, 2012
▣ Induction of Decision Trees, J. R. Quinlan, Machine
Learning, 1: 81-106, 1986, Kluwer
▣ Python Machine Learning, S. Raschka, Packt, 2015

46