Python: как вычислить индекс jaccard между двумя сетями?

Question

У меня есть два кадра данных df1 а также df2 который содержит пограничный список двух сетей g1 а также g2 содержащие одинаковые узлы, но разные соединения. Для каждого узла я хочу сравнить индекс jaccard между двумя сетями.

Я определяю функцию, которая вычисляет индекс jaccard

def compute_jaccard_index(set_1, set_2):
    n = len(set_1.intersection(set_2))
    return n / float(len(set_1) + len(set_2) - n) 

df1  
     i   j
0    0   2
1    0   5
2    1   2
3    2   3
4    2   4
5    2   7


df2  
     i   j
0    0   2
1    0   5
2    0   1
3    1   3
4    2   4
5    2   7

что я делаю, это следующее:

tmp1 = pd.unique(df1['i'])
tmp2 = pd.unique(df2['i'])

JI = []
for i in tmp1:
    tmp11 = df1[df1['i']==i]
    tmp22 = df2[df2['i']==i]
    set_1 = list(tmp11['j'])
    set_2 = list(tmp22['j'])

    JI.append(compute_jaccard_index(set_1, set_2))

Мне интересно, если есть более эффективный способ

Answer 1

Я всегда считал, что быстрее использовать преимущества разреженных матриц Сципи и векторизовать операции, а не зависеть от функций множеств Python. Вот простая функция, которая объединяет списки ребер DataFrame в разреженные матрицы (как направленные, так и ненаправленные):

import scipy.sparse as spar

def sparse_adjmat(df, N=None, directed=False, coli='i', colj='j'):
    # figure out size of matrix if not given
    if N is None:
        N = df[[coli, colj]].max() + 1

    # make a directed sparse adj matrix
    adjmat = spar.csr_matrix((np.ones(df.shape[0],dtype=int), (df[coli].values, df[colj].values)), shape = (N,N))

    # for undirected graphs, force the adj matrix to be symmetric
    if not directed:
        adjmat[df[colj].values, df[coli].values] = 1

    return adjmat

тогда это просто простые векторные операции над бинарными матрицами смежности:

def sparse_jaccard(m1,m2):

    intersection = m1.multiply(m2).sum(axis=1)
    a = m1.sum(axis=1)
    b = m2.sum(axis=1)
    jaccard = intersection/(a+b-intersection)

    # force jaccard to be 0 even when a+b-intersection is 0
    jaccard.data = np.nan_to_num(jaccard.data)
    return np.array(jaccard).flatten() 

Для сравнения, я сделал функцию случайного списка панд и обернул ваш код в следующие функции:

def erdos_renyi_df(N=100,m=400):
    df = pd.DataFrame(np.random.randint(0,N, size=(m,2)), columns = ['i','j'])
    df.drop_duplicates(['i','j'], inplace=True)
    df.sort_values(['i','j'], inplace=True)
    df.reset_index(inplace=True, drop=True)
    return df

def compute_jaccard_index(set_1, set_2):
    n = len(set_1.intersection(set_2))
    return n / float(len(set_1) + len(set_2) - n) 

def set_based_jaccard(df1,df2):
    tmp1 = pd.unique(df1['i'])
    tmp2 = pd.unique(df2['i'])
    JI = []
    for i in tmp1:
        tmp11 = df1[df1['i']==i]
        tmp22 = df2[df2['i']==i]
        set_1 = set(tmp11['j'])
        set_2 = set(tmp22['j'])

        JI.append(compute_jaccard_index(set_1, set_2))

    return JI

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

N = 10**3
m = 4*N

df1 = erdos_renyi_df(N,m)
df2 = erdos_renyi_df(N,m)

И вычисление подобия Jaccard для каждого узла, используя ваш метод на основе набора:

%timeit set_based_jaccard(df1,df2)
1.54 s ± 113 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

И разреженный метод (включая накладные расходы на преобразование в разреженные матрицы):

%timeit sparse_jaccard(sparse_adjmat(df1, N=N, directed=True, coli='i', colj='j'),sparse_adjmat(df2, N=N, directed=True, coli='i', colj='j'))
1.71 ms ± 109 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Как видите, код разреженной матрицы примерно в 1000 раз быстрее.