# Similarity of two lists of pairs

I want to compare two lists with different lengths. There should be a percentage for their similarity as result. An example:

List 1:
main ID: 233423

ID: no.
1324: 312
22433: 259
244: 5236

List 2:
main ID: 2831

ID: no.
1324: 8687
231: 9283
244: 4872


In context, this means: the main ID 233423 occurs together 312 times with ID 1324, 259 times with ID 22433 and so on. The same for the second list.

Now I want to compare the lists of two different main IDs for their similarity.

IDs which are in both lists obviously should have a positive impact on the similarity. But because the absolute numbers can be totally different, I already compare the share of the total volume, so if ID 1324 is in both lists, I compare this share like

share1324List1 = 312/sumOfNoList1
share1324List2 = 8687/sumOfNoList2
|share1324List1-share1324List2| = simil1324


Then, I sum these values up and calculate the average, let's call it

avgAll = (siml1324+suml244)/2


But only comparing IDs which are in both lists and ignoring all other entries which are not in both lists is far too inaccurate, so the IDs which are only in one list need to be included somehow (with a negative impact on the similarity). I'm not sure how to do this in a nice way.

At the moment I sum up the no. values of entries which are in both lists and look how their share of the total amount is and simply multiply:

avgAll*sumInBothLists/(sumOfNoList1+sumOfNoList2)


(if share of "volume" that is in both lists is bigger, the average similarity is reduced less...)

Is there a better way to compare those two lists? Or, better, is there any "best practice"? I've already seen the Kolmogorov-Smirnov test, but it seems to be not appropriate, because the ID itself means nothing, so it's not some x for the probability distribution - you can't sort by that ID and say the functions now should look the same. Any ideas?

When an ID is not common to both lists, this is because it does not occur together with the respective main ID and can thus be assigned a value of 0 (no occurrences).

About the similarity metric, there are many possibilities as pointed out here

... there are many other measures of similarity, each with its own eccentricities. When deciding which one to use, try to think of a few representative cases and work out which index would give the most usable results to achieve your objective.

## Jaccard Similarity

One possible way of determining the similarity between finite sample sets, is by using Jaccard similarity. Defined as the size of the intersection divided by the size of the union of the sample sets:

$$J(A,B) = {{|A \cap B|}\over{|A \cup B|}} = {{|A \cap B|}\over{|A| + |B| - |A \cap B|}}.$$

For this specific case one could use something like the Generalized Jaccard Similarity.

$$J(\mathbf{x}, \mathbf{y}) = \frac{\sum_i \min(x_i, y_i)}{\sum_i \max(x_i, y_i)},$$

Where we compare two vectors $\mathbf{x} = (x_1, x_2, \ldots, x_n)$ and $\mathbf{y} = (y_1, y_2, \ldots, y_n)$ with $x_i, y_i \geq 0$.

How this would work in practice is illustrated by the following examples:

### Example 1

main ID: 233423

ID no.
1324: 312
22433: 259
244: 5236


and

main ID: 2831

ID no.
1324: 8687
231: 9283
244: 4872


This would then give:

#ID  1324  22433   244   231
x = ( 312,   259, 5236,    0)
y = (8687,     0, 4872, 9283)


$$J = \frac{312 + 0 + 4872 + 0}{8687+259+5236+9283} = 0.22$$

### Example 2

When removing the ID's 22433 and 231 that are not common among both lists:

#ID  1324   244
x = ( 312, 5236)
y = (8687, 4872)


The similarity goes up

$$J = \frac{312 + 90}{8687+5236} = 0.37$$

### Example 3

And when adding more ID's not common in both lists:

#ID  1324  22433   244   231   62   783
x = ( 312,   259, 5236,    0, 732,    0)
y = (8687,     0, 4872, 9283,   0, 8732)


As would be expected intuitively results in a lower similarity

$$J = \frac{312 + 0 + 4872 + 0 + 0 + 0}{8687+259+5236+9283+732+8732} = 0.15$$