Выбор одного к одному результату по матрице сходства

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

Существует скучная реализация этого: 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)

Надеюсь это поможет.