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

• Item type: Trans(1)
• 公開日: 2004-03-15
• タイトル: ダイナミックタイムワーピングのための類似探索手法
• タイトル / 言語: en
• タイトル: A Similarity Search Method for Dynamic Time Warping
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文（論文賞受賞）
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 日本電信電話株式会社NTTサイバースペース研究所
• 著者所属: 名古屋大学
• 著者所属(英): en
• 著者所属(英): NTT Cyber Space Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者名: 櫻井, 保志; 吉川, 正俊
• 著者名(英): Yasushi, Sakurai; Masatoshi, Yoshikawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文ではダイナミックタイムワーピングのための類似探索手法を提案する．気象学，天体物理学，地質学，マルチメディア，経済など，時系列データは数多くの分野で用いられている．それらの中では，時系列データのシーケンスどうしを比較して，その類似性を評価することが頻繁に行われている．従来の研究では，シーケンスの距離基準として主にユークリッド距離が用いられていた．ユークリッド距離関数はシーケンスの各要素を独立して比較するため，長さの異なるシーケンスのペア，もしくはサンプリングレートの異なるシーケンスのペアの距離を比較することは難しい．さらにユークリッド距離関数は，シーケンスに少しでもアウトライアー（異常値）があると，それらに影響を受けることもある．これに対してダイナミックタイムワーピング（DTW; Dynamic Time Warping）は，各々のシーケンスの中で時間軸を柔軟に変化させて距離を算出することができる．このため，近年数多くのアプリケーションでDTWが用いられている．しかし，DTWは動的計画法に基づくアプローチで計算されるため，計算コストが高いことが問題となっている．そこで，DTWに基づく類似検索を高速化するために，DTW距離を近似する距離関数，およびその関数を用いた索引手法，探索手法を提案する．提案手法は効率的に類似シーケンスを探索することができ，また近似距離関数を用いているものの，探索漏れがないことを保証する．すなわち，探索アルゴリズムはどのような問合せに対しても正確な答えを返す．具体的には，本論文ではまず，探索漏れが発生しないことを保証するための必要十分条件を提案する．そして，その必要十分条件を満足するDTWの近似距離関数について述べる．探索処理では，距離近似によって厳密な距離計算の回数が大幅に低減化する．これは高い探索性能につながる．実験では，既存手法と比べ最大で約54倍の性能向上を達成し，提案手法の優位性が明らかとなった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Time-series data naturally arise in many application domains, such as meteorology, astrophysics, geology, multimedia, economics, etc. There is a frequent need to find similarities between such data sequences. Most of the earlier works on high-speed sequence matching are based on the Euclidean distance function. Since the Euclidean distance function makes all sequence elements independent of each other, this function cannot calculate the distance between sequences of which the length or sampling rate is different. In addition, this function may be sensitive to a few outliers. Recent applications have employed dynamic time warping to overcome these problems. The distance of dynamic time warping is calculated with a dynamic programming algorithm. Although dynamic time warping incurs a heavy CPU cost, it is robust versus noise and scaling for the time axis. To significantly reduce the CPU cost of DTW, we introduce here an approximation technique, an index structure, and a search method. Although our search method utilizes an approximation technique, it is guaranteed to return exact answers, that is, it gives the desired sequences without false dismissals. In particular, we first propose a necessary and sufficient condition for guaranteeing that a distance approximation causes no false dismissals in similarity query processing. We then present a new approximation technique for DTW that satisfies the necessary and sufficient condition. This method prunes a significant number of the search candidates, which leads to a direct reduction in the search cost. Experiments were conducted on real and synthetic sequence data sets. The results reveal that our method is significantly (up to 54 times) faster than the best existing method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 45, 号 SIG04(TOD21), p. 23-36, 発行日 2004-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会