3
\$\begingroup\$

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

enter image description here

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

enter image description here

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

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ In your second code block you are assigning a value to each of the like animal pairings (Monkey->Monkey,Lion->Lion, etc.) Your final table shows no Association Strength for Monkey->Monkey, etc. Are the like parings significant, and not in the last table for space reasons? Or, is their inclusion in the second block an artifact of the looping structure, and wasted CPU cycles and storage space? \$\endgroup\$ – Gypsy Spellweaver Feb 27 at 8:16
  • \$\begingroup\$ @GypsySpellweaver Its an artifact of the looping structure. I just ignore them in the last block (if row_word!=col_word). But the first 2 blocks don't cause much problem - they finish executing in the order of minutes, while the last block (calculating the association strengths) takes hours to finish. So, the last block is what I really want optimized. \$\endgroup\$ – Kristada673 Feb 27 at 8:27
  • \$\begingroup\$ Cannot answer, don't know Python at all. Hints for you, and those who will actually be of help: If the data is not created in step 2 it cannot use use cycles in the 3rd step. If the data is symmetrical could you not collapse steps 2 and 3 into a single loop structure. Don't store the "times together' just use it in doing the math and store A->B strength in top-right and B->A strength in bottom-left. Secondly, try to avoid processing strings until needed. \$\endgroup\$ – Gypsy Spellweaver Feb 27 at 8:34
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Amazing! I did not know about ‘pandas.melt’. For my ~1000x1000 matrix, the code executes in <1 second. \$\endgroup\$ – Kristada673 Feb 27 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.