17

現実の問題:

私は多くの企業の取締役に関するデータを持っていますが、「XYZ の取締役であるジョン・スミス」と「ABC の取締役であるジョン・スミス」が同一人物である場合もあれば、そうでない場合もあります。また、「John J. Smith, director of XYZ」と「John Smith, director of ABC」は同一人物である場合もあれば、同一でない場合もあります。多くの場合、追加情報の調査 (たとえば、「XYZ のディレクター、ジョン・スミス」と「ABC のディレクター、ジョン・スミス」に関する伝記データの比較) により、2 つの観測が同一人物であるかどうかを解決できます。

問題の概念的なバージョン:

その精神で、一致するペアを特定するデータを収集しています。たとえば、次の一致するペアがあるとします: {(a, b), (b, c), (c, d), (d, e), (f, g)}. 「同一人物」という関係の推移性を利用して、 の「連結成分」を生成したい{{a, b, c, d, e}, {f, g}}。それは{a, b, c, d, e}一人であり、{f, g}別の人です。(質問の以前のバージョンでは、明らかに別のものである「クリーク」に言及していました。これは、(私の目的では)「間違った」結果を与えていた理由を説明します) find_cliques。networkx

次の Python コードがその役割を果たします。しかし、私は疑問に思います: より良い (計算コストの少ない) アプローチ (例えば、標準または利用可能なライブラリを使用する) はありますか?

関連すると思われる例があちこちにありますが (例: Cliques in python )、これらは不完全であるため、それらが参照しているライブラリや、それらを使用するためのデータのセットアップ方法がわかりません。

サンプル Python 2 コード:

def get_cliques(pairs):
    from sets import Set

    set_list = [Set(pairs[0])]

    for pair in pairs[1:]:
        matched=False
        for set in set_list:
            if pair[0] in set or pair[1] in set:
                set.update(pair)
                matched=True
                break
        if not matched:
            set_list.append(Set(pair))

    return set_list

pairs = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e'), ('f', 'g')]

print(get_cliques(pairs))

これにより、目的の出力が生成されます: [Set(['a', 'c', 'b', 'e', 'd']), Set(['g', 'f'])].

サンプル Python 3 コード:

これにより生成されます[set(['a', 'c', 'b', 'e', 'd']), set(['g', 'f'])]):

def get_cliques(pairs):

    set_list = [set(pairs[0])]

    for pair in pairs[1:]:
        matched=False
        for a_set in set_list:
            if pair[0] in a_set or pair[1] in a_set:
                a_set.update(pair)
                matched=True
                break
        if not matched:
            set_list.append(set(pair))

    return set_list

pairs = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e'), ('f', 'g')]

print(get_cliques(pairs))
4

4 に答える 4

12

networkX の場合:

import networkx as nx
G1=nx.Graph()
G1.add_edges_from([("a","b"),("b","c"),("c","d"),("d","e"),("f","g")])
sorted(nx.connected_components(G1), key = len, reverse=True)

与える:

[['a', 'd', 'e', 'b', 'c'], ['f', 'g']]

今すぐ最速のアルゴリズムを確認する必要があります...

OP:

これはうまくいきます！これは現在、PostgreSQL データベースにあります。ペアを 2 列のテーブルに整理し、array_agg()PL/Python 関数に渡すために使用しますget_connected()。ありがとう。

CREATE OR REPLACE FUNCTION get_connected(
    lhs text[],
    rhs text[])
  RETURNS SETOF text[] AS
$BODY$
    pairs = zip(lhs, rhs)

    import networkx as nx
    G=nx.Graph()
    G.add_edges_from(pairs)
    return sorted(nx.connected_components(G), key = len, reverse=True)

$BODY$ LANGUAGE plpythonu;

（注：このステップを示すことは補遺に役立つかもしれないと思ったので、回答を編集しましたが、コメントするには長すぎます。）

于 2015-01-15T16:44:42.000 に答える
2

DSM のコメントにより、Python でセット統合アルゴリズムを探すようになりました。Rosetta Codeには、同じアルゴリズムの 2 つのバージョンがあります。使用例 (非再帰バージョン):

[('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e'), ('f', 'g')]

# Copied from Rosetta Code
def consolidate(sets):
    setlist = [s for s in sets if s]
    for i, s1 in enumerate(setlist):
        if s1:
            for s2 in setlist[i+1:]:
                intersection = s1.intersection(s2)
                if intersection:
                    s2.update(s1)
                    s1.clear()
                    s1 = s2
    return [s for s in setlist if s]

print consolidate([set(pair) for pair in pairs])
# Output: [set(['a', 'c', 'b', 'd']), set([None, 'f']), set(['i', 'h', 'j'])]
于 2015-01-15T16:45:18.250 に答える