Periodic Pattern Mining
The goal of periodic pattern mining is to find some patterns that are repeating over time in a sequence of events or symbols. For example, a simple periodic pattern that can be found in customer data is that someone buys wine with cheese about every 7 days. This pattern is illustrated below:
Finding such periodic pattern can be useful. For instance, if we know that a customer has this habit, we can send him a message every week to remind him of buying wine and cheese or offering him some discount. Such pattern can also help to understand the behavior of customers, and thus be used for taking decisions.
Besides, shopping data, periodic pattern mining can be applied to many other applications. For example, periodic patterns could be found in a sequence of events observed in a computer network, or periodic patterns could be found in the locations visited by a person.
Amphawan, K., Lenca, P., Surarerks, A.: Mining top-K periodicfrequent pattern from transactional databases without support threshold. In: Proc. Third International Conference on Advanced in Information Technology, pp. 18–29 (2009) This is one of the first papers for periodic pattern mining. It has introduced key ideas such as using a maximum periodicity threshold to look for periodic patterns.
Fournier-Viger, P., Li, Z., Lin, J.C., Kiran, R.U., Fujita, H.: Discovering periodic patterns common to multiple sequences. In: Proc. 20th International Conference on Big Data Analytics and Knowledge Discovery, pp. 231–246 (2018). This paper explains how to find periodic patterns in multiple sequences instead of only one sequence. This can be used for example to find patterns that are periodic for many customers instead of a single customer.
Fournier-Viger, P., Lin, J.C., Duong, Q., Dam, T.: PHM: mining periodic high-utility itemsets. In: P. Perner (ed.) Proc. 16th Industrial Conference, ICDM 2016, New York, NY, USA, July 13-17, pp. 64–79. Springer (2016). This paper generalized the problem of periodic pattern mining to handle utility values. This problem called periodic high utility itemset mining can be used to find periodic patterns that yield a lot of money instead of just finding frequent patterns.
Fournier-Viger, P., Yang, P., Lin, J.C.W., Kiran, R.U.: Discovering stable periodic-frequent patterns in transactional data. In: Proc. 32nd Intern. Conf. on Industrial, Engineering and Other Applications of Applied Intelligent Systems, pp. 230–244. Springer A problem with the traditional problem of periodic pattern mining is that the maximum periodicity threshold is too strict. As a solution, this paper generalized the basic problem of periodic pattern mining to use the average, minimum and maximum periodicity as evaluation functions to provide more flexibility for finding periodic patterns.
Fournier-Viger, P., Yang, P., Lin, J.C.W., Kiran, R.U.: Discovering stable periodic-frequent patterns in transactional data. In: Proc. 32nd Intern. Conf. on Industrial, Engineering and Other Applications of Applied Intelligent Systems, pp. 230–244. Springer This paper proposed finding patterns that are not only periodic but are also stable over time. This is useful to avoid finding patterns with unstable behavior.
Venkatesh, J.N., Kiran, R.U., Reddy, P.K., Kitsuregawa, M.: Discovering periodic-frequent patterns in transactional databases using allconfidence and periodic-all-confidence. In: Proc. 27th International Conference on Database and Expert Systems Applications Part I, pp. 55–70 (2016). This paper proposed using the variance of periods to select periodic patterns.
Nofong, V.M.: Discovering productive periodic frequent patterns in transactional databases. Annals of Data Science 3(3), 235–249 This paper proposed using the standard deviation of periods to find periodic patterns as an alternative measure. Moreover, a statistical test is performed to ensure that patterns are statistically significant.
Software and datasets
To apply periodic pattern mining, the SPMF software provides open-source efficient implementations of many algorithms and variations. These algorithms can be used to find periodic patterns in a single sequence or multiple sequences. The SPMF software can be downloaded from the website: http://www.philippe-fournier-viger.com/spmf/ .
To install the software, you may follow the instructions on the download page of that website. Then, you may check the documentation page which provides examples of how to run various algorithms such as PFPM and MPFPS for periodic pattern mining. Besides, you may check the datasetspage of that website provides several benchmark datasets for testing the algorithms and comparing their performance.