2
$\begingroup$

I'm working on a project where I want to find similarities between groups of events. So far I have expressed groups of events as vectors of event counts and computing similarities between them. I'm looking for a similarity metric that, at the same time, captures the proportion between events and the number of events itself. For example, say I have the following vectors:

$a = [0, 1, 2, 3, 0]$

$b = [0, 3, 6, 9, 0]$

$c = [1, 1, 1, 1, 1]$

$d = [0, 100, 200, 300, 0]$

$e = [0, 110, 210, 310, 0]$

I would like to have something like

$sim(d,e) > sim(a,b) > sim(a,c) > sim(a,d) > sim(a,e)$

From one side I have metrics like cosine similarity, which is good to find that $sim(a,b)$ is big, but will also make $sim(a,d)$ big. From another side I have metrics such as manhattan distance, which will give a big distance to $(d,e)$, which shouldn't be the case. I could normalize the vectors, but then I would be saying that $sim(a,b) \sim sim(a,c)$, which is also wrong for what I want.

$\endgroup$
  • 1
    $\begingroup$ Do I get it correct that you treat events equally and they shouldn't have different weights? $\endgroup$ – mapto Feb 4 at 9:40
  • $\begingroup$ Yes, that's correct $\endgroup$ – jcp Feb 4 at 9:43
  • 1
    $\begingroup$ Are you in a position to define the domain (min and max values for each dimension) of your space? The reason I'm asking is that I'm about to propose you an approach that combines the two metrics with desired properties. However, one has range in [0,1], the other in [0, infinity). Thus obviously the second would outweight the first one if we don't balance them. $\endgroup$ – mapto Feb 4 at 10:06
  • $\begingroup$ The domain would be [0, inf), as I am dealing with counts of events $\endgroup$ – jcp Feb 4 at 10:23
  • 1
    $\begingroup$ Could you please explain the rationale behind sim(d,e) > sim(a,b)? By both Cosine and Manhattan metrics it is the opposite. Would choosing a negative p for a Minkowski distance get closer to what you are aiming for? Normalisation would get you this property, but as you pointed out, this would get in conflict with your other requirements. $\endgroup$ – mapto Feb 4 at 11:26
1
$\begingroup$

Your requirements are not restrictive enough to determine some cases. For example, for these values:

f = [0,110,200,300,0]
g = [0, 13, 6, 9, 0]
h = [1, 3, 6, 9, 1]

how would you wish sim(d,f) and sim(e,g) to compare? What about sim(h,b) - would a Minkowski distance with p != 1 be any good for you? How about negative p?

However, you can try to construct a combined parametrised metric that satisfies your desired properties. You've already identified cosine similarity, manhattan similarity and normalisation to be useful. I'll give you an example in python, because it is as good as any language (or pseudolanguage) and it determines functions that otherwise might have more than one possible definition.

The basic principle is that one could use the metrics that have the desired properties, parametrise them, and finally weight them to achieve the desired balance. They need to be in the same domain, and because of cosine similarity I will bring all metrics in the [0,1] domain.

I'm not employing normalisation, because I don't see how it could add value to discern the given values. This might change, depending on other relationships you might wish to provide.

So an initial take could be this:

from math import atan, pi
from scipy.spatial.distance import cosine, cityblock

a = [0, 1, 2, 3, 0]
b = [0, 3, 6, 9, 0]
c = [1, 1, 1, 1, 1]
d = [0, 100, 200, 300, 0]
e = [0, 110, 210, 310, 0]

coef1 = 100

def man_derived(a, b):
    return (2 / pi) * atan(cityblock(a, b))

def bespoke_sim(a, b, p1):
    return (1 - cosine(a, b)) * (1 - man_derived(a, b))**p1

print("sim(d,e)=%.5f"%bespoke_sim(d,e,coef1))
print("sim(a,b)=%.5f"%bespoke_sim(a,b,coef1))
print("sim(a,c)=%.5f"%bespoke_sim(a,c,coef1))
print("sim(a,d)=%.5f"%bespoke_sim(a,d,coef1))
print("sim(a,e)=%.5f"%bespoke_sim(a,e,coef1))

This results in:

sim(d,e)=0.88270
sim(a,b)=0.99565
sim(a,c)=0.71714
sim(a,d)=0.10168
sim(a,e)=0.09702

This gives you a desired order of the other elements, except for sim(d,e), but as I already indicated, I am not sure what logic should lead this to be larger then sim(a,e).

In general I hope you can see the thinking: Metrics are combined by multiplication, because this keeps them in the [0,1] domain. Parameters (in the example this is p2)are used to weight individual metrics by rising them to a higher multiplicative power.

Also, you didn't want to limit your domain, but obviously one event has different implications when one of few, and when one of many. Then what is many - 100, 1 million, more? In my formula this comes into play with the atan function.

$\endgroup$
  • $\begingroup$ Thanks a lot! I like the idea of the atan, but I don't understand how it addresses your point. I understand that it is transforming the manhattan distance in the [0,1] domain. What I don't understand is how it addresses the problem of the difference of (1,0,0)-(0,0,0) vs (1000,0,0) - (999,0,0) for example. I also don't understand p1. It is raising a number in [0,1] to some power, so it will result in a smaller number in the same domain (for p1>1). $\endgroup$ – jcp Feb 5 at 9:29
  • $\begingroup$ Regarding p1, notice that the number it operates on is before you apply atan. Thus, it is the Manhattan distance which - due to your components being integer - is integer and not necessarily in [0,1]. It was meant to balance for the fact that atan results in very close values for huge numbers. Take with a grain of salt, since today - one day later, the rationale behind this factor doesn't sound all that relevant to me either. $\endgroup$ – mapto Feb 5 at 10:00

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.