# binary vector similarity with the considering edit distance

Here, i have a set of binary vectors. For example, three binary vectors $a, b, c$ as:

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

$b = [0, 0, 1, 0, 0]$

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

When i use the cosine similarity, then $sim(a, b) = sim(a, c) = 0.0$.

However, I want to find a similarity metric $sim(\cdot,\cdot)$ having:

$\mathrm{sim}(a, b) > \mathrm{sim}(a, c) \neq 0.0$

Any ideas?

NOTES: each binary vector can have multiple non-zero values, for example a vector $d = [0, 1, 0, 1, 0]$;

-
What exactly is your question? It sounds like you want a function $f:\{a,b,c\}^2\to\mathbb{R}$ where $f(a,b)>f(a,c)\neq 0$ but then what do the notes mean? – Eric Stucky Jan 4 '13 at 7:20

Cosine similarity is not a metric in the usual sense, so I'm assuming you are just looking for a symmetric function $f:\{0,1\}^n\times\{0,1\}^n\to \mathbb{R}$ where $f(a,b)>f(a,c)\neq 0$, and in general vectors that look similar have bigger values. Something reasonable might be the following:

Define the left-shift operation $\sigma$ to be a function on a binary vector such that $\sigma([x_1,x_2, \cdots, x_{n-1}, x_n])=[x_2, x_3, \cdots, x_n]$. Also, define the projection-like function $\pi([x_1,x_2, \cdots, x_{n-1}, x_n])=[x_1,x_2, \cdots, x_{n-1}]$. Both of these vectors have one fewer element then the originals. Then we determine values of $f$ as follows:

$$f(\mathbf{u}, \mathbf{v})=\sum_{k=0}^{n-1} \frac{\pi^k(\mathbf{u})\cdot\sigma^k(\mathbf{v})}{2^{k+1}}+\frac{\sigma^k(\mathbf{u})\cdot\pi^k(\mathbf{v})}{2^{k+1}}$$

where the $\cdot$ represents a dot-product-like operation but with nxor instead of ordinary multiplication (so that each coordinate gets a score of 1 if they're the same or 0 if they're not, and these are added), and the exponents on the functions stand for iteration.

Notice that $f(\mathbf{u}, \mathbf{v})=f(\mathbf{v}, \mathbf{u})$, so $f$ is symmetric. Furthermore, $f(a,b)=\frac{81}{16}$ and $f(a,c)=\frac{80}{16}\neq 0$, as desired. The difference would probably be more meaningful if you subtracted off the mean, but I don't really want to figure out what that is right now.

EDIT: The difference is also more pronounced if you use the actual dot product, in which case $f(a,b)=\frac{1}{4}$ and $f(a,c)=\frac{1}{8}$. But then $f(0,\mathbf{x})=0$ for any $\mathbf{x}$, which felt wrong to me; if this seems okay to you, it might be a better function for your purposes.

-