In this blog post, I will list the key algorithms for periodic itemset mining (according to me) with comments about their contributions. Of course, this list is subjective. I did not list all the papers of all authors but I have listehttps://data-mining.philippe-fournier-viger.com/introduction-to-the-apriori-algorithm-with-java-code/d the key papers that I have read and found interesting, as they introduced some innovative ideas. I did not list papers that were mostly incremental in their contributions. I also did not list papers that had very few references unless I found them interesting.
| Algorithm | Author / Date | Key idea |
| PF-Growth | Tanbeer 2009 | – First algorithm for periodic itemset mining in transactions Uses the maxPer constraint to select periodic patterns. – Based on FP-Growth |
| MTKPP | Amphawan 2009 | – First algorithm for top-k periodic itemset mining – Uses the maxPer constraint to select periodic patterns. – Based on Eclat |
| ITL-tree | Amphawan 2010 | – Performs an approximate calculation of the periods of patterns – Based on FP-Growth |
| MIS-PF-tree | Kiran 2009 | – Mining periodic patterns with a maxPer threshold for each item – Based on FP-Growth |
| Lahiri 2010 | – Proposed to study periodic patterns as subgraphs in a sequence of graphs. | |
| PFP | Rashid 2012 | – Find periodic itemsets using the variance of periods. – The periodic patterns are called regular periodic patterns. – Based on FP-Growth |
| PFPM | Fournier-Viger 2016 | – Generalize the problem of periodic itemset mining to provide more flexibility using three measures: the average periodicity, minimum periodicity and maximum periodicity – It is shown that average periodicity is inversely related to the support measure. – Based on Eclat |
| PHM | Fournier-Viger 2015 | – An extension of the PFPM algorithm to mine high utility itemsets (itemsets that are periodic but also important such as yield a high profit) – Based on PFPM, Eclat and FHM |
| MPFPS | Fournier-Viger 2019 (ppt) | – Find periodic patterns in multiple sequences – Introduce a measure called “sequence periodic ratio“ – Based on PFPM and Eclat |
| MRCPPS | Fournier-Viger 2019 | – Find periodic patterns in multiple sequences that are rare and correlated. – Use the sequence periodic ratio, bond measure and maximum periodicity to select patterns – Based on PFPM and Eclat |
| PPFP | Nofong 2016 | – Find periodic itemsets using the standard deviation of periods as measure to select patterns. – Apply a statistical test to select periodic patterns that are significant. – Vertical algorithm based on Eclat and inspired by OPUS-Miner for the statistical test |
| PPFP+, PFP+… | Nofong 2018 | – Find periodic itemsets using the standard deviation and variance of periods as measure to select patterns. – The measures are integrated in existing algorithms such as PPFP and PFP |
| PHUSPM | Dinh 2018 | – Proposed to find periodic sequential patterns (subsequences that are periodic) |
| SPP-Growth | Fournier-Viger 2019 (ppt) | – Find the stable periodic patterns using a novel measure called lability. – The goal is to find patterns that are generally stable rather than enforcing a very strict maxPer constraint as many algorithms do. – Based on FPGrowth |
| TSPIN | Fournier-Viger 2020 | – Algorithm for mining the top-k stable periodic patterns. – Based on SPP-Growth |
| LPP-Growth LPP-Miner | Fournier-Viger 2020 (ppt) | – Find locally periodic patterns (periodic in some time intervals rather than the whole database). That is, unlike most algorithms, it is not assumed that a pattern must be always periodic. – LPP-Growth is based on FPGrowth – LPP-Miner is based on PFPM, which is inspired by Eclat and Apriori-TID |
Implementations
Several algorithms above are implemented in the SPMF data mining software in Java as open-source code.
Some survey papers
I have also written two chapters recently that give some overview of some topics on periodic pattern mining. You may read them if you want to have a quick and easy-to-understand overview of some topics in periodic pattern mining.
- Fournier-Viger, P., Wu. Y., Dinh, D.-T., Song, W., Lin, J.C.W. (2021). Discovering Periodic High Utility Itemsets in a Discrete Sequence. In the book “Periodic Pattern Mining: Theory, Algorithms and Application”, Springer, to appear.
- Fournier-Viger, P., Chi, T. T., Wu, Y., Qu, J.-F., Lin, J. C.W., Li, Z. (2021). Finding Periodic Patterns in Multiple Discrete Sequences. In the book “Periodic Pattern Mining: Theory, Algorithms and Application”, Springer, to appear.
Conclusion
In this blog post, I have listed some key references in periodic pattern mining. Of course, I did not list all the references of all authors. I mainly listed the key papers that I have read and found interesting. This is obviously subjective.
Philippe Fournier-Viger is a full professor working in China and founder of the SPMF open source data mining software.
Pingback: Discovering the Top-K Stable Periodic Patterns in a Sequence of Events | The Data Mining Blog
Lpp growth is consuming more memory.
Is there any new technique to find local
Periodic patterns that is memory efficient, fast , and generating interested local patterns along with time intervals.
Hi, thanks for your feedback and comment on the blog! Yes, it actually depends on the dataset. This type of pattern mining algorithm can consume much time or memory depending on the input parameters that are used and the type of data. A possibility to improve performance is to adjust the parameters. Another solution would be to modify the algorithm to add some constraints such as to not mine patterns with more than a maximum number of items (e.g. max = 3), or to further optimize the algorithm memory management or develop alternative techniques. For now, I dont know of any other improvement, but it is a potential research topic, if you or someone else is interested. There are certainly some ways to improve it.
Thanks sir for your valuable suggestion. I will try to search any new measure to improve the performance. If any such discovered please let me know.