ダイナミックタイムワーピングのための類似探索手法

概要

論文の詳細を見る
本論文ではダイナミックタイムワーピングのための類似探索手法を提案する.気象学,天体物理学,地質学,マルチメデイア,経済など,時系列データは数多くの分野で用いられている.それらの中では,時系列データのシーケンスどうしを比較して,その類似性を評価することが頻繁に行われている.従来の研究では,シーケンスの距離基準として主にユークリッド距離が用いられていた.ユークリッド距離関数はシーケンスの各要素を独立して比較するため,長さの異なるシーケンスのペア,もしくはサンプリングレートの異なるシーケンスのペアの距離を比較することは難しい.さらにユークリッド距離関数は,シーケンスに少しでもアウトライアー(異常値)があると,それらに影響を受けることもある.これに対してダイナミックタイムワーピング(DTW ; Dynamic Time Warping)は,各々のシーケンスの中で時間軸を柔軟に変化させて距離を算出することができる.このため,近年数多くのアプリケーションでDTWが用いられている.しかし,DTWは動的計画法に基づくアプローチで計算されるため,計算コストが高いことが問題となっている.そこで,DTWに基づく類似検索を高速化するために,DTW距離を近似する距離関数,およびその関数を用いた索引手法,探索手法を提案する.提案手法は効率的に類似シーケンスを探索することができ,また近似距離関数を用いているものの,探索漏れがないことを保証する.すなわち,探索アルゴリズムはどのような問合せに対しても正確な答えを返す.具体的には,本論文ではまず,探索漏れが発生しないことを保証するための必要十分条件を提案する.そして,その必要十分条件を満足するDTWの近似距離関数について述べる.探索処理では,距離近似によって厳密な距離計算の回数が大幅に低減化する.これは高い探索性能につながる.実験では,既存手法と比べ最大で約54倍の性能向上を達成し,提案手法の優位性が明らかとなった.
一般社団法人情報処理学会の論文
2004-03-15

ダイナミックタイムワーピングのための類似探索手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク