時系列の類似性検索における上界関数による効率化

瀧 敬士  中村 哲也  上原 邦昭  

誌名
電子情報通信学会論文誌 D   Vol.J91-D   No.12   pp.2926-2938
発行日: 2008/12/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: データマイニング
キーワード: 
データマイニング,  時系列,  類似度,  次元圧縮,  

本文: PDF(737.9KB)>>
論文を購入




あらまし: 
近年,時系列の分類に関する研究が盛んに行われている.その一つとして多次元時系列の類似性検索に有効な手法Angular Metrics for Shape Similarity(AMSS)がある.AMSSは時系列をベクトル系列として扱い,個々のベクトルの角度を比較して類似度を計測し,動的計画法を用いてベクトル系列間全体の類似度を計算する手法である.また,角度の比較にはコサイン類似度を用いているため,ノイズのような部分は類似度に影響を与えないようにできるという特徴がある.しかしながら,計算コストが高いという問題点を抱えている.本論文では,AMSSを用いた検索のフィルタリングとして上界関数を導入して,計算コストを削減する手法を提案する.ここで上界関数とは,本来の関数より必ず大きな値となる近似値を求める関数である.具体的には,ベクトル系列を合成ベクトル系列に変換して,近似値を求めている.上界関数を用いるため,類似しない時系列をfalse dismissalなしに検索対象から取り除くことができるという特徴がある.最終的に,上界関数の正当性を示すために,数学的帰納法による証明について述べる.