データサイエンティストが知っておくべき 5 つのグラフアルゴリズム

導入

グラフ分析はデータサイエンティストの未来だからです。

データサイエンティストとして、私たちは pandas、SQL、その他のリレーショナルデータベースに非常に精通しています。

私たちは、ユーザー属性を行として列として表示することに慣れています。しかし、現実世界では本当にそうなのでしょうか?

つながりのある世界では、ユーザーを独立した存在として考えることはできません。これらには一定の関係があり、機械学習モデルを構築するときにこれらの関係を考慮することがあります。

リレーショナルデータベースでは、異なる行 (ユーザー) 間のこのような関係は使用できませんが、グラフデータベースでは非常に簡単に使用できます。

この記事では、知っておくべき最も重要なグラフアルゴリズムのいくつかと、それらを Python を使用して実装する方法について説明します。

1. 接続されたコンポーネント

3つの連結要素を持つグラフ

クラスタリングがどのように機能するかは誰もが知っています。

連結コンポーネントは、一般の人でも簡単に理解できます。連結コンポーネントは、関連/連結されたデータ内のクラスター/アイランドを見つけるハードクラスタリングアルゴリズムです。

具体的な例を挙げると、世界中の任意の 2 つの都市を結ぶ道路に関するデータがあるとします。世界の大陸とそこに含まれる都市をすべて調べる必要があります

あなたならこれをどうやって達成しますか? 考えてみてください。

私たちが使用する連結コンポーネントアルゴリズムは、BFS/DFS の特殊なケースです。ここではその仕組みについてはあまり詳しく説明しません。Networkx を使用してコードを記述および実行する方法について説明します。

応用

小売業の観点から見ると、多くの顧客がいて、多くのアカウントを使用しているとします。接続コンポーネントアルゴリズムを使用する 1 つの方法は、データセット内の個別のファミリーを見つけることです。

同じクレジットカードの使用、同じ住所、同じ携帯電話番号などに基づいて、顧客 ID 間にエッジを設定できます。これらの接続を確立したら、接続コンポーネントアルゴリズムを実行して個々のクラスターを作成し、それにファミリー ID を割り当てることができます。

これらのファミリー ID を使用して、家族のニーズに基づいたパーソナライズされた推奨事項を提供できます。このファミリー ID を使用して、ファミリーベースのグループ化機能を作成し、分類アルゴリズムをサポートすることもできます。

財務の観点から見ると、もう 1 つの使用例は、これらの家族 ID を使用して詐欺を捕まえることです。あるアカウントが過去に詐欺被害に遭ったことがある場合、関連するアカウントも詐欺被害に遭う可能性が高くなります。

可能性はあなた自身の想像力によってのみ制限されます。

コード

Python の Networkx モジュールを使用してグラフを作成および分析します。

まずは、目的に応じて使用するサンプルグラフから始めましょう。都市と都市間の距離に関する情報が含まれています。

ランダム距離を使用したグラフ

まず、エッジの重みとして使用する距離を含むエッジのリストを作成します。

 edgelist = [[ 'マンハイム' 、 'フランクフルト' 、 85], [ 'マンハイム' 、 'カールスルーエ' 、 80], [ 'エアフルト' 、 'ヴュルツブルク' 、 186], [ 'ミュンヘン' 、 'ナンバリング' 、 167], [ 'ミュンヘン' 、 'アウクスブルク' 、 84], [ 'ミュンヘン' 、 'カッセル' 、 502], [ 'ナンバリング' 、 'シュトゥットガルト' 、 183], [ 'ナンバリング' 、 'ヴュルツブルク' 、 103], [ 'ナンバリング' 、 'ミュンヘン' 、 167], [ 'シュトゥットガルト' 、 'ナンバリング' 、 183] 'アウクスブルク' 、 'ミュンヘン' 、 84]、[ 'アウクスブルク' 、 'カールスルーエ' 、 250]、[ 'カッセル' 、 'ミュンヘン' 、 502]、[ 'カッセル' 、 'フランクフルト' 、 173]、[ 'フランクフルト' 、 'マンハイム' 、 85]、[ 'フランクフルト' 、 'ヴュルツブルク' 、 217]、[ 'フランクフルト' 、 'カッセル' 、 173]、[ 'ヴュルツブルク' 、 'ナンベルグ' 、 103]、[ 'ヴュルツブルク' 、 'エアフルト' 、 186]、[ 'ヴュルツブルク' 、 'フランクフルト' 、 217]、[ 「カールスルーエ」 、 「マンハイム」 、「80」]、[ 「カールスルーエ」 、 「アウクスブルク」 、「250」]、[ 「ムンバイ」 、 「デリー」 、「400」]、[ 「デリー」 、 「コルカタ」 、「500」]、[ 「コルカタ」 、 「バンガロール」 、「600」]、[ 「TX」 、 「NY」 、「1200」]、[ 「ALB」 、 「NY」 、「800」]]

