e-RNSP: An Efficient Method for Mining Repetition Negative Sequential Patterns

Negative sequential patterns (NSPs), which capture both frequent occurring and nonoccurring behaviors, become increasingly important and sometimes play a role irreplaceable by analyzing occurring behaviors only. Repetition sequential patterns capture repetitions of patterns in different sequences as well as within a sequence and are very important to understand the repetition relations between behaviors. Though some methods are available for mining NSP and repetition positive sequential patterns (RPSPs), we have not found any methods for mining repetition NSP (RNSP). RNSP can help the analysts to further understand the repetition relationships between items and capture more comprehensive information with repetition properties. However, mining RNSP is much more difficult than mining NSP due to the intrinsic challenges of nonoccurring items. To address the above issues, we first propose a formal definition of repetition negative containment. Then, we propose a method to convert repetition negative containment to repetition positive containment, which fast calculates the repetition supports by only using the corresponding RPSP's information without rescanning databases. Finally, we propose an efficient algorithm, called e-RNSP, to mine RNSP efficiently. To the best of our knowledge, e-RNSP is the first algorithm to efficiently mine RNSP. Intensive experimental results on the first four real and synthetic datasets clearly show that e-RNSP can efficiently discover the repetition negative patterns; results on the fifth dataset prove the effectiveness of RNSP which are captured by the proposed method; and the results on the rest 16 datasets analyze the impacts of data characteristics on mining process.