An Efficient Algorithm for Exact Segmentation of Large Compositional and Categorical Time Series

ABSTRACT Change‐point detection, also known as signal segmentation, is an essential preprocessing step in many applications, ranging from industrial monitoring to bioinformatics. In short, it consists in finding the temporal boundaries of homogeneous regimes in long and non‐stationary time series. While this area of research is active, most existing methods are designed for Euclidean data. However, in many practical scenarios, the collected time series are compositional, meaning that each observation belongs to the probability simplex (the set of non‐negative vectors whose components sum to one). In this work, we propose an algorithm detecting change‐points in large compositional signals with an underlying piecewise stationary model. We cast the change‐point detection task as a discrete optimization problem, whose solution is shown to converge to the true change‐points. We introduce a new and time‐efficient dynamic programming algorithm that solves exactly this problem. To limit the number of operations, we describe a novel pruning rule that allows us to reduce the set of candidate change‐point indices. Our method is tested on a thorough simulation study, which confirms its efficiency. Additionally, we apply our method to a human activity segmentation task, highlighting the necessity for such novel techniques compared to standard algorithms.