Heavy path based super-sequence frequent pattern mining on web log dataset

摘要

Mining web log datasets has been extensively studied using Frequent Pattern Mining (FPM) and its various other forms. Identifying frequent patterns in different sequences can help in analyzing the most common sub-sequences (e.g., the pages visited together). However, this approach would not be able to identify general structures spanning over multiple sequences. In response to understanding general structures, we introduce a new form of sequential pattern mining called super-sequence frequent pattern mining (SS-FPM). In contrast to sub-sequences determined by FPM, SS-FPM determines the super-sequences that can contain the common parts from different sequences. This can be useful in understanding the general behavior/flow of users in web usage mining, classifying web pages and users, making predictions etc. In essence, finding frequent super-sequence patterns turns out to be related to the well-known heaviest (longest) path problem in graphs, which is known to be NP-hard. Accordingly, we transform a given sequential dataset into a sequence graph and formulate the problem as k-hop heaviest path problem. We then propose an efficient heuristic called sequence matrix method using dynamic programming techniques. We compared our method to the existing Heavypath method. The results show that our method is more efficient especially on large datasets.