6

遷移確率によってリンクされている状態がいくつかあります（マルコフ連鎖のように遷移行列内に埋め込まれています）。ある状態（〜ノード）から別の状態（遷移行列の最初と最後）に移行できる十分に高い確率のみを考慮して、この遷移行列を要約したいと思います。より高い確率のみを考慮した場合、遷移行列が最初の状態（またはノード）から最後の状態（またはノード）に移動することを決して許可しないようにするためのしきい値。

2つの質問：

そのようなメソッドを実装するいくつかのよく知られたライブラリ（優先的にPython言語）はありますか？私のナイーブ/経験的/プロトタイプのアプローチは、しきい値の値を減らす1つのループであり、最初の状態から最後の状態への遷移行列を通過できるかどうかを確認します（距離行列のベストパスアルゴリズムの一種ですか？）。しかし、これには非常に長い計算時間が必要になる可能性がありますか？

Example 1: 
DistMatrix = [[       'a',   'b',     'c',    'd'], 
             ['a',  0,      0.3,    0.4,    0.1],
             ['b',   0.3,    0,      0.9,    0.2],
             ['c',   0.4,    0.9,    0,      0.7],
             ['d',   0.1,    0.2,    0.7,   0]]  
    states are a,b,c,d. I want to find the value (threshold) that allow to go from a to d (no matter if other states are walked)  
    Naive approach:
    - first loop: threshold 0.9, I get rid of lesser probabilities: I can only connect c and b 
    - second loop: threshold 0.7, I get rid of lesser probabilities: I can only connect c, b, d
    - third loop: threshold 0.4, I get rid of lesser probabilities: I can connect a,c, b, d: here is my threshold: 0.4

->遷移行列に数千の状態があるとすぐに、信じられないほど複雑になるはずですか？->提案するアルゴリズム？

Example 2:
DistMatrix =
[       'a',   'b',     'c',    'd'],
['a',   0,      0.3,    0.4,    0.7],
['b',   0.3,    0,      0.9,    0.2],
['c',   0.4,    0.9,    0,      0.1],
['d',   0.7,    0.2,    0.1,    0] ] 
states are a,b,c,d. I want to find the value (threshold) that allow to go from a to d (no matter if other states are walked) 
Naive approach:
-first loop: threshold 0.9, I get rid of all others: I can only connect c and b
-second loop: threshold 0.7, I get rid of lesser connexion: I connect b and c, and a and d but because a and d are connected, I have my threshold!
4

2 に答える 2

8

E氏が提案したことを拡張するために、数千ノードのグラフで適切に機能するアルゴリズムの2つのバージョンを次に示します。どちらのバージョンもNumpyを使用し、2番目のバージョンもNetworkXを使用します。

Numpy配列を使用できるようにするには、「a」、「b」、「c」、および「d」の識別子を削除する必要があります。これは、ノード名を0から。までの整数に変換することで簡単に実行できますlen(nodes)。アレイは次のようになります

DistMatrix1 = np.array([[0,      0.3,    0.4,    0.1],
                        [0.3,    0,      0.9,    0.2],
                        [0.4,    0.9,    0,      0.7],
                        [0.1,    0.2,    0.7,   0]])

DistMatrix2 = np.array([[0,      0.3,    0.4,    0.7],
                        [0.3,    0,      0.9,    0.2],
                        [0.4,    0.9,    0,      0.1],
                        [0.7,    0.2,    0.1,    0]])

numpy.unique距離行列内のすべての確率のソートされた配列を取得するために使用します。次に、E氏の提案に従って、標準の二分探索を実行します。二分探索の各ステップで、行列のエントリが現在の確率を下回っている場合は、0に置き換えます。グラフで幅優先探索を実行し、最初のノードを開始して、最後のノードに到達するかどうかを確認します。実行するとしきい値が高くなり、そうでない場合はしきい値が低くなります。bfsコードは、実際にはNetworkXバージョンから採用されています。

import numpy as np

