PDF de programación - Árboles de decisión y Series de tiempo

Árboles de decisión y

Series de tiempo

21 de diciembre de 2009

Tesis de Maestría en Ingeniería

Matemática

Facultad de Ingeniería, UDELAR

Ariel Roche

Director de Tesis: Dr. Badih Ghattas

Co-Tutor: Dr. Marco Scavino

Tribunal:

Dr. Ricardo Fraiman

Dr. Eduardo Grampin

Dr. Ernesto Mordecki

Dr. Gonzalo Perera

:

Agradezco por su dedicación, compañerismo e impulso, a Badih, Juan,
Gonzalo, Marco, Anita, Mathias, Laurita, Paola, Pepe y Cacha.
También por su paciencia, a Dieguin, Paulita y a mi Amor de siempre.
Un recuerdo especial a mi mamá.

3

R. Dentro de los métodos enmarcados en el aprendizaje
automático supervisado, muchos pueden adaptarse a los problemas
que tratan con atributos en forma de series de tiempo. Se han de-
sarrollado métodos específicos, que permiten captar mejor el factor
temporal. Muchos de ellos, incluyen etapas de pre-procesamiento
de los datos, que extraen nuevos atributos de las series para su
posterior tratamiento mediante métodos tradicionales. Estos mo-
delos suelen depender demasiado del problema particular y a veces
también resultan difíciles de interpretar. Aquí nos propusimos de-
sarrollar un algoritmo, específico para clasificación y regresión con
atributos series de tiempo, sin tratamiento previo de los datos y
de fácil interpretación. Implementamos una adaptación de CART,
cambiando la forma de particionar los nodos, utilizando la medida
DTW de similaridad entre series. Aplicamos el método a la base ar-
tificial CBF, ampliamente utilizada en el contexto de clusterización
y clasificación de series de tiempo. También experimentamos en un
problema de regresión, con datos reales de tráfico en redes de in-
ternet.

Índice general

Capítulo 1.

Introducción

Capítulo 2. Aprendizaje automático

1. Modelo general
2. Función de pérdida, riesgo
3. Principio de minimización del riesgo empírico
4. Errores en la predicción
5. Estimación de la performance del predictor
6. Algunas técnicas del apendizaje automático

Capítulo 3. Árboles de Clasificación y Regresión

1. CART
2. Árboles de Clasificación
3. Árboles de Regresión

Capítulo 4. Aprendizaje automático y Series de tiempo

1. Análisis de datos funcionales
2. Dynamic Time Warping
3. Complejidad del algoritmo de cálculo de la DTW
4. Clasificación con atributos series de tiempo

Capítulo 5. Árboles de decisión con atributos series de tiempo

1. Principios del método AST
2. Reducción en el número de particiones utilizadas
3. Agregación de modelos. Bagging.

Capítulo 6. Experimentación

Implementación

1. Base CBF
2.
3. Resultados del modelo AST
4. Resultados del modelo AST-Bagging
5. AST en regresión - Tráfico en redes de internet

Capítulo 7. Conclusiones y perspectivas

5

7

9
10
10
12
13
14
15

19
19
21
36

41
41
42
50
55

59
59
62
63

65
65
66
68
73
74

79

6

Bibliografía

ÍNDICE GENERAL

81

CAPíTULO 1

Introducción

En muchas áreas como la ingeniería, medicina, biología, etc., apare-
cen problemas de clasificación o regresión, donde los atributos de los
datos tienen la forma de series de tiempo. Desde el punto de vista
del aprendizaje automático, cada punto de cada serie puede conside-
rarse como un atributo del individuo, para poder de esa manera aplicar
cualquiera de los métodos tradicionales. El inconveniente radica en que
de esta forma, puede suceder que no se logre captar adecuadamente, el
efecto temporal en la estructura de los datos.

Es así, que se han desarrollado diversas metodologías específicas
para dominios temporales. Muchas de ellas, proponen definir nuevos
atributos por intermedio de la extracción de patrones o característi-
cas de las series y posteriormente aplicar algún método tradicional a
esas nuevas variables. En muchos casos, los modelos obtenidos son difí-
ciles de interpretar y en otros resultan muy espécificos a la aplicación
considerada.

Como los árboles de decisión suelen ser muy efectivos y de fácil in-
terpretación en diversas situaciones, decidimos explorar la posibilidad
de su utilización, en el contexto de atributos con características tem-
porales. Siguiendo la estructura de CART [3, Breiman y otros, 1984],
donde en cada nodo interno del árbol, se define una partición binaria,
preguntando si el valor de uno de los atributos del individuo supera o
no un determinado umbral, se puede trasladar esa idea y determinar
una partición, planteándose si uno de los atributos serie de tiempo del
individuo está “cerca” o no, de la correspondiente serie de tiempo de
un individuo tomado como referencia.

Surge entonces la necesidad de utilizar una medida de similaridad
entre series de tiempo. Encontramos en la literatura un consenso bas-
tante amplio, en cuanto a la efectividad de la medida DTW introducida
por [46, Sakoe y Chiba, 1978], especialmente cuando se quieren permi-
tir ciertas deformaciones en el eje del tiempo. Si bien, esta medida fue
originalmente desarrollada para su utilización en áreas específicas como
el reconocimiento de voz, más tarde se generalizaron extensamente sus
aplicaciones a otras áreas. Resulta fundamental tener en cuenta, que la

