Técnicas para el descubrimiento de patrones temporales= Techniques for the discovery of temporal patterns

Abstract

Uno de los problemas a los que las tecnologías de la información han tenido que enfrentarse en los últimos años es el análisis de una enorme cantidad de datos originada en las actividades cotidianas de organizaciones o personas. Este análisis puede consistir en la búsqueda tanto de modelos como patrones que ayuden en la comprensión de los datos o el comportamiento de estas organizaciones o personas. Una componente esencial asociada a este tipo de conocimiento es la dimensión temporal, que cuando es tenida en cuenta en los patrones, no sólo proporciona mucha más información, sino también los convierte en más complejos. La minería de datos de secuencias (SDM) es un área en el campo de la detección de conocimiento en bases de datos (KDD) cuyo objetivo es extraer los conjuntos de patrones frecuentes que se encuentran, ordenados en el tiempo, en una base de datos. Algunas técnicas de SDM han sido empleadas en una amplia variedad de dominios de aplicación, tales como el descubrimiento de patrones en secuencias de ADN, el análisis de secuencias de compras de clientes, número de clics en una web, etcétera. Los patrones que se obtienen en estos dominios dependen de la naturaleza de los datos que son objeto de análisis y del propósito de dicho análisis. Por un lado, hay patrones sencillos que sólo contienen eventos que denotan puntos ordenados en el tiempo. Por ejemplo, un patrón puede modelar el comportamiento de una persona que, durante la noche, se despierta, toma agua, va al baño, y luego regresa a la cama. Por otra parte, otros patrones mucho más complejos incluyen eventos que denotan intervalos con distancias temporales entre ellos. Por ejemplo, una persona duerme durante 3 horas, seguidamente pasa 3 minutos en la cocina y, después de ver la televisión durante 40 minutos, vuelve a dormir durante 2 horas más. Entre estos dos extremos existe una amplia gama de diferentes patrones. Esta tesis supone distintas aportaciones al campo de la SDM. En primer lugar, proponemos una clasificación clara de los patrones y algoritmos dentro de la SDM. Hacemos un estudio claramente diferenciado en tres distintas dimensiones: representación de los patrones, su expresividad y la estrategia de búsqueda utilizada para la extracción de patrones frecuentes. En esta clasificación hemos encontrado algunas lagunas en los algoritmos existentes en el estado del arte. En segundo lugar, con el fin de completar las lagunas que aún no han sido exploradas, ofrecemos cinco nuevos algoritmos que utilizan diferentes representaciones y estrategias. Finalmente, discutimos la conveniencia de utilizar un algoritmo determinado en función de las propiedades de la base de datos y los patrones que son objeto de nuestro interés.

One of the problems that information technologies have had to confront in recent years is the analysis of the huge amount of data that originates during the daily activities of organisations or people. This analysis may consist of searching for models or patterns that will assist in understanding the data or behaviour of these organisations or people. One essential component in this kind of knowledge is the temporal dimension. When time is included in the patterns, they provide much more information but also become more complex. Sequence Data Mining (SDM) is an area in the field of Knowledge Discovery whose aim is to extract sets of frequent patterns that occur, ordered in time, in a database. SDM techniques have been used in a wide array of application domains, such as the discovery of motifs in DNA sequences, the analysis of customer purchase sequences, web click streams, and so forth. The patterns obtained in these domains depend on the nature of the data under analysis and the purpose of the analysis. On the one hand, there are simple patterns that only contain point events ordered in time. For example, a pattern can model the behavior of a person who, during the night, wakes up, drinks water, goes to the bathroom, and then goes back to bed again. On the other hand, much more complex patterns include interval events with temporal distances between them. For example, a person sleeps for 3 hours, then spends 3 minutes in the kitchen and, after watching TV for 40 minutes, goes back to sleep for 2 more hours. There is a wide range of patterns between these two extremes. This thesis presents a number of contributions to the SDM field. Firstly, we propose a clear categorisation of patterns and algorithms within SDM. We principally study three different dimensions: the representation of the patterns, their expressiveness and the search strategy used to mine patterns. In this categorisation we have found certain gaps in the state-of-the-art algorithms. Secondly, in order to complete those gaps that have not yet been explored, we provide five new algorithms that use different representations and strategies. Finally, we discuss the convenience of using a particular algorithm depending on the properties of the database and the patterns that we are interested in finding.