Analyzing state sequences with probabilistic suffix trees: the PST R package

TitleAnalyzing state sequences with probabilistic suffix trees: the PST R package
Publication TypeJournal Article
Year of Publication2016
AuthorsGabadinho, A, Ritschard, G
JournalJournal of Statistical Software
Volume72
Issue3
Pagination1-39
Date Publishedaug
Keywordscategorical sequences, Probabilistic suffix trees, R, Sequence data mining, sequence visualization, state sequences, Variable-length Markov chains
Abstract

This article presents the PST R package for categorical sequence analysis with probabilistic suffix trees (PSTs), i.e., structures that store variable-length Markov chains (VLMCs). VLMCs allow to model high-order dependencies in categorical sequences with parsimonious models based on simple estimation procedures. The package is specifically adapted to the field of social sciences, as it allows for VLMC models to be learned from sets of individual sequences possibly containing missing values; in addition, the package is extended to account for case weights. This article describes how a VLMC model is learned from one or more categorical sequences and stored in a PST. The PST can then be used for sequence prediction, i.e., to assign a probability to whole observed or artificial sequences. This feature supports data mining applications such as the extraction of typical patterns and outliers. This article also introduces original visualization tools for both the model and the outcomes of sequence prediction. Other features such as functions for pattern mining and artificial sequence generation are described as well. The PST package also allows for the computation of probabilistic divergence between two models and the fitting of segmented VLMCs, where sub-models fitted to distinct strata of the learning sample are stored in a single PST.

DOI10.18637/jss.v072.i03
Refereed DesignationRefereed