Super-sequence frequent pattern mining on sequential dataset
Xinran Yu, Turgay Korkmaz · 2013
Due to the importance of Frequent Pattern Mining (FPM) in bioinformatics, web mining, social networks and so on, researchers have been paying significant attention to FPM and its various forms. In this study, we introduce a new form that we call super-sequence pattern mining. In contrast to frequent sub-sequence pattern mining studied significantly in the literature, frequent super-sequence mining requires to identify super-sequences that may contain sequential parts from different sequences and that have the total support larger than a given threshold. In essence, finding frequent super-sequence patterns turns out to be related to the well-known NP-hard longest path problem in graphs. Accordingly, we transform a given sequential dataset into a sequence graph and formulate the problem as k-hop longest path problem. We then propose a heuristic algorithm using dynamic programming techniques. The running time of our solution is depending on the number of different items in the sequence set but not on the size of the dataset. Through experiments, we demonstrate the effectiveness of the proposed solution. We also illustrate its use on an actual web log dataset and find out some interesting facts based on the identified frequent super-sequences on the web log dataset.