# 時系列次元削減 ## 定義 長さ M の時系列を、長さ K(K < M)の別の表現に写す非可逆圧縮。索引・クラスタリング・分類などの計算負荷を下げ、次元の呪い([[次元の呪い]])を避けるために使う。圧縮率と保持する情報のトレードオフが本質である。 ## 手法の系譜 [[@2014__Information-Sciences__An approach to dimensionality reduction in time series]] が整理する分類は次のとおり(本節はこの 1 本の整理に基づく)。 - 間引き: 一定間隔の標本化。形状は粗く保つ。 - 区分近似: 区間ごとに関数で近似する。PAA(等長区間の平均)、APCA(区間長が可変)、区間の総変動、線形補間・回帰、知覚的に重要な点(PIP)の保持など。 - 変換領域: DFT、DWT、PCA、HMM。 - 記号表現: 区間を記号に写す。SAX は PAA の出力を記号列にする(区間数とアルファベットサイズの 2 パラメータ)。時間順序と全体の形を保つが、次元削減の幅は大きくない。 - 複数手法の連鎖: SEAA は区間の最大・最小によるエンベロープ、自己連想ニューラルネットワークの中間層出力(本質属性)、等幅離散化を重ね、時間順序を捨てて長さ 10 の名義属性ベクトルにした。 ## 未編纂の観察 - 記号表現の評価は、Synthetic Control Chart の分類・クラスタリング精度で行われることが多い(SAX 系 3 系統と SEAA)。手法間の比較は、クラス数や分割が揃わないと成り立たない。(Source: [[@2014__Information-Sciences__An approach to dimensionality reduction in time series]]) - [フレーム数の自動決定] PAA のフレーム数は通常人手で決める。YADING は標本化定理の考えを用い、各系列の自己相関曲線の最初の極小から代表周波数を求め、全系列の 80 パーセンタイルを周波数上限として、その逆数をフレーム数とする。自己相関は FFT で O(sD log D) で求まる。SEAA のような名義属性への連鎖圧縮とは異なり、時間順序と形状を保つ削減である。(Source: [[@2015__VLDB__YADING - Fast Clustering of Large-Scale Time Series Data]], [[@2014__Information-Sciences__An approach to dimensionality reduction in time series]]) - [手法の系譜] 表現手法を「データ適応・非データ適応・モデルベース・データ支配」の 4 種に分ける分類がある。データ適応は個々を良く近似するが複数系列の比較が難しく、非データ適応は等長で比較が容易。クリップド表現(平均との大小 1 ビット)は形状でなく変化の類似に基づくクラスタリングに十分とされる。(Source: [[@2015__Information-Systems__Time-series clustering - A decade review]]) - Ding らの比較(8 表現 × 38 データセット、下限の緊密さ)では、近年の表現手法の間の差はごくわずかである。多くの表現は高速化と索引に主眼を置き、表現の質を扱う研究は少ない。(Source: [[@2015__Information-Systems__Time-series clustering - A decade review]]。Ding らの結果は同レビュー内の引用) - 離散値系列・不均一標本・データ誤差・長さの異なる変数を持つ多変量系列を扱う表現手法は、2015 年のレビュー時点でほぼ無いと指摘される。(Source: [[@2015__Information-Systems__Time-series clustering - A decade review]]) ## 未解決の問い - 名義表現への圧縮で失う情報は、時系列類似度検索や異常箇所の特定といった、分類・クラスタリング以外のタスクでどこまで許容されるか。 - 離散化法(等幅・等頻度・エントロピー基準)の選択は、次元削減後のタスク精度にどう効くか。 - 自己相関に基づくフレーム数の推定は、ストリームでは逐次更新できない(著者が将来課題とする)。逐次更新できる次元削減はクラスタリング品質をどこまで保てるか。 - 長さの異なる変数を持つ多変量系列向けの表現は、その後どこまで整ったか ## 関連 - 概念: [[時系列クラスタリング]] / [[時系列類似度検索]] / [[次元の呪い]] - ソース: [[@2014__Information-Sciences__An approach to dimensionality reduction in time series]] / [[@2015__VLDB__YADING - Fast Clustering of Large-Scale Time Series Data]] / [[@2015__Information-Systems__Time-series clustering - A decade review]] - エンティティ: [[Maciej Krawczak]] / [[Grażyna Szkatuła]] ## 出典 - [[@2014__Information-Sciences__An approach to dimensionality reduction in time series]](手法の分類と SEAA) - [[@2015__VLDB__YADING - Fast Clustering of Large-Scale Time Series Data]](PAA のフレーム数の自動推定) - [[@2015__Information-Systems__Time-series clustering - A decade review]](表現手法の 4 分類と Table 2 の一覧)