Mining Local Periodic Patterns in a Discrete Sequence

Abstract

Periodic frequent patterns are sets of events or items that periodically appear in a sequence of events or transactions. Many algorithms have been designed to identify periodic frequent patterns in data. However, most assume that the periodic behavior of a pattern does not change much over time. To address this limitation, this paper proposes to discover a novel type of periodic patterns in a sequence of events or transactions, called Local Periodic Patterns (LPPs) which are patterns (sets of events) that have a periodic behavior in some non prede ned time-intervals. A pattern is said to be a local periodic pattern if it appears regularly and continuously in some time-interval(s). Two novel measures are proposed to assess the periodicity and frequency of patterns in time-intervals. The maxSoPer (maximal period of spillovers) measure allows detecting time-intervals of variable lengths where a pattern is continuously periodic, while the minDur (minimal duration) measure ensures that those time-intervals have a minimum duration. To discover all LPPs, the paper presents three e cient algorithms. An experimental evaluation on real datasets shows that the proposed algorithms are e cient and can provide useful patterns that cannot be found using traditional periodic pattern mining algorithms.