ｽﾗｲﾄﾞﾀｲﾄﾙなし

Size: px

Start display at page:

Download "ｽﾗｲﾄﾞﾀｲﾄﾙなし"

たかとしままだ
6 years ago
Views:

1 グラフマイニング技術とその応用ビッグデータをリアルタイムに分析処理分散データ処理エンジン人モノ場所などのつながりから新たな知識を発見するグラフマイニング大阪大学大学院情報科学研究科ビッグデータ工学講座教授鬼塚真

2 自己紹介所属 ~H26.6 NTT 研究所特別研究員 H26.7~ 大阪大学ビッグデータ工学講座教授これまでの研究開発画像検索マルチメディアデータベースの研究開発 XMLストリーム / データベースの高速化ウェブの検索システムの開発現在の研究テーマグラフマイニング高速化分散処理エンジンカラオケ検索ホームラン検索アラートシステム大規模分散データベース 2

3 全体構成概要グラフマイニングの応用例企業間取引分析, ウェブグラフ, テロリストソーシャル分析, トレンド分析,IoT での応用グラフマイニングの高速化技術グラフクラスタリング PageRank 計算 3

4 グラフデータの有用性データ構造の多様化 Web, facebook, 写真などの多様な情報の増加や, 携帯端末の急速な普及単純な表構造での表現処理能力の限界人物場所といった多様な情報のつながり ( ウェブ上あるいは実世界のどの場所で利用者が何を参照したか等 ) を表現可能なグラフ構造が有効大量のグラフデータを分析することが重要 4

5 高速グラフマイニング技術巨大なグラフデータウェブグラフは世界で 100 億ページ超 Facebook のソーシャルグラフは 12 億人規模購買ログ / 利用ログ : 利用者とアイテムのグラフグラフマイニング処理のコスト大 2 階層型クラスタリング :, 但しノード数ランダムウォーク :, 但しエッジ数, 繰り返し回数 O( N O(mt) ) m 高速なグラフマイニング技術が不可欠 N t 5

6 我々の研究の取り組み高速グラフクラスタリングアルゴリズム高速 modularity クラスタリング [AAAI 13] 高速 SCAN クラスタリング [DEIM 14] 高速 top-k PageRank アルゴリズム top-k PageRank[VLDB 12,14, KDD 12, SIGMOD 13, AAAI 13] top-k SimRank[ICDE 13] 繰返し型分析の分散最適化技術 Query optimization[vldb 13] 分散 NMF 最適化 [DEIM 14] 6

7 グラフマイニングの応用例 7

8 グラフマイニングの事例 NHK の震災ビッグデータ企業間の取引データを CG で可視化し, 復興後に早期に立ち上がった企業を明らかにしている Google のランキング計算ウェブのリンク構造を捉えて, 影響力のあるウェブページのランキング計算を実現ソーシャルネットワークの分析ダークネットワーク : テロリストやバイヤーのネットワークを解析して, 中枢の人物を捉える 8

9 9

10 ページランクを可視化した例出展 : The architecture of complexity, ASIS Keynote

11 global salafi jihad ネットワーク分析 Pink: bin laden グループ Yellow: core arabs Blue: maghreb arabs Green: southeast asians Bali Bombing, 2002 バリ島爆弾テロ事件アメリカ同時多発テロ事件 bin Laden 9/11 Attacks, 2001 出展 : The topology of dark networks, CACM vol.51, no.10,

12 グラフマイニングの事例人間関係の分析 : 俳優政治家のソーシャル分析グラフの均等分割 : 交通量に基づく道路網の均等メッシュ分割トレンド分析 : 論文メタデータを用いた技術年表の生成多様なグラフデータ分析結果グラフ分析政治家の勢力分析道路網の最適メッシュ分割トレンド分析 12

利用例 1: 俳優のソーシャル分析 Wikipedia から芸能人のページを機械的に収集同ページに登場する芸能人のつながりをグラフ化グラフ抽出芸能人約

14 円の大きさ = 芸能界への影響力円の色 = コミュニティ 14

15 男性俳優女性俳優女性モデル宝塚男性モデルタレント ( バラエティ一般 ) ジャニーズ系お笑い芸人女性アナウンサーハロプロ系タレント ( バラエティ司会者 ) AKB 系 15