Networkx を使用してグラフを構築する:

 g = nx.グラフ()
 edgelist内のedgeの場合:
 g.add_edge(エッジ[0]、エッジ[1]、重み = エッジ[2])

ここで、この地図からさまざまな大陸とそこに含まれる都市を見つけたいと思います。

連結コンポーネントアルゴリズムを使用してこれを実行できるようになりました。

 i, xがenumerate(nx.connected_components(g))に含まれる場合:
 print( "cc" +str(i)+ ":" ,x)
 ------------------------------------------------------------  
 cc0: { 'フランクフルト' 、 'カッセル' 、 'ミュンヘン' 、 'ナンベルク' 、 'エアフルト' 、 'シュトゥットガルト' 、 'カールスルーエ' 、 'ヴュルツブルク' 、 'マンハイム' 、 'アウグスブルク' }
 cc1: { 'コルカタ' 、 'バンガロール' 、 'ムンバイ' 、 'デリー' }
 cc2: { 'ALB' 、 'NY' 、 'TX' }

ご覧のとおり、データ内にさまざまなセクションを見つけることができました。エッジと頂点のみを使用する必要があります。このアルゴリズムは、さまざまなデータに対して実行して、上で説明したいずれのユースケースにも対応できます。

2. 最短経路

上記の例を続けると、ドイツの都市とそれらの間の距離のグラフができます。

フランクフルト（出発地）からミュンヘンまでの最短距離を取得する方法を知りたいです。

この問題を解決するために使用するアルゴリズムは、ダイクストラと呼ばれます。ダイクストラ自身の言葉によれば:

ロッテルダムからフローニンゲンまでの最短ルートは何でしょうか? 一般的に、最短経路のアルゴリズムは次のようなもので、これを設計するのに約 20 分かかりました。ある朝、私は若い婚約者とアムステルダムで買い物をしていました。私たちは疲れていたので、カフェのテラスに座ってコーヒーを飲んでいました。そして、この最短経路アルゴリズムを思いつくことができないかと考え、そしてそれを思いついたのです。言ったように、これは 20 分間の発明です。実際、それは 1959 年に出版されました。 3年経った今でもまだ読めるし、実際かなり良い本です。これがとても美しい理由の一つは、鉛筆と紙でデザインしなかったからです。後で知ったのですが、鉛筆と紙を使ってデザインしないことの利点の 1 つは、避けられる複雑さをすべて避けざるを得なくなることです。結局、驚いたことに、このアルゴリズムは私の名声の礎の一つとなりました。

- エドガー・ダイクストラ、フィリップ・L・フラナとのインタビューより

応用

ダイクストラのアルゴリズムのバリエーションは、最短経路を見つけるために Google マップで広く使用されています。

ウォルマートでは、さまざまな通路があり、通路間の距離も異なります。チャネル A からチャネル D への最短パスを顧客に提供したいと考えています。

LinkedIn が 1 次および 2 次接続をどのように表示するかを確認できます。舞台裏では何が起こっているのでしょうか?

コード

print(nx.shortest_path(g, 'シュトゥットガルト' , 'フランクフルト' ,weight= 'weight' ))
 print(nx.shortest_path_length(g, 'シュトゥットガルト' , 'フランクフルト' ,weight= 'weight' ))
 --------------------------------------------------------  
 [ 'シュトゥットガルト' 、 'ナンベルク' 、 'ヴュルツブルク' 、 'フランクフルト' ]
 503

