论文标题
在有限尺寸的参数空间中的变更斜率最佳分区算法
Change-in-Slope Optimal Partitioning Algorithm in a Finite-Size Parameter Space
论文作者
论文摘要
我们考虑通过使用平方的残留总和拟合连续的分段线性信号来检测单变量时间序列中变化点的问题。坡度断裂处的推断信号的值仅限于尺寸$ M $的有限集。使用此有限参数空间，我们为$ n $数据点构建了一个动态编程算法，其控制时间复杂度为$ O（m^2n^2）$。一些加速策略可用于在$ n^2 $之前减少常数。基于经典不平等的经典修剪的仿真方法的“通道”方法表现优于更简单的“通道”方法。此外，我们的有限参数空间设置允许在推断信号上轻松介绍约束。例如，在连续的段斜率之间施加最小角度，为模型错误指定和异常值提供了鲁棒性。我们对算法进行算法，对抗体图图像分析问题的算法约束，该问题的算法效率是在移动健康和嵌入式医疗设备的新兴背景下的基石。对于此应用程序，有限的状态方法可以是有效的妥协。
We consider the problem of detecting change-points in univariate time series by fitting a continuous piecewise linear signal using the residual sum of squares. Values of the inferred signal at slope breaks are restricted to a finite set of size $m$. Using this finite parameter space, we build a dynamic programming algorithm with a controlled time complexity of $O(m^2n^2)$ for $n$ data points. Some accelerating strategies can be used to reduce the constant before $n^2$. The adapted classic inequality-based pruning is outperformed by a simpler "channel" method on simulations. Besides, our finite parameter space setting allows an easy introduction of constraints on the inferred signal. For example, imposing a minimal angle between consecutive segment slopes provides robustness to model misspecification and outliers. We test our algorithm with an isotonic constraint on an antibiogram image analysis problem for which algorithmic efficiency is a cornerstone in the emerging context of mobile-health and embedded medical devices. For this application, a finite state approach can be a valid compromise.