男性俳優クラスタ影響力ランキング 1. 勝新太郎 2. 三谷幸喜 3. 北大路欣也 4. ビートたけし 5. 杉良太郎 6.

17 男性俳優女性俳優女性モデル宝塚男性モデルタレント ( バラエティ一般 ) ジャニーズ系お笑い芸人女性アナウンサーハロプロ系タレント ( バラエティ司会者 ) AKB 系 17

ジャニーズ系クラスタ男性俳優クラスタ影響力ランキング 1. 香取慎吾 2. 中居正広 3. 森光子 4. 木村拓哉 5. 滝沢秀明 6. 稲垣吾郎 7.

19 利用例 2: 論文データから技術年表生成 IT 分野の論文データを利用論文著者論文タイトル中の単語をグラフ化 + 年代分割技術年表として技術の変遷を可視化グラフ抽出 Relational Automata 50 年以上に渡る計算機科学領域の技術動向を分析 19

20 技術の変遷の可視化長いクラスタを時系列分解して可視化短いクラスタを時系列方向の関連を導出して可視化 2015/3/3 20

21 技術の変遷の可視化 graphs,algorithm, networks,time,schedulig graphs,algorithm, networks,time,complexity ,223 件 ,405 件 15,893 件 16,471 件クラスタ間分析トレンドの変遷を分析する 2015/3/3 21

22 技術の変遷の可視化 protein,analysis,structure,gene,molecular protein,analysis,prediction,gene,structure protein,analysis,prediction,networks,gene,structure クラスタ間分析トレンドの変遷を分析する 2015/3/3 22

23 利用例 3: IoT の応用例 EU との共同プロジェクト : smart city, energy, shopping, EU: スペインサンタンデル, フランスリヨン等 JP: 大阪テストベッドを利用した IoT の実証実験既存テストベッドの活用と相互連携利用者の参加による実証実験アーキテクチャセンサを利用してデータを収集サーバ側でビッグデータ処理アクチュエータなどを用いてサービスを実現 23

24 A horizontal and extensible platform for hosting services and applications from various domains divers application domains SmartShopping SmartHealth Horizontal Scenario SmartHome SmartCity SmartTransport APIs, Data as a Service, user portal, service management portal security and privacy user context environmental context user future behaviour user preferences user location Heterogenou s IoT devices Device as a Service; device/service discovery, generic APIs for resource access

25 » Large scale experimentation in real-life environments: Santander, Lyon, Smart city, smart building, open data, participatory sensing» Smaller scale, experimental platforms» Smart home, smart health, smart transport, art Art&Science

26 » のセンサを街中に設置» MapReduce + Hive でデータ処理» 様々な応用空き駐車スペースの掲示, バスの運行状況の把握, 電子クーポン配布, 空気の汚れ騒音のセンシング, ゴミ箱の状況を検知

experimental platform at Osaka and Kansai area» Smart POS,

27 » Large scale experimentation in real-life environments: Osaka train station: smart city, smart building» Smaller scale, experimental platform at Osaka and Kansai area» Smart POS, smart energy, smart health, smart transport, Osaka Osampo service(isid)

28 » 収集 :ibeacon を使って人の行動をセンシングアプリックス社の beacon MacBook, ipad mini» 分析 : 相互クラスタリング (matrix/tensor factorization) ( 利用者, 展示物, 状況 ) の 3 つ組みをテンソル分解» 制御 : リモコンを使って機器を制御 ( 照明, 音楽, アロマディフューザ ) A 君が休憩スペースに来ると, レモングラスのアロマが香る

29 グラフマイニングの高速化技術 29

ソーシャルグラフや Web グラフ等の人や物のつながりを表すグラフ構造入力されたグラフ構造に隠れた

30 クラスタ分析とはクラスタ分析は大量のデータから関連性の高いデータのグループを自動的に抽出してデータの隠れた構造を発見します入力 : グラフ構造出力 : グラフ構造に隠れたコミュニティ野球派バスケ派クラスタ解析サッカー派テニス派ソーシャルグラフや Web グラフ等の人や物のつながりを表すグラフ構造入力されたグラフ構造に隠れた類似した人や物同士のコミュニティグループ構造を自動的に発見 Copyright 2014 NTT corp. All Rights Reserved. 30

