通过相似矩阵选择一对一的结果

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 产生最大分数。

在很多情况下，为每个 column/row 找到最大值是不够的。令矩阵为：

[[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

如果你转置矩阵，那么你可以很容易地找到每一列的最大值，而无需重复，如下所示：

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)

希望对您有所帮助。

Answer 2

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

感谢您考虑！

通过相似矩阵选择一对一的结果

choosing one to one result by a similarity matrix

python

algorithm

sequence-alignment