Mining negative sequential patterns

Sequential pattern mining is to discover all frequent sequences from a sequence database and has been an important issue in data mining. A lot of methods have been proposed for mining sequential pattern. However, conventional methods consider only the occurrences of itemsets in a sequence database, and the sequential patterns are referred to as positive sequential patterns. In practice, the absence of a frequent itemset in a sequence may imply significant information. In this paper, we introduce negative sequential pattern concept in which the absence of an itemset in a sequence is also considered. The major difficulties of negative sequential pattern mining are that there may be huge amounts of the candidates of negative sequences and most of them are meaningless. We proposed an algorithm for mining negative sequential patterns (NSPM). Using NSPM, we prune a number of redundant candidates by applying apriori-principle, and extract meaningful negative sequences from a large number of frequent negative sequences using the interestingness measure.