用相似矩阵选择一对一结果

Question

我建立了一个函数，通过一些度量找到一些对齐。你知道吗

它将获得一个矩阵，其中包含已计算的相似度值： weighted_res可以是：

[[0.2, 0.5, 0.3],
 [0.1, 0.2, 0.4],
 [0.8, 0.2, 0.4],
 [0.1, 0.2, 0.7],
 [0.1, 0.2, 0.4],

我的函数将exs1和exs2的索引的所有组合的值之和最大化，但索引不能取两次。结果是这些最优指标。（0,1），（2,0），（3,2）的和相应地0.5+0.8+0.7产生最大得分。你知道吗

在许多情况下，仅为每一列/每一行查找最大值是不够的。让矩阵为：

[[0.1, 0.0, 0.1]
 [0.5, 0.6, 0.4],
 [0.5, 0.8, 0.3],
 [0.0, 0.0, 0.2]]

这里，它选择（1,1），（2,1），（3,2），因为0.5+0.8+0.2是最大可达分数。你知道吗

我的代码如下，我担心，这是最大限度地无效。我会很高兴得到一些提示，找到一个更有效的算法，而不是计算所有的可能性，总结和最大化。代码如下：

def one_to_one(weighted_res, exs1, exs2, mask):

    inner_cube_len = min(len(list(exs1)), len(list(exs2)))
    turned = False

    if (len(exs1) < len(exs2)):
        exs1, exs2 = exs2, exs1
        weighted_res = weighted_res.T
        mask = mask.T
        turned = True

    x_to_choose = np.array(list(itertools.permutations(range(len(exs1)), inner_cube_len)))
    y_to_choose  = np.array(list(range (len(exs2))))

    weighted_res_overall = \
        weighted_res[x_to_choose,y_to_choose].sum(axis=1)

    best_overall_row  = np.argmax(weighted_res_overall)
    best_x_values     = np.array (x_to_choose[best_overall_row] )

    valid_mask        = mask[best_x_values,y_to_choose]
    best_res1         = best_x_values[valid_mask]
    best_res2         = y_to_choose[valid_mask]

    if not valid_mask.any():
        return [],[]
    if turned:
        left_value   = best_res2.tolist()
        right_values = [[x] for x in best_res1.tolist()]
        exs1, exs2 = exs2, exs1
        weighted_res = weighted_res.T
        mask = mask.T
    else:
        right_values =  [[x] for x in best_res2.tolist()]
        left_value   =  best_res1.tolist()
    return left_value, right_values

对于长度为8和6的输入值，weighted_res_overall的大小为20160，并且增长非常快。你知道吗

Answer 1

我找到了，它叫匈牙利算法，但是用最大化而不是最小化分数。https://en.wikipedia.org/wiki/Hungarian_algorithm

它有一个scipy实现：https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

或https://github.com/src-d/lapjv

谢谢你的考虑！你知道吗

Answer 2

如果转置矩阵，则可以轻松找到每列的最大值，而无需重复如下操作：

from numpy import array

mat = [[0.2, 0.5, 0.3],
       [0.1, 0.2, 0.4],
       [0.8, 0.2, 0.4],
       [0.1, 0.2, 0.7],
       [0.1, 0.2, 0.4]]

mat = array(mat).T

maxis = [max(col) for col in mat]

如果要求和而不是最大值列表，可以将最终的生成器表达式更改为：

max_sum = sum(max(col) for col in mat)

希望这有帮助。你知道吗