Herramientas para la extracción de redes bayesianas predictivas a partir de bases de datos temporales [computer file]

Abstract

This thesis presents a tool for the extraction of graph-type models from data, where input data consists of a set of time series. The constructed model expresses each time series as a node, and direct relations between them as directed arcs in the graph. Besides the graphical result, the model holds information about the behavior of each relation in the form of a conditional probability density. The kind of model obtained is commonly known as a Bayesian Network, and has been widely studied in the field of Machine Learning. Traditionally, Bayesian Networks learning techniques have been developed aiming to their use on discrete data, forcing the discretization of continuous time series. As the correct discretization of data is an important problem, a new time series discretization method was developed in order to represent as much information as possible, considering both its amplitude and its variations. This discretization method requires a parameter (λ ) which specifies the importance given to the slope at each point in the time series. Distinct values for λ produce different discrete sequences. When trying to discover relations among time series, it’s desirable to use those values of λ which produce the greatest coincidences among them Some time is expected to elapse between the occurrence of an event and its corresponding effect. This is reflected as time delays between the time series which represent such events. Discretized time series must be aligned in order to discover the correct delay between them. As distinct values of λ may produce distinct time delays, these parameters must be studied as a whole. A simulated annealing algorithm has been applied to find the best configuration for this values. This process facilitates the discovery of subtle relations between pairs of time series. The Bayesian Network was extracted from those aligned discrete sequences using well known learning algorithms. The traditional Bayesian Networks model was extended in order to represent time delays between pairs of nodes. This way, every arc linking two nodes has an associated integer number, obtained from the alignment of the underlying time series, which represents the difference in time between the occurrence of an event in the “cause node” and the occurrence of the corresponding event in the “consequence node”. Finally, some time series can be recovered from the Bayesian Network for evaluation and short-term prediction proposes. Known values must be given to some other nodes in order to get the probability density in the target node and sample over it. The tool has been implemented as a distributed environment, allowing for collaboration among users at different places. The distribution was achieved using CORBA objects. // Esta tesis presenta una herramienta para la extracción automática de modelos de tipo grafo a partir de datos, en donde los datos de entrada consisten en un conjunto de series de tiempo. El modelo construido expresa cada serie de tiempo como un nodo, y las relaciones directas entre ellas como arcos dirigidos en el grafo. Además del resultado gráfico, el modelo mantiene información acerca del comportamiento de cada relación en forma de una densidad de probabilidad condicional. El tipo de modelo obtenido se conoce comúnmente como Red Bayesiana, y ha sido estudiado ampliamente en el área de Machine Learning. Tradicionalmente, las técnicas para el aprendizaje de Redes Bayesianas han sido desarrolladas con miras a su uso en datos discretos, forzando así la discretización de series de tiempo continuas. Dado que la correcta discretización de las series de tiempo es un problema importante, se ha desarrollado un nuevo método con el objetivo de representar tanta información como sea posible, tomando en cuenta tanto la amplitud como las variaciones de la serie de tiempo. Este método de discretización requiere un parámetro (λ ) que especifica la importancia dada a la pendiente en cada punto de la serie de tiempo. Distintos valores de λ producen diferentes secuencias discretas. Cuando se intenta descubrir relaciones entre series de tiempo, es deseable utilizar aquellos valores de λ que produzcan la mayor coincidencia entre ellas. Se espera que pase algún tiempo entre la ocurrencia de un evento y su efecto correspondiente. Esto se refleja como retrasos en tiempo entre las series que representan tales eventos. Las series de tiempo discretizadas deben ser alineadas para descubrir el retraso correcto entre ellas. Debido a que distintos valores de λ pueden producir distintos retrasos en tiempo, estos parámetros deben ser vistos como una unidad. Se aplicó un algoritmo de recocido simulado para encontrar la mejor configuración para estos valores. Este proceso facilita el descubrimiento de relaciones sutiles entre pares de series. La Red Bayesiana fue entonces extraída a partir de las secuencias discretas alineadas utilizando algoritmos de aprendizaje bien conocidos. Se realizó una extensión al modelo de Redes Bayesianas para representar retrasos de tiempo entre pares de nodos. De este modo, cada arco que une dos nodos tiene un número entero asociado, obtenido de la alineación de las series de tiempo subyacentes, que representa la diferencia de tiempo entre la ocurrencia de un evento en el “nodo causa” y la ocurrencia del evento correspondiente en el “nodo consecuencia”. Por último, algunas series de tiempo pueden ser recuperadas a partir de la Red Bayesiana para fines de evaluación y predicción a corto plazo. Para esto se deben asignar valores conocidos a algunos otros nodos, con el objetivo de obtener la densidad de probabilidad en el nodo objetivo y muestrear sobre ella. La herramienta ha sido implementada como un ambiente distribuido, permitiendo la colaboración entre usuarios que se encuentran en diferentes lugares. La distribución se llevó a cabo utilizando objetos CORBA.