Mining Association Rules in Time-series Databases

Discovering association rules can reveal the cause-effect relationships among events in a time-series database. The problem can be transformed to finding frequent sequential patterns. However, most of sequential pattern mining algorithms proposed are not suitable to mine frequent patterns in a time-series database since they are not efficient to mine frequent patterns for long sequences and a time-series database usually contains long sequences. Moreover, they do not consider the distance between the frequent patterns. Thus, in this thesis, we propose an efficient algorithm to mine frequent patterns in time-series database. Our proposed algorithm, CP-Miner, consists of three phases. First of all, we transform every real value number in a time-series sequence into a symbolic level so that every time-series sequence can be considered as a string. Then we employ a suffix tree to store the whole database thus we can easily find the frequent strings by traversing the suffix tree. Finally, we can combine these frequent strings to generate longer frequent patterns by traversing the suffix tree. It is shown that the CP-Miner algorithm outperforms the Apriori-like algorithm in terms of runtime and space requirement.Table of Contents i List of Figures ii List of Tables iii Chapter 1 Introduction 1 Chapter 2 Literature Survey 3 2.1 AprioriAll Algorithm 3 2.2 PrefixSpan 5 2.3 Discussion 7 Chapter 3 Mining Association Rules in Time-series Databases 9 3.1 Problem Definition and Notations 9 3.2 Suffix Tree 10 3.3 Our Proposed Method 12 3.3.1 Quantization phase 12 3.3.2 Discovering phase 12 3.3.3 Combination phase 15 Chapter 4 Performance Evaluation and Experimental Results 28 4.1 Synthetic Data 28 4.2 Real Data 31 Chapter 5 Conclusions and Future Work 35 References 3