文献

J-GLOBAL ID：201202221946136607   整理番号：12A1673242

階層グリッドを用いた四分木探索による移動軌跡データからの並列分散型頻出パターン検出

Parallel Distributed Trajectory Pattern Mining Based on Quadtree Search with Hierarchical Grid

著者 (5件)： 神野良太 (神戸大学大学院システム情報学研究科計算科学専攻(現在は,西日本旅客鉄道株式会社に勤務.)) ,  熊南昂司 (神戸大学大学院システム情報学研究科計算科学専攻) ,  福井聡 (神戸大学工学部情報知能工学科) ,  関和広 (神戸大学大学院システム情報学研究科計算科学専攻) ,  上原邦昭 (神戸大学大学院システム情報学研究科計算科学専攻)
資料名： 人工知能学会論文誌(Web)  (TJSAI (Web))
巻： 27  号： 5  ページ： 308-319 (J-STAGE)  発行年： 2012年 
JST資料番号： U0128A  ISSN： 1346-8030  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 移動軌跡データマイニングでは2次元で表現された位置情報をグリッドによって1次元情報に簡略化しているが,データや位置によって適切なグリッドの解像度が異なる。本論文では,複雑な移動軌跡パターンの検出と大規模データへの適用を実現するために,グリッドの粗い上位空間レベルから細かい下位空間レベルに向かい,トップダウン的に四分木探索することで頻出パターンを検出する階層グリッド法を提案した。頻出パターンが検出されなかった領域はより下位レベルでの探索を行わないのでメモリ不足に陥りにくく,領域ごとに子パターンを検出する処理とそれらを元のパターンごとに結合する処理を並列分散処理できる。一方,似ている移動を同一パターンとして検出する場合にグリッドの解像度によって適切な移動時間誤差の決定が異なるので,ある2領域間の移動時間のばらつきが混合正規分布に基づくと仮定し,そのパラメータ推定をEMアルゴリズムによって行うことで移動時間誤差を推定した。平成10年東京都市圏パーソントリップ調査に基づく移動軌跡データに本手法を適用したところ,単一の空間レベルに注目するだけでは検出できないパターンを少ないメモリ使用量で検出できた。また,MapReduceを用いてReducer数を増やしたところ,実行時間が減少して並列化の効果が確かめられた。

シソーラス用語： *データマイニング ,  *四分木 ,  *木探索 ,  頻度 ,  記憶容量 ,  *並列処理 ,  分散処理 ,  分解能 ,  パラメータ推定 ,  最適化手法 ,  評価試験 ,  高速化
準シソーラス用語： *四分木探索 ,  並列分散処理 ,  頻出パターン ,  解像度 ,  EMアルゴリズム ,  MapReduce

分類 (3件)： 人工知能  (JE08000Z) ,  グラフ理論基礎  (IA02020S) ,  ディジタル計算機方式一般  (JC02010O)

引用文献 (17件)：

• [Agrawal 98] Agrawal, R., Gehrke, J., Gunopulos, D., and Raghavan, P.: Automatic Subspace Clustering of High Dimensional Datafor Data Mining Applications, in Proc. of SIGMOD '98, pp. 94-105 (1998)
• [Cook 00] Cook, D. J. and Holder, L. B.: Graph-Based Data Mining, IEEE Intelligent Systems, Vol. 15, No. 2, pp. 32-41 (2000)
• [Dempster 77] Dempster, A. P., Laird, N. M., and Rubin, D. B.: Maximum Likelihood from Incomplete Data via the EM Algorithm, Journal of the Royal Statistical Society Series B, Vol. 39, No. 1, pp. 1-38 (1977)
• [Giannotti 07] Giannotti, F., Nanni, M., Pinelli, F., and Pedreschi, D.:Trajectory Pattern Mining, in Proc. of 13th SIGKDD, pp. 330-339 (2007)
• [Gidofalvi 09] Gidofalvi, G. and Pedersen, T. B.: Mining Long, Sharable Patterns in Trajectories of Moving Objects, Geoinformatica, Vol. 13, No. 1, pp. 27-55 (2009)

タイトルに関連する用語 (5件)： 階層 ,  グリッド ,  探索 ,  移動軌跡 ,  頻出パターン