Optimal Partitioning Changepoint Analysis

doi:10.3390/math14081353

2026-04-17

Vittorio Maniezzo *

Vecchi, Lisa

DOI：10.3390/math14081353

原文链接

原文求助

摘要

En 中文

时间序列中的变点检测是统计建模和数据驱动决策中的基本任务。我们提出了一种基于集合划分的变点检测模型，该模型利用组合优化来识别解释观测数据的最佳分段集合。与依赖成本函数上严格结构假设以确保可计算性的传统动态规划方法不同，我们的模型基于整数线性规划。虽然保留了分段成本的可加性假设，但所提出的框架在能够直接在优化模型中纳入局部和全局结构约束方面区别于现有方法。特别是，它支持从简单的分段级限制到耦合多个分段的复杂全局条件等一系列约束，而无需修改底层求解方案。这种增强的建模能力构成了本工作的主要贡献，显著提高了框架的表达能力，同时保留了可加成本结构的可计算性。该模型的设计使其能够高度适应不同的应用领域，包括金融、生物信息学和工业监控。现代MILP求解器的效率与定制的支配规则相结合，使得在合理时间内求解包含数百个观测值的实例成为可能。计算结果表明，该方法将可计算性扩展到先前研究过的设置之外，有效处理了结构约束无法被现有方法容纳的实例类别，同时保持了鲁棒性和可解释性。

Keyword:

time series

set partitioning problem

segmentation

changepoint detection