最近在学习拐点检测的相关问题， 发现 C.Truong 的论文 对拐点检测的整个流程和目前主流的一些算法介绍的比较清楚，所以在这里进行了一些记录以及总结，并且对 Truong 发布的 ruptures 库做了一些简单的介绍。如果想要进行更深入的研究，请参考原论文和 ruptures。

拐点检测名为 change point detection，对于一条不平缓的时间序列曲线，认为存在一些时间点 ( t 1 , t 2 , . . . , t k ) (t_{1},t_{2},...,t_{k}) (t1​,t2​,...,tk​)，使得曲线在这些点对应的位置发生突变，这些时间点对应的曲线点称为拐点，在连续的两个拐点之间，曲线是平稳的。

拐点检测算法的质量通过算法输出拐点与实际观测到的拐点的差值绝对值除以样本数来评估。 ∀ k , ∣ t ^ k − t k ⋆ ∣ / T , \forall k, \quad\left|\hat{t}_{k}-t_{k}^{\star}\right| / T, ∀k,∣∣​t^k​−tk⋆​∣∣​/T, 理想情况下，当样本数T无穷大时，误差应该减少到0，这种性质称为满足渐近一致性 (asymptotic consistency.) max ⁡ k = 1 , … , K ∗ ∣ t ^ k − t k ⋆ ∣ / T ⟶ p 0 \max _{k=1, \ldots, K^{*}}\left|\hat{t}_{k}-t_{k}^{\star}\right| / T \stackrel{p}{\longrightarrow} 0 k=1,…,K∗max​∣∣​t^k​−tk⋆​∣∣​/T⟶p​0

y a . . b y_{a..b} ya..b​ 表示时间点 a 和 b 之间的时间序列，因此完整信号为 y 0.. T y_{0..T} y0..T​。

对于给定的拐点索引 t t t，它的关联分数 associate fraction 称为拐点分数 change point fractions ，公式为 ： τ : = t / T ∈ ( 0 , 1 ] . \tau :=t / T \in(0,1]. τ:=t/T∈(0,1].

拐点分数的集合 τ = { τ 1 , τ 2 , … } \boldsymbol{\tau}=\left\{\tau_{1}, \tau_{2}, \ldots\right\} τ={ τ1​,τ2​,…} 写作 ∣ τ |\boldsymbol{\tau} ∣τ|

一般思路是构造一个对照函数 contrast function，目标是将对照函数的值最小化。 V ( t , y ) : = ∑ k = 0 K c ( y t k … t k + 1 ) ， V(\mathbf{t}, y) :=\sum_{k=0}^{K} c\left(y_{t_{k} \ldots t_{k+1}}\right)， V(t,y):=k=0∑K​c(ytk​…tk+1​​)， 其中 c ( ⋅ ) c(\cdot) c(⋅) 表示用来测量拟合度 goodness-of-fit 的损失函数 cost function, 损失函数的值在均匀的子序列上较低，在不均匀的子序列上较高。

基于离散优化问题 discrete optimization problem，拐点的总数量记为 K K K ：

如果 K K K 是固定值，估算的拐点值为： min ⁡ ∣ t ∣ = K V ( t ) , \operatorname{min}_{|\mathbf{t}|=K} V(\mathbf{t}), min∣t∣=K​V(t), 如果 K K K 不是固定值，估算的拐点值为： min ⁡ t V ( t ) + pen ⁡ ( t ) . \min _{t} V(\mathbf{t})+\operatorname{pen}(\mathbf{t}). tmin​V(t)+pen(t). 其中 p e n ( t ) pen(t) pen(t)为对 t t t 的惩罚项项

在这种方法论下，拐点检测的算法包含以下三个元素：

损失函数与被检测拐点的变化类型有关，下文介绍的损失函数使用在子序列 y a . . b y_{a..b} ya..b​ 上，其中 1 < = a < b < = T 1