# 時系列の次元削減へのアプローチ(An approach to dimensionality reduction in time series) > [!abstract] 概要 > データ系列(時系列)の次元削減手法は過去数十年にわたって数多く提案されてきた。 > その一部は元データの記号表現に基づくが、その場合、得られる次元削減は大きくない。 > 本論文では、多次元時系列の次元を削減する新しい手法として、記号的本質属性近似(Symbolic Essential Attributes Approximation, SEAA)を提案する。 > これにより、元のデータ系列の新しい名義表現を形成する。 > この手法は、データ系列のエンベロープと、多層ニューラルネットワークが生成する本質属性の概念に基づく。 > 実数値の属性を離散化することで、データ系列の記号表現が形成される。 > SEAA は、元のデータ系列の圧縮表現となる新しい属性の名義値ベクトルを生成する。 > この名義属性は合成的であり、直接解釈することはできないが、元のデータ系列の重要な特徴を保持している。 > 提案する次元削減の有用性は、分類とクラスタリングのタスクで検証した。 > 実験では、次元を大きく削減しても、新しい表現が時系列の分類とクラスタリングに十分な情報を保持することが示された。 ## 論文情報 - 著者: [[Maciej Krawczak]](ワルシャワ情報技術大学 / ポーランド科学アカデミー系統研究所)、[[Grażyna Szkatuła]](ポーランド科学アカデミー系統研究所) - 掲載: Information Sciences, 260, 15-36, 2014(受理 2013-10-30、オンライン公開 2013-11-06) - DOI: 10.1016/j.ins.2013.10.037 - 種別: 手法提案(22 ページ)。評価は UCI の Synthetic Control Chart 1 データセットのみ。 ## 概要 時系列を 3 段で圧縮して名義属性のベクトルにする SEAA を提案する。第 1 段が区間ごとの最大値・最小値によるエンベロープ、第 2 段が 5 層の自己連想ニューラルネットワーク(オートエンコーダ相当)の第 2 隠れ層出力である本質属性、第 3 段が等幅離散化である。Synthetic Control Chart の 3 クラス 150 系列で、規則ベースの分類とクラスタリングがほぼ満点になったと報告する。ただし比較の土台は揃っておらず、成立範囲は検証された範囲に限られる。 ## 問題設定 - 時系列マイニング(索引・クラスタリング・分類・要約・異常検知)は、系列が長いと計算負荷が重く、手法が脆くなる(次元の呪い。[[次元の呪い]])。次元削減で表現を短くしつつ、対象タスクに必要な情報を残したい。 - 代表的な既存手法は PAA(区間平均)、APCA、DFT、DWT、PCA、HMM などで、多くは実数値を扱う。記号表現では SAX が最も競争力が高いとされるが、PAA の後に記号化するだけで、次元削減の幅は大きくない。 - 動機は「単一手法で情報を大きく失うより、複数手法を重ねて情報を段階的に減らす方が有効ではないか」という観察である。 ## 提案手法 SEAA は 3 部からなる(SAX の 2 部構成に対し、中央の本質属性生成が SAX に無い部分である)。前処理として各系列を平均 0・標準偏差 1 に正規化する。 ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig01-sax.png]] (Figure 1. SAX の構成: 系列 → PAA → 離散化 → 記号表現) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig02-seaa.png]] (Figure 2. SEAA の構成: 系列 → エンベロープ近似 → 本質属性生成 → 離散化 → 記号表現) ### 1. エンベロープ近似 長さ M の系列を長さ m の等間隔区間に分け、各区間の最大値(上側)または最小値(下側)で置き換えて区間ごとに 1 点にする。長さは ⌊M/m⌋ になり、圧縮率は 1/m である。m は実験的に決める(大きいほど圧縮が強いが情報を失う)。 ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig03-envelopes.png]] (Figure 3. (a) 4 ステップの上側・下側近似、(b) 4 ステップのエンベロープ) ### 2. 本質属性の生成 エンベロープ(次元 ⌊M/m⌋)を入力と出力に取る 5 層の自己連想ニューラルネットワークを学習する。第 1・第 3 隠れ層と入出力層は ⌊M/m⌋ 個、第 2 隠れ層は E 個(E ≪ ⌊M/m⌋)のシグモイドニューロンで、第 2 隠れ層の出力を本質属性 b_i とする(出力 [-1,1] を 1000 倍して用いる、式 5)。学習は誤差逆伝播(モーメンタム付き)で、誤差は式 6・7 の二乗誤差である。本質属性は集合として扱い、要素の順序に意味は無いが、全データで固定の並びを使う。 ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig04-autoassoc-nn.png]] (Figure 4. 本質属性を生成するニューラルネットワーク。破線部が圧縮を担う) 本質属性の差 b_i - b_j(i > j)の全組合せ K = C(E,2) 個を新属性 c_j とし(式 8)、暗黙の関係を明示する。E = 5 なら K = 10 で、属性数は増える。 ### 3. 離散化 新属性の共通値域を [0, 1000] に写像し(c := c/2 + 500)、P 個の等幅区間に分けて文字 a, b, c, ... を割り当てる(式 9)。全属性で分割が共通なので、同じ文字は属性間で同じ意味を持つ。他の離散化法(等頻度、エントロピー基準など)は未検討であり、未解決として残す。 ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig05-discretization.png]] (Figure 5. 属性の離散化: 値域を等幅の区間に分け、a, b, c, ... を割り当てる) ## 新規性 - 系列そのものの記号化ではなく、エンベロープをニューラルネットワークで圧縮した特徴の記号化である。時間順序と形状は保存されない(著者も認める)。 - 属性の差をとる再編成と、全属性共通の等幅離散化により、名義属性の集合として規則学習・クラスタリングにそのまま渡せる表現を作る。 - 事前の研究は同じ著者らのエンベロープ分類(2010)、名義クラスタリング(2012)で、本論文はそれらの構成を一本化してまとめた位置づけである。 ## 実験設定 - データ: UCI の Synthetic Control Chart Time Series。6 クラス(正常・周期・増加トレンド・減少トレンド・下方シフト・上方シフト)各 100 系列、長さ 60。本論文は上方シフト(E)・下方シフト(F)・正常(A)の 3 クラスだけを使う。 - 各クラス 50 系列、計 150 系列を、学習 75(各 25)と検証 75(各 25)に分割する。系列 1・40・75 の値例を Table 1 に示す。 (Table 1. 選んだ 3 本の学習用系列 x1..x60 の値とパターン) - 設定: m = 4(⌊60/4⌋ = 15 点のエンベロープ)。隠れ層数 E は 1〜15 で学習誤差を比較し、E = 5(誤差 0.05、平均差 2.5%)を採用。離散化は P = 10。ニューラルネットワークはシミュレータ JNNS で 10,000 サイクル学習した。 - 分類: 整数計画法(集合被覆の変形)で各クラスの最小規則集合を導く。学習データを全件説明する規則を作り、検証データで精度を測る。 - クラスタリング: 名義属性向けの階層型手法である摂動法(Clustering Perturbation Method)で 3 クラスタに分ける。クラス名は使わず、結果との照合だけに使う。 ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig06-learning-series.png]] (Figure 6. 正規化した学習用 75 系列(パターン E・F・A)) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig07-step-approx.png]] (Figure 7. 系列 1 の 4 ステップ (a) 上側近似 と (b) 下側近似) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig08-deviation.png]] (Figure 8. 4 ステップ (a) 上側近似 と (b) 下側近似 の平均偏差) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig09-envelopes.png]] (Figure 9. 4 ステップの (a) 上側エンベロープ と (b) 下側エンベロープ) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig10-learning-error.png]] (Figure 10. (a) 隠れニューロン数と学習誤差、(b) E = 5 の学習誤差曲線) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig11-nn-five-attrs.png]] (Figure 11. 5 個の本質属性を生成するニューラルネットワーク(入力・出力 15、第 2 隠れ層 5)) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig12-essential-attrs.png]] (Figure 12. 本質属性 b_j(j = 1..5)の (a) 上側 と (b) 下側 エンベロープでの値) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig13-new-attributes.png]] (Figure 13. 新属性 c_j(j = 1..10)の (a) 上側 と (b) 下側 エンベロープでの値) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig14-discretization-ex.png]] (Figure 14. 新属性の離散化: [0, 1000] を 100 刻みの 10 区間に分け a〜j を割り当てる) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig15-nominal-attributes.png]] (Figure 15. 名義属性 a_j(j = 1..10)の (a) 上側 と (b) 下側 エンベロープでの値) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig16-sax-sarg-flow.png]] (Figure 16. Lavangnananda らの手法(SAX + 自己調整型関連規則生成器 SARG)の構成) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig17-sax-nn-flow.png]] (Figure 17. Lavangnananda らの手法(SAX + ニューラルネットワーク)の構成) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig18-classification-flow.png]] (Figure 18. 分類の流れ: SEAA → 記号表現 → 整数計画法 → 基本規則) ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig19-clustering-flow.png]] (Figure 19. クラスタリングの流れ: SEAA → 記号表現 → 摂動法 → クラスタ数) ## 実験結果 エンベロープと本質属性の値例は Table 2(系列 1・40・75 の 4 ステップ上側・下側エンベロープ y1..y15)と Table 3(同じ系列の本質属性 b1..b5)、名義属性は Table 4 に載る。 (Table 2. 4 ステップの (a) 上側 と (b) 下側 エンベロープ) (Table 3. (a) 上側 と (b) 下側 エンベロープの本質属性 b1..b5) (Table 4. (a) 上側 と (b) 下側 エンベロープの名義属性 a1..a10) - 圧縮率(式 10-12): エンベロープで 1/4、本質属性で 1/3(15 → 5)、離散化で 4/32 = 1/8(32 ビットの実数を 10 値の記号に)。積は 1/96。属性の差をとる段で属性数は 5 から 10 に増えるため、この 1/96 は差の再編成による増加を勘定していない。値の個数だけで見れば 60 → 10 の 6 倍圧縮である。 - 分類(Table 7・8): 上側エンベロープは学習 100%・検証 98.7%(75 件中 74 件正解。誤りは正常クラスの 1 件で、クラス 3 は 96%)、下側エンベロープは学習・検証とも 100%。規則は少数の属性に集約された(例: 上側は a4 = g、a7 = i、a10 = j なら上方シフト、下側は a4 の値だけで 3 クラスを分けた)。 (Table 9. 上側エンベロープのクラスタ記述) (Table 10. 下側エンベロープのクラスタ記述) (Table 11. クラスタリング精度: 上側・下側とも 100%) (Table 12. Control Chart 分類の既存手法の精度: 1 近傍 98.7%、論理規則 + ブースティング 96.4%、多層パーセプトロン 98.1%、複数分類器 92.8%、多重スケールヒストグラム 94.0%) - クラスタリング: 上側・下側の両方で 75 系列すべてを元のクラスに正しく分け、精度 100%。下側では a4 または a10 の 1 属性でクラスタを一意に区別できた。 ![[wiki/sources/_attachments/2014__Information-Sciences__An-approach-to-dimensionality-reduction-in-time-series/fig20-clusters.png]] (Figure 20. 属性 a4 と a8 の空間で得られた 3 クラスタ) (Table 7. 分類精度: SEAA 上側 学習 100% / 検証 98.7%、下側 100% / 100%) (Table 8. クラス別の検証精度: 上側 100・100・96%、下側 100・100・100%) - 比較(Table 5・6・12): 同じ Control Chart データ(6 クラス)への既存手法の精度は(Table 5: SAX + SARG 98.00%、回帰木 98.3%、決定木 69.3%。Table 6: SAX + 多層パーセプトロン 94.78%、SAX + 時間遅れ 98.5%。Table 12: 下記)、SAX + SARG 98.00%、回帰木 98.3%、SAX + 時間遅れニューラルネットワーク 98.5%、1 近傍(ユークリッド距離)98.7%、多層パーセプトロン 98.1% など。著者は SEAA の分類が「特化した既存手法を上回る」とまとめる。 ## 考察 - 著者は、記号表現が系列パターンの主要な特徴を保つため、時系列の分類・クラスタリングに有効だと結論する。 - 本質属性は物理的な解釈を持たない。形状を保存しない点は SAX と異なる。 - 今後の課題として、エンベロープ以外の近似を自己連想ネットワークの入力にすること、本質属性の生成を一般的な特徴生成として掘り下げることを挙げる。 ## 強み / 弱点・課題 強み: - 段階的な圧縮(3 段)で、最終表現が名義属性の短い記号列になり、規則学習や名義データ向けクラスタリングにそのまま使える。規則は少数の属性条件で読める。 - ビット換算で見た圧縮が強い。 弱点・課題(本ページの評価であり、原文の主張ではない): - **比較が揃っていない**。SEAA は 3 クラス・75 学習/75 検証で測った値で、比較表の既存手法は 6 クラスの精度である。「特化手法を上回る」は同じ設定の比較ではない。著者自身、クラスタリングは文献に結果が無く比較できないと述べる。 - 検証は合成データ 1 種類のみ。同データの 3 クラスは、平均レベルが階段状に異なるシフト系列で、エンベロープ 4 点の違いでも区別しやすい。他のデータ(UCR など)で成り立つかは不明である。 - 検証データが 75 件と小さく、98.7% は 1 件の誤りに相当する。乱数の初期値や学習の再現性(複数回の平均・分散)の報告は無い。 - m、E、P、離散化法、上側と下側のどちらを使うかを実験的に選ぶ必要があり、その選び方に検証データを使ったかの記述は無い(学習誤差のみで選んだと読める)。 - 属性の差による再編成は属性数を増やすが、それが精度に効く根拠(アブレーション)は示されない。 - 時間順序を捨てるため、系列の可視化・類似度検索・異常箇所の特定には向かない。 出典: 本文と図表(Figure 1-20、Table 1-12)。