隠れマルコフモデルに基づくストリーム処理

• Item type: Trans(1)
• 公開日: 2011-12-28
• タイトル: 隠れマルコフモデルに基づくストリーム処理
• タイトル / 言語: en
• タイトル: Stream Processing through Hidden Markov Models
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 日本電信電話株式会社NTTコミュニケーション科学基礎研究所
• 著者所属: 京都大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 松原, 靖子; 櫻井, 保志; 吉川, 正俊
• 著者名(英): Yasuko, Matsubara; Yasushi, Sakurai; Masatoshi, Yoshikawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，データストリーム処理に関する研究がさかんに行われている．本論文は，隠れマルコフモデル（HMM）に基づき，与えられた問合せモデルの特徴に類似した部分シーケンスをデータストリームから検出することを目的とする．HMMはシーケンスを確率密度関数に従う生成モデルを有する状態の遷移として表現するデータモデルであり，様々な分野で広く使われているが，主として有限長の蓄積データに用いられてきた．しかし，ネットワーク分析，センサ監視等，データ量が多く緊急性が要求されるような近年のアプリケーションでは，すべてのデータを蓄積してから処理することが困難である．本研究では，このような問題を解決する手法であるStreamScanを提案する．さらに，理論的な分析を行い，精度を犠牲にしないにもかかわらず計算コストがデータストリームの長さに依存せず一定であることを証明する．様々な実データを用いた実験を行い，StreamScanがデータストリームから正確に部分シーケンスを検出し，そして従来の手法と比較して大幅な性能向上を達成していることを明らかにした．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Data stream processing has recently attracted an increasing amount of interest. Our aim is to monitor data streams, and find subsequences that have the characteristics of a given Hidden Markov Model (HMM). A lot of research effort has concentrated on pattern discovery for HMMs, and it has been studied for finite, stored sequence sets. However, in many applications such as sensor monitoring, massive amounts of data arrive continuously and it is infeasible to save all the historical data. We propose StreamScan, a novel algorithm that can solve the problem. We provide a theoretical analysis and prove that StreamScan guarantees the exactness of the output, while it requires constant space and time per time-tick. These are significant improvements over the alternative solution. Our experiments on real data illustrate that StreamScan does indeed detect the qualifying subsequences correctly and that it can offer great improvements in speed over the alternative method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 4, 号 4, p. 48-62, 発行日 2011-12-28
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会