分段聚合近似法

分段聚合近似法（英文：Piecewise Aggregate Approximation，PAA）是一种时间序列数据的降维方法，最早由埃蒙·基奥（Eamonn Keogh）等人提出，用于建立时间序列索引。相比于离散傅里叶变换、离散小波变换、奇异值分解等降维方法，分段聚合近似法操作比较简便，适用于更多距离度量，例如加权欧氏距离。并且分段聚合近似法还适用于索引长度和查询长度不同的情况。如今分段聚合近似法已经成为一种广泛应用的时间序列处理方法。

定义

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

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

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

索引建立方法

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

应用领域

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

外部連結

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