Evaluating association strengths of items

Question

I have a list of animals with their counts:

import numpy as np
import pandas as pd
from random import randint

table = np.zeros((5,1), dtype=int)
for i in range(5):
    table[i]=randint(10, 20)

df1 = pd.DataFrame(columns=['Animal', 'Count'])
df1['Animal'] = animal_list
df1['Count'] = table
df1

And I have a matrix of how many times they appear together:

table = np.zeros((5,5), dtype=int)
animal_list = ['Monkey', 'Tiger', 'Cat', 'Dog', 'Lion']

for i in range(5):
    for j in range(5):
        table[i][j]=randint(0, 9)

df2 = pd.DataFrame(table, columns=animal_list, index=animal_list)
df2

I want to find the animals' association strength, which is defined like so - if Lion and Cat appear together 5 times, and Lion's count is 10 and Cat's count is 15, then Lion -> Cat association strength is 5/10=0.5, and Cat -> Lion association strength is 5/15=0.33.

I do it like so:

assoc_df = pd.DataFrame(columns=['Animal 1', 'Animal 2', 'Association Strength'])
for row_word in df2:
    for col_word in df2:
        if row_word!=col_word:
            assoc_df = assoc_df.append({'Animal 1': row_word, 'Animal 2': col_word, 
                                        'Association Strength': df2[col_word][row_word]/df1[df1.Animal==row_word]['Count'].values[0]}, ignore_index=True)

assoc_df

The problem is, if I have a large number (say, 1000) of animals to loop on, it takes hours to finish computing the association strength table.

So, how to do I better optimize this last code block, the creation/generation process of this association table?

P.S.: In most practical use cases, df2 is a symmetric matrix, as "X appears together with Y" generally also means the same as "Y appears together with X". So, I am ok with solutions that assume that df2 is symmetric, and cut down the running time by half. In the above example, df2 is not a symmetric matrix, which is the more general case, and applicable for situations where we want to express meanings such as "X appears after Y" and "Y appears after X", which may not be the same.

Answer 1

Even in the non-symmetric case you can speed this up by not having the explicit double for loop. Since your case is not even normalized (apparently an animal can appear together with more than one other animal at a time), you do need your df1 as the normalization (instead of just e.g. df2.sum(axis=1). This gives you the matrix of the associations:

assoc_matrix = (df2.T / df1.set_index("Animal").Count).T
print(assoc_matric)
#           Monkey     Tiger       Cat       Dog      Lion
# Monkey  0.461538  0.692308  0.307692  0.692308  0.615385
# Tiger   0.200000  0.150000  0.200000  0.250000  0.250000
# Cat     0.062500  0.312500  0.250000  0.312500  0.000000
# Dog     0.000000  0.133333  0.333333  0.200000  0.466667
# Lion    0.500000  0.388889  0.333333  0.000000  0.333333

(I figured out the needed transposes by trial and error until I got the same values as in your post...)

And then you can use pandas.melt to get it into your format:

assoc_df2 = pd.melt(assoc_matrix.reset_index(), id_vars="index")
assoc_df2.columns = "Animal 1", "Animal 2", "Association Strength"
print(assoc_df2)

#    Animal 1 Animal 2  Association Strength
# 0    Monkey   Monkey              0.461538
# 1     Tiger   Monkey              0.200000
# 2       Cat   Monkey              0.062500
# 3       Dog   Monkey              0.000000
# 4      Lion   Monkey              0.500000
# 5    Monkey    Tiger              0.692308
# 6     Tiger    Tiger              0.150000
# 7       Cat    Tiger              0.312500
# 8       Dog    Tiger              0.133333
# 9      Lion    Tiger              0.388889
# 10   Monkey      Cat              0.307692
# 11    Tiger      Cat              0.200000
# 12      Cat      Cat              0.250000
# 13      Dog      Cat              0.333333
# 14     Lion      Cat              0.333333
# 15   Monkey      Dog              0.692308
# 16    Tiger      Dog              0.250000
# 17      Cat      Dog              0.312500
# 18      Dog      Dog              0.200000
# 19     Lion      Dog              0.000000
# 20   Monkey     Lion              0.615385
# 21    Tiger     Lion              0.250000
# 22      Cat     Lion              0.000000
# 23      Dog     Lion              0.466667
# 24     Lion     Lion              0.333333

Note that the order is different to your solution and this also contains the association of each animal with itself (and it is not one in this example, due to the normalization). You can just filter it out, though, if needed:

assoc_df2 = assoc_df2[assoc_df2["Animal 1"] != assoc_df2["Animal 2"]]

Finally, all of this only works as long as the dataframes still fit into memory, of course.