最优 row/column 配对算法

Question

我在尝试将图像与其相关系数进行匹配时遇到了问题。

假设我们有 5 个缩略图 (a, b, c, d, e)，我们需要在另一组缩略图 (f, g, h, i, j) 上为每个缩略图找到最佳对应缩略图). （一件物品不能重复使用。）

对于每个可能的对，我们计算相关系数（相似性度量）。

     f     g     h     i     j
  |-----|-----|-----|-----|-----|
a | 0.5 | 0.7 |  0  |  0  |  0  |
  |-----|-----|-----|-----|-----|
b | 0.7 | 0.8 |  0  |  0  |  0  |
  |-----|-----|-----|-----|-----|
c |  0  |  0  |  0  |  0  | 0.8 |
  |-----|-----|-----|-----|-----|
d |  0  |  0  | 0.5 | 0.6 | 0.7 |
  |-----|-----|-----|-----|-----|
e |  0  | 0.6 | 0.7 | 0.5 |  0  |
  |-----|-----|-----|-----|-----|

我的工作：

找到每个原始数据的最大值

     f     g     h     i     j
  |-----|-----|-----|-----|-----|
a |  0  | 0.7 |  0  |  0  |  0  |
  |-----|-----|-----|-----|-----|
b |  0  | 0.8 |  0  |  0  |  0  |
  |-----|-----|-----|-----|-----|
c |  0  |  0  |  0  |  0  | 0.8 |
  |-----|-----|-----|-----|-----|
d |  0  |  0  |  0  |  0  | 0.7 |
  |-----|-----|-----|-----|-----|
e |  0  |  0  | 0.7 |  0  |  0  |
  |-----|-----|-----|-----|-----|

找出每列的最大值

      f     g     h     i     j
   |-----|-----|-----|-----|-----|
 a |  0  |  0  |  0  |  0  |  0  |
   |-----|-----|-----|-----|-----|
 b |  0  | 0.8 |  0  |  0  |  0  |
   |-----|-----|-----|-----|-----|
 c |  0  |  0  |  0  |  0  | 0.8 |
   |-----|-----|-----|-----|-----|
 d |  0  |  0  |  0  |  0  |  0  |
   |-----|-----|-----|-----|-----|
 e |  0  |  0  | 0.7 |  0  |  0  |
   |-----|-----|-----|-----|-----|

将这些对保存在 table

创建一个掩码，其中最后一个 table 中每个数字的原始和列都等于零

      f     g     h     i     j
   |-----|-----|-----|-----|-----|
 a |  1  |  0  |  0  |  1  |  0  |
   |-----|-----|-----|-----|-----|
 b |  0  |  0  |  0  |  0  |  0  |
   |-----|-----|-----|-----|-----|
 c |  0  |  0  |  0  |  0  |  0  |
   |-----|-----|-----|-----|-----|
 d |  1  |  0  |  0  |  1  |  0  |
   |-----|-----|-----|-----|-----|
 e |  0  |  0  |  0  |  0  |  0  |
   |-----|-----|-----|-----|-----|

将掩码与第一个 table

相乘

     f     g     h     i     j
  |-----|-----|-----|-----|-----|
a | 0.5 |  0  |  0  |  0  |  0  |
  |-----|-----|-----|-----|-----|
b |  0  |  0  |  0  |  0  |  0  |
  |-----|-----|-----|-----|-----|
c |  0  |  0  |  0  |  0  |  0  |
  |-----|-----|-----|-----|-----|
d |  0  |  0  |  0  | 0.6 |  0  |
  |-----|-----|-----|-----|-----|
e |  0  |  0  |  0  |  0  |  0  |
  |-----|-----|-----|-----|-----|

重复该过程，直到第二步得到的矩阵为零

所以最后，匹配的 table 看起来像这样：

        f     g     h     i     j
     |-----|-----|-----|-----|-----|
   a |  1  |  0  |  0  |  0  |  0  |
     |-----|-----|-----|-----|-----|
   b |  0  |  1  |  0  |  0  |  0  |
     |-----|-----|-----|-----|-----|
   c |  0  |  0  |  0  |  0  |  1  |
     |-----|-----|-----|-----|-----|
   d |  0  |  0  |  0  |  1  |  0  |
     |-----|-----|-----|-----|-----|
   e |  0  |  0  |  1  |  0  |  0  |
     |-----|-----|-----|-----|-----|

