Inteligencia Artificial

Á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 desarrollado métodos específicos, que permiten captar mejor elfactor 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 modelos suelen depender demasiado del problema particular y a veces también resultan difíciles de interpretar. Aquí nos propusimos desarrollar un algoritmo, específico para clasificación y regresión conatributos 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 artificial CBF, ampliamente utilizada en el contexto de clusterización y clasificación de series de tiempo. También experimentamos en un problema deregresión, con datos reales de tráfico en redes de internet.

Í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 yRegresión 1. CART 2. Árboles de Clasificación 3. Árboles de Regresión 7 9 10 10 12 13 14 15 19 19 21 36

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étodoAST 2. Reducción en el número de particiones utilizadas 3. Agregación de modelos. Bagging. Capítulo 6. Experimentación 1. Base CBF 2. Implementación 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

41 41 42 50 55 59 59 62 63 65 65 66 68 73 74 79

6

ÍNDICE GENERAL

Bibliografía81

CAPíTULO 1

Introducción
En muchas áreas como la ingeniería, medicina, biología, etc., aparecen 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 considerarse como un atributo del individuo, para poder de esa manera aplicar cualquiera de losmé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ísticas de las series y posteriormenteaplicar 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 interpretación en diversas situaciones, decidimos explorar la posibilidad de su utilización, en el contexto de atributos con características...