I work with elements that have a representation in two different vector spaces and I would like to compute an indicator of how similar the neighbors of the elements are in these two spaces.

To do so, I start by computing the list of the $n$-nearest neighbors of all elements, then I use a sequence similarity measure that, given two sequences, return a score between 0 and 1.

For now I used :

I would like to use a distance that take neighbors order into account and that gives more weight to firsts neighbors since they are more significant.

I have thought about the following similarity measure that appears to deals with both these properties but I can not find it anywhere so I wonder if someone have heard of such similarity measure :

Given to sequences $ a = (a_1, a_2, ..., a_n)$ and $b = (b_1, b_2, ..., b_n)$ I define the similarity $S(a,b)$ as :

$$S(a,b) = \frac{1}{n}\sum_{k=1}^{n} \frac{|(\{a_i | i \in [1,k]\} \cap \{b_i | i \in [1,k]\}|}{k}$$

Some examples :

For $a = b = (1, 2, 3, 4)$ : $$S(a, b) = \frac{1}{4} \times \left( \frac{1}{1} + \frac{2}{2} + \frac{3}{3} + \frac{4}{4}\right) = 1$$

For $a = (1, 2, 3, 4)$ and $b = (9, 8, 7, 6)$ : $$S(a, b) = \frac{1}{4} \times \left( \frac{0}{1} + \frac{0}{2} + \frac{0}{3} + \frac{0}{4}\right) = 0$$

For $a = (1, 2, 3, 4, 5, 6)$ and $b = (2, 1, 4, 3, 6, 5)$ : $$S(a, b) = \frac{1}{6} \times \left( \frac{0}{1} + \frac{2}{2} + \frac{2}{3} + \frac{4}{4} + \frac{4}{5} + \frac{6}{6} \right)$$

Thus :

  • if $a = b$, $S(a,b) = 1$
  • if $\{a_i | i \in [1,n]\} \cap \{b_i | i \in [1,n]\} = \emptyset$, $S(a,b) = 0$

Does anyone have heard of such similarity measure between sequences ?


1 Answer 1


Given two sequences $ a = (a_1, a_2, ..., a_n)$ and $b = (b_1, b_2, ..., b_n)$ you define the similarity $S(a,b)$ as :

$$S (a,b) = \frac{1}{n}\sum_{k=1}^{n} \frac{|(\{a_i | i \in [1,k]\} \cap \{b_i | i \in [1,k]\}|}{k}. $$

If instead you had

$$S(a,b) = \frac{1}{n}\sum_{k=1}^{n} \frac{|(\{a_i | i \in [1,k]\} \cap \{b_i | i \in [1,k]\}|}{| \{a_i | i \in [1,k]\} \cup \{b_i | i \in [1,k]\} |}$$ this would be the arithmetic mean of partial Jaccard distances on the first $k$ symbols as $k$ varies from $1$ to $n.$

So you chose to normalize by $k$ instead of the union. In some cases people normalize Jaccard by the maximum of the two set sizes, namely $$\max(|(\{a_i | i \in [1,k]\}|, |\{a_i | i \in [1,k]\}|)$$ but you have chosen to normalize by the maximum possible value of the two set sizes which is $k$ when all symbols in the partial sequence are distinct.

I haven't found anything else at a quick look over the book Dictionary of Distances by Deza and Deza.


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.