PageRank、最小全域木: ML 開発者が知っておくべき 5 つのグラフアルゴリズム

接続された世界では、ユーザーを独立したエンティティとして考えることはできません。機械学習モデルを構築するときに考慮したい特定の関係がそれらの間には存在します。

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

この記事では、データサイエンティストが知っておくべき非常に重要なグラフアルゴリズムと、それらを Python を使用して実装する方法について説明します。

接続コンポーネント

クラスタリングがどのように機能するかは誰もが知っており、接続コンポーネントは、関連/接続されたデータ内のクラスター/個体を見つけるためのハードクラスタリングアルゴリズムと考えることができます。

たとえば、世界中の任意の 2 つの都市を結ぶ道路に関するデータがあるとします。次に、世界中のすべての大陸とそこに含まれる都市を見つける必要があります。

どうやってこれを達成するのでしょうか?

私たちが使用する連結コンポーネントアルゴリズムは、幅優先探索 (BFS)/深さ優先探索 (DFS) アルゴリズムの特殊なケースです。ここでは、これがどのように機能するかを詳しく説明しません。Networkx を使用してこのコードを起動して実行する方法を見てみましょう。

応用

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

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

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

財務的な観点から: 別の使用例としては、これらの家族 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' }

ご覧のとおり、頂点とエッジのみを使用して、データ内のさまざまなコンポーネントを見つけることができます。このアルゴリズムはさまざまなデータに対して実行できるため、上記のさまざまなユースケースを満たすことができます。

最短経路

上記の例を続けると、ドイツの都市とそれらの間の距離のグラフができました。フランクフルト（出発地）からミュンヘンまでの最短距離を見つけるにはどうすればいいですか？この問題を解決するために使用するアルゴリズムは、ダイクストラと呼ばれます。ダイクストラ自身の言葉によれば：

ロッテルダムからフローニンゲンまでの最短ルートは何ですか?これは私が約 20 分で設計した最短経路アルゴリズムです。ある朝、婚約者と私はアムステルダムで買い物をしていました。疲れていたので、カフェのテラスに座ってコーヒーを飲みました。私は最短経路アルゴリズムを実装できないかと考えただけで、成功しました。

言ったように、これは 20 分間の発明です。実際、この本は 1959 年に出版されましたが、今日でも非常に読みやすい本です。これがとても素晴らしい理由の一つは、ペンと紙を使わずにデザインしたことです。後で知ったのですが、ペンと紙を使わずにデザインする利点の 1 つは、避けられる複雑さをすべて避けざるを得なくなることです。結局、驚いたことに、このアルゴリズムは私の有名な成果の 1 つになりました。

応用

ダイクストラのアルゴリズムのバリエーションは、最短ルートを見つけるために 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)
 --------------------------------------------------------
 ( 'マンハイム' 、 { 'マンハイム' : [ 'マンハイム' ], 'フランクフルト' : [ 'マンハイム' 、 'フランクフルト' ], 'カールスルーエ' : [ 'マンハイム' 、 'カールスルーエ' ], 'アウクスブルク' : [ 'マンハイム' 、 'カールスルーエ' 、 'アウクスブルク' ], 'カッセル' : [ 'マンハイム' 、 'フランクフルト' 、 'カッセル' ], 'ヴュルツブルク' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' ], 'ミュンヘン' : [ 'マンハイム' 、 'カールスルーエ' 、 'アウクスブルク' 、 'ミュンヘン' ], 'エアフルト' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' 、 'エアフルト' ]、 'ナンベルク' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' ]、 'シュトゥットガルト' : [ 'マンハイム' 、 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' 、 'シュトゥットガルト' ]})
 ( 'フランクフルト' 、 { 'フランクフルト' : [ 'フランクフルト' ], 'マンハイム' : [ 'フランクフルト' 、 'マンハイム' ], 'カッセル' : [ 'フランクフルト' 、 'カッセル' ], 'ヴュルツブルク' : [ 'フランクフルト' 、 'ヴュルツブルク' ], 'カールスルーエ' : [ 'フランクフルト' 、 'マンハイム' 、 'カールスルーエ' ], 'アウクスブルク' : [ 'フランクフルト' 、 'マンハイム' 、 'カールスルーエ' 、 'アウクスブルク' ], 'ミュンヘン' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルグ' 、 'ミュンヘン' ], 'エアフルト' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'エアフルト' ]、 'ナンベルク' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' ]、 'シュトゥットガルト' : [ 'フランクフルト' 、 'ヴュルツブルク' 、 'ナンベルク' 、 'シュトゥットガルト' ]})
 ....

最小全域木 (MST)

今、私たちは別の問題に直面しています。私たちが配管会社や電気配線会社で働いているとしましょう。最小限の配線/パイプを使用して、マップ内のすべての都市を接続する必要があります。どうすればいいでしょうか?

左:無向グラフ、右:対応する MST

応用

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

コード

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

左:無向グラフ、右:対応する MST。

ページランク

上の図は、Google が長年サポートしてきたページ並べ替えアルゴリズムを示しています。入ってくるリンクと出ていくリンクの数と品質に基づいてページにスコアを付けます。

応用

Pagerank は、ネットワークノードの重要性を推定したい場所であればどこでも使用できます。

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

コード

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

 # データセットの読み取り
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(pagerank.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次接続ノード = リスト(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 = [ '黄色'   v == 3437の場合 それ以外  '赤'  サブグラフ_3437のvについて]
ノードサイズ = [ 1000   v == 3437の場合 それ以外  35  サブグラフ_3437のvについて] 
 
 plt.style.use( 'fivethirtyeight' )
 plt.rcParams[ 'figure.figsize' ] = ( 20 , 15 )
 plt.axis( 'オフ' )
 nx.draw_networkx(サブグラフ_3437、pos、with_labels = False、ノードカラー = node_color、ノードサイズ = node_size)
 plt.show()

黄色は最も影響力のあるユーザーを表します

中心性測定

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

他のメトリックへのリンク: https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness。

媒介中心性: 多くの友人を持つユーザーだけでなく、ある地理的な場所を別の地理的な場所に接続するユーザーも重要です。これにより、ユーザーはさまざまな場所からのコンテンツを閲覧できるようになります。

媒介中心性は、特定のノードが他の 2 つのノード間の最短経路に出現する回数を定量化します。

次数中心性: ノードが持つ接続の数です。

コード

以下はサブグラフの媒介中心性を見つけるコードです。

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