データマイニング - グラフデータと経路

1. グラフとは
2. 経路

Transcript

1. グラフデータ ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科 yusuke_yamamoto@acm.org 第9回 データマイニング （グラフ分析入門） ⼭本祐輔 クリエイティブコモンズライセンス (CC BY-NC-SA 4.0)
2. クエスチョン Q. 「グラフ」と聞いて 思い浮かべるものは？
3. グラフと⾔えば グラフ グラフ チャート データ構造 CS/DSに学んだ人で「右」のグラフが頭によぎらないのはマズい…
4. 「データ構造」としてのグラフ § “点”と “ つながり”によって表されるデータ § 事物間の関係性を抽象化する強⼒なデータ構造 § “ネットワーク”と呼ぶことも
5. グラフデータの例（1/5）- ウェブページのリンク
6. グラフデータの例（1/5）- ウェブページのリンク
7. グラフデータの例（2/5）- ⼈物関係 画像出典: https://ebookjapan.yahoo.co.jp/content/author/243/ Aさん Bさん Cさん Dさん Eさん 友⼈関係
8. グラフデータの例（2/5）- ⼈物関係 画像出典: https://ebookjapan.yahoo.co.jp/content/author/243/ Aさん Bさん Cさん Dさん Eさん M F O A L D 対⽴ 恋 恋 恋 友 婚姻 C A B E D
9. グラフデータの例（3/5） - 路線図 画像出典: https://www.kotsu.city.nagoya.jp/jp/pc/subway/routemap.html
10. グラフデータの例（4/5） - 購買・出版 ユーザA ユーザB い ろ は に ほ 出版社X 出版社Y 出版社Z 出版 出版 出版 購⼊ 購⼊ 購⼊
11. グラフデータの例（5/5） 画像出典2: https://www.researchgate.net/ 画像出典1: https://commons.wikimedia.org/ 分⼦構造 化学反応
12. 関係性を表すデータはグラフとして抽象化できる ウェブ構造 分⼦構造・化学反応 経路情報 購買・製造情報 グラフ化 グラフ化 抽象化の目を養えば，グラフデータは身近にあることが分かる!!
13. グラフデータに抽象化するとできること グラフの中での点の重要度を評価できる グラフ中の特徴的なグループを発見できる グラフ中の点同士の関係性を評価・予測できる グラフの構造を定量的に分析できる 橋渡し役の点，多くの点と繋がっている点の発⾒etc. コミュニティの発⾒，分極している点群の発⾒etc. 点同⼠をつなぐ最短経路の発⾒，点と点がつながる可能性の予測etc. グラフ全体の特徴の評価，頻出する関係（つながり）の発⾒etc.
14. グラフの定義 1 Definition of Graph
15. グラフ § 事物間の関係性を抽象化する強⼒なデータ構造 § “点”と “ つながり”によって表されるデータ ノード エッジ
16. グラフの数学的定義 グラフを構成する要素 ノード （頂点; vertex） ノード間の連結関係 エッジ （枝; edge） グラフ（graph） ノードの集合とエッジの集合から構成されるデータ 2 3 4 1 5 6
17. グラフの数学的定義 グラフを構成する要素 ノード （頂点; vertex） ノード間の連結関係 エッジ （枝; edge） グラフ（graph） ノードの集合とエッジの集合から構成されるデータ 2 3 4 1 5 6
18. グラフの数学的定義 グラフを構成する要素 ノード （頂点; vertex） ノード間の連結関係 エッジ （枝; edge） グラフ（graph） ノードの集合とエッジの集合から構成されるデータ 2 3 4 1 5 6
19. グラフの数学的な定義の例 G = (V, E) V = {1, 2, 3, 4, 5, 6} E = {(1, 2), (2, 3), (4, 3), (3, 5), (4, 6), (5, 6)} ノード集合→ エッジ集合→ 2 3 4 1 5 6
20. 有向グラフと無向グラフ 2 3 4 1 5 6 有向グラフ エッジに⽅向性がある 2 3 4 1 5 6 無向グラフ エッジに⽅向性がない （双⽅向に関係があるとも⾔える）
21. 重み付きグラフ 名古屋 京都 ⼤阪 ⾦沢 東京 40分 90分 150分 100分 25分 グラフはエッジに重みを設定することが可能 例: 移動コスト, 関係の強さ 本講義では断りがない限り，枝の重みは考えない
22. NetworkX グラフの処理のためのPythonライブラリ NetworkX ⾏列計算の 効率化 汎⽤機械学習 汎⽤機械学習 グラフ深層学習
23. 例題1 以下の有向グラフをNetworkXで定義してみよう 2 4 3 1 0
24. グラフの定義 on NetworkX import networkx as nx コード中で頻繁にnetworkxライブラリを参照 するので，短い名前でアクセスできるように 略称を付けておく 2 4 3 1 0
25. グラフの定義 on NetworkX import networkx as nx V = [0, 1, 2, 3, 4] E = [ (0, 1), (1, 0), (1, 2), (2, 4), (3, 1), (4, 2), (4, 3)] ← ノードの定義 ← エッジの定義 2 4 3 1 0
26. グラフの定義 on NetworkX import networkx as nx V = [0, 1, 2, 3, 4] E = [ (0, 1), (1, 0), (1, 2), (2, 4), (3, 1), (4, 2), (4, 3)] G = nx.DiGraph() G.add_nodes_from(V) G.add_edges_from(E) ← 空の有向グラフを⽤意 ← ノード， エッジの追加 2 4 3 1 0
27. グラフの定義 on NetworkX import networkx as nx V = [0, 1, 2, 3, 4] E = [ (0, 1), (1, 0), (1, 2), (2, 4), (3, 1), (4, 2), (4, 3)] G = nx.DiGraph() G.add_nodes_from(V) G.add_edges_from(E) nx.draw(G) ← グラフの可視化 2 4 3 1 0
28. 例題2 以下の無向グラフをNetworkXで定義してみよう 2 4 3 1 0
29. 無向グラフの定義 on NetworkX import networkx as nx V = [0, 1, 2, 3, 4] E = [ (0, 1), (1, 0), (1, 2), (2, 4), (3, 1), (4, 2), (4, 3)] G = nx.Graph() G.add_nodes_from(V) G.add_edges_from(E) nx.draw(G) 2 4 3 1 0 ← 無向グラフはDiGraphではなくGraph
30. ノード，エッジの確認 on NetworkX V = G.nodes() 2 4 3 1 0 ← グラフGのノード集合にアクセス E = G.edges() ← グラフGのノード集合にアクセス for e in E: print(e) ← エッジ集合をひとつずつ確認
31. 隣接⾏列 (Adjacency Matrix ) (1/4) § グラフにおけるノードの接続関係を⽰す⾏列 § N個のノードを持つグラフの隣接⾏列のサイズは(N, N) 隣接⾏列は正⽅⾏列!! 2 4 3 1 0 𝐴 = 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0
32. 隣接⾏列 (Adjacency Matrix ) (2/4) 2 4 3 1 0 𝐴 = 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 重みなしグラフの場合 隣接⾏列のa⾏b列の要素が1 → a番⽬のノードからb番⽬の要素へのエッジが存在する 隣接⾏列のa⾏b列の要素が0 → a番⽬のノードからb番⽬の要素へのエッジが存在しない 0⾏⽬ 1列⽬ ノード0から ノード1へのエッジが存在
33. 隣接⾏列 (Adjacency Matrix ) (3/4) 2 4 3 1 0 𝐴 = 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 重みなしグラフの場合 隣接⾏列のa⾏b列の要素が1 → a番⽬のノードからb番⽬の要素へのエッジが存在する 隣接⾏列のa⾏b列の要素が0 → a番⽬のノードからb番⽬の要素へのエッジが存在しない 無向グラフの場合，隣接行列は対称行列になる
34. 隣接⾏列 (Adjacency Matrix ) (4/4) 𝐴 = 0 1 0 0 0 1 0 3 0 0 0 0 0 0 0.5 0 8 0 0 0 0 0 2 0.5 0 重み付きグラフの場合 a番⽬のノードからb番⽬の要素へのエッジが存在する場合 → 隣接⾏列のa⾏b列の要素の値は重みの値 a番⽬のノードからb番⽬の要素へのエッジが存在しない場合 → 隣接⾏列のa⾏b列の要素の値はゼロ 2 4 3 1 0 1 3 0.5 0.5 2 8
35. 隣接⾏列の取得 on NetworkX 2 4 3 1 0 import networkx as nx V = [0, 1, 2, 3, 4] E = [ (0, 1), (1, 2), (2, 4), (3, 1), (4, 3)] G = nx.Graph() G.add_nodes_from(V) G.add_edges_from(E) A = nx.adjacency_matrix(G).toarray() NumPy形式に変換 neighbors_from_1 = list(G.neighbors(1)) ノード1の隣接ノード
36. Hands-on タイム 以下のURLにアクセスして， 第9回のクイズQ1を解いてみよう https://graphnote.hontolab.org/ 36
37. 経路 2 Path
38. 経路 2 4 3 1 0 § グラフ上のエッジをたどって，あるノードから 別ノードに移動する際に通るノードの系列 § ノード間の経路が複数ある場合もある ノード4からノード2への経路 (4, 2) (4, 3, 1, 2) …
39. 到達可能性 ノード nx からノード ny への経路が存在するとき nx から ny へ到達可能という ノード0からノード3へは 到達可能 ノード3からノード0へは 到達不可能 2 4 3 1 0
40. 隣接⾏列と到達可能性（1/4） 2 4 3 1 0 𝐴 = 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 重みなし行列の場合，隣接行列のべき乗を 計算することで到達可能性を調べられる
41. 隣接⾏列と到達可能性（2/4） 2 4 3 1 0 𝐴2 = 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 ノード0が接続しているノード ノード2に 接続しているノード
42. 隣接⾏列と到達可能性（3/4） 2 4 3 1 0 𝐴2 = 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 ノード0から2ホップで 到達できるノード
43. 隣接⾏列と到達可能性（4/4） 2 4 3 1 0 𝐴3 = 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 2 1 0 ノード4から3ホップで 到達できるノード ノード4からノード2へは 経路が2つあることを意味
44. Hands-on タイム 以下のURLにアクセスして， 第9回のクイズQ2を解いてみよう https://graphnote.hontolab.org/ 44
45. 距離 ノード nx からノード ny への最短経路の長さ （or エッジの重み合計）を距離と呼ぶ 2 4 3 1 0 ノード4からノード2へは 最短経路は(4, 2) ノード4からノード2への 距離は1
46. 距離⾏列 グラフに属する全ノード間の距離を表記した行列 2 4 3 1 0 𝐷 = 0 1 2 4 3 ∞ 0 1 3 2 ∞ 3 0 2 1 ∞ 1 2 0 3 ∞ 2 1 1 0 たどり着けない ノードの距離は∞ ノード1から ノード3への距離は3
47. [参考] 最短経路発⾒や距離計算のための効率的なアルゴリム 幅優先探索 重みなしグラフ限定で効率的 ダイクストラ法 指定したノードから他の全ノードへの最短経路を⾼速に探索 ワーシャルフロイド法 グラフに属する全ノード間の最短経路を⾼速に探索 行列のべき乗計算はグラフが大きくなるとコストが大きい…
48. 最短経路アルゴリズム on NetworkX shortest_paths = dict( nx.single_source_all_shortest_paths(G, 3) ) all_shortest_paths = dict( nx.all_pairs_shortest_paths(G) ) D = nx.floyd_warshall_numpy(G) # ワーシャルフロイド法で距離⾏列を計算 # ダイクストラ法で全ノード間の最短経路を取得 # ダイクストラ法でノード3から他ノードへの最短経路を取得
49. Hands-on タイム 以下のURLにアクセスして， 第9回のクイズQ3を解いてみよう https://graphnote.hontolab.org/ 49
50. 回 実施日 トピック 9 06/13 グラフデータ 10 06/20 グラフ構造の諸指標 11 06/27 ノードの中心性 12 07/04 コミュニティ発見 13 07/11 ウェブグラフ 14 07/18 グラフ埋め込み 15 07/25 総合演習 – 社会ネットワーク分析 授業計画 50