Download ARBOLES DE DECISION

ARBOLES DE DECISION
Miguel Cárdenas-Montes
Los árboles de decisión son estructuras lógicas con amplia utilización en
la toma de decisión, la predicción y la minería de datos.
Objetivos:
Entender como funcionan los algoritmos basados en árboles de decisión.
Conocer el uso práctico de la ganancia de información en estos algoritmos.
1
Este documento puede contener imprecisiones o errores. Por favor no lo utilice
para citarlo como una fuente fiable.
Introducción
Un árbol de decisión puede ser tan simple como la imposición de
una regla sobre el comportamiento mayoritario de un conjunto de datos.
Por ejemplo, en la tabla 1 se presenta cuando se juega o no al golf
en función de las condiciones meteorológicas.
Aspecto
Temperatura
Humedad
Viento
Jugar
cubierto
cubierto
cubierto
cubierto
lluvia
lluvia
lluvia
lluvia
lluvia
soleado
soleado
soleado
soleado
soleado
frío
calor
calor
templado
frío
templado
frío
templado
templado
calor
calor
templado
frío
templado
normal
alta
normal
alta
normal
alta
normal
alta
normal
alta
alta
alta
normal
normal
verdad
falso
falso
verdad
verdad
verdad
falso
falso
falso
falso
verdad
falso
falso
verdad
sí
sí
sí
sí
no
no
no
sí
sí
no
no
no
sí
sí
Estas reglas son siempre de la forma IF...THEN..., y pueden aplicarse tanto a variables continuas como discretas. Cuando se implementa
una sola sola regla condicional el algoritmo se denomina 1-rule algorithm.
Un ejemplo sencillo de este tipo de algoritmo de una regla es:
IF humedad=’normal’ THEN jugar=si
ELSE IF humedad=’alta’ then jugar=no
Cuadro 1: Meteorología y golf.
Las reglas con muy fáciles de entender
y aplicar a problemas de clasificación,
siendo uso genérico a la clasificación con
árboles.
2
m
m
La precisión de esta regla se puede medir mediante la matriz de
confusión (Tabla 1).
Cuadro 2: Matriz de confusión para una
sola regla sobre el atributo "humedad".
La entropía caracteriza la impureza de
una colección de datos.
Se define la entropía de Shannon (1948),
H ( X ), de una variable aleatoria discreta
X como la esperanza matemática de la
variable aleatoria asociada I ( X ).
H ( X ) = E( I ( X )) = − ∑ p( xi ) · log2 ( p( xi ))
∀x
Clas. Verdadero
Clas. Falso
5
2
3
4
Verdadero
Falso
+4 = 64 %. La
Con esta simple regla se obtiene un 64 % de acierto, 514
pregunta que se plantea a continuación es ¿cuál es la mejor elección
(mejor regla) para obtener el mejor árbol de decisión (más preciso)?.
Si se utiliza otro criterio, por ejemplo si no hace viento sí se juega, y
si hace viento no se juega, entonces se obtiene el siguiente porcentaje
+3 = 57 %. Como puede apreciarse, esta regla produce una
de acierto 514
más baja predecibilidad sobre los datos.
2 Elección del Mejor Atributo
Un aspecto esencial de los algoritmos basado en árboles de decisión
es la elección del mejor criterio para la división de los datos. Una de las
mejores opciones es realizar esta selección basándose en el concepto de
entropía (ecuación 1).
Entropia = − ∑ p x · log2 ( p x )
(1)
∀x
Figura 1: Para una muestra homogénea
la entropía es ∑∀ x p x · log2 ( p x ) = −1 ·
log2 (1) = 0. Esta muestra no es buena
para el proceso de aprendizaje.
Figura 2: Para una nuestra con dos clases con 50 % de aparición de cada una,
la entropía es ∑∀ x p x · log2 ( p x ) = −0,5 ·
log2 (0,5) − 0,5 · log2 (0,5) = 1. Esta muestra sí es buena para el proceso de aprendizaje.
donde p x es la probabilidad de la clase x.
Valores más bajos de la entropía (ecuación 1) hacen más predecible
el caso. Dicho de otra forma: un valor más alto de la entropía produce
más impredecibilidad, mientras que un valor más bajo de la entropía
se interpreta como una menor impredecibilidad.
La ganancia de información es la reducción de la entropía causada por
el particionado de los datos por un determinado atributo.
La entropía del conjunto de datos mostrado en la tabla 1 es:
8
6
6
8
− 14
· log2 14
= 0,985 puesto que de los 14 casos, hay 8
− 14 · log2 14
casos de sí y 6 casos de no.
Si se dividen los datos por la temperatura, se obtiene que hay 4
casos de frío de los cuales hay 2 en que sí se juega y 2 casos de
frío en que no se juega. Por otro lado, hay 6 casos de templado de lo
cuales sí se juega en 4 y otros 2 casos en que no se juega. Finalmente,
hay 4 casos de calor de los cuales en 2 sí se juega y en 2 no se juega
no se juega.
De esta forma, las entropías de cada uno de estos subgrupos es:
• E( f rio ) = −(2/4) · log2 (2/4) − (2/4) · log2 (2/4) = 1
a
r
b
o
l
e
s
d
e
d
e
i
s
i
o
n
3
• E(templado ) = −(4/6) · log2 (4/6) − (2/6) · log2 (2/6) = 0,918
• E(calor ) = −(2/4) · log2 (2/4) − (2/4) · log2 (2/4) = 1
• Estos resultados tienen que ser pesados por el frecuencia de aparición de cada caso:
6
4
4
· E( f rio ) + 14
· E(templado ) + 14
· E(calor ) =
E( Temperatura) = 14
6
4
4
14 · 1 + 14 · 0,918 + 14 · 1 = 0,965
Si se dividen los datos por el viento, se obtiene que hay 6 casos de
verdad de los cuales sí se juega en 3 y otros 3 casos en los cuales no
se juega. Por otro lado, de los 8 casos de falso, de los cuales en 5 sí
se juega y en 8 en los cuales no se juega.
• E(verdad) = −(3/6) · log2 (3/6) − (3/6) · log2 (3/6) = 1
• E( f also ) = −(5/8) · log2 (5/8) − (3/8) · log2 (3/8) = 0,954
• Estos resultados son pesados por el frecuencia de aparición:
6
8
6
8
E(Viento ) = 14
· E(verdad) + 14
· E( f also ) = 14
· 1 + 14
· 0,954 =
0,974
¿Cuánta información se gana dependiendo si se establece el atributo
viento o el atributo temperatura como punto de decisión del árbol?
• G ( E( Jugar ), E( Jugar |temperatura)) = E( Jugar ) − E( Jugar |temperatura) =
0,985 − 0,965 = 0,020
• G ( E( Jugar ), E( Jugar |viento )) = E( Jugar ) − E( Jugar |viento ) =
0,985 − 0,974 = 0,011
Como consecuencia de este resultado el primer nodo del árbol de
decisión debe ser la división por el atributo temperatura, y no por
el atributo viento. En un caso real, este cálculo debe ser aplicado a
todos los atributos.
Figura 3: Datos más el nodo raíz del árbol.
3
Algoritmo C4.5
El algoritmo C4.5 construye árboles de decisión basándose en la
ganancia de información, I ( Xi , C ) = H (C ) − H (C, Xi ). En cada nodo
4
m
m
Figura 4: Datos, nodo raíz del árbol con
algunas divisiones adicionales.
Figura 5: Datos más el árbol completamente desarrollado.
del árbol, el algoritmo elige el atributo que produce la mayor ganancia
de información, y divide los datos por este criterio. En los siguientes
pasos del algoritmo, el algoritmo aplica esta estrategia a los atributos
restantes.
En pseudocódigo, el algoritmo general para construir árboles de
decisión es:
1. Para cada atributo
2. Encontrar la ganancia de información normalizada de la división
de este atributo.
La técnica denominada bagging es
ampliamente utilizada para mejorar la
precisión de los algoritmos de aprendizaje. La técnica opera de la siguiente forma, dato un conjunto de entrenamiento
D compuesto de n objetos, se generan m
nuevos conjuntos de entrenamiento Di
de tamaño n mediante un muestreo uniforme de D con reemplazamiento. Para
un número suficientemente de n se espera que la muestra bootstrap Di tenga una
fracción 1 − 1e ≈ 63,2 % de muestras únicas, siendo el resto duplicadas.
La técnica denominada Random subspace
o attribute bagging consiste en la selección
de un subconjunto m << M aleatorio
de atributos de una muestra bootstrap
Di >> D. De foma que al final se tiene un subconjunto Di >> D de objetos
tomando solamente un subconjunto de
atributos m << M.
3. Una vez encontrado el atributo cuya ganancia de información es
más alta, crear un nodo de decisión que divida a éste.
4. Repetir en las sublistas obtenidas por división del mejor atributo, y
agregar estos nodos como hijos de nodo
4 Random Forest
La técnica denominada Random Forest consiste en la aplicación de
Random subspace a árboles de decisión. De esta forma se obtiene un
amplio conjunto de clasificadores cada uno de ellos con distintan calidad, y en algunos casos con diferente asignación de clase. Para la
asignación de la clase se establece un sistema de voto mayoritario. El
resto de objetos no seleccionados mediante Random subspace son utilizados para estimar el error.
Para medir el error de random forest se suele utilizar la técnica denominada out-the-bag error. Para cada árbol se utiliza el conjunto de
a
r
b
o
l
e
s
d
e
d
e
i
s
i
o
n
5
Figura 6: Ejemplo de random forest utilizando la técnica de bagging.
objetos no seleccionados por su muestra bootstrap de entrenamiento
para ser clasificados con dicho árbol. Promediando sobre el conjunto
de árboles de random forest se puede estimar el error del algoritmo.
Por otro lado, random forest puede ser paralelizado eficazmente puesto que cada árbol puede construirse de manera independiente a los
otros árboles. Esta característica lo hace deseable para entornos paralelos.