使用 Jaccard Index 找到所需技能和教师之间的最佳匹配

Question

我有一组学生和一组教师，其中列出了他们想要学习的技能，并有一组教师列出了他们准备教授的技能。

根据这些信息，我得到了下面给出的表格。一份给学生，一份给老师。 “1”代表学生愿意学习并且老师愿意教授的技能。 '0'表示相反。

|  Students  |  Skill 1  |  Skill 2  |  Skill 3 |  Skill 4 |  Skill 5  |
|------------|-----------|---- ------|----------|----------|-----------|
|      A     |      1    |      0    |     0    |     1    |     0     |
|      B     |      1    |      1    |     0    |     0    |     1     |
|      C     |      0    |      0    |     1    |     1    |     0     |
|      D     |      1    |      1    |     0    |     1    |     1     |
|      E     |      0    |      1    |     1    |     0    |     1     |


|  Teachers  |  Skill 1  |  Skill 2  |  Skill 3 |  Skill 4 |  Skill 5  |
|------------|-----------|---- ------|----------|----------|-----------|
|      F     |      1    |      1    |     1    |     1    |     1     |
|      G     |      0    |      1    |     0    |     0    |     0     |
|      H     |      0    |      0    |     1    |     1    |     1     |
|      I     |      1    |      1    |     0    |     0    |     0     |
|      J     |      0    |      0    |     1    |     0    |     1     |

我正在尝试将教师与合适的学生相匹配，我看到的一个建议是使用 Jaccard 索引。但是，我不确定 Jaccard 索引是否在二进制数据上正常工作。

我试着按照下面的方法在一个小数据集上使用它，但我没有得到正确的结果。

import numpy as np

a = [0, 1, 1, 0, 1, 0, 0]
b = [0, 1, 1, 0, 1, 0, 0]

#define Jaccard Similarity function

def jaccard(list1, list2):
    intersection = len(list(set(list1).intersection(list2)))
    union = (len(list1) + len(list2)) - intersection
    return float(intersection) / union

#find Jaccard Similarity between the two sets 

jaccard(a, b)

0.16666 是输出，即使二进制列表完全相同。

关于如何在这种情况下正确使用 Jaccard 指数或任何其他方式来匹配教师和学生有什么建议吗？谢谢！

Answer 1

如果我理解正确，您想使用 Jaccard index 计算最大技能重叠并为每个学生分配“最佳”老师。

第一步是计算 Jaccard 指数矩阵：

S = (df1.melt(id_vars='Students')
        .query('value==1')
        .groupby('Students')['variable']
        .agg(frozenset)
     )
T = (df2.melt(id_vars='Teachers')
        .query('value==1')
        .groupby('Teachers')['variable']
        .agg(frozenset)
     )

def jaccard(s1, s2):
    return len(s1&s2)/len(s1|s2)

from itertools import product

df = (pd
   .Series({(s,t): jaccard(S[s], T[t]) for s,t in product(S.index, T.index)})
   .unstack()
   .rename_axis(index='student', columns='teacher')
)

# df
teacher    A         B         C         D         E
student                                             
A        0.4  0.000000  0.250000  0.333333  0.000000
B        0.6  0.333333  0.200000  0.666667  0.250000
C        0.4  0.000000  0.666667  0.000000  0.333333
D        0.8  0.250000  0.400000  0.500000  0.200000
E        0.6  0.333333  0.500000  0.250000  0.666667

那么，我们就可以解决assignment problem using scipy.optimize.linear_sum_assignment:

from scipy.optimize import linear_sum_assignment

x, y = linear_sum_assignment(df, maximize=True)

out = pd.DataFrame({'student': df.columns[y], 'teacher': df.index[x]})

# out
  student teacher
0       B       A
1       D       B
2       C       C
3       A       D
4       E       E

或者，如果您只想为每个学生配备最好的老师，即使这意味着可能有老师没有学生而其他老师有很多学生，请使用 idxmax:

df.idxmax(axis=1)

student
A    A
B    D
C    C
D    A
E    E
dtype: object

使用 Jaccard Index 找到所需技能和教师之间的最佳匹配

Using Jaccard Index to find the best match between skill required and teachers

python

binary

similarity

python-3.x

pandas