分段聚合近似法

设时间序列${\displaystyle X=x_{1},...,x_{n}}$ 的长度为${\displaystyle n}$ 。将其用一条长度为${\displaystyle N}$ 的向量${\displaystyle {\overline {X}}}$ 表示，${\displaystyle {\overline {X}}}$ 第${\displaystyle i}$ 个元素的定义为^[5]： ${\displaystyle {\overline {X}}_{i}={\frac {N}{n}}\sum _{j={\frac {n}{N}}(i-1)+1}^{{\frac {n}{N}}i}x_{j}}$ 

简言之，为了将原始时间序列从${\displaystyle n}$ 维降低到${\displaystyle N}$ 维，需要将原始数据分割成${\displaystyle N}$ 个等长的分段，在每个分段内计算均值就可以得到降维后的数据表示。

当${\displaystyle N=n}$ 时，分段聚合近似法得到的向量就是原始时间序列本身，当${\displaystyle N=1}$ 时，分段聚合近似法得到的得到值就是原始时间序列的均值^[6]。

用分段聚合近似法建立用于子序列匹配的索引的时间复杂度为${\displaystyle O(nm)}$ 。因为对于大约${\displaystyle m}$ 个“窗口”，每个分段都要用上述公式计算${\displaystyle N}$ 次，并且上述公式要对长度为${\displaystyle {\frac {n}{N}}}$ 的部分求和。埃蒙·基奥（Eamonn Keogh）提出了一种快速计算的方法，可以将时间复杂度降低到${\displaystyle O(Nm)}$ ： 每次计算时只要从上次的结果减去上一段离开“窗口”的数据点的部分，加上新进入“窗口”的数据点的部分即可。在第${\displaystyle j}$ 个“窗口”内的第${\displaystyle i}$ 个值可以通过以下公式更新^[7]： ${\displaystyle {\overline {x}}_{ji}={\overline {x}}_{j-1i}-{\frac {N}{n}}x_{{\frac {n}{N}}(i-1)+1}+{\frac {N}{n}}x_{{\frac {n}{N}}i+1}}$ 

作为一种时间序列降维方法，分段聚合近似法得到了广泛的应用，是一些时间序列的低维表示方法的前期处理步骤之一^[8]。 在使用分段聚合近似法建立索引后，为了进行各种查询，要使用某种距离${\displaystyle D_{PAA}}$ 进行相似度（英语：Similarity measure）度量。为了避免假阴性情况的出现，所使用的距离需要满足以下特征^[9]： ${\displaystyle D_{PAA}({\overline {X}},{\overline {Y}})\leq D(X,Y)}$  如果${\displaystyle D_{PAA}}$ 的定义为： ${\displaystyle D_{PAA}({\overline {X}},{\overline {Y}}):={\sqrt {\frac {n}{N}}}{\sqrt {\sum _{i=1}^{N}({\overline {x}}_{i}-{\overline {y}}_{i})^{2}}}}$ ，则满足上述条件^[10][11]。一些时间序列的检索方法，例如K-NN的算法中，会使用具有以上特征的距离，根据索引进行初步筛选^[12]。

• Dimensionality reduction for fast similarity search in large time series databases（提出分段聚合近似法的原始论文） （页面存档备份，存于互联网档案馆）
• Piecewise Aggregate Approximation of time series （页面存档备份，存于互联网档案馆）
• Eammon Keogh的个人主页 （页面存档备份，存于互联网档案馆）