分段聚合近似法

分段聚合近似法（英文：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的個人主頁 （頁面存檔備份，存於互聯網檔案館）