выбор одного к одному результату по матрице сходства - PullRequest
Новая
       6

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

0 голосов
/ 08 января 2019

Я строю функцию, которая находит выравнивание по некоторой метрике.

Получает матрицу с уже вычисленными значениями подобия: 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 и очень быстро растет.

Ответы [ 2 ]

0 голосов
/ 09 января 2019

Я нашел его, он называется венгерским алгоритмом, но с максимизацией вместо минимизации счета. 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

Спасибо, что подумали об этом!

0 голосов
/ 08 января 2019

Если вы транспонируете матрицу, вы можете легко найти максимальное значение для каждого столбца без повторов следующим образом: 

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)

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

...