I would like to ask your opinion on how to choose a similarity measure. I have a set of vectors of length N, each element of which can contain either 0 or 1. The vectors are actually ordered sequences, so the position of each element is important. Suppose I have three vectors of length 10, x_1 x2, x3: x1 has three 1 at positions 6,7,8 (indexes start from 1. Both x2 and x3 have an additional 1, but x2 has it in position 9 while x3 has it in position 1. I am looking for a metric according to which x1 is more similar to x2 than to x3, in that the additional 1 is closer to the "bulk" of ones. I guess this is a relatively common problem, but I am confused on the best way to approach it. Many thanks in advance!
3 Answers
$\begingroup$
$\endgroup$
One thing you could do is fuzzify your vectors: replace each 1 by (for example) 0.4 in its position, 0.2 in the neighbouring positions, and 0.1 in the second position over. Then add up what's in each position. With these fuzzified vectors, you can apply a similarity metric either based on a distance or one like cosines similarity. Your example would produce: (showing only first decimal)
0000011100 -> 0001378731
0000011110 -> 0001378873
1000011100 -> 4211378731
cos(x1, x2) = 0.9613, cos(x1,x3) = 0.9469
$\begingroup$
$\endgroup$
If speed isn't a great concern you could use a KDE with a high bandwidth to pick up the similarity between neighboring elements, then an appropriate metric like the K-L divergence. Similarity and divergence are complementary, of course, so as a final step you would have to relate them; e.g., sim(A, B) = exp[- KLD(A, B)]
$\begingroup$
$\endgroup$
Another possibility is the Earth Mover's Distance. I applied it to Computer Vision, but I think that it may be adapted to your specific problem.
