I have $n$ binary vectors $x_i, ..., x_n$ of length $d$. I wish to compute a similarity measure between all $n$ of them. My initial thought was to use the Jaccard Index, since each binary element $x_{i_k}$ actually represent the presence / absence of member $k$ from set $i$. Specifically, the index would be $$J(x_1, ..., x_n) = \frac{|x_1 \cap ... \cap x_n|}{|x_1 \cup ... \cup x_n|}$$

However, a small number of my vectors have all zeros. This leads to the index $J$ between all vectors begin 0, although the majority of the other vectors are similar. Does anyone know of a different similarity measure that doesn't penalise the similarity score based on a few very sparse vectors?

This seems difficult. If all the vectors for example, have only their first element set i.e $x_{i_1} = 1$ I would want $J=1$, but if however only one of the vectors has $x_{i_1} = 1$ and the others are dense, I would want this outlier not to penalise the similarity score. It seem to me perhaps the best approach is to somehow partition the $n$ vectors and then apply $J$ to each partition.

Any advice on how to handle this issue is much appreciated.

Best, Izaak

  • 1
    $\begingroup$ What is the intended purpose of the similarity measure? $\endgroup$ – whuber May 1 '19 at 17:22

I hesitated on posting this answer because it treats the vectors as continuous variables.

I'm assuming that each vector $x_j$ has $m$ coordinates $x_j^k$, so $x_j = (x_j^1, \ldots, x_j^m)$.

With this, you can compute the variance of each coordinate and get a vector $v = (v^1, \ldots, v^m)$.

Afterwards, you can compute the mean variance of vector $v$. Since each coordinate will have a variance of at most $1/4$, the mean variance will be in $[0; 1/4]$, where larger values represent a smaller similarity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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