Mining of high utility-probability sequential patterns from uncertain databases

TLDR

High‑utility sequential pattern mining is widely used for tasks such as consumer behavior analysis and sensor‑network event detection, yet most existing methods assume precise data and ignore the uncertainty inherent in real‑world sensor collections. The authors propose HUPSPM, a framework for mining high‑utility‑probability sequential patterns in uncertain databases. They introduce a baseline algorithm with three pruning strategies and a projection mechanism that generates smaller database slices for each sequence to accelerate mining. Experiments on real‑life and synthetic data demonstrate that the algorithm significantly reduces candidate numbers and runtime while maintaining low memory usage and scaling well across varying utility and probability thresholds.

Abstract

High-utility sequential pattern mining (HUSPM) has become an important issue in the field of data mining. Several HUSPM algorithms have been designed to mine high-utility sequential patterns (HUPSPs). They have been applied in several real-life situations such as for consumer behavior analysis and event detection in sensor networks. Nonetheless, most studies on HUSPM have focused on mining HUPSPs in precise data. But in real-life, uncertainty is an important factor as data is collected using various types of sensors that are more or less accurate. Hence, data collected in a real-life database can be annotated with existing probabilities. This paper presents a novel pattern mining framework called high utility-probability sequential pattern mining (HUPSPM) for mining high utility-probability sequential patterns (HUPSPs) in uncertain sequence databases. A baseline algorithm with three optional pruning strategies is presented to mine HUPSPs. Moroever, to speed up the mining process, a projection mechanism is designed to create a database projection for each processed sequence, which is smaller than the original database. Thus, the number of unpromising candidates can be greatly reduced, as well as the execution time for mining HUPSPs. Substantial experiments both on real-life and synthetic datasets show that the designed algorithm performs well in terms of runtime, number of candidates, memory usage, and scalability for different minimum utility and minimum probability thresholds.