31 クラスタ分析高速化技術 Shiokawa et al. AAAI 13 グラフ構造を入力グラフ構造から隠れた構造を獲得野球派バスケ派サッカー派テニス派グラフ構造の計算順序を最適化グラフ構造を階層的に集約処理順序繰り返しグラフ構造の統計情報に基づき計算時間の短くなる処理順序を決定決定した処理順序に基づき類似データを探索探索により得られた類似データ集合を階層的に集約し不要な計算を削減 Copyright 2014 NTT corp. All Rights Reserved. 31

Grapon( 全て ) 計算機スペック Intel Xeon Quad-Core

32 評価実験現状最速のLouvain 法と比べ, 15.0 倍 ~58.0 倍の高速化に成功 1.2 億ノード,10 億エッジの処理を6 時間から3 分程度に短縮既存手法 Louvain 法 Grapon( 集約のみ ) Grapon( 集約 + 次数 ) Grapon( 全て ) 計算機スペック Intel Xeon Quad-Core L GHz 144GB RAM g Copyright 2014 NTT corp. All Rights Reserved. 32

34 34 Copyright 2014 NTT corp. All Rights Reserved. ノード群を入力重要度の低いノードを枝刈り重要度の上限値を利用して重要度の低いノードを枝刈りすることにより計算量削減野球選手野球コーチ重要度の高いノードを発見野球監督野球ショップのオーナ Top-k PPR 高速化技術グラフの行列化による重要度の計算ノードを並び替えてから行列分解を行うことにより行列のゼロ要素を増やし計算量削減 + = d s s c A c) (1 = d s P R Q P C T 1 ノードの並び替えと行列分解重要度計算の効率化 Fujiwara et al. KDD 12

処理速度の評価上位 K 個 (K は 10,50,100) のランキングを求める処理で従来手法と比較し

36 繰返し型処理の分散クエリ最適化技術繰返し型分析を対象 : グラフ分析クラスタリング課題 : 繰返し処理において冗長な処理がある initialize PageRank 計算の例 Onizuka et al. PVLDB 13 グラフのデータ転送を繰り返して冗長実行 query 収束したデータでも繰返して冗長実行 convergence? return 36

37 冗長性を自動的に排除する実体化ビューを利用 1. 操作対象データを繰返し更新される部分 / されない部分に分割 2. 更新されない部分データにアクセスする処理を実体化して再利用差分計算方式 1. 繰返し更新される部分を差分計算し, 収束データの処理を排除 initialize initialize initialize invariant view construction materialized view invariant view construction materialized view query U = variant view(u) U += variant view(delta U) convergence? convergence? convergence? return return return 37

38 評価実験 PageRank/k-means のケースで 5 倍高速 MapReduce/Spark 環境の両方において同様の傾向 default view view + incremental default view view + incremental response time (min) # of iterations response time (min) # of iterations PageRank Computation/webbase-2001 K-means clustering/mnist8m 38

39 まとめ : グラフマイニングと応用大規模グラフデータの分析可視化動向 : 単純な表構造データから人物場所といった多様な情報のつながりを表現するグラフ構造へ技術 : 大規模グラフの高速処理エンジン : 1 億規模のデータを数分で分析グラフマイニングの応用例企業間取引分析, ウェブグラフ, テロリストソーシャル分析, トレンド分析,IoT での応用キラーアプリ探索中 : 多言語翻訳, 知識の構造化 39

symposium_talk

symposium_talk 規模グラフデータ分析塩川浩昭筑波学計算科学研究センター計算情報学研究部助教第 8 回学際計算科学による新たな知の発統合創出シンポジウム 2016 年 10 18 1 Graph is everywhere l データエンティティと, データエンティティ間の関係性を表現した基本的なデータ構造のひとつノードエッジ 2 近にあるグラフデータ l 交通ネットワークノード : 駅交差点など

ｽﾗｲﾄﾞ ﾀｲﾄﾙなし

ｽﾗｲﾄﾞﾀｲﾄﾙなし