May 23, 2006

時系列分析におけるドットプロット
Dragomir Yankov, Eamonn J. Keogh, Stefano
Lonardi, Ada Waichee Fu: Dot Plots for Time
Series Analysis, 17th IEEE International
Conference on Tools with Artificial Intelligence
(ICTAI 2005), 2005, pp.159-168,(吉原担当)
目次
•
•
•
•
•
はじめに
手法
テストデータによる実験
Dynamic Sliding Window
結論
はじめに
• Dot Plots
– 70年代，Gibbs, McIntyre
– 連続分析とマイニングにおける強力かつ直感的手法
– 生命情報学
• ゲノム解析
• 連続類似性や整列性
– データ固有の不連続な構造には制限あり
• Ex) テキスト
• Dot Plotsの拡張
– 新たに設計
– オンラインデータのモニタリングにも使用可
導入
• “diagnal match”, “diagram method”
– アミノ酸の順序列における類似性発見の最も単
純な方法
– 例）表1：プロットとは
• 2つの要素（i成分，j成分）に
おける対行列はMmnで表現
• 3つのパターン
– matches： (atg, atg)
– reverses： (atg, gta)
– gaps： 一致はしてないが例外的な重要点
（遺伝子における突然変異 等）
• Maizel, J.V., Lenk, R.P.(1981)
– 部分的な相同関係を許した改善手法
– 生命情報学団体で普及
– 単純かつ強力な方法
– 有限長のアルファベットに限定
• 生命情報学以外の例
– コードやテキストの類似性検証
– 二ヶ国語テキスト翻訳
– ハイパーテキストリンク構造の検出
• 時系列データへの応用は？
– recurrence plots (Eckmann et al.)
• 再発性行動パターンの発見を可能にするダイナミックなシステムの設計
• 高次元の相は2次元の繰り返しで表現
xi: システムの状態 , r(xi): xi点における半径
• これによる変更点
– 特定の変動、変化なし、激しい変動、など
• 欠点
– ノイズな変動も含んでいる点
• 対応策
– 閾値でノイズを減少、パターンを強調
• 点データを扱う手法は柔軟性に欠ける
• 本稿での提案手法
– 近似した繰り返し起こる結果の確率的発見アル
ゴリズム
• 低次元における代表的な結果の比較
• 異なったクラスに分類する
– ハッシュ関数のセットを使用
• 有用なDot Plotsを作るための必要条件
–
–
–
–
ノイズに強い
不変な値と時間変化
不変なある量の時間偏り
効率的な計算
• 過去の手法との違い
– 対角線
• サイン波の連続性
– 白い境界線と中央の対角線
– サイン波の頻度変更
• 対角線の湾曲で表現
– Dot Plotsの色表現
• 準拠：青、反転：赤
方法
• 時系列におけるDot Plotsの構築
– 変化する期間の比較
– 期間ごとに対応する結果を表示
• モチーフの発見
– 時系列のマイニングにおいては不可欠なステップ
– ランダムプロジェクションにより確率的に発見
問題の定義
• 1.Match
– R：長さ（実数）, P, Q：系列, T1, T2：時系列
以下の不等号が成立 ⇒ QとPはMatch
D(P, Q)≦R
– T1において、QjでPと一致
• Qj+1でもPと一致する可能性が高い
⇒ trivial match
– 時系列データにおけるDot Plots作成の問題点
• 全ての可能なモチーフを探すために、2つの時間に縮
小されること
• 2. Time Series Dot Plot
– m, n：T1, T2における時系列の長さ
(T1, T2)：m×nのbinary行列A
• 両定義におけるP, Qは長さ制限はない
– 4章で変化する期間に対応できない例あり
– 良い長さの時、ダイナミックな変化に対応した例あり
個別の時系列
• 重要な目的
– ノイズの減少し、低次元での特性維持の提供
– 系列にプロジェクションアルゴリズムを適用
• Symbolic Aggregate approXimation(SAX) [Lin, J., 2003] を利用
• SAX
– P=p1, p2, …, pn：入力時系列パラメータ
|∑|：アルファベットの種類
w：アルファベットの大きさ、長さ
– Pはある長さごとに分割、その平均 P
P ：Piecewise Aggregate Approximation (PAA) [Keogh, E., 2000]
時系列モチーフの確率的発見
• モチーフの発見アルゴリズム
– 確率的発見の手法 [Keogh, E., 2003]
– (w, d)-motifs
• 長さwの近似したモチーフを発見
• 最高d<wでミスマッチの発生・・・don’t care
– ベースはBuhler, Tompaのプロジェクションアルゴリズム
プロジェクションと導入したモチーフの
問題
• 導入した(w, d)-motif問題 [Penvzner, Sze, 2000]
– (15,4)-motif, 20シーケンスでn=600以上, 4つの
DNAアルファベット の時に発生
• (18,6)- では確率手法を用いて発見可能
• (14,4)-, (15,4)-, (16,5)- ではモチーフ構築が困難か
時系列ドットプロットにおけるプロジェ
クション
• 時系列T1,T2の長さm=1024
sliding windows size n=128
単語長w=4
アルファベットの種類|∑|=3
• 連続した文字列は圧縮可能
– 2項目＝10番目のシーケンス（1～9番目がbcba）
• (4,0)-, (4,1)-motif ：d=1までdon’t care
– プロジェクトk < w-d なら、ハミング距離はdと同等かそれ以下
– （例）k=2の任意の箇所を選択（図4では2, 4番目）
•
•
•
•
同じプロジェクションをハッシュ
行列にカウント
閾値sでフィルタリング
対応する箇所に点をプロット
繰り返し回数の推定
• モチーフの区分け
– Buhler, Tompaは95%の信頼閾値で容易に推定
• 現実には計算量は膨大
– w=16, k=7のとき、d=3でm=132, d=5でm=3599
– Raphael et al.[2004]
• 任意で一様なkポジションを
選択するよりも、可能な
ポジションを予測
– 一様な選択でも、はるかに少ない繰り返し
• 2対のシーケンス(i1, j1), (i2, j2)
– X1, X2：m回繰り返し後の行列数
• 確率はそれぞれ推定（式6,7）
– a：アルファベットの大きさ
– 式4：長さd文字列の相違確率
– 式5：dにおける文字列の
一致する確率
– 式8,9：平均と標準偏差
オンラインにおけるモチーフ発見
• オンラインマイニングにおける不可欠な特性
– 良い時間パフォーマンス
• 計算量O(m|M|), Mは非常にまばら
• Mは比較的小さな値に制限
– 更新性
• 全てのmハッシュを保持しながら、わずかなオーバーヘッドで更新可能
• ユーザーがLデータ毎に更新
– 過去のハッシュを再利用
– 最初のL時間分は消去
• 応用：ストリーミングデータのモニタリング
– Ex)心臓のモニタリング、地震学など自然現象における調査
実験結果
• データセットで本稿のツールを検証
–薬
– 産業
– 株式市場
– 自然現象
– 音楽
例外発見におけるドットプロット
• ECG data
– 周期的なパターン：対角線
– 例外パターン：白の十字線
– W=16, d=max2
– タイムワープ
• Bは発見、Cは未発見
– 固定の長さ期間をもたないことが欠点
– Section4の手法が有効
• Powerplant data
– １９９５年前期半年の電力消費量
– 例外箇所
• 元日週
• 4月イースターと解放日
• 5月労働デー
パターン発見におけるドットプロット
• Stock Market Data
– Yahoo!とNextelの5年間の株価
（Yahoo!Financeのデータ）
– 類似点の多くは分散
• 図8B
Nextel 2001 (切り下げ)
第一、第二四半期
Yahoo! 2004（株式分割）
第二、第三四半期
– 例外点は有効
• 図8A：Nextelは下降、Yahoo!は上昇
• Audio data
– ジングルベルの短いサンプル
• ピッチを抽出
– A：コーラスの繰り返し（全体の1/3）
– 単語wを大
• ノイズのフィルタリング
• 一致、高い類似した対角線
まで除去(B地点)
• Discrete data
– 不連続なDNAデータ
(2種類のランダムな文字列)
– ダウンサンプリング手法比較
• 上図：MUMer
– 検出されなくなる
• 下図：Dot Plots
– 検出可能を維持
Dynamic Sliding Window
• 固定長の枠組みの利用
– 例外点を暗示可能
• 例外は現実に存在したかが問題
– Dynamic sliding windowのアルゴリズム
• s1, s2, …, sk：切片限度
s=s1, e=s2：Sliding Windowの始めと終わり
(si, si+1)で比率がa/bなら、(si+1, s+2)も比率a/b
• 心電図データ
– 心臓の鼓動の頻度
– 上図：一定のsliding window
• 湾曲した対角線
– 下図：Dynamic sliding window
• ほぼ直線的な対角線
結論
• 時系列にモチーフを用いたことで改善
– プロジェクションを利用したツールの開発
• ツールの有用性
– 多くのデータセットで検証
• Sliding windowの可変長化
– 時系列データの分割