We consider the problem of breaking a multivariate (vector) time series into segments over which the data is well explained as independent samples from a Gaussian distribution. We formulate this as a covariance-regularized maximum likelihood problem, which can be reduced to a combinatorial optimization problem of searching over the possible breakpoints, or segment boundaries. This problem can be solved using dynamic programming, with complexity that grows with the square of the time series length. We propose a heuristic method that approximately solves the problem in linear time with respect to this length, and always yields a locally optimal choice, in the sense that no change of any one breakpoint improves the objective. Our method, which we call greedy Gaussian segmentation (GGS), easily scales to problems with vectors of dimension over 1000 and time series of arbitrary length. We discuss methods that can be used to validate such a model using data, and also to automatically choose appropriate values of the two hyperparameters in the method. Finally, we illustrate our GGS approach on financial time series and Wikipedia text data.

David Hallac

Peter Nystrup

Stephen Boyd

Advances in Data Analysis and Classification

国际期刊《数据分析与分类进展》（ADAC）旨在作为一个论坛，提供有关从多种类型数据中提取已知方面的研究和应用的高标准出版物。它发表有关数据分析的结构、定量或统计方法等主题的文章；分类、聚类和模式识别方法的进展；对复杂数据进行建模和挖掘大型数据集的策略；从数据中提取知识的方法，以及在特定实践领域中应用先进方法。文章说明了如何通过熟练使用数据分析方法从数据中获取新的特定领域知识。该杂志还发表概述和阐明特殊方法的基本思想和技术的调查论文。

The international journal "Advances in Data Analysis and Classification" (ADAC) aims to provide a high-standard forum for research and applications focused on extracting known aspects from various types of data. It publishes articles on topics such as the structure, quantitative, or statistical methods of data analysis; advancements in classification, clustering, and pattern recognition methods; strategies for modeling complex data and mining large datasets; methods for extracting knowledge from data; and the application of advanced methods in specific practical fields. The articles illustrate how to derive new domain-specific knowledge from data through the proficient use of data analysis methods. The journal also publishes survey papers that outline and clarify the fundamental ideas and techniques of special methods.

国际期刊《Advances in Data Analysis and Classification》（ADAC）旨在提供一个高标准的论坛，专注于从多种类型的数据中提取已知信息的研究与应用。期刊发表关于数据分析的结构、定量或统计方法的文章；分类、聚类和模式识别方法的最新进展；对复杂数据建模和大数据集挖掘的策略；从数据中提取知识的方法，以及在特定实践领域中应用先进方法的研究。文章展示了如何通过熟练运用数据分析方法，从数据中获取新的领域知识。此外，期刊还发表对特殊方法的基本思想和技术的综述性论文。

Greedy Gaussian segmentation of multivariate time series

This work considers the problem of breaking a multivariate (vector) time series into segments over which the data is well explained as independent samples from a Gaussian distribution as a covariance-regularized maximum likelihood problem, and proposes a heuristic method that approximately solves the problem in linear time with respect to this length.

Category	Quartile
计算机科学	4
计算机科学, 统计学与概率论	4

Greedy Gaussian segmentation of multivariate time series

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
STATISTICS & PROBABILITY	2