Sequential pattern mining provides an important way to obtain special patterns from sequence data. Different from traditional positive sequential pattern (PSP) mining, negative sequential pattern (NSP) mining takes negative itemsets into account besides positive ones. It is more interesting in applications where non-occurring itemsets need to be considered.
A comprehensive literature of negative frequent pattern mining is described in this thesis. After that, formal definitions of the NSP mining problem are stated to make the following descriptions of methodology to be clear and accurate.

Three algorithms of NSP mining are then proposed in this thesis.
(1) The first algorithm, Neg-GSP, is based on a PSP mining algorithm GSP (Srikant & Agrawal 1996), and then extended to deal with negative cases by introducing new methods of joining and generating candidates. And also, an effective pruning method to reduce the number of candidates is introduced as well.
(2) The second one is a Genetic Algorithm (GA)-based NSP mining algorithm (Zheng, Zhao, Zuo & Cao 2010), which is called GA-NSP. The proposed method is to find NSP with novel crossover and mutation operations, which are efficient at passing good genes on to next generations. An effective dynamic fitness function and a pruning method are also provided to improve performance.
(3) The third algorithm, e-NSP, is based on the Set Theory, and mines for NSP by only involving the identified PSP, without re-scanning a database. In this way, mining NSP does not require additional database scans, and it facilitates that the existing PSP mining algorithms can mine NSP. It offers a new strategy for efficient mining of NSP.

The results of extensive experiments about the three algorithms show that the proposed methods can find NSP efficiently and have good performance compared with some other algorithms of mining NSP. Comparing the NSP definitions of the above three methods, Neg-GSP and GA-NSP share the same definitions, e-NSP uses stronger constraints since it requires clear boundary to follow the Set Theory. When we compare their efficiency, GA-NSP algorithm slightly outperforms Neg-GSP in terms of the running time, but it misses some of patterns in the complete result sets due to limitations of GA. Apparently, e-NSP is the most efficient and effective one since it doesn¡¯t need to scan datasets to calculate the support of NSP. Although adding stronger constraints makes the NSP set much smaller than what it is under the normal definitions, it is still very practicable while being used in some real-life applications.

Following that, NSP mining case studies coming from health insurance industry are introduced. Based on real-life industry datasets, we use the proposed NSP mining methods to find PSP and NSP in ancillary service over-service analysis and fraud claim detection, which show the applicability and benefits gained from mining NSP.