Mining probabilistic automata: a statistical view of sequential pattern mining

Stéphanie Jacquemont, François Jacquenet, Marc SebbanMachine Learning 2009 · DOI

Abstract

Traditional sequential pattern mining (SPM) often lacks statistical rigor, leading to potential false discoveries, and poses significant privacy risks by requiring access to raw individual trajectories. This paper proposes a shift from purely algorithmic counting to a statistical framework based on Probabilistic Deterministic Finite state Automata (PDFA). By modeling sequences as generative processes, the authors provide mathematical guarantees against false positives and negatives while enabling privacy-preserving mining through data aggregation.

Introduction

Sequential pattern mining is a cornerstone of data analysis in domains ranging from e-commerce to urban mobility. However, conventional methods face two critical challenges. First, they often fail to distinguish between "true" behavioral patterns and sampling noise, particularly in small datasets. Second, the requirement for raw sequence data is increasingly incompatible with modern privacy standards. This research addresses these gaps by asking how we can mathematically guarantee the relevance of findings while keeping individual identities hidden.

Statistical Framework and Methodology

The core of the proposed approach is the representation of sequences using Probabilistic Deterministic Finite state Automata (PDFA). This framework allows the application of classical hypothesis testing to the mining process.

Theoretical Bounds

The authors derive a lower bound ($N_{low}$) on the number of sequences required to ensure that the risks of false positives (Type I error, $\alpha$) and false negatives (Type II error, $\beta$) remain below user-defined thresholds. This provides a rigorous foundation for determining if a dataset is large enough to support reliable pattern discovery.

Table 1: Statistical decision matrix defining Type I error (α) and Type II error (β) in the context of hypothesis testing.

The ACSM Algorithm

The paper introduces the Automata-based Constrained Sequence Mining (ACSM) algorithm. Unlike standard miners that scan entire databases, ACSM traverses the learned PDFA. It employs two primary statistical tests to prune the search space:

  1. Proportion Test: Verifies that a pattern covers a significant portion of the probability density.
  2. Fisher’s Exact Test: Evaluates whether there is a true statistical dependence between components of a pattern (e.g., whether event B follows event A more frequently than would be expected by chance).

Experimental Evaluation

The framework was validated across three distinct datasets:

  • ATIS (Air Travel Information Service): Used to confirm that theoretical bounds ($N_{low}$) effectively control empirical error rates in real-world language data.
  • Reber Grammar: A synthetic dataset used to demonstrate that PDFA-based estimation is superior to raw frequency counting for pattern probability.
  • Arlington Traffic Map: A simulation used to showcase the TRAFFIC MINER application, which identifies frequent routes without tracking individual vehicles.

Key Insights

  • Privacy through Aggregation: A significant advantage of the PDFA approach is that it only requires aggregate transition counters (e.g., how many cars moved from intersection A to B) rather than individual trajectories. This allows for mining frequent paths while maintaining anonymity.
  • Computational Efficiency: Once a PDFA is constructed, the execution time for ACSM is independent of the number of original sequences. In traffic simulations, ACSM maintained constant execution time as the dataset grew from 5,000 to 35,000 sequences, whereas classical algorithms like SPAM saw significant runtime increases.
  • Robustness: The "smoothing" effect of the PDFA allows it to represent sequences not explicitly present in the training set, making the mining process more resilient to noise.

Conclusion and Future Work

By treating sequential pattern mining as a statistical inference problem, this work provides a robust alternative to traditional frequency-based methods. While the current Markovian assumptions in PDFAs may struggle with very long-distance dependencies, the framework offers a scalable, statistically sound, and privacy-preserving path forward for sequence analysis. Future research will focus on integrating more complex temporal constraints and applying the model to social network and web usage mining.

Summary updated

BibTeX
@article{jacquemont2009mining,
  author = {Stéphanie Jacquemont and François Jacquenet and Marc Sebban},
  title = {{Mining probabilistic automata: a statistical view of sequential pattern mining}},
  journal = {Machine Learning},
  year = {2009},
  doi = {10.1007/s10994-008-5098-y},
}
Figure