7

8

1. INTRODUCCIÓN

aplicación reiterada de los algoritmos para calcular la DTW, en muchas
aplicaciones reales, suele tener una alta demanda computacional, por
lo que en muchos casos se hace necesario implementar técnicas que
permitan superar este inconveniente.

Los métodos que desarrollamos en base a las ideas anteriores fueron
aplicados, en el caso de clasificación, a una base de datos sintéticos
(CBF), que intenta simular determinados fenómenos temporales. Como
esta base ha sido utilizada en muchos trabajos a los cuales hacemos
referencia, también nos resultó útil a los efectos de comparar nuestros
resultados. En el caso de regresión, los aplicamos a un problema de
tráfico en redes de internet.

El resto del trabajo se organiza de la siguiente manera, en el Capí-
tulo 2 se hace una revisión básica de conocimientos del aprendizaje
automático. En el Capítulo 3, se analiza con cierto detalle el méto-
do CART de árboles de decisión, desarrollado en [3, Breiman y otros,
1984]. En el Capítulo 4, hablamos de series de tiempo en el contex-
to del aprendizaje automático, de la medida de similaridad DTW y
de su utilización en algunas aplicaciones al problema de clasificación
con atributos series de tiempo. En el Capítulo 5, damos los detalles de
nuestro método para árboles de decisión con atributos series de tiem-
po. En el Capítulo 6, presentamos resultados de experimentos con la
base de datos CBF, con los datos de tráfico en redes y los comparamos
con otros métodos. En el Capítulo 7, sacamos algunas conclusiones y
dejamos planteados ciertos temas para profundizar e investigar.

CAPíTULO 2

Aprendizaje automático

El aprendizaje automático (AA) consta de un conjunto de técnicas
capaces de ayudar a resolver problemas de modelización en distintas
áreas como ser, la biología, economía, informática, metereología, tele-
comunicaciones, etc. Algunos ejemplos:

Predecir si un paciente tiene o no una determinada enfer-
medad, basándose en variables clínicas y demográficas.
Establecer agrupamientos entre países, en función de algunas
variables económicas.
Asignar a un correo electrónico un puntaje del 0 al 10, vincu-
lado a su nivel de “spam”, teniendo en cuenta algunas carac-
terísticas del mismo.

El AA, además de predecir una determinada variable, nos puede
brindar una mejor comprensión del fenómeno de estudio desde el pun-
to de vista de la causalidad, por ejemplo, estableciendo relaciones y
jerarquías entre las variables involucradas. Otra ventaja es que pueden
manejarse grandes bases de datos.

En muchas situaciones, el problema consta de algunas variables
que deseamos predecir (cantidad de dólares exportados, presencia o
no de una enfermedad) y otras variables que suponemos pueden expli-
carlas (tipo de cambio, edad del paciente). En esos casos hablaremos
de aprendizaje supervisado. Otras veces, tenemos un conjunto de
datos en los cuales no se determina una variable a explicar y el objeti-
vo es organizar los datos de alguna manera, lo llamamos aprendizaje
no supervisado. Un caso típico es el llamado “clustering”, que in-
tenta determinar una partición de un conjunto de datos. Por ejemplo,
supongamos que contamos con cierta información sobre una centena de
países que le compran carne bovina al Uruguay y queremos agruparlos
de algún modo, de manera de diseñar para cada grupo una estrategia
particular de “marketing”. Este trabajo se enmarca en el caso super-
visado.

9

10

2. APRENDIZAJE AUTOMÁTICO

1. Modelo general

Sea un vector aleatorio (X, Y ) donde:

X es la llamada variables de entrada (también denominada
independiente, explicativa, atributo), que toma valores en el
espacio medible SX.
Y es la llamada variable de salida (también denominada de-
pendiente, de respuesta), toma valores en el espacio medible
SY .
P es la probabilidad subyacente sobre el espacio de probabili-
dad donde está definido el vector aleatorio (X, Y ).
γ es la distribución conjunta del vector (X, Y ), es decir
γ (A × B) = P (X ∈ A, Y ∈ B) ∀ A ⊂ SX y B ⊂ SY
p (. | X) es la distribución condicional de Y dado X.
π es la distribución marginal de X, es decir π (A) = P (X ∈ A),
con lo cual
γ (A × B) =A

p (B | X) π (dx) =AB

p (dy | X) π (dx)

En el problema de predicción se observa X y se trata de predecir el

valor de Y por medio de f (X) donde

es una función medible llamada predictor.

f : SX → SY

Cuando la variable Y es continua hablamos de problemas de re-

gresión y cuando es categórica de clasificación.

2. Función de pérdida, riesgo

Para determinar la bondad de un predictor f definimos la función

de pérdida

L : SX × SY × SY → R,
donde L (x, u, y) representa la “pérdida” que significa, a partir de x,
tomar u = f (x) en lugar del verdadero valor y.

Luego se trata de elegir f de manera de minimizar el riesgo RL

Veamos como algunos problemas clásicos de la estadística, cuando se
elige la función de pérdida adecuadamente, pueden v