分段聚合近似法

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

定义 
设时间序列的长度为。将其用一条长度为的向量表示，第个元素的定义为：

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

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

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

应用领域 
作为一种时间序列降维方法，分段聚合近似法得到了广泛的应用，是一些时间序列的低维表示方法的前期处理步骤之一。
在使用分段聚合近似法建立索引后，为了进行各种查询，要使用某种距离进行度量。为了避免假阴性情况的出现，所使用的距离需要满足以下特征：

如果的定义为：
，则满足上述条件。一些时间序列的检索方法，例如K-NN的算法中，会使用具有以上特征的距离，根据索引进行初步筛选。
时间序列降维方法

參考資料

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