もなってくらえ学院におすすめす「猫子化技術が拓くマイニングの新しい未来jシンポ石動農組,北大, 2014/03/10平成25年度JST特別課題調査「ビッグデータ統合利活用のための次世代基盤技術の創出・体系化」位置情報マイニングの現状と展望～実世界高速非構造マイニングの最前線～有村博紀北海道大学院情報科学研究科http://www-ikn.ist.hokudai.ac.jp/~arim/ e-mail: arim@ist.hokudai.ac.jp集世界からのデータマイニングに向けてノ莫世界の大規模・非定型・時空間デーの超高速処理に正面から取り組む！ B.半構造データマイニング・モデリング(グラフ・系列マイニング) Mining A.超大規模情報処理技術(超並列計算Hadoop・クラウド）検索Search庄縮表ハードウェア Compression Succinct 「定合医薬師が行くml LLV555 Iシングロデータマイニングとは●大量のデータから人間にとって有用なパターンや規則を効率良くとりだす方法の研究● 1990年代半ばから研究が盛んになった• Apriori algorithm [Agrawal, Srikant,  VLDB1994] ●潜在的には古くからある研究の集大成.ただし,大量データに対する効率的計算に重点機械学習・数理統計学・データベース技術の境界分野3.発見し知識の利用2.知識をパターンや規則として発見有利農組,北天, 2014/03/10
パターン発見■トランザクションデータから共通して出現する規則州名発目する■頻出パターン発見[Agrawal et a. ‘94] ■最適化マイニング[森下’96, ’98, ‘00]予測学習・自動分類■不完全なデータから,未知の規則を学習する■ SVM [Vapnik ‘96], ■ Boosting [Shapire & Kearns ‘96] ■ C4.5 [Quinlan ‘96]構造マイニング一■非定型構造データから特徴的な部分構造を規則性を発見する■グラフマイニング[Washio & Motoda  00], [Zaki  02], [Uno, Asai, Arimura, ’02, ‘03]クラスタリング. ■データを類似したものどうしグルーピングする. ■大規模･不完全なデータからの高速クラスタリング■ K-means, CLARANS, DBSCAN確率モデリング■高次元大規模データから不確実な現象を予測・モデル化する■ベイジアンネットワーク[Pearl '90s] ■ HMM [Asai], MCMC,ベイズ推定・MDL・AIC新しいタイプのデータマイニング, ■テキストマイニング自然言語テキスト情報抽出意味マイニング■ストリームマイニングセンサー監視近似統計処理ビッグデータ時代のデータマイニングとは？ビッグデータ時代の大規模データ処理情報世界と実世界の融合もシサOr大書のデータ・カールドOを表のCPUを(高速/永不ツト酸大な耐熱15 ■■せませんデバイス乡後本人間活動と応用き様で時的一次時空間イ完全で硬種なデークと書IN GOETLい形式リング「猫子化表術が起くてどこが新しい動きなのか？
位置情報マイニングの現状ビッグデータマイニングの鍵
■ CPS(サイバーフィジカルシステム) ■人とモノのモビリティに関心● 移動を通じて人間の活動にアクセス●社会活動の最適化(スマートXX) ●各種サービス･産業の基盤と媒体となる？ ■大量の移動体データ●プローブカー,歩行者,野生動物？ ●  GPS,スマホ,  WIFI,  etc. ■どのような情報を取り出す？ ●時空間における移動の解析・予測●移動パターンの発見(「トラジェクトリパターン」)
■「グリーン・サイバー・フィジカル・システム基盤技術開発」（代表:坂内先生／安達先生） ■ NII,九大,北大,阪大の4拠点で● NII(安達淳)「IT統合基盤のCPS共通技術」 ● 九大(安浦寛人)「データ収集／解析技術と学研都市スマートシティ化への適用」 ● 北大(田中譲)「オープン・スマート・フェデレーション技術とスマート除排雪への適用実証実験」 ● 阪大(東野輝夫)「プラットフォーム技術と都市街区における行動」 ■北大は「スマート除排雪への適用実証実験」
■時空間データはさまざまな定式化が可能①移動体(moving objects)の集合Q = $ 1 ,...,on} ●　野生動物,歩行者,プローブカー ●　付加情報は仮定しない（属性ラベルなし） ②時間T連続時間T = R離散時間T = [0..T]. (等間隔) ③空間S 2次元連続空間S = R² 2次元のメッシュS = [0..u]²道路ネットワークS = (V, E) 12有村博紀,北海道大学Mining Interesting Locations and Travel Sequences from GPS trajectories (Zheng, WWW'09)
▪ GeoLife Project
■ Microsoft Research Asia ■ Mobile phone with GPS ■ Purpose: Recommendation ■ Interesting location ■ Travel sequences ■ Using Tree-based index structure時空間ストリームマイニング▪極大群れパターン(flock pattern)発見: ▪ 2次元／3次元の時空間データストリーム・離散構造列挙技術に基づく高速マイニングアルゴリズムの開発
r = 10m, k = 3 P = (X={01,03,04}, A=[t2..t4]) ■トラジェクトリマイニング■群れ」パターンP = (X, A) ● Gudmundssonらによって導入(AGIS2006) ●移動体の集団X = {01, …, om}が,ある長さｋ以上の時間区間A = [beg, end]の間，距離r以内で一緒に移動することを表す「一緒に移動する」とは，Aの各時点tにおいて，すべての移動体の位置が，一辺rのある矩形に含まれるいと.有村博紀,北大, 2014/03/10
同期型と非同期型のパターン●移動体の位置が，厳密に同じ時刻で同期するか（同期型）(Gudmundsson他'06) ,同期せず相対時刻の意味で近接するか（非同期型）の違い. ● オリジナルの群れパターンは同期型●今回は,非同期型も導入する. O:すべての極大群れパターンの列挙が出力多項式時間（多項式遅延）でできるか？ (最大はNP完全)
■ GCPS情報学研グループとの共同開発頻出＆極大トラジェクトリパターン発見■同期と非同期のパターンを両方マイニング可能■  C++言語。今後の展開：ビッグデータ向けの大規模化Hiroki Arimura (HU) ✓　30点×3000トレース(10秒サンプリングで5分×３千台の自動車に対応） ✓　メモリ1.28MB使用✓　PC (Intel Core i7, 2.9GHz, Takeaki Uno (NII)
■ Comparing the #patterns and cputime for FPMsync and FPMasync algorithms Setting
時間がズレたパターンが正しく見つかっている

with geo-index
●  Area 100.0 x 100.0 ● 400 trajectories of length 100 generated by random walk with step 1.0 and angle ±90deg ●  5 inplanted copies of each of 40 random patterns of length 10 within width 1.0x1.0 ● Mining with max width 1.0x1.0, min length 10, and frequency at least 5. 18
Setting: N = 25 to 200 trajectories of length 40 in which N/10 patterns x 5 copies are implanted Setting: N trajectories of length 40. Other parameters are same to EXP2:
有村博紀,北大, 2014/03/10
19 「猫子化技術が花くマイニングの新しい表示シンボ「群れ」パターンマイニングで何ができるか？当日の発表で. . .非構造＆半構造マイニングビッグデータマイニングの鍵半構造マイニング■ 1990年代後半～の大規模半構造データの出現●大規模で,多様な,非定型データ●時間変化も(ビッグデータ)直接適用不可能■高速かつ頑健なマイ技術が鍵モノとモノの関係トワーク●葉物･化合物の構造からの機能予測23
超高速半構造パターン発見技術最右拡張技法(Rightmost expansion)まとめ■ビッグデータ時代のデータマイニング■位置情報マイニング■超高速な非構造パターンマイニング■移動軌跡からのマイニング■今後の展望