根据此方法，可能的最佳配对是： (a,f)、(b,g)、(c,j)、(d,i) 和 (e,h)

现在的问题是：有没有更好的方法？

像 (a,b) 和 (f,g) 一样，将它们的分数相加以找到最佳匹配不是更好吗？

例如：

  (a,f) (b,g)
   0.5 + 0.7 = 1.2

  (a,g) (b,f)
   0.7 + 0.7 = 1.4

   1.4 > 1.2 => best pairs are (a,g) and (b,f)
   (As opposed to (a,f), (b,g) with the first method.)

如果是这样，如何使其具有普遍性？

希望我已经足够清楚，让您理解问题所在。

在此先感谢您的帮助。

编辑：

我发现匈牙利算法比 AirSquid 提供的 ILP 解决方案快得多。

我将 Scipy (https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html) 的匈牙利语实现与基于 ILP 的解决方案进行了比较。

在对随机 20x20 矩阵进行 1000 次一对一匹配迭代后，我得到：

Method	ite/s
ILP solution	4.06e-2
Hungarian algorithm	1.808e-5

根据测试，我没有发现这两种方法有任何区别。

Answer 1

我认为你的方法在某些情况下是错误的。

举个例子：

      f     g     
     |-----|-----|
   a | 0.9 | 0.8 |
     |-----|-----|
   b | 0.8 |  0  |
     |-----|-----|

对于这种情况，最好的解决方案是ag和bf，总分是“0.8 + 0.8 = 1.6”。如果您首先选择最高分 (af)，您将被迫使用 bg 作为第二对（因为没有其他选择），这会给您总分“0.9 + 0 = 0.9"，更糟。

请注意，5 对也存在同样的问题（而且可能更糟）。例如。对于极端情况：

     f      g      h      i      j
  |------|------|------|------|------|
a | 0.99 | 0.98 | 0.97 | 0.96 | 0.95 |
  |------|------|------|------|------|
b | 0.98 | 0.97 | 0.96 | 0.95 |   0  |
  |------|------|------|------|------|
c | 0.97 | 0.96 | 0.95 |   0  |   0  |
  |------|------|------|------|------|
d | 0.96 | 0.95 |   0  |   0  |   0  |
  |------|------|------|------|------|
e | 0.95 |   0  |   0  |   0  |   0  |
  |------|------|------|------|------|

这里“最大优先”导致af、bg、ch、di、ej总分2.91；但最好的解决方案是ef、dg、ch、bi、aj，总分4.75。

寻找最佳配对；您想计算每种可能性的总数，然后找到最高的总数。最简单的方法是使用蛮力方法（从字面上看，计算每种可能性的总数）但开销相对较高。

假设采用“嵌套循环”方法（例如，您有一个外循环迭代 a 的可能性，一个内循环迭代 b 的可能性，...；以及每个内部循环都可以创建一个新的“部分总计”，以便最内层循环可以使用部分总计而不是自己计算全部总计）；我不认为有提高性能的实用方法（不会产生无法找到最佳解决方案的风险）。

Answer 2

对于大多数数学求解器来说，这是一个简单的配对模型，可以表述为 ILP。如果你想在 python 中走这条路，你有几个选择（在了解了一些 LP/ILP 公式之后 :)）。我偏爱 pyomo 但 pulp 和 or-tools 也是可行的。您还需要一个求解器引擎。那里有几个免费赠品，有些比其他的更容易安装。我相信 pulp 有一个内置的求解器，这很好。

可能还需要考虑一个动态规划解决方案，但这既快速又简单。对于我在下面的问题中提到的例子（上面反例的复制品和一个随机的 20x20 矩阵），最优解几乎是瞬时的。

# pairing

import pyomo.environ as pyo
import numpy as np

data = [[.99, .98, .97, .96, .95],
        [.98, .97, .96, .95, 0],
        [.97, .96, .95, 0,   0],
        [.96, .95, 0,   0,   0],
        [.95, 0,   0,   0,   0]]

#data = np.random.rand(20, 20)  #alternate random data for testing...

model = pyo.ConcreteModel('r-c pairings')

#re-label the data and push into a dictionary
labels = list('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ')
data = {(labels[r], labels[len(data) + c]) : data[r][c] 
            for r in range(len(data)) for c in range(len(data[0]))}

# pyomo components
model.R = pyo.Set(initialize = [k[0] for k in data.keys()])
model.C = pyo.Set(initialize = [k[1] for k in data.keys()])
model.corr = pyo.Param(model.R, model.C, initialize=data)
model.X = pyo.Var(model.R, model.C, within=pyo.Binary)  # select pairing (r, c)


