如何将匹配对聚合到 "connected components" in Python
How to aggregate matching pairs into "connected components" in Python
现实世界的问题：
我有许多公司董事的数据，但有时 "John Smith, director of XYZ" 和 "John Smith, director of ABC" 是同一个人，有时则不是。 "John J. Smith, director of XYZ" 和 "John Smith, director of ABC" 可能是同一个人，也可能不是。通常检查附加信息（例如，比较 "John Smith, director of XYZ" 和 "John Smith, director of ABC" 的传记数据）可以确定两个观察结果是否是同一个人。
问题的概念版本：
本着这种精神，我正在收集数据以识别匹配对。例如，假设我有以下匹配对：{(a, b), (b, c), (c, d), (d, e), (f, g)}。我想使用关系 "is the same person as" 的传递性 属性 来生成 {{a, b, c, d, e}, {f, g}} 的 "connected components"。即{a, b, c, d, e}是一个人，{f, g}是另一个人。 （该问题的早期版本提到 "cliques"，这显然是另外一回事；这可以解释为什么 networkx 中的 find_cliques 给出了 "wrong" 结果（出于我的目的） .
下面的 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))
我尝试了使用字典作为查找的替代实现，可能会稍微减少计算延迟。
# Modified to use a dictionary
from collections import defaultdict
def get_cliques2(pairs):
maxClique = 1
clique = defaultdict(int)
for (a, b) in pairs:
currentClique = max(clique[i] for i in (a,b))
if currentClique == 0:
currentClique = maxClique
maxClique += 1
clique[a] = clique[b] = currentClique
reversed = defaultdict(list)
for (k, v) in clique.iteritems(): reversed[v].append(k)
return reversed
并且只是为了说服自己 returns 正确的结果（get_cliques1 这里是你原来的 Python 2 解决方案）：
>>> from cliques import *
>>> get_cliques1(pairs) # Original Python 2 solution
[Set(['a', 'c', 'b', 'e', 'd']), Set(['g', 'f'])]
>>> get_cliques2(pairs) # Dictionary-based alternative
[['a', 'c', 'b', 'e', 'd'], ['g', 'f']]
以秒为单位的计时信息（重复 1000 万次）：
$ python get_times.py
get_cliques: 75.1285209656
get_cliques2: 69.9816100597
为了完整和参考，这是 cliques.py 和 get_times.py 计时脚本的完整列表：
# cliques.py
# Python 2.7
from collections import defaultdict
from sets import Set # I moved your import out of the function to try to get closer to apples-apples
# Original Python 2 solution
def get_cliques1(pairs):
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
# Modified to use a dictionary
def get_cliques2(pairs):
maxClique = 1
clique = defaultdict(int)
for (a, b) in pairs:
currentClique = max(clique[i] for i in (a,b))
if currentClique == 0:
currentClique = maxClique
maxClique += 1
clique[a] = clique[b] = currentClique
reversed = defaultdict(list)
for (k, v) in clique.iteritems(): reversed[v].append(k)
return reversed.values()
pairs = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e'), ('f', 'g')]
# get_times.py
# Python 2.7
from timeit import timeit
REPS = 10000000
print "get_cliques: " + str(timeit(
stmt='get_cliques1(pairs)', setup='from cliques import get_cliques1, pairs',
number=REPS
))
print "get_cliques2: " + str(timeit(
stmt='get_cliques2(pairs)', setup='from cliques import get_cliques2, pairs',
number=REPS
))
所以至少在这个人为的场景中，有一个可衡量的加速。诚然，这不是开创性的，我确信我在我的实现中在 table 上留下了一些性能位，但也许它会帮助您考虑其他替代方案？
我不相信（如果我错了请纠正我）这与最大的集团问题直接相关。 cliques 的定义（维基百科）说一个 clique "in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge"。在这种情况下，我们想要找到哪些节点可以相互访问（甚至是间接访问）。
我做了一个小样。它构建一个图并遍历它寻找邻居。这应该是非常有效的，因为在形成组时每个节点只被遍历一次。
from collections import defaultdict
def get_cliques(pairs):
# Build a graph using the pairs
nodes = defaultdict(lambda: [])
for a, b in pairs:
if b is not None:
nodes[a].append((b, nodes[b]))
nodes[b].append((a, nodes[a]))
else:
nodes[a] # empty list
# Add all neighbors to the same group
visited = set()
def _build_group(key, group):
if key in visited:
return
visited.add(key)
group.add(key)
for key, _ in nodes[key]:
_build_group(key, group)
groups = []
for key in nodes.keys():
if key in visited: continue
groups.append(set())
_build_group(key, groups[-1])
return groups
if __name__ == '__main__':
pairs = [
('a', 'b'), ('b', 'c'), ('b', 'd'), # a "tree"
('f', None), # no relations
('h', 'i'), ('i', 'j'), ('j', 'h') # circular
]
print get_cliques(pairs)
# Output: [set(['a', 'c', 'b', 'd']), set(['f']), set(['i', 'h', 'j'])]
如果您的数据集最好像图形一样建模并且非常大，那么 Neo4j 这样的图形数据库是否合适？
使用 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 数据库中有这个。只需将对组织成两列 table，然后使用 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;
（注意：我编辑了答案，因为我认为显示此步骤可能会对附录有所帮助，但对于评论来说太长了。）
DSM 的评论让我在 Python 中寻找集合合并算法。 Rosetta Code 具有相同算法的两个版本。使用示例（非递归版本）：
[('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'])]
现实世界的问题：
我有许多公司董事的数据，但有时 "John Smith, director of XYZ" 和 "John Smith, director of ABC" 是同一个人，有时则不是。 "John J. Smith, director of XYZ" 和 "John Smith, director of ABC" 可能是同一个人，也可能不是。通常检查附加信息（例如，比较 "John Smith, director of XYZ" 和 "John Smith, director of ABC" 的传记数据）可以确定两个观察结果是否是同一个人。
问题的概念版本：
本着这种精神，我正在收集数据以识别匹配对。例如，假设我有以下匹配对：{(a, b), (b, c), (c, d), (d, e), (f, g)}。我想使用关系 "is the same person as" 的传递性 属性 来生成 {{a, b, c, d, e}, {f, g}} 的 "connected components"。即{a, b, c, d, e}是一个人，{f, g}是另一个人。 （该问题的早期版本提到 "cliques"，这显然是另外一回事；这可以解释为什么 networkx 中的 find_cliques 给出了 "wrong" 结果（出于我的目的） .
下面的 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))
我尝试了使用字典作为查找的替代实现，可能会稍微减少计算延迟。
# Modified to use a dictionary
from collections import defaultdict
def get_cliques2(pairs):
maxClique = 1
clique = defaultdict(int)
for (a, b) in pairs:
currentClique = max(clique[i] for i in (a,b))
if currentClique == 0:
currentClique = maxClique
maxClique += 1
clique[a] = clique[b] = currentClique
reversed = defaultdict(list)
for (k, v) in clique.iteritems(): reversed[v].append(k)
return reversed
并且只是为了说服自己 returns 正确的结果（get_cliques1 这里是你原来的 Python 2 解决方案）：
>>> from cliques import *
>>> get_cliques1(pairs) # Original Python 2 solution
[Set(['a', 'c', 'b', 'e', 'd']), Set(['g', 'f'])]
>>> get_cliques2(pairs) # Dictionary-based alternative
[['a', 'c', 'b', 'e', 'd'], ['g', 'f']]
以秒为单位的计时信息（重复 1000 万次）：
$ python get_times.py
get_cliques: 75.1285209656
get_cliques2: 69.9816100597
为了完整和参考，这是 cliques.py 和 get_times.py 计时脚本的完整列表：
# cliques.py
# Python 2.7
from collections import defaultdict
from sets import Set # I moved your import out of the function to try to get closer to apples-apples
# Original Python 2 solution
def get_cliques1(pairs):
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
# Modified to use a dictionary
def get_cliques2(pairs):
maxClique = 1
clique = defaultdict(int)
for (a, b) in pairs:
currentClique = max(clique[i] for i in (a,b))
if currentClique == 0:
currentClique = maxClique
maxClique += 1
clique[a] = clique[b] = currentClique
reversed = defaultdict(list)
for (k, v) in clique.iteritems(): reversed[v].append(k)
return reversed.values()
pairs = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'e'), ('f', 'g')]
# get_times.py
# Python 2.7
from timeit import timeit
REPS = 10000000
print "get_cliques: " + str(timeit(
stmt='get_cliques1(pairs)', setup='from cliques import get_cliques1, pairs',
number=REPS
))
print "get_cliques2: " + str(timeit(
stmt='get_cliques2(pairs)', setup='from cliques import get_cliques2, pairs',
number=REPS
))
所以至少在这个人为的场景中，有一个可衡量的加速。诚然，这不是开创性的，我确信我在我的实现中在 table 上留下了一些性能位，但也许它会帮助您考虑其他替代方案？
我不相信（如果我错了请纠正我）这与最大的集团问题直接相关。 cliques 的定义（维基百科）说一个 clique "in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge"。在这种情况下，我们想要找到哪些节点可以相互访问（甚至是间接访问）。
我做了一个小样。它构建一个图并遍历它寻找邻居。这应该是非常有效的，因为在形成组时每个节点只被遍历一次。
from collections import defaultdict
def get_cliques(pairs):
# Build a graph using the pairs
nodes = defaultdict(lambda: [])
for a, b in pairs:
if b is not None:
nodes[a].append((b, nodes[b]))
nodes[b].append((a, nodes[a]))
else:
nodes[a] # empty list
# Add all neighbors to the same group
visited = set()
def _build_group(key, group):
if key in visited:
return
visited.add(key)
group.add(key)
for key, _ in nodes[key]:
_build_group(key, group)
groups = []
for key in nodes.keys():
if key in visited: continue
groups.append(set())
_build_group(key, groups[-1])
return groups
if __name__ == '__main__':
pairs = [
('a', 'b'), ('b', 'c'), ('b', 'd'), # a "tree"
('f', None), # no relations
('h', 'i'), ('i', 'j'), ('j', 'h') # circular
]
print get_cliques(pairs)
# Output: [set(['a', 'c', 'b', 'd']), set(['f']), set(['i', 'h', 'j'])]
如果您的数据集最好像图形一样建模并且非常大，那么 Neo4j 这样的图形数据库是否合适？
使用 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 数据库中有这个。只需将对组织成两列 table，然后使用 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;
（注意：我编辑了答案，因为我认为显示此步骤可能会对附录有所帮助，但对于评论来说太长了。）
DSM 的评论让我在 Python 中寻找集合合并算法。 Rosetta Code 具有相同算法的两个版本。使用示例（非递归版本）：
[('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'])]