Correlating activity between entities using Python

Question

I have some data that contains IDs along with an associated column containing times. What I want to do is to be able to determine which IDs are most similar, based upon the times e.g. Which IDs have correlated times for performing an action

The data looks something like this;

ID      Time(secs)
AAAA    1
AAAA    6
AAAA    5
AAAA    2
AAAA    4
BBBB    2
BBBB    4
BBBB    6
BBBB    3
CCCC    3
CCCC    4
CCCC    1
CCCC    6
DDDD    7 
DDDD    4
DDDD    5
DDDD    3

Naively I initially thought this would be a simple case of plotting the values and then calculating the Correlation Coefficient but I soon realised this isn't possible;

ID             CorrCoef
AAAA>BBBB      ????
AAAA>CCCC
AAAA>DDDD
BBBB>CCCC
BBBB>DDDD
CCCC>DDDD

I am now thinking I need to be able to compare 2 populations using something like a t-statistic or perhaps by using something like an AutoRegression. It is fair to say I am now feeling a little bit out of my depth with something that seemed quite basic initially.

Does anyone have any pointers as to the best way of doing this?

Thanks in advance!

Edit

Based upon a suggestion below, it seems a KS test could be useful here. What I need to do therefore is subset the data so that it can be fed into the below line of code

scipy.stats.ks_2samp(data1, data2)

Answer 1

You may compute the $id$ co-occurrences frequencies in a given time-window. Suppose (without loss of generality) your criteria for co-occurrence is that both $id$s must occur on the second t, than using maximum likelihood estimate $P(id_{i}|id_{j})$ is:

$P(id_{i}|id_{j}) = \frac{count(id_{i}, id_{j})}{count(id_{j})}$

and the maximum likelihood estimate for the joint probability is:

$P(id_{i}, id_{j}) = \frac{count(id_{i}, id_{j})}{\sum{k \in IDs}{} \ count(id_{k})}$

Where $id_j, id_i \in IDs\ $ and $IDs$ is the set containing all $id$s (AAAA,BBB,CCCC,...),

You can then calculate the pointwise mutual information between each $id$ pair, that is, how ofter two $id$s co-occur, compared with what we would expect if they were independent:

$I(id_i, id_j) = \log_{2}{\frac{P(id_i, id_j)}{P(id_i)P(id_j)}}$

Given you a estimation of how strong is the association between $id_i$ and $id_j$.

The same strategy may be used to find similarities, you may think about each $id_i$ being a $|IDs|$-dimensional vector with the co-occurrences frequencies being the values. You can then apply cosine-similarity or pearson-correlation to find the most similar vectors ($id$s).

---

EDIT

Complementing my answer follows python demonstrating the ideas above for the sample dataset given in the question.

First we create our dataframe from the data in the question

import pandas as pd
import numpy as np
import collections

d = {'ID': ['AAAA', 'AAAA', 'AAAA', 'AAAA', 'AAAA', 'BBBB', 'BBBB', 'BBBB', 'BBBB', 'CCCC', 'CCCC', 'CCCC', 'CCCC','DDDD', 'DDDD', 'DDDD', 'DDDD'],
     'Time': [1, 6, 5, 2, 4, 2, 4, 6, 3, 3, 4, 1, 6, 7, 4, 5, 3]}

df = pd.DataFrame(d)

Computes the co-occurrences

dfm = df.merge(df, on='Time')
dfm = dfm[dfm.ID_x != dfm.ID_y]  # ID_x and ID_y are created by the merge
df_M = pd.get_dummies(dfm.ID_x).groupby(dfm.ID_y).apply(sum)
print(df_M)

The dataframe df_M represents the co-occurrence matrix

      AAAA  BBBB  CCCC  DDDD
ID_y                        
AAAA     0     3     3     2
BBBB     3     0     3     2
CCCC     3     3     0     2
DDDD     2     2     2     0

• Pairwise Mutual Information

Let N be the total amount of co-occurrences, than I can compute every joint probability simply dividing the co-occurrences in the df_M matrix by N.

N = df_M.sum().sum()
df_joint_P = df_M/N  # Computes every joint probability P(id_i, id_j)

The probability of each $id$ is the sum of all its joint probabilities

df_ID_P = df_joint_P.sum(axis=0) # Marginalizes to produces P(id_i)

Now that we have all we need to compute a PMI dataframe

idx = [(r, c) for r in list(df_M) for c in list(df_M)]
pmi_dict = collections.defaultdict(dict)
for r,c in idx:
    pmi_dict[r][c] = np.log2(2*df_joint_P[r][c]/(df_ID_P[r] * df_ID_P[c])) if df_joint_P[r][c] > 0 else 0
pmi_df = pd.DataFrame(pmi_dict)
print(pmi_df)

The pairwise mutual information between every pair of different $id$s is different than zero and like bellow

          AAAA      BBBB      CCCC      DDDD
AAAA  0.000000  1.491853  1.491853  1.321928
BBBB  1.491853  0.000000  1.491853  1.321928
CCCC  1.491853  1.491853  0.000000  1.321928
DDDD  1.321928  1.321928  1.321928  0.000000

We can see that every $id$ seems to be almost equally associated with each other.

• Cosine Similarity

Now we can compute the cosine similarity, remembering that it is the $l_2$-normalized dot-product

df_NM = df_M.div(df_M.pow(2).sum(axis=1).pow(0.5), axis=0) 
df_cos = df_NM.dot(df_NM.T)
print(df_cos)

The cosines are

          AAAA      BBBB      CCCC      DDDD
AAAA  1.000000  0.590909  0.590909  0.738549
BBBB  0.590909  1.000000  0.590909  0.738549
CCCC  0.590909  0.590909  1.000000  0.738549
DDDD  0.738549  0.738549  0.738549  1.000000

Obviously every $id$ is (trivially) most similar to itself but from the data above we see that every $id$ is similar to all the others (confirming the result we found using PMI) but we may notice that $id$ DDDD is more similar to all the other $id$s (at least for this tiny example).

Answer 2

This depends a bit if you have a lot of data per ID. If you have you can apply the Kolmogorov–Smirnov test between these distributions to check how similar they are.