# objective:  maximize overall value
model.obj = pyo.Objective(expr=pyo.summation(model.corr, model.X), sense=pyo.maximize)  #shortcut to ∑cX

# constraint:  only use each column value once
def single_use(m, c):
    return sum(model.X[r,c] for r in model.R) <= 1
model.C1 = pyo.Constraint(model.C, rule=single_use)

# constraint:  only use each row value once
def single_use_row(m, r):
    return sum(model.X[r,c] for c in model.C) <= 1
model.C2 = pyo.Constraint(model.R, rule=single_use_row)

# solve it...
solver = pyo.SolverFactory('glpk')  # <-- need to have this solver installed
result = solver.solve(model)
print(result)
pyo.display(model)

输出（来自较小的数据运行）：

Problem: 
- Name: unknown
  Lower bound: 4.75
  Upper bound: 4.75
  Number of objectives: 1
  Number of constraints: 11
  Number of variables: 26
  Number of nonzeros: 51
  Sense: maximize
Solver: 
- Status: ok
  Termination condition: optimal
  Statistics: 
    Branch and bound: 
      Number of bounded subproblems: 1
      Number of created subproblems: 1
  Error rc: 0
  Time: 0.010313272476196289
Solution: 
- number of solutions: 0
  number of solutions displayed: 0

Model r-c pairings

  Variables:
    X : Size=25, Index=X_index
        Key        : Lower : Value : Upper : Fixed : Stale : Domain
        ('a', 'f') :     0 :   0.0 :     1 : False : False : Binary
        ('a', 'g') :     0 :   0.0 :     1 : False : False : Binary
        ('a', 'h') :     0 :   0.0 :     1 : False : False : Binary
        ('a', 'i') :     0 :   0.0 :     1 : False : False : Binary
        ('a', 'j') :     0 :   1.0 :     1 : False : False : Binary
        ('b', 'f') :     0 :   0.0 :     1 : False : False : Binary
        ('b', 'g') :     0 :   0.0 :     1 : False : False : Binary
        ('b', 'h') :     0 :   0.0 :     1 : False : False : Binary
        ('b', 'i') :     0 :   1.0 :     1 : False : False : Binary
        ('b', 'j') :     0 :   0.0 :     1 : False : False : Binary
        ('c', 'f') :     0 :   0.0 :     1 : False : False : Binary
        ('c', 'g') :     0 :   0.0 :     1 : False : False : Binary
        ('c', 'h') :     0 :   1.0 :     1 : False : False : Binary
        ('c', 'i') :     0 :   0.0 :     1 : False : False : Binary
        ('c', 'j') :     0 :   0.0 :     1 : False : False : Binary
        ('d', 'f') :     0 :   0.0 :     1 : False : False : Binary
        ('d', 'g') :     0 :   1.0 :     1 : False : False : Binary
        ('d', 'h') :     0 :   0.0 :     1 : False : False : Binary
        ('d', 'i') :     0 :   0.0 :     1 : False : False : Binary
        ('d', 'j') :     0 :   0.0 :     1 : False : False : Binary
        ('e', 'f') :     0 :   1.0 :     1 : False : False : Binary
        ('e', 'g') :     0 :   0.0 :     1 : False : False : Binary
        ('e', 'h') :     0 :   0.0 :     1 : False : False : Binary
        ('e', 'i') :     0 :   0.0 :     1 : False : False : Binary
        ('e', 'j') :     0 :   0.0 :     1 : False : False : Binary

  Objectives:
    obj : Size=1, Index=None, Active=True
        Key  : Active : Value
        None :   True :  4.75

  Constraints:
    C1 : Size=5
        Key : Lower : Body : Upper
          f :  None :  1.0 :   1.0
          g :  None :  1.0 :   1.0
          h :  None :  1.0 :   1.0
          i :  None :  1.0 :   1.0
          j :  None :  1.0 :   1.0
    C2 : Size=5
        Key : Lower : Body : Upper
          a :  None :  1.0 :   1.0
          b :  None :  1.0 :   1.0
          c :  None :  1.0 :   1.0
          d :  None :  1.0 :   1.0
          e :  None :  1.0 :   1.0

最优 row/column 配对算法

Optimal row/column pairing algorithm

algorithm

optimization

matching

pairing

pyomo

输出（来自较小的数据运行）：