すべての場所のペア間の最短経路を見つけることもできます。

 nx.all_pairs_dijkstra_path(g,weight= 'weight' )内のxについて:
 印刷(x)
 --------------------------------------------------------  
 ( 'マンハイム' 、 { 'マンハイム' : [ 'マンハイム' ], 'フランクフルト' : [ 'マンハイム' 、 'フランクフルト' ], 'カールスルーエ' : [ 'マンハイム' 、 'カールスルーエ' ], 'アウクスブルク' : [ 'マンハイム' 、 'カールスルーエ' 、 'アウクスブルク' ], 'カッセル' : [ 'マンハイム' 、 'フランクフルト' 、 'カッセル' ], 'ヴュルツブルク' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' ], 'ミュンヘン' : [ 'マンハイム' 、 'カールスルーエ' 、 'アウクスブルク' 、 'ミュンヘン' ], 'エアフルト' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' 、 'エアフルト' ]、 'ナンベルク' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' ]、 'シュトゥットガルト' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' 、 'シュトゥットガルト' ]})
 ( 'フランクフルト' 、 { 'フランクフルト' : [ 'フランクフルト' ], 'マンハイム' : [ 'フランクフルト' 、 'マンハイム' ], 'カッセル' : [ 'フランクフルト' 、 'カッセル' ], 'ヴュルツブルク' : [ 'フランクフルト' 、 'ヴュルツブルク' ], 'カールスルーエ' : [ 'フランクフルト' 、 'マンハイム' 、 'カールスルーエ' ], 'アウクスブルク' : [ 'フランクフルト' 、 'マンハイム' 、 'カールスルーエ' 、 'アウクスブルク' ], 'ミュンヘン' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルグ' 、 'ミュンヘン' ], 'エアフルト' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'エアフルト' ]、 'ナンベルク' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' ]、 'シュトゥットガルト' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' 、 'シュトゥットガルト' ]})
 ....

3. 最小全域木

今、別の問題があります。私たちは水道管敷設会社やインターネット光ファイバー会社に勤めています。マップ内のすべての都市を最小限の配線/パイプで接続する必要がありますが、どうすればよいでしょうか?

最小全域木が右側にある無向グラフ

応用

最小全域木は、コンピュータネットワーク、通信ネットワーク、輸送ネットワーク、給水ネットワーク、電力網 (元々は電力網のために発明された) などのネットワーク設計に直接応用されています。
MSTは巡回セールスマン問題を近似するために使用される
クラスタリング - 最初に MST を構築し、次にクラスター間距離とクラスター内距離を使用して、MST 内の特定のエッジの分割しきい値を決定します。
画像セグメンテーション — 画像セグメンテーションでは、まず、ピクセルがノードであり、ピクセル間の距離が何らかの類似性尺度 (色、強度など) に基づいているグラフ上に MST を構築します。

コード

# nx.minimum_spanning_tree(g) はグラフ型のインスタンスを返します
nx.draw_networkx(nx.minimum_spanning_tree(g))

グラフの最小全域木

ご覧のとおり、上には敷設する必要のある配線があります。

4. ページランク

これは、Google を長年支えてきたページランキングアルゴリズムです。入ってくるリンクと出ていくリンクの数と品質に基づいて、ページにスコアを割り当てます。

応用

Pagerank は、あらゆるネットワーク内のノードの重要性を推定したい場合に使用できます。

引用を使用して最も影響力のある論文を見つけるために使用されます。
Googleがページのランク付けに使用
ツイート-ユーザーとツイート-ツイートをノードとしてソートするために使用できます。ユーザー A がユーザー B をフォローしている場合は、ユーザー間にリンクを作成し、ユーザーがツイートをツイート/リツイートした場合は、ユーザーとツイート間にリンクを作成します。
推奨エンジン

コード

この演習では、Facebook データを使用します。 Facebook ユーザー間のエッジ/リンクのファイルがあります。まず、次を使用して FB グラフを作成します。

 # データセットの読み取り
fb = nx.read_edgelist( '../input/facebook-combined.txt' 、 create_using = nx.Graph() 、 nodetype = int )

それは次のようになります:

位置 = nx.spring_layout(fb)
 輸入警告
 警告をフィルターする( '無視' )
 plt.style.use( 'fivethirtyeight' )
 plt.rcParams[ 'figure.figsize' ] = (20, 15)
 plt.axis( 'オフ' )
 nx.draw_networkx(fb, pos, with_labels = False 、node_size = 35) を描画します。
 plt.show()

Facebook ユーザーマップ

今、私たちは影響力の高いユーザーを見つけたいと考えています。

直感的に言えば、Pagerank アルゴリズムは、多くの友達を持ち、さらに Facebook 上にも多くの友達を持つユーザーに高いスコアを与えます。

ページランク = nx.pagerank(fb)
印刷(ページランク)
 ------------------------------------------------------  
 {0: 0.006289602618466542,
 1: 0.00023590202311540972,
 2: 0.00020310565091694562,
 3: 0.00022552359869430617,
 4: 0.00023849264701222462,
 ........}

PageRank を使用すると、最も影響力のあるユーザーを取得できます。

インポート演算子
sorted_pagerank = sorted(pageranks.items(), key = operator.itemgetter(1), reverse = True ) です。
印刷(ソートされたページランク)
 ------------------------------------------------------  
 [(3437, 0.007614586844749603), (107, 0.006936420955866114), (1684, 0.0063671621383068295), (0, 0.006289602618466542), (1912, 0.0038769716008844974), (348, 0.0023480969727805783), (686, 0.0022193592598000193), (3980, 0.002170323579009993), (414, 0.0018002990470702262)、(698、0.0013171153138368807)、(483、0.0012974283300616082)、(3830、0.0011844348977671688)、(376、0.0009014073664792464)、(2047、0.000841029154597401)、(56、0.0008039024292749443)、(25、0.000800412660519768)、(828、0.0007886905420662135)、 （322、0.0007867992190291396）、......]

上記の ID は最も影響力のあるユーザー用です。

最も影響力のあるユーザーのサブグラフを見ることができます。

 1次接続ノード = list(fb.neighbors(3437))
 2次接続ノード数 = []
 first_degree_connected_nodes内のxの場合:
 2次接続ノード+=list(fb.neighbors(x))
 2番目の接続ノードを削除します(3437)
 2 番目に接続されたノード = リスト ( (2 番目に接続されたノード)を設定)
サブグラフ_3437 = nx.subgraph(fb、第 1 次接続ノード + 第 2 次接続ノード)
位置 = nx.spring_layout(サブグラフ_3437)
 node_color = [ 'yellow' if v == 3437 else   '赤'  サブグラフ_3437のvについて]
 node_size = [v == 3437 の場合は 1000 、それ以外の場合はsubgraph_3437内のvの場合は35 ]
 plt.style.use( 'fivethirtyeight' )
 plt.rcParams[ 'figure.figsize' ] = (20, 15)
 plt.axis( 'オフ' )
 nx.draw_networkx(subgraph_3437、pos、with_labels = False 、node_color = node_color、node_size = node_size)
 plt.show()

最も影響力のあるユーザー（黄色）

5. 中心性測定

機械学習モデルの特徴として使用できる中心性指標は多数あります。そのうちの2つについて説明します。

内部センター: 最も多くの友達を持つユーザーだけでなく、ある地理的な場所を別の地理的な場所に接続するユーザーも重要です。これにより、ユーザーは異なる地理的な場所からのコンテンツを表示できるようになります。本質的中心性は、特定のノードが他の 2 つのノード間の最短経路に出現する回数を測定します。
次数中心性: ノードが持つ接続の数です。

応用

中心性指標は、あらゆる機械学習モデルの機能として使用できます。

コード

上記のコードは、サブグラフの内部中心を見つけるために使用されます。

位置 = nx.spring_layout(サブグラフ_3437)
 betweennessCentrality = nx.betweenness_centrality(subgraph_3437、正規化 = True 、エンドポイント = True )
 node_size = [v * 10000 、 vはbetweennessCentrality.values () ]
 plt.figure(図サイズ=(20,20))
 nx.draw_networkx(サブグラフ_3437、pos=pos、with_labels= False 、node_size=node_size)
 plt.axis( 'オフ' )