Negative Sequential Pattern Mining from Uncertain Data

Abstract

Negative Sequential Pattern Mining (NSPM) provides an efficient way to extract hidden predictive information from sequential data. In recent years, NSPM is gaining more interest, as it provides complete knowledge by considering both negative and positive item sets, ensuring better analysis and decision making. In classical NSPM data is deterministic, but recently in several applications data is uncertain in nature, which requires a framework to deal with uncertain or noisy data. Traditional mining techniques cannot be applied for mining uncertain data, we use probabilistic framework, which is the most efficient way for NSPM from uncertain data. Our thesis is the first effort, for mining NSPM from uncertain data by extending positive SPM concepts to negative SPM. We consider uncertainty that could arise at tuple level, known as Tuple Level Uncertainty (TLU) and provides a probabilistic model for TLU using possible world semantics. We extract frequent NSP based on the values of expected support and probabilistic frequentness. It is hard to compute these values using possible worlds, so we use an alternative approach, that is, dynamic programming for computing them. We propose two algorithms known as uncertain Negative Sequential Pattern Mining (U-NSP) based on expected support and probabilistic frequentness for the tuple level uncertainty. The algorithms first mine frequent positive patterns based on user specified minimum support threshold and minimum confidence threshold, using candidate-generation algorithm. Then it generates negative patterns from identified positive patterns. Finally it mines frequent negative sequential patterns, using dynamic programming. The implemented U-NSP algorithms are also evaluated under different parameters using uncertain data.