特定時系列データの検索手法の提案
指導教員：小林 一郎

大根千明
研究の背景と目的計算する．最後に，データベース内の全ての特徴ベクトルの中で，最もユーザのクエリの特徴ベクトルに近いものを検索結果とし，対応する時系列データをユーザへ提示する．



今日，の利用拡大に伴って膨大なデータの中から，いかに必要な情報を検索し，ユーザーに提示するかが重要な課題となっている．現在，実用化されている検索システムは主にユーザがキーワードを入力し，それを含む文書を検索する手法が主流である．この手法の問題点は文章で書かれた情報のみしか扱えないことである．そこで近年，画像や音楽などの文書以外の情報．
を検索する技術の研究も数多く報告されている
本論文では，文章以外の情報源の一つとして，グラフとして視覚化される時系列データに着目し，特定の時系列データをその形状から検索できる手法を提案する．
我々の提案手法では時系列データに対し最小二乗法近似を用いてグラフの近似曲線を作り，その近似曲線の特徴を抽出することによって，人が通常行っている方法に近い視覚的な情報からの検索を行う．また，我々の手法ではグラフの部分的な形状，および特徴を認識することにより，検索質問として与えた入力の時系列データに最も類似したデータを検索することを可能にする．本手法の適用対象としては，経済学者や天気予報士などが時系列データで観測された過去事例を検索・利用するなどが考えられる．

¾º¾ 特徴ベクトルの生成方法
入力となる時系列データは， 座標に時刻， 座標に値を持つ  平面上の標本点の集合  として与えられるものとする．以後の説明のために，  ，  ， ，  をそれぞれ  に含まれる点の 座標， 座標の最大値・最小値とする．
特徴ベクトル生成手法の概要を図 に示す．まず，与えられた標本点の集合  から最小二乗法近似を用いて， 次多項式の近似関数 を生成する．次に，この
 の導関数  ¼ を求め，方程式  ¼を解く事上の極大点・極小点の座標をによって£，曲線  得る．ここで得られる極の個数  は， ≦  ≦ となる．この点に ，  ，  ， の２点を加えたものを特徴点集合  と呼ぶ．さらに，
 に含まれる各点について，， ， ， ， となるように線形変換を施し，
 ， 正規化したものを  とする．
以上の処理により生成された正規化された特徴点集
合  の各要素の 座標， 座標を 座標の小さい順に並べたものを，特徴ベクトル， ，  ， ，
，   ，  と定義
する．



 提案手法¾º½ 提案手法の概要
本研究では複数の時系列データの中から，ユーザーの指定した時系列データに最も似ている形状の時系列データを検索し，提示する手法を提案する．図 に提案手法の概要を示す．

図112.2112.2

最小二乗法近似

112111.8

1$/ 111.6
ENY112111.8

1$/ 111.6NE
Y

111.4

111.4

111.2

111.2
111
110.8

110.8

time

time

DB

最も距離の近いベクトルを検索する

特徴ベクトル化
ユーザの検索したい時系列データ

112.4

112.4

111

特徴ベクトル化
検索対象の時系列データ集合

 

ユーザのクエリに相当する特徴ベクトル

⎞
⎛0⎟
⎜
⎟
⎜1
⎜ 0 . 15 ⎟⎟⎜⎜ 0 . 41 ⎟⎜0 . 36 ⎟⎟⎜r⎜ 0 . 55 ⎟f = ⎜⎟⎜ 0 . 72 ⎟⎜ 0 . 26 ⎟⎟⎜⎜ 0 . 92 ⎟⎜ 0 . 36 ⎟
⎟
⎜
⎟
⎜1
⎟
⎜
⎝ 0 . 23 ⎠

特徴点抽出
1

112.4
112.2

0.8

正規化

0.6

0.4

111.4
111.2

0.2

111
110.8

000.2

図 提案手法の概要

112111.8$1/ 111.6
ENY0.40.60.8 特徴ベクトルの生成¾º¿ 特徴ベクトル間の距離の計算

