Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]$;

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.