python - 根据条件相等，在数据框中查找匹配的人员对或人员链

Question

我是 Python 的初学者 - 首先，我想为我相当长的问题以及我为解决“问题”而编写的可能非常丑陋的程序道歉。

问题如下:想象一下交换房子去度假。人们可以用自己的房子交换彼此的假期。 “A”中的人员 1 想去“B”，“B”中的人员 2 想去“A”。然后完成匹配或易货，并且两者都不再可用于进一步的匹配。此外，还应该涵盖这样的情况:人 1 想从“A”到“B”，人 2 从“B”到“C”，因此不可能直接匹配。然而，第三个人想要从“C”转到“A”。那么这个 3 链中的交易就成为可能。人们还可以选择不指定具体目的地，因此如果有人想去他们的地方，则可以去任何地方。

所有城市都存储在字典中，其中包含相应城市定义半径内的所有地点，因此还可以在更广泛的区域(而不仅仅是特定城市)找到合适的住宿。

数据集如下所示:

name, from, to, matching partner

person1, a, b,
person2, b, a,
person3, a, b,
person4, b, c,
person5, c, a,

经过我的算法:

name, from, to, matching partner

person1, a, b,person2
person2, b, a,person1
person3, a, b,person4person5
person4, b, c,person5person3
person5, c, a,person3person4

这就是我用 Python 程序实现它的方法:

import pandas as pd
import numpy as np
import datetime as dt

data = pd.read_csv("myfile.csv", delimiter=";")

#Fill Missing Data in column "matchingpartner"
data.loc[:,"matchingpartner"] = data.loc[:,"matchingpartner"].fillna("no partner yet")

#Decide which Search Distance should be used (dict_5 for 5miles, dict_10 for 10miles, dict_9000 for 9000miles)
dict_postcode = dict_10

#Matching: Direkt 1:1 or Chain with 3 Persons
for x in range(0,data.shape[0]):
    for y in range(1,data.shape[0]): 
        for z in range(2,data.shape[0]): 
            if (x==y) | (x==z) | (y==z):
                continue
             #1 search for direct matching partners:
            if (    ((str(data.loc[x,"to"]) in dict_postcode[str(data.loc[y,"from"])]) or data.loc[x,"to"] =="dontcare") 
                and ((str(data.loc[y,"to"]) in dict_postcode[str(data.loc[x,"from"])]) or data.loc[y,"to"] =="dontcare")
                #only for persons without existing matching partner
                and (data.loc[x,"matchingpartner"] == "no partner yet") 
                and (data.loc[y,"matchingpartner"] == "no partner yet")):
                    data.loc[x,"matchingpartner"] = data.loc[y,"name"]
                    data.loc[y,"matchingpartner"] = data.loc[x,"name"]

            #2 If pairwise matching from #1 did not work, try to build matching chains of 3 or more
            elif (   str(data.loc[x,"to"]) in dict_postcode[str(data.loc[y,"from"])]  or data.loc[x,"to"] =="dontcare")     
                and (str(data.loc[y,"to"]) in dict_postcode[str(data.loc[z,"from"])]  or data.loc[y,"to"] =="dontcare")    
                and (str(data.loc[z,"to"]) in dict_postcode[str(data.loc[x,"from"])]  or data.loc[z,"to"] =="dontcare")   
                #only for persons without existing matching partner
                and (data.loc[x,"matchingpartner"] == "no partner yet")
                and (data.loc[y,"matchingpartner"] == "no partner yet")
                and (data.loc[z,"matchingpartner"] == "no partner yet")):
                    data.loc[x,"matchingpartner"] = data.loc[y,"name"] + data.loc[z,"name"]
                    data.loc[y,"matchingpartner"] = data.loc[z,"name"] + data.loc[x,"name"] 
                    data.loc[z,"matchingpartner"] = data.loc[x,"name"] +data.loc[y,"name"]

它可以工作并提供我想要的输出，但它非常慢。问题1:你知道有更优雅、更有效的方法来解决这个问题吗？现在的运行时间很长。我的数据集有大约 400,000 个观察值。

问题2:目前，由于算法速度较慢，我只允许3人的链式。你知道我如何在没有 for 循环的情况下概括这个过程吗，这样我就可以定义一个最大的链大小(例如 5 人，1 人想要从 a 到 b，2 人想要从 b 到 c，3 人想要从 c 到 d，4 人想要从 d到 e 和 5 从 e 到 a)？

Answer 1

这可以表示为 directed graph其中节点代表人，边代表一个人是否可以搬到另一个人的家。一般来说你可以使用 np.equal.outer用于计算候选主机，然后使用 networkx创建相应的图形。例如:

           home destination
Carole        A           C
Irvin         A           D
Kelvin        C           A
Stanley       A           D
Lazaro        E           C
Yong          C           A
Florentino    B           E
Jose          C           E
Bettye        B           E
Clinton       A           D
Georgia       A           D
Lon           A           E
Ezra          C           D
Tim           A           E
Mae           A           B

