Article Preview
TopIntroduction
In the past, periodic pattern mining has been one of the important issues in sequential pattern mining due to the discovery of regularity in time series or event sequences. Periodic pattern mining techniques have widely been applied to various business applications, such as analyzing web usage every day, tracing the regularity of company’s stock prices every week, analyzing the product re-order points every month, tracing product sales volume every season, etc (Aref et al., 2004; Elfeky et al., 2004). However, the limitation of mining frequent full periodic patterns is a strict constraint since all events in a full periodic pattern have to be known, and their positions in the pattern are fixed and frequently appeared in the long-term time-series data with a specific periodic length. To solve this problem, Han et al. (1998) thus proposed another kind of periodic pattern mining called partial periodic pattern mining, which considered most but not all points in a period contributing to an approximate cyclic behavior of a time series. For example, “The price of the stock goes up on Monday” is a partial periodicity because it only considers Mondays and says nothing about the price fluctuations. In this example, a unit of the period length is set as a week (seven days), and “the stock price goes up” can be defined as an “event”. To effectively find such patterns, Han et al. subsequently proposed a partial periodic mining algorithm called a max-subpattern hit set (Han et al., 1999), which mainly used a max-subpattern tree structure to store the hit counts and to represent candidate patterns, and then all partial periodic patterns could be found from the built tree structure. Afterward, most of existing studies related to partial periodic pattern mining directly adopted Han et al.’s max-subpattern hit set algorithm to various data applications.
To efficiently find partial periodic patterns, Yang et al. (2013) proposed a projection-based partial periodic pattern mining algorithm (abbreviated as PPA) to find partial periodic patterns with the consideration of only single event in a time stamp. Chen et al. (2011) applied FP-tree’s concept (Han et al., 2000) to proposed PFP-growth partial periodic pattern mining algorithm with multiple minimum supports. In both Yang et al.’s study and Chen et al.’s study, their algorithms adopted the ‘cycle’ encoding method used in Han et al.’s study (1998) to re-encode events into new event representation by the positions of the events in the corresponding periodic segments. However, in terms of finding partial periodic patterns with consideration of multiple events in a time stamp, a great deal of unpromising candidates was still generated in mining. Thus, it is desirable to effectively handle the problem of partial periodic pattern mining with the consideration of multiple events in a time stamp.
Based on the above reasons, this work thus presents an efficient projection-based candidate reduction algorithm (abbreviated as PRA) to find partial periodic patterns in a sequence of event sets (instead of a single event). Different from the PPA algorithm in Yang et al.’s study (2013), two effective strategies, pruning and filtering, are designed to reduce unpromising candidates in mining. With the help of the two strategies, all partial periodic patterns can efficiently be explored by the proposed PRA algorithm from the set of period sub-sequences. Finally, the experimental results on synthetic and real datasets reveal that the proposed PRA algorithm outperforms the other compared algorithms, traditional max-subpattern algorithm and the PFP-growth algorithm, in terms of execution efficiency.