def find_threshold_bfs(array):
    first_node = 0
    last_node = len(array) - 1
    probabilities = np.unique(array.ravel())
    low = 0
    high = len(probabilities)

    while high - low > 1:
        i = (high + low) // 2
        prob = probabilities[i]
        copied_array = np.array(array)
        copied_array[copied_array < prob] = 0.0
        if bfs(copied_array, first_node, last_node):
            low = i
        else:
            high = i

    return probabilities[low]


def bfs(graph, source, dest):
    """Perform breadth-first search starting at source. If dest is reached,
    return True, otherwise, return False."""
    # Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py
    # by D. Eppstein, July 2004.
    visited = set([source])
    nodes = np.arange(0, len(graph))
    stack = [(source, nodes[graph[source] > 0])]
    while stack:
        parent, children = stack[0]
        for child in children:
            if child == dest:
                return True
            if child not in visited:
                visited.add(child)
                stack.append((child, nodes[graph[child] > 0]))
        stack.pop(0)
    return False

低速ですが短いバージョンはNetworkXを使用します。二分探索では、bfsを実行する代わりに、行列をNetworkXグラフに変換し、最初のノードから最後のノードへのパスがあるかどうかを確認します。パスがある場合はしきい値が高く、パスがない場合はしきい値が低くなります。NetworkXのすべてのグラフデータ構造はNumpy配列よりもはるかに効率が悪いため、これは低速です。ただし、他の多くの便利なアルゴリズムにアクセスできるという利点があります。

import networkx as nx
import numpy as np

def find_threshold_nx(array):
    """Return the threshold value for adjacency matrix in array."""
    first_node = 0
    last_node = len(array) - 1
    probabilities = np.unique(array.ravel())
    low = 0
    high = len(probabilities)

    while high - low > 1:
        i = (high + low) // 2
        prob = probabilities[i]
        copied_array = np.array(array)
        copied_array[copied_array < prob] = 0.0
        graph = nx.from_numpy_matrix(copied_array)
        if nx.has_path(graph, first_node, last_node):
            low = i
        else:
            high = i

    return probabilities[low]

NetworkXバージョンは、（私のラップトップ上で）1,000ノード以上のグラフでクラッシュします。bfsバージョンは、数千ノードのグラフのしきい値を簡単に見つけることができます。

コードの実行例は次のとおりです。

In [5]: from percolation import *

In [6]: print('Threshold is {}'.format(find_threshold_bfs(DistMatrix1)))
Threshold is 0.4

In [7]: print('Threshold is {}'.format(find_threshold_bfs(DistMatrix2)))
Threshold is 0.7

In [10]: big = np.random.random((6000, 6000))

In [11]: print('Threshold is {}'.format(find_threshold_bfs(big)))
Threshold is 0.999766933071

タイミングについては、（最近のMacbook Proで）次のようになります。

In [5]: smaller = np.random.random((100, 100))

In [6]: larger = np.random.random((800, 800))

In [7]: %timeit find_threshold_bfs(smaller)
100 loops, best of 3: 11.3 ms per loop

In [8]: %timeit find_threshold_nx(smaller)
10 loops, best of 3: 94.9 ms per loop

In [9]: %timeit find_threshold_bfs(larger)
1 loops, best of 3: 207 ms per loop

In [10]: %timeit find_threshold_nx(larger)
1 loops, best of 3: 6 s per loop

お役に立てれば。

アップデート

宛先ノードに到達するたびに停止するようにbfsコードを変更しました。上記のコードとタイミングが更新されました。

于 2012-12-04T01:02:22.520 に答える
0

ただし、あなたの質問を正しく解釈しているのかわかりません。

候補のしきい値があり、との間にパスがあるかどうかを判断したいとしaますd。aしきい値処理されたグラフで単純な深さ優先探索を実行し、目的のエンドノードにアクセスしたかどうかを確認することで、アクセス可能なノードを確認できますd。

しきい値を実際に見つけるには、ゼロとグラフの最大遷移確率（ここでは0.9）の間にある必要があります。したがって、各段階で深さ優先探索を使用してしきい値の二分探索を実行し、との間にパスがあるかどうかを確認できaますd。

于 2012-11-28T14:24:12.530 に答える