分段聚合近似法

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

定义

设时间序列$X=x_1,...,x_n$的长度为$n$。将其用一条长度为$N$的向量$\bar{X}$表示，$\bar{X}$第$i$个元素的定义为： ${\bar{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$个值可以通过以下公式更新： ${\bar{x}}_{ji}={\bar{x}}_{j-1i}-\frac{N}{n}{x}_{\frac{n}{N}(i-1)+1}+\frac{N}{n}{x}_{\frac{n}{N}i+1}$

应用领域

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

外部連結

• Dimensionality reduction for fast similarity search in large time series databases（提出分段聚合近似法的原始论文） Template:Wayback
• Piecewise Aggregate Approximation of time series Template:Wayback
• Eammon Keogh的个人主页 Template:Wayback