SciPy-CSGraph

CSGraphは Compressed Sparse Graph の略で、スパース行列表現に基づく高速グラフアルゴリズムに焦点を当てています。

グラフ表現

まず、スパースグラフとは何か、グラフ表現でどのように役立つかを理解しましょう。

スパースグラフとは正確には何ですか？

グラフはノードのコレクションであり、ノード間にリンクがあります。グラフはほとんどすべてを表すことができます-ソーシャルネットワーク接続。各ノードは人であり、知り合いに接続されています。画像。各ノードはピクセルであり、隣接するピクセルに接続されています。各ノードが最近傍に接続されている高次元分布のポイント。そして、あなたが想像できる他の実質的に何でも。

グラフデータを表す非常に効率的な方法の1つは、スパース行列です。これをGと呼びましょう。マトリックスGのサイズはN x Nで、G [i、j]はノード「i」とノード「j」間の接続の値を示します。スパースグラフには、ほとんどゼロが含まれています。つまり、ほとんどのノードには少数の接続しかありません。このプロパティは、関心のあるほとんどの場合に当てはまります。

スパースグラフサブモジュールの作成は、以下を含むscikit-learnで使用されるいくつかのアルゴリズムによって動機付けられました-

Isomap -グラフ内の最短経路を見つける必要がある多様な学習アルゴリズム。
階層的クラスタリング-最小スパニングツリーに基づくクラスタリングアルゴリズム。
スペクトル分解-スパースグラフラプラシアンに基づく投影アルゴリズム。

具体的な例として、次の無向グラフを表現したいことを想像してください-

無向グラフ

このグラフには3つのノードがあり、ノード0と1は重み2のエッジで接続され、ノード0と2は重み1のエッジで接続されています。次の例に示すように、無向グラフは対称行列で表されることを念頭に置いて、密集したマスクされた疎な表現を構築できます。

G_dense = np.array([ [0, 2, 1],
                     [2, 0, 0],
                     [1, 0, 0] ])

G_masked = np.ma.masked_values(G_dense, 0)
from scipy.sparse import csr_matrix

G_sparse = csr_matrix(G_dense)
print G_sparse.data

上記のプログラムは、次の出力を生成します。

array([2, 1, 2, 1])

対称マトリックスを使用した無向グラフ

これは、ノード0と2が重みゼロのエッジで接続されていることを除いて、前のグラフと同じです。この場合、上記の密な表現はあいまいさをもたらします。ゼロが意味のある値である場合、どのように非エッジを表現できますか。この場合、あいまいさを解消するには、マスク表現またはスパース表現を使用する必要があります。

次の例を考えてみましょう。

from scipy.sparse.csgraph import csgraph_from_dense
G2_data = np.array
([
   [np.inf, 2, 0 ],
   [2, np.inf, np.inf],
   [0, np.inf, np.inf]
])
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print G2_sparse.data

上記のプログラムは、次の出力を生成します。

array([ 2., 0., 2., 0.])

スパースグラフを使用したワードラダー

ワードラダーは、ルイス・キャロルが発明したゲームで、各ステップで1文字ずつ変更することで単語がリンクされます。たとえば-

*APE→APT→AIT→BIT→BIG→BAG→MAG→MAN*

ここでは、「APE」から「MAN」に7つのステップで進み、そのたびに1文字ずつ変更します。問題は、同じルールを使用してこれらの単語間の短いパスを見つけることができますか？この問題は、当然、スパースグラフの問題として表されます。ノードは個々の単語に対応し、最大で1文字だけ異なる単語間の接続を作成します。

単語リストの取得

最初に、もちろん、有効な単語のリストを取得する必要があります。 Macを実行していますが、Macには次のコードブロックで指定された場所に単語辞書があります。別のアーキテクチャを使用している場合、システム辞書を見つけるために少し検索する必要がある場合があります。

wordlist = open('/usr/share/dict/words').read().split()
print len(wordlist)

上記のプログラムは、次の出力を生成します。

次に、長さ3の単語を調べたいので、正しい長さの単語だけを選択しましょう。また、大文字（固有名詞）で始まる単語や、アポストロフィやハイフンなどの英数字以外の文字を含む単語も削除します。最後に、後で比較するためにすべてが小文字であることを確認します。

word_list = [word for word in word_list if len(word) == 3]
word_list = [word for word in word_list if word[0].islower()]
word_list = [word for word in word_list if word.isalpha()]
word_list = map(str.lower, word_list)
print len(word_list)

上記のプログラムは、次の出力を生成します。

これで、1135個の有効な3文字の単語のリストができました（使用されている特定のリストによって正確な数は変わる場合があります）。これらの単語のそれぞれがグラフのノードになり、各単語のペアに関連付けられたノードを接続するエッジを作成します。これは、1文字だけ異なります。

import numpy as np
word_list = np.asarray(word_list)

word_list.dtype
word_list.sort()

word_bytes = np.ndarray((word_list.size, word_list.itemsize),
   dtype = 'int8',
   buffer = word_list.data)
print word_bytes.shape

上記のプログラムは、次の出力を生成します。

(1135, 3)

各ポイント間のハミング距離を使用して、どの単語のペアが接続されているかを判断します。ハミング距離は、異なる2つのベクトル間のエントリの割合を測定します。ハミング距離が1/N1/Nに等しい2つの単語（NNはワードラダーで接続されている文字の数）。

from scipy.spatial.distance import pdist, squareform
from scipy.sparse import csr_matrix
hamming_dist = pdist(word_bytes, metric = 'hamming')
graph = csr_matrix(squareform(hamming_dist < 1.5/word_list.itemsize))

距離を比較するとき、これは浮動小数点値に対して不安定になる可能性があるため、等式を使用しません。単語リストの2つのエントリが同一でない限り、不等式は望ましい結果をもたらします。グラフが設定されたので、最短パス検索を使用して、グラフ内の2つの単語間のパスを見つけます。

i1 = word_list.searchsorted('ape')
i2 = word_list.searchsorted('man')
print word_list[i1],word_list[i2]

上記のプログラムは、次の出力を生成します。

ape, man

単語がリストにない場合、出力にエラーがあるため、これらが一致することを確認する必要があります。ここで必要なのは、グラフ内のこれら2つのインデックス間の最短パスを見つけることです。 dijkstra’s アルゴリズムを使用します。これにより、1つのノードだけのパスを見つけることができるためです。

from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(graph, indices = i1, return_predecessors = True)
print distances[i2]

上記のプログラムは、次の出力を生成します。

5.0

したがって、「ape」と「man」の間の最短経路には5つのステップしか含まれていないことがわかります。アルゴリズムによって返された先行を使用して、このパスを再構築できます。

path = []
i = i2

while i != i1:
   path.append(word_list[i])
   i = predecessors[i]

path.append(word_list[i1])
print path[::-1]i2]

上記のプログラムは、次の出力を生成します。

['ape', 'ope', 'opt', 'oat', 'mat', 'man']

Scipy-csgraph

SciPy-CSGraph

グラフ表現

スパースグラフとは正確には何ですか？

スパースグラフを使用したワードラダー

単語リストの取得

目次