2
$\begingroup$

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)
$\endgroup$

2 Answers 2

2
$\begingroup$

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).

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for this amazing answer @xboard. One thing I am wanting to get my head around is the following however; When conducting a MLE, we have to make an assumption that the data is normally distributed. Could you provide a little more detail on how this assumption plays out in this case? Are we assuming that for each ID, the data is normally distributed around it's own individual mean? $\endgroup$
    – Taylrl
    Oct 2, 2017 at 10:24
  • $\begingroup$ Thank you @Taylrl ! Cosine similarity, mutual information (MI) and pointwise mutual information don´t assume any generating distribution. $\endgroup$
    – xboard
    Oct 2, 2017 at 16:17
  • 1
    $\begingroup$ You are quite right that MI, pointwise mutual information and the Cosine similarity do not assume any generating distribution but am I not right in thinking that the Maximum Likelihood Estimate (MLE) and the Joint Probability do? $\endgroup$
    – Taylrl
    Oct 20, 2017 at 8:26
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks that's great. I think a KS test could be useful here. I have taken a look into this and edited my question above accordingly. $\endgroup$
    – Taylrl
    Sep 28, 2017 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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