Mining Negative Sequential Patterns with Periodic Gap Constraints

Abstract

Sequential pattern mining with gap constraints is a special form of sequential pattern mining,which can reveal frequent subsequences in a certain gap.However,the current sequential pattern mining methods with gap constraints only focus on positive sequential pattern mining,and ignore the missing behavior in a series of events.To solve this problem,a negative sequential pattern method with periodic gap constraints(NSPG) mining is explored,which can reflect the relationship between elements more flexibly.To solve the problem of NSPG mining,this paper proposes an NSPG-INtree(incomplete nettrees) algorithm,which includes two key steps:candidate pattern generation and support calculation.For candidate pattern generation,to reduce the number of candidate patterns,the algorithm uses a pattern join strategy.For support calculation,to improve the efficiency and reduce space consumption,the algorithm employs an incomplete nettree structure to calculate the supports of patterns.Experimental results show that NSPG-INtree not only has high mining efficiency,but also can mine positive and negative sequential patterns with gap constraints.NSPG-INtree can find 209% ~ 352% more patterns than other gap-constrained sequential pattern mining algorithms.Moreover,NSPG-INtree can reduce the running time by 6%~38% than other competitive algorithms with different stra-tegies.

Keywords

• sequential pattern mining|negative sequential pattern|frequent pattern|gap constraint|incomplete nettree