本手法では時系列データの検索を効率的に行うため，時系列データを特徴ベクトルへと変換し，その特徴ベクトル同士の距離を２つの時系列データの類似度として用いる．検索対象空間となる時系列データ群をあらかじめ特徴ベクトルに変換した状態でデータベースに登録しておき，ユーザからのクエリを受け付けるたびにそのクエリの時系列データから特徴ベクトルを生成し，データベース内の全ての特徴ベクトルとの距離をtime

1

前節で説明したように，特徴ベクトルの次元数は ，の範囲にある整数となる．そこで，２つの特徴ベ ， を以下のように定義する．
クトル間の距離 ，  と  の次元数が違う場合
 と  の次元数が同じ場合

 ここでは厳密な解ではなく，微分係数の符号が逆転する点を近似解としてもちいている

ただし  

log No.08

113.5

113

112.5

1$/N
EY

これは，図 の全ての双方向矢印の長さの合計に相当する．つまり，特徴点同士の位置が近いほど時系列データ間の類似性が高いと判断されることになる．また，となり「類似特徴点の個数が異なる場合は距離がしていない」と判断される．

112111.5

111

110.5

元データ
近似関数
特徴点

110
time

 ユーザのクエリ

log No100

11

144.3

144

0.8

0.8
143.7

0.6

0.6

0.4

0.4

1$/EN
Y

143.4

143.1

142.8

142.5

元データ
近似関数
特徴点

0.2

0.2

142.2
time

0000.2

0.4

0.6

0.8

100.2

0.4

0.6

0.8

1 検索結果 

最も類似していると判断された時系列データ«1log No.118

146.40.8146.1

$1/
N
EY

145.80.6

145.5145.2
元データ

0.4144.9

近似関数
特徴点

144.6
time0.2  検索結果 00

図0.20.40.60.8« 

 特徴ベクトル間の距離図

我々は提案手法を実装し，為替相場の時系列データを対象に実験を行った．対象とする時系列データは１より取得した米ドル・円，ユーロドル・分おきに
年 月から
年 月
円の為替相場データをまでの，為替取引がされていない土・日・月曜を除外
日間分にあたる個を用意したものを用いした個のデータの中から１個のデータを取た．実験は個分のデータの中から選択した１つり出し，残りのデータに最も近いものから順にデータの番号と距離を提示する，という手順で行った．本実験での，最小二乗近似の次数  は， の次数を変更してグラフの類似性を評価する予備実験により， と設定した．図にその一例を示す．

  

参考文献

  

 実験結果

中では，予備実験で得た最も良い結果の近似次数が５次であったが，為替以外の時系列データでは何次の近似次数が適しているかについては試行する必要がある．

 実装と評価番目に類似していると判断された時系列データ

1 まとめと今後の課題
本研究では，時系列データを用いて特徴ベクトルを抽出することにより，入力したデータに最も類似したデータを検索することを提案した．すべての特徴点に対する距離計算を行う完全一致のデータ検索以外にも，連続するいくつかの特徴点に対する距離が近い場所を探すことによる部分的な形状一致の検索を行うことができる．また，特徴ベクトル間の距離計算だけでは，正規化後の特徴ベクトルの分布によっては，マッチングの精度が下がる可能性がある。そのため，今後，更なる精度の向上には改善の余地がある．また本実験の   ! "#$，% #!&$， '絵の特徴から選びだす画像検索法(， 日経サイエンス )#*  +* , --* .&, /-* ,,*0* 
 "$12 34 5 / '6! 074%-!! 6#47 87-# 9
+2#&6:&;:&< =9%:4!! /7(， 0>>> 5!* +2# +&
9$ )#*  +*  --* & /-7 
 奥村菜穂子，小林一郎 'グラフの挙動を表すテキ
スト生成(，第  回年次大会ワークショップ「言語処理と情報可視化の接点」 --&.   大桃 諭，陳 漢雄，古瀬一隆，'大保信夫タイムワー
ピングに基づく時系列データの類似検索：次元縮小による効率化 >Æ:! /: ? /7# 57/ 2! 57 -!4 9 7!!#%2:! (，日本データベース学会 @ )#*+* --*& ，</ @ )#* +* 2!  --*&