1

我构建了一个函数，它通过一些度量找到一些对齐。

它得到一个具有已经计算的相似度值的矩阵： 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，并且增长极快。

4

2 回答 2

0

如果您转置矩阵，那么您可以轻松找到每列的最大值而无需重复，如下所示：

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)

希望这可以帮助。

于 2019-01-08T14:01:58.383 回答
0

我找到了它，它被命名为匈牙利算法，但是最大化而不是最小化分数。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

感谢您考虑！

于 2019-01-09T01:28:40.627 回答