# Create the graph by feeding the edges.
graph = nx.DiGraph()
graph.add_edges_from(np.argwhere(np.equal.outer(df['destination'], df['home'])))

结果图的一些属性:

graph.number_of_nodes()  # 15
graph.number_of_edges()  # 31
list(graph.edges())  # [(0, 2), (0, 5), (0, 7), (0, 12), (2, 0), (2, 1), (2, 3), (2, 9), (2, 10), (2, 11), (2, 13), (2, 14), (5, 0), (5, 1), (5, 3), (5, 9), (5, 10), (5, 11), (5, 13), (5, 14), (7, 4), (11, 4), (13, 4), (14, 6), (14, 8), (4, 2), (4, 5), (4, 7), (4, 12), (6, 4), (8, 4)]

寻找可能的候选人

现在我们可以通过在该图中搜索周期来获得可能的候选集合(周期意味着每个搬到另一个家的人也会出租他们的房子)；我们可以使用nx.simple_cycles:

Find simple cycles (elementary circuits) of a directed graph.

A simple cycle, or elementary circuit, is a closed path where no node appears twice. Two elementary circuits are distinct if they are not cyclic permutations of each other.

list(nx.simple_cycles(graph))  # [[0, 7, 4, 5], [0, 7, 4, 2], [0, 5, 14, 8, 4, 2], [0, 5, 14, 6, 4, 2], [0, 5, 13, 4, 2], [0, 5, 11, 4, 2], [0, 5], [0, 2, 14, 8, 4, 5], [0, 2, 14, 6, 4, 5], [0, 2, 13, 4, 5], [0, 2, 11, 4, 5], [0, 2], [2, 14, 8, 4], [2, 14, 6, 4], [2, 13, 4], [2, 11, 4], [4, 7], [4, 5, 14, 8], [4, 5, 14, 6], [4, 5, 13], [4, 5, 11]]

寻找最佳映射

贪婪方法

为了找到最佳解决方案，我们可以将每个循环视为一组节点，并且我们需要找到具有最大量值的不相交集合的组合。这是一个计算要求较高的问题，因此贪婪的解决方案可能更可取(即，仅逐个添加循环并丢弃与累积集不相交的循环)。例如:

# Greedy approach.
cycles = []
nodes = set()
for cycle in nx.simple_cycles(graph):
    if nodes.isdisjoint(cycle):
        cycles.append(cycle)
        nodes.update(cycle)

这给出了cycles == [[0, 7, 4, 5]]，但这不是最佳解决方案。

最优解

如果计算上可行，可以通过使用另一个表示兼容(即不相交)集的图来暴力破解；我们添加空集，以便我们可以使用其他集的大小(相应循环的长度)作为边权重:

import itertools as it

all_cycles = list(nx.simple_cycles(graph))
disjoint = np.zeros((len(all_cycles),)*2 , dtype=bool)
disjoint[np.triu_indices(disjoint.shape[0], k=1)] = list(map(
    lambda x: set.isdisjoint(*x),
    it.combinations(map(set, all_cycles), 2)
))

# Add the empty set as a starting point, so we can use cycle length as edge weight.
disjoint = np.concatenate([np.ones((1, disjoint.shape[1]), dtype=bool), disjoint], axis=0)
disjoint = np.concatenate([np.zeros((disjoint.shape[0], 1), dtype=bool), disjoint], axis=1)
lengths = np.fromiter(map(len, [[]] + all_cycles), dtype=int)
indices = np.argwhere(disjoint)

c_graph = nx.DiGraph()
c_graph.add_edges_from(zip(indices[:, 0], indices[:, 1], ({'weight': l} for l in lengths)))
best_combination = nx.dag_longest_path(c_graph, 'weight')

结果是[0, 7, 13]。请注意，这包括作为第 0 个索引的空集，因此我们需要将每个索引偏移 -1。因此，最终的解决方案是总长度为 6 的循环 [[0, 5], [2, 14, 8, 4]] 的复合。实际上，这意味着

• Carole 应与 Yong 切换，
• 和Kelvin -> Mae -> Bettie -> Lazaro -> Kelvin。

可扩展性

现在这一切在计算上并不容易，对于您的 400,000 个样本的示例来说这是不可能的。 np.equal.outer 已经消耗了 O(N^2) 内存，因此最终约为 20 GiB。在这里，您还可以通过逐行迭代数据框来增量构建图表。然而，结果图可能非常复杂，以至于计算所有周期仍然不可行。

将其扩展到更大的数据集的另一个选择是放弃保证最优性，将数据集随机分成子集，每个子​​集都足够小以使算法能够工作。然后获得每个子集的结果并将其合并为全局结果。通过执行多次此类随机分割并比较各个结果，我们还可以改进解决方案。

除了分割数据集之外，我们还可以对子集进行采样，求解子集，然后将那些未匹配的人员放回池中。类似地，在拆分方法中，您可以在一轮拆分后将所有不匹配的人集中在一起，然后继续迭代。