Mining gap-constrained sequential patterns in certain and uncertain databases

© 2014 Dr. Yuxuan LiSequential pattern mining is a branch of data mining task that aims at modeling sequence data and develops algorithms that are able to automatically discover and extract interesting and potentially useful knowledge from large databases. Most of the previously proposed methods for discovering subsequence and substring patterns focused on mining techniques for certain sequences and there are only a few results for uncertain sequences. Various factors contribute to data uncertainty, including incompleteness of data sources, the addition of artificial noise in privacy-sensitive applications, and most importantly, uncertainty arising from imprecision in measurements and observations. Uncertain sequences provide powerful representations for modelling sequence behavioural characteristics in emerging domains, such as bioinformatics, sensor stream management and trajectory analysis. Modeling uncertain sequences and discovering subsequence or substring patterns are complex tasks. The problem space of mining a subsequence or substring pattern grows exponentially with the size of the sequence data. This makes a naive method that exhaustively enumerate every instance in the problem space infeasible. In this thesis, we study the problem of sequential pattern mining for both certain and uncertain data. In certain data, we introduce a novel spatial sequential pattern called the platoon pattern to capture the co-occurrence of moving objects for most of the time. We present an efficient algorithm called PlatoonMiner to mine the complete set of platoon patterns from large databases. In the context of data uncertainty, we model uncertain sequences based on possible world semantics. The occurrence of an element is specified by some probability interpretations. We introduce a novel dynamic programming framework to efficiently match and mine subsequence and substring patterns from uncertain sequence data. To provide more flexibility, we also allow users to specify a (maximum) gap constraint to restrict or relax the consecutiveness requirement of a subsequence pattern. Our extensive empirical studies show the efficiency and effectiveness of our methods for synthetic and real-world datasets. With the great flexibility and adaptability, our proposed methods can serve as powerful tools for many other data mining tasks