给定相似度分数，用于最佳匹配物品对的算法

Question

我正在尝试通过产品名称匹配两个列表。

这些产品来自不同的网站，它们的名称可能有许多微妙的变化，例如“iPhone 128 GB”与“Apple iPhone 128GB”。

这些产品列表相交，但不相等，并且一个列表也不是另一个列表的超集；即一些来自列表A的产品不在列表B中，反之亦然。

给定一个比较两个字符串（产品名称）并返回介于0和1之间的相似度得分的算法（我已经拥有了一个满意的实现），我正在寻找一种将列表A与列表B进行最优匹配的算法。

换句话说，我认为我正在寻找一种最大化匹配中所有相似分数总和的算法。

注意，一个列表中的产品最多只能与另一个列表中的一个产品匹配。

我的初始想法是，对于A中的每个产品，获取其与B中每个产品的相似度，并保留得分最高的产品，前提是它超过某个阈值，例如0.75。匹配这些产品。如果得分最高的产品已经在循环中的先前迭代中与A中的另一个产品匹配，请选择第二高的产品，前提是它超过上述阈值。等等。

我的担忧是，如果在后面的循环中有更好的匹配，但是来自B的产品在前面的迭代中已经分配给A中的另一个产品，则匹配不是最佳的。

为确保将产品与其最高相似度对应的产品配对，我想到了以下实现：

预先计算所有A-B对的相似度得分

丢弃低于上述阈值的相似性

按相似度排序，从高到低

对于每个对，如果A和B中的产品均未被匹配，请匹配这些产品。这个算法应该优化地匹配产品对，确保每对产品都获得最高的相似度。

我的担忧是，它非常耗费计算和内存资源：假设我有5000个产品在两个列表中，那就是要预先计算并且潜在地存储（或在数据库中）25,000,000个相似度得分；尽管由于所需的最小阈值而实际上会更少，但仍可能非常大，并且仍然需要大量的CPU资源。

我是否漏掉了什么？

有没有更高效的算法可以得到与这个改进版本相同的输出？

- BenMorel

---

假设由于某种算法原因，您不会计算一对特定的分数，那么您可能会错过最优解（我们都知道它的分数可能非常高）：因此您必须计算所有分数。 - trincot

你听说过匹配算法吗？关于大小，一个5000 x 5000的距离矩阵并不是很大，如果它不增长太多，它可以很容易地处理。 - m.raynal

@trincot 的确有道理！ - BenMorel

@m.raynal 没有听说过这些，我对图论是个新手，感谢你的指引。5000x5000 可能还能管理，但随着数字的增长，问题会成倍地变得更加困难。10000x10000 呢？20000x20000 呢？我开始理解我不会有其他选择了，因此解决方案的一部分可能在于以合理的限制设计应用程序，例如产品数量和重新匹配的频率（产品数据库发生变化时可能需要重新匹配）。 - BenMorel

我目前正在处理200,000 x 200,000的数据，它变得非常庞大，实际上是一个问题（构建距离矩阵需要250GB的空间...）。解决方法是利用这些权重中绝大部分应该非常低的事实。因此，您可以定义一个阈值，在此阈值以下将权重设置为零，并使用稀疏矩阵表示您的图形。这是一种非常常见的数据结构，用于处理大型图形实例。 - m.raynal

此外，如果您不需要最优解，而只需要一个非常好的解决方案，那么可以使用随机算法（或最终MILP求解器）计算出合理的匹配。因为像花之类的算法非常美丽，但当实例变得太大时可能会变得棘手。 - m.raynal

Answer 1

你的模型可以用图形术语重新表述：考虑一个完全加权的二分图，其中第一部分的顶点是列表A中的名称，第二部分的顶点是列表B中的名称，边缘带有预先计算好的相似度分数。

现在你的问题看起来非常接近密集型 分配问题，其最优解可以使用 匈牙利算法（O（n³）复杂度）找到。

如果最优解不是你的最终目标，并且一些良好的近似解也可以满足你的要求，请尝试使用启发式算法解决分配问题，这里有另一个主题，简要概述了它们。

- gimme_danger

---

感谢您提供图论的指针！同时获得相同答案使我有信心我得到了正确的答案；关于匈牙利算法，查阅后我发现它在最佳情况下的复杂度为O(n³)。如果我没记错的话，我的第二个算法应该具有更低的复杂度？我之所以问这个问题是因为正如我在Cihan Ceyhan的回答中所说，我甚至不知道哪个算法在这种特定情况下会转化为最准确的匹配。 - BenMorel

O(n³) 复杂度是最优解的代价，如果某个良好的近似解能够满足您的要求，请尝试使用启发式算法来解决分配问题。这里有另一个主题，其中简要概述了它们。此外，您可以将第二个启发式算法与它们进行比较，以确定哪个对您来说更好。 - gimme_danger

是的，匈牙利算法有点费用高，但是能够得到最优解。 - DollarAkshay

Answer 2

你的第二个算法应该能够提供一个不错的输出，但它并不是最优的。请检查以下情况：

Set0 Set1 
A    C
B    D

Similarities:
A-C = 900
A-D = 850
B-C = 850
B-D = 0

Your algorithm's output: [(A,C), (B,D)]. Value 900.
Optimal output: [(A,D), (B,C)]. Value 1700.  

你正在处理的问题正是分配问题，它是“在带权二分图中找到一组匹配，使得边权之和最大”的问题。你可以找到许多优化和高效解决这个问题的方法。

- Cihan

---

谢谢指出我的算法不是最优的！但在这种情况下，什么会产生最佳结果：最大总和，还是像我实现的那样优先考虑高值？我想只有与已知正确匹配的基准测试才能说明。 - BenMorel