Efficient mining of intra-periodic frequent sequences

Abstract

Frequent Sequence Mining (FSM) is a fundamental task in data mining. Although FSM algorithms extract frequent patterns, they cannot discover patterns that periodically appear in the data. However, periodic trends are found in many areas such as market basket analysis, where discovering itemsets periodically purchased by customers can help understand periodic customer behavior. This is the task of Periodic Frequent Pattern Mining (PFPM). A major limitation common to traditional PFPM algorithms is that they reduce the periodicity between non-disjoint itemsets. They do not take into account the periods between disjoint itemsets. Thus, they find itemsets that appear periodically, but would fail to find a periodic appearance of distinct itemsets. To address this limitation, this paper extends the traditional problem of FSM with intra-periodicity and provides a theoretical background to extract intra-periodic frequent sequences. This leads to a new mining algorithm called Intra-Periodic Frequent Sequence Miner. Experimental results confirm its efficiency.

Keywords

• Intra-periodicity
• Inclusion-carried mapping
• Search space
• Pruning
• Partitioning
• Sequence irreducibility