Research On Mining Periodic Frequent Patterns Common To Multiple Sequences

Data mining is a set of techniques,designed for taking advantage of this data and is a fast-developing area of research in computer science.Among various data mining tasks,association rule mining has been extensively studied.It consists of identifying all possible sets of items whose number of occurrences is not smaller than a minimum support threshold.Periodic pattern mining is a variation of the traditional association rule mining task,which consists of identifying patterns that periodically appear in data.Traditional periodic pattern mining algorithms are designed to find patterns in a single sequence.However,in several domains,it is desirable to discover patterns that are periodic in many sequences.To discover periodic patterns common to multiple sequences,this thesis extends the traditional problem of mining periodic patterns in a sequence.Two novel measures are defined called the standard deviation of periods and the sequence periodic ratio.The standard deviation of periods is proposed to mine periodic patterns in a single sequence.It helps to settle the problem that the maximum period threshold is too strict in previous studies.The sequence periodic ratio is a minimum proportion of the number of sequences in the entire database.With these two measures,all possible periodic patterns which appear at a certain time interval can be found in a database,which consists of multiple sequences.To mine these patterns efficiently,two algorithms are proposed,called MPFPS_BFSFS and MPFPS_DFS,which perform a breadth-first search and depth-first search,respectively.Because the sequence periodic ratio is neither monotone nor anti-monotone,these algorithms rely on a novel upper-bound called boundRa and two novel search space pruning properties to find periodic patterns efficiently.The algorithms have been evaluated on multiple datasets.Results show that they are efficient and can filter numerous non periodic itemsets to identify periodic patterns.