Research On Fast Negative Sequential Pattern Mining Algorithms Based On Bitmap

As a crucial part of behavioral science,non-occurring behavior(NOB)studies have attracted the growing attention of scholars.As an effective method to discover both NOB and occurring behaviors(OB),negative sequential pattern(NSP)mining is successfully used in medical behavior analysis,abnormal behavior detection,recommendation system,education,etc.Therefore,this paper studies the efficiency of NSP mining and explores the method of positive and negative sequential patterns synchronous mining,and then discusses the key issues.To address the weakness of f-NSP,we propose a highly efficient algorithm with improved techniques,named sc-NSP,to mine efficient NSP.We first propose an improved Prefix Span algorithm in the PSP mining process,which connects to a bitmap storage structure instead of the original one.Secondly,sc-NSP loosens the frequent constraint and exploits the negative candidate sequence(NSC)generation method of PNSP(a classic NSP mining method).Besides,a novel pruning strategy is well designed to reduce the computational complexity of sc-NSP.Finally,sc-NSP obtains the support of NSC by using the most efficiently bitwise-based calculation operation.Theoretical analyses show that sc-NSP performs particularly well on dense datasets.The experiment results prove that,compared with other state-of-the-art methods,the sc-NSP algorithm can efficiently mine more NSPs.To solve the problem that the existing NSP mining algorithms are all segmented algorithm,this paper presents a new algorithm to mine positive and negative sequential patterns simultaneously,named B-NSP.Firstly,we propose a new negative containment,which is suitable for mining PSPs and NSPs simultaneously,and further relax the frequent constraint.Then due to the complexity of mining NSPs,it is impossible to represent all the information of the negative sequence using only a bitmap structure.Therefore,we propose a new storage structure to store sequence information.This structure contains the bitmap,hashtable and pointer.Finally,the B-NSP generates positive and negative candidate sequences by deep recursion,and uses bit operations to calculate the support of the candidate sequence.Experiments show that the time and space efficiency of B-NSP algorithm are better than other algorithms.