Найдите максимальное значение в Матрице, чтобы максимизировать балл

Question

Вопрос:

Я хотел бы найти наибольшее значение в Матрице для каждого учителя и группы, чтобы максимально увеличить соотношение какой группы go с каким учителем.

            Teacher A   Teacher B   Teacher C   Teacher D
Group 1     50          40          20           50
Group 2     30          10          40          100
Group 3     80          60          40           20

В приведенной выше таблице. Я знаю, как найти самое высокое значение в строках и столбцах, но я хочу найти самое высокое в комбинации Учителя и Группы, при котором Учитель не может принадлежать двум группам, а Группы - двум учителям. Да, учителей может быть больше, чем групп.

Итак, я ищу окончательный результат следующим образом:

Решение

Group 1 with Teacher B: 40
Group 2 with Teacher D: 100
Group 3 with Teacher A: 80

Моя работа до сих пор Я пытался решить эту проблему несколькими способами, используя pandas, но все выбирает только самое высокое значение строк и столбцов ИЛИ в лучшем случае имя ключа это самое высокое. Я следовал уроку здесь , но не добился большого успеха. Любое руководство будет отличным.

Answer 1

Это похоже на вопрос оптимизации.

У вас есть два способа приблизиться к нему (с теоретической точки зрения).

1. heuristi c:

   За исключением случая патологического использования, мы можем думать, что наибольшее значение в матрице закончится в конечном результате. Здесь у нас есть 100 для Группы 2 и Учителя D. Затем мы удаляем строку для Группы 2 и столбец для Учителя D и выполняем итерацию.

   Это дает шаг за шагом:

   Group 2    Teacher D   100
   Group 3    Teacher A    80
   Group 1    Teacher B    50
   

2. исчерпывающий

   Предыдущий метод приведет к правильному результату, если значения имеют большие различия, но могут найти решение, близкое к максимальному, только если значения находятся слишком близко друг к другу. Исчерпывающий метод состоит в том, чтобы вычислять сумму значений для каждой возможной комбинации и сохранять наибольшее значение. Это, конечно, даст тот же результат, но мне потребуется слишком много операций, чтобы показать его здесь вручную ...

Python перевод

Первый метод итеративный, но простой:

# heuristic

dfA = df
result = {}

while (len(dfA) > 0):
    mx = dfA.max()     # find max per teacher
    mmx = pd.Series(mx[mx == mx.max()])  # find absolute max of matrix
    teacher = mmx.index[0]                       # get teacher
    val = mmx.values[0]                          # get value
    group = dfA[dfA[teacher] == val].index[0]    # get group
    result[group] = (teacher, val)               # store the triplet
    dfA = dfA.drop(index = group).drop(columns = teacher) # remove the row and column

dfout = pd.DataFrame(result).T
print(dfout.to_string())

Дает, как и ожидалось:

                 0    1
Group 2  Teacher D  100
Group 3  Teacher A   80
Group 1  Teacher B   40

Второй метод более детерминирован c, но может не масштабироваться для больших наборов данных:

import itertools

# compute with itertools all the possible permutations of group-teachers
mindex = pd.MultiIndex.from_tuples(itertools.permutations(df.columns, len(df)))

# compute the total value for each permutation
total = pd.DataFrame(data = 0, columns=mindex, index=df.index
                     ).transform(lambda x: pd.Series(
                         [df.loc[x.index[i], x.name[i]]
                          for i in range(len(x))], index=x.index)).sum()

# prepare the resulting dataframe
dfout = pd.DataFrame({'Groups': df.index,
                      'Teachers': total[total == total.max()].index[0]})

# extract the value per group
dfout['val'] = dfout.apply(lambda x: df.loc[x['Groups'], x['Teachers']], axis=1)

print(dfout.to_string())

Это дает то же значение, что и ожидалось

    Groups   Teachers  val
0  Group 1  Teacher B   40
1  Group 2  Teacher D  100
2  Group 3  Teacher A   80

Answer 2

Сначала найдите все возможные перестановки, затем возьмите максимум для суммы значений и, наконец, напечатайте его. Вот моя реализация с фреймами данных:

import itertools
m = [
    [50, 40, 20, 50],
    [30, 10, 40, 100],
    [80, 60, 40, 20]
]
rows = ['Group 1', 'Group 2', 'Group 3']
cols = ['Teacher A', 'Teacher B', 'Teacher C', 'Teacher D']
df = pd.DataFrame(m, index=rows, columns=cols)

permuts = itertools.permutations(cols, len(rows))

L = []
for p in permuts:
    s = 0
    d = {}
    for i, r in enumerate(rows):
        s += df[p[i]][r]
        d[r] = p[i]
    obj = [s, d]
    L.append(obj)

result = max(L, key=lambda x: x[0])
# [220, {'Group 1': 'Teacher B', 'Group 2': 'Teacher D', 'Group 3': 'Teacher A'}]
# Here 220 is the maximum sum you can have

result_dict = result[1]
# {'Group 1': 'Teacher B', 'Group 2': 'Teacher D', 'Group 3': 'Teacher A'}

for i, v in result_dict.items():
    print("{} with {} : {}".format(i, v, df[v][i]))

# Group 1 with Teacher B : 40
# Group 2 with Teacher D : 100
# Group 3 with Teacher A : 80

Пояснения

Вот небольшой пример работы itertools.permutations. Число 2 - это длина каждой перестановки, а ['a','b','c'] - элементы перестановки:

import itertools
permuts = itertools.permutations(['a','b','c'],2)
for i in a:
    print(i)

Вывод: (6 перестановок здесь)

('a', 'b')
('a', 'c')
('b', 'a')
('b', 'c')
('c', 'a')
('c', 'b')

В нашем В этом случае у нас есть 3 группы, поэтому нам нужно 3 учителя из 4 доступных (учителя A, B, C и D). Например, перестановка ('Teacher A', 'Teacher B', 'Teacher C') означает Group1=Teacher A, Group2=Teacher B, Group3=Teacher C).

Итак, мы перечислим все упорядоченные перестановки 3 учителей с помощью permuts = itertools.permutations(cols, len(rows)):

('Teacher A', 'Teacher B', 'Teacher C')
('Teacher A', 'Teacher B', 'Teacher D')
('Teacher A', 'Teacher C', 'Teacher B')
...
('Teacher D', 'Teacher C', 'Teacher A')
('Teacher D', 'Teacher C', 'Teacher B')

Так что получим 24 кортежа в нашей переменной permuts

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

L = []
for p in permuts:
    s = 0
    d = {}
    for i, r in enumerate(rows):
        s += df[p[i]][r]
        d[r] = p[i]
    obj = [s, d]
    L.append(obj)

Выходные данные L:

[
    [100, {'Group 1': 'Teacher A', 'Group 2': 'Teacher B', 'Group 3': 'Teacher C'}]
    [80, {'Group 1': 'Teacher A', 'Group 2': 'Teacher B', 'Group 3': 'Teacher D'}]
...
    [220, {'Group 1': 'Teacher B', 'Group 2': 'Teacher D', 'Group 3': 'Teacher A'}]
]
...

первое число (например, 100, 80 и 220) представляет сумму значений для этой перестановки c.

Затем мы выбираем перестановку с максимальной суммой, здесь 220

result = max(L, key=lambda x: x[0])
# [220, {'Group 1': 'Teacher B', 'Group 2': 'Teacher D', 'Group 3': 'Teacher A'}]

И, наконец, мы печатаем перестановку со значениями из кадра данных с print("{} with {} : {}".format(i, v, df[v][i])). Например df["Teacher B"]["Group 1"] = 40:

Group 1 with Teacher B : 40
Group 2 with Teacher D : 100
Group 3 with Teacher A : 80

Answer 3

Рассчитать оптимальную комбинацию строк и столбцов для оптимизации для преобразования. Я использовал пакет linear_sum_assignment , который использует венгерский алгоритм. Больше можно узнать здесь

from scipy.optimize import linear_sum_assignment
import pandas as pd

df = pd.read_csv("myfile.csv", index_col=0)
gain = df.to_numpy()
row_ind, col_ind = linear_sum_assignment(gain, maximize=True)
print(row_ind)
print(col_ind)
print(gain[row_ind, col_ind].sum())