Efficiently Mining Temporal Patterns in Time Series Using Information Theory
Van Ho Long · 2023
The rapid and persistent development of IoT technology has generated a massive volume of time series data.For example, sensors are deployed in smart city applications to collect time series on air quality, humidity, and temperature.In energy management, IoT-enabled smart grids and smart meters contain time series on energy consumption and distribution.In health monitoring applications, wearable devices, such as medical sensors and fitness trackers, collect time series on sleep patterns, heart rate, and physical activity.These time series contain hidden insights and patterns, and when they are discovered, they can offer valuable information to support forecasting and decision-making.Temporal pattern mining in time series is an approach that assists in extracting valuable insights.A temporal pattern has two characteristics.First, temporal information is added to each event within a pattern.Second, the pattern is formed by the complex temporal relations between events.The characteristics make the temporal patterns more expressive and comprehensive, enabling them to provide detailed information.However, it is worth noting that these characteristics also increase the complexity of the mining process due to the search space's explosion.In this thesis, we focus on optimization methods for temporal pattern mining to enhance the efficiency of the mining process.Moreover, we use information theory-based measures, i.e., mutual information and entropy, to estimate the correlation between time series, thereby pruning the uncorrelated time series to reduce the search space.We solve three problems: frequent temporal pattern mining, rare temporal pattern mining, and seasonal temporal pattern mining.First, we present a comprehensive process for mining frequent temporal patterns from time series.The input of this process consists of a set of time series, while the output comprises all the frequent temporal patterns.As part of this process, we use a splitting strategy that converts time series into event sequences, while preserving the underlying temporal patterns.Our proposal includes an efficient algorithm for Frequent Temporal Pattern Mining, called FTPM, that optimizes the mining process by utilizing efficient data structures and pruning techniques.Additionally, we propose an approximate version of iii FTPM that employs mutual information to eliminate unpromising time series.This approximation method proves the efficiency when working with large datasets.Second, we propose a solution to mine rare temporal patterns from time series.The solution comprises an efficient Rare Temporal Pattern Mining (RTPM) algorithm that incorporates a support lower bound and a support upper bound.These support bounds are assigned to low values that constrain a low occurrence frequency for temporal patterns.Furthermore, we set the confidence threshold to a high value to ensure that the discovered patterns exhibit high confidence.The RTPM algorithm uses an efficient data structure, i.e., a variant of the hierarchical hash table, and applies two pruning techniques based on the Apriori principle and the transitivity property to perform the efficient mining process.Moreover, by establishing the connection between mutual information and support as well as confidence, we put forth an approximate version of RTPM that focuses exclusively on mining rare temporal patterns from the most promising time series, accelerating the mining process while maintaining high accuracy.Third, we propose the first-ever solution for mining seasonal temporal patterns from time series.In this solution, we introduce several measures to capture the seasonality characteristics of temporal patterns.Additionally, we propose an efficient Seasonal Temporal Pattern Mining (STPM) algorithm including several novelties.The first novelty is we introduce a new measure called a maximum season, which adheres to the anti-monotonicity property.We then use the maximum season to define the concept of a candidate seasonal temporal pattern that is used to eliminate infrequent seasonal temporal patterns.The second novelty is we use hierarchical hash tables data structures, ensuring fast retrieval of candidate events and patterns, and propose two efficient pruning techniques: Apriori-like pruning and transitivity pruning.To handle large datasets more effectively, we introduce an approximate version of STPM that utilizes mutual information to perform the mining on only the promising time series, speeding up the mining process, while retaining high accuracy.We evaluate the proposed solutions on real-world and synthetic datasets.For real-world datasets, four smart energy datasets are from Spain, the U.S.A., and the U.K.; one smart city dataset is from the U.S.A.; one American Sign Language dataset is from the U.S.A.; and two health datasets are from Japan.For synthetic datasets, we generate a large number of sequences and time series from each real-world dataset, adapting the generation process based on the problem being addressed.The experimental results show that the exact algorithms (FTPM, RTPM, and STPM) outperform the baselines in terms of runtime and memory usage and scale well on large datasets.Moreover, the approximate FTPM is up to two orders of magnitude, and the approximate RTPM and STPM are up to one order of magnitude, faster than the baselines, while maintaining a high level of accuracy.I would like to thank many people who were with me to overcome the challenges of this Ph.D. journey and achieve its completion.First, I would like to express my gratitude to my supervisor Prof. Torben Bach Pedersen.Under his guidance, I have gained a wealth of knowledge regarding scientific writing skills and research methods.His insightful feedback and valuable suggestion have played a crucial role in refining my ideas and enhancing the quality of my work.I have gained worthwhile lessons from him, particularly in his meticulousness and pursuit of perfection.I am deeply appreciative of his guidance and instructions throughout my Ph.D. study.Second, I am especially grateful to my co-supervisor Asst.Prof. Nguyen Ho.She has put so much effort in supervising me.She hold weekly meetings with me throughout my PhD years, actively engaged in thought-provoking discussions, suggesting appropriate approaches to solve problems that guided me in the right direction.I have learned so much from her, from how to look for a promising and interesting research topic, define a research problem and find the solutions for it, to how to write a good scientific paper.I also deeply appreciate the significant amount of time she dedicated to revise my drafts.Further, I am truly grateful for her encouragement during the challenging phases of my Ph.D. study, which helped me overcome the difficulties posed by the Corona lockdown and the inherent challenges in my research.