Abstract
Periodic pattern mining is the task of discovering patterns that periodically appear in transactions. Typically, periodic pattern mining algorithms will discard a pattern as being nonperiodic if it has a single period greater than a maximal periodicity threshold, defined by the user. A major drawback of this approach is that it is not flexible, as a pattern can be discarded based on only one of its periods. In this chapter, we present a solution to this issue by proposing to discover periodic patterns using three measures: the minimum periodicity, the maximum periodicity, and the average periodicity. The combination of these measures has the advantage of being more flexible. Properties of these measures are studied. Moreover, an efficient algorithm named PFPM (Periodic Frequent Pattern Miner) is proposed to discover all frequent periodic patterns using these measures. An experimental evaluation on real data sets shows that the proposed PFPM algorithm is efficient and can filter a huge number of nonperiodic patterns to reveal only the desired periodic patterns.
Introduction
Frequent Itemset Mining (FIM) is a cornerstone of data mining, identifying items that frequently co-occur in transactions. However, traditional FIM fails to capture the temporal regularity of these occurrences. Periodic Frequent Pattern (PFP) mining addresses this by finding items purchased at regular intervals (e.g., a customer buying milk every 3–4 days).
Existing PFP mining techniques often rely on a strict maximal periodicity threshold. If a pattern exhibits a single gap exceeding this threshold, it is discarded. This "one strike and you're out" approach is often too rigid for messy, real-world data. The PFPM framework introduces a more flexible approach using a trio of periodicity measures to better capture recurring behaviors without sacrificing computational speed.
The PFPM Framework
The authors propose three distinct measures to define periodicity more nuancedly:
- Average Periodicity ($avgper$): Represents the overall regularity. A key mathematical finding in the paper is that $avgper$ can be derived directly from an itemset's support ($s(X)$) and the total number of transactions ($|D|$): $avgper(X) = |D| / (s(X) + 1)$. This allows for extremely fast calculations without iterating through every interval.
- Minimum Periodicity ($minper$): Identifies patterns that occur too frequently in short bursts, which may not represent true long-term periodicity.
- Maximum Periodicity ($maxper$): Sets an upper bound on the gaps between occurrences to ensure the pattern remains active.
The PFPM Algorithm
The Periodic Frequent Pattern Miner (PFPM) algorithm is built upon the Eclat vertical mining approach, utilizing transaction ID lists (tid-lists). The core efficiency of PFPM stems from its pruning capabilities. By leveraging the monotonic properties of the new periodicity measures, PFPM can mathematically exclude large portions of the search space. If an itemset fails a periodicity threshold, the algorithm proves that no superset of that itemset can satisfy the requirements, significantly reducing computational overhead.
Experimental Evaluation
PFPM was tested against standard benchmark datasets: Retail, Chainstore, Foodmart, and Mushroom.
- Performance: PFPM outperformed the standard Eclat algorithm significantly. On the Retail and Foodmart datasets, it was 4 to 5 times faster.
- Scalability: In dense datasets like Mushroom, where Eclat often fails due to memory or time constraints, PFPM completed the task in under 10 seconds.
- Efficiency: PFPM demonstrated superior memory management, using up to 5 times less RAM than Eclat by filtering out non-periodic patterns early in the process.
Conclusion
PFPM offers a flexible and efficient alternative to traditional periodic pattern mining. By moving away from rigid thresholds and utilizing the mathematical relationship between support and average periodicity, the algorithm provides a powerful tool for discovering reliable recurring patterns in large-scale transactional data. Future research will explore extending this framework to correlated and high-utility periodic patterns.
Summary updated