茶年 · 中文维基百科

分段聚合近似法

Wikipedia · 2021-02-05 维基百科 👁 1 阅读

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

定义
设时间序列X = x_1,...,x_n的长度为n。将其用一条长度为N的向量\overline{X}表示，\overline{X}第i个元素的定义为：
\overline{X}_i = \frac{N} {n} \sum^{\frac{n} {N} i}_{j = \frac{n} {N} (i-1)+1}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^{N}_{i=1}(\overline{x}_{i} - \overline{y}_{i})^{2}}，则满足上述条件。一些时间序列的检索方法，例如K-NN的算法中，会使用具有以上特征的距离，根据索引进行初步筛选。

參考資料
外部連結

#时间序列降维方法

评论 (0)

  • 还没有评论，来抢沙发吧。