# Is there an existing similarity measure for comparing sequences similar to this one?

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 ?

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}.$$
$$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.