Effective Mining Sequential Pattern by Last Position Induction
Zhenglu Yang, Masaru Kitsuregawa · 2005
Sequence pattern mining is an important research problem because it is the basis of many other applications. Yet how to efficiently implement the mining is difficult due to the inherent characteristic of the problem-the large size of the data set. In this paper, by combining SPAM, we propose a new algorithm called LAst Position INduction Sequential PAttern Mining (abbreviated as LAPIN-SPAM), which can efficiently get all the frequent sequential patterns from a large database. The main difference between our strategy and the previous works is that when judging whether a sequence is a pattern or not, they use S-Matrix by scanning projected database (PrefixSpan) or count the number by joining (SPADE) or ANDing with the candidate item (SPAM). In contrast, LAPIN-SPAM can easily implement this process based on the following fact- if an item’s last position is smaller than the current prefix position, the item can not appear behind the current prefix in the same customer sequence. When scanning the database for the first time, LAPIN-SPAM will construct the ITEM IS EXIST TABLE. Then in every recursive, it only needs to check this table, avoid constructing S-Matrix, joining or ANDing. Because of the recursive characteristic in this research area, LAPIN-SPAM can save much time by improving efficiency for each recursive. The experimental results confirm that our algorithm outperforms previous algorithms.