グラフマイニング技術とその応用 ビッグデータをリアルタイムに分析処理 分散データ処理エンジン 人 モノ 場所などのつながりから新たな知識を発見する グラフマイニング 大阪大学大学院情報科学研究科ビッグデータ工学講座教授鬼塚真 2015.3.11
自己紹介 所属 ~H26.6 NTT 研究所特別研究員 H26.7~ 大阪大学ビッグデータ工学講座教授 これまでの研究開発 画像検索 マルチメディアデータベースの研究開発 XMLストリーム / データベースの高速化ウェブの検索システムの開発 現在の研究テーマグラフマイニング高速化 分散処理エンジン カラオケ検索 ホームラン検索 アラートシステム 大規模分散データベース 2
全体構成 概要 グラフマイニングの応用例企業間取引分析, ウェブグラフ, テロリストソーシャル分析, トレンド分析,IoT での応用 グラフマイニングの高速化技術グラフクラスタリング PageRank 計算 3
グラフデータの有用性 データ構造の多様化 Web, facebook, 写真などの多様な情報の増加や, 携帯端末の急速な普及単純な表構造での表現 処理能力の限界人 物 場所といった多様な情報のつながり ( ウェブ上あるいは実世界のどの場所で利用者が何を参照したか 等 ) を表現可能なグラフ構造が有効 大量のグラフデータを分析することが重要 4
高速グラフマイニング技術 巨大なグラフデータウェブグラフは世界で 100 億ページ超 Facebook のソーシャルグラフは 12 億人規模購買ログ / 利用ログ : 利用者とアイテムのグラフ グラフマイニング処理のコスト大 2 階層型クラスタリング :, 但しノード数ランダムウォーク :, 但しエッジ数, 繰り返 し回数 O( N O(mt) ) m 高速なグラフマイニング技術が不可欠 N t 5
我々の研究の取り組み 高速グラフクラスタリングアルゴリズム高速 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
グラフマイニングの事例 NHK の震災ビッグデータ企業間の取引データを CG で可視化し, 復興後に早期に立ち上がった企業を明らかにしている Google のランキング計算ウェブのリンク構造を捉えて, 影響力のあるウェブページのランキング計算を実現ソーシャルネットワークの分析ダークネットワーク : テロリストやバイヤーのネットワークを解析して, 中枢の人物を捉える 8
9
ページランクを可視化した例 出展 : The architecture of complexity, ASIS Keynote 2006 10
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, 2008. 11
グラフマイニングの事例人間関係の分析 : 俳優 政治家のソーシャル分析グラフの均等分割 : 交通量に基づく道路網の均等メッシュ分割トレンド分析 : 論文メタデータを用いた技術年表の生成 多様なグラフデータ 分析結果 グラフ分析 政治家の勢力分析 道路網の最適メッシュ分割 トレンド分析 12
利用例 1: 俳優のソーシャル分析 Wikipedia から芸能人のページを機械的に収集 同ページに登場する芸能人のつながりをグラフ化 グラフ抽出 芸能人約 3,000 人のつながりから隠れたコミュニティや影響力を分析 Copyright 2014 NTT corp. All Rights Reserved. 13
円の大きさ = 芸能界への影響力 円の色 = コミュニティ 14
男性俳優 女性俳優 女性モデル 宝塚 男性モデル タレント ( バラエティ一般 ) ジャニーズ系 お笑い芸人 女性アナウンサー ハロプロ系 タレント ( バラエティ司会者 ) AKB 系 15
男性俳優クラスタ 影響力ランキング 1. 勝新太郎 2. 三谷幸喜 3. 北大路欣也 4. ビートたけし 5. 杉良太郎 6. 蜷川幸雄 7. 三船敏郎 8. 映画 舞台 ドラマ Copyright 2014 NTT corp. All Rights Reserved. 16
男性俳優 女性俳優 女性モデル 宝塚 男性モデル タレント ( バラエティ一般 ) ジャニーズ系 お笑い芸人 女性アナウンサー ハロプロ系 タレント ( バラエティ司会者 ) AKB 系 17
ジャニーズ系クラスタ 男性俳優クラスタ 影響力ランキング 1. 香取慎吾 2. 中居正広 3. 森光子 4. 木村拓哉 5. 滝沢秀明 6. 稲垣吾郎 7. 国分太一 8. 草なぎ剛 9. 近藤真広 10. 亀梨和也 お笑いクラスタ Copyright 2014 NTT corp. All Rights Reserved. 18
利用例 2: 論文データから技術年表生成 IT 分野の論文データを利用 論文 著者 論文タイトル中の単語をグラフ化 + 年代分割 技術年表として技術の変遷を可視化 グラフ抽出 Relational Automata 50 年以上に渡る計算機科学領域の技術動向を分析 19
技術の変遷の可視化 長いクラスタを時系列分解して可視化 短いクラスタを時系列方向の関連を導出して可視化 2015/3/3 20
技術の変遷の可視化 graphs,algorithm, networks,time,schedulig graphs,algorithm, networks,time,complexity 2010 14,223 件 2011 2012 2013 15,405 件 15,893 件 16,471 件 クラスタ間分析 トレンドの変遷を分析する 2015/3/3 21
技術の変遷の可視化 protein,analysis,structure,gene,molecular protein,analysis,prediction,gene,structure protein,analysis,prediction,networks,gene,structure クラスタ間分析 トレンドの変遷を分析する 2015/3/3 22
利用例 3: IoT の応用例 EU との共同プロジェクト : smart city, energy, shopping, EU: スペインサンタンデル, フランスリヨン等 JP: 大阪 テストベッドを利用した IoT の実証実験 既存テストベッドの活用と相互連携 利用者の参加による実証実験 アーキテクチャ センサを利用してデータを収集 サーバ側でビッグデータ処理 アクチュエータなどを用いてサービスを実現 23
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
» 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
» 18000 のセンサを街中に設置» MapReduce + Hive でデータ処理» 様々な応用 空き駐車スペースの掲示, バスの運行状況の把握, 電子クーポン配布, 空気の汚れ 騒音のセンシング, ゴミ箱の状況を検知
» 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)
» 収集 :ibeacon を使って人の行動をセンシング アプリックス社の beacon MacBook, ipad mini» 分析 : 相互クラスタリング (matrix/tensor factorization) ( 利用者, 展示物, 状況 ) の 3 つ組みをテンソル分解» 制御 : リモコンを使って機器を制御 ( 照明, 音楽, アロマディフューザ ) A 君が休憩スペースに来ると, レモングラスのアロマが香る
グラフマイニングの高速化技術 29
クラスタ分析とは クラスタ分析は 大量のデータから関連性の高いデータのグループを自動的に抽出してデータの隠れた構造を発見します 入力 : グラフ構造 出力 : グラフ構造に隠れたコミュニティ 野球派 バスケ派 クラスタ解析 サッカー派 テニス派 ソーシャルグラフや Web グラフ等の人や物のつながりを表すグラフ構造 入力されたグラフ構造に隠れた 類似した人や物同士のコミュニティ グループ構造を自動的に発見 Copyright 2014 NTT corp. All Rights Reserved. 30
クラスタ分析高速化技術 Shiokawa et al. AAAI 13 グラフ構造を入力 グラフ構造から隠れた構造を獲得 野球派 バスケ派 サッカー派 テニス派 グラフ構造の計算順序を最適化 グラフ構造を階層的に集約 処理順序 繰り返し グラフ構造の統計情報に基づき 計算時間の短くなる処理順序を決定 決定した処理順序に基づき類似データを探索 探索により得られた類似データ集合を階層的に集約し 不要な計算を削減 Copyright 2014 NTT corp. All Rights Reserved. 31
評価実験 現状最速のLouvain 法と比べ, 15.0 倍 ~58.0 倍の高速化に成功 1.2 億ノード,10 億エッジの処理を6 時間から3 分程度に短縮 既存手法 Louvain 法 Grapon( 集約のみ ) Grapon( 集約 + 次数 ) Grapon( 全て ) 計算機スペック Intel Xeon Quad-Core L5640 2.26GHz 144GB RAM g++ 4.1.2 Copyright 2014 NTT corp. All Rights Reserved. 32
Personalized PageRank (PPR) とは PPR は一部のノード群を指定して重みづけをすることで 指定ノード群への影響が強い重要なノード群を自動的に決定します ノード群を入力 野球選手 野球コーチ PPR 実行 野球監督 重要度の高いノードを発見 野球ショップのオーナ Copyright 2014 NTT corp. All Rights Reserved. 33
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) のランキングを求める処理で従来手法と比較し 50 倍高速 Copyright 2014 NTT corp. All Rights Reserved. 35
繰返し型処理の分散クエリ最適化技術 繰返し型分析を対象 : グラフ分析 クラスタリング 課題 : 繰返し処理において冗長な処理がある initialize PageRank 計算の例 Onizuka et al. PVLDB 13 グラフのデータ転送を繰り返して冗長実行 query 収束したデータでも繰返して冗長実行 convergence? return 36
冗長性を自動的に排除する 実体化ビューを利用 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
評価実験 PageRank/k-means のケースで 5 倍高速 MapReduce/Spark 環境の両方において同様の傾向 25 20 default view view + incremental 250 200 default view view + incremental response time (min) 15 10 5 0 1 11 21 31 41 51 61 71 # of iterations response time (min) 150 100 50 0 1 2 3 4 5 6 7 8 9 1011121314151617 # of iterations PageRank Computation/webbase-2001 K-means clustering/mnist8m 38
まとめ : グラフマイニングと応用 大規模グラフデータの分析 可視化動向 : 単純な表構造データから 人 物 場所といった多様な情報のつながりを表現するグラフ構造へ技術 : 大規模グラフの高速処理エンジン : 1 億規模のデータを数分で分析 グラフマイニングの応用例企業間取引分析, ウェブグラフ, テロリストソーシャル分析, トレンド分析,IoT での応用 キラーアプリ探索中 : 多言語翻訳, 知識の構造化 39