Similarity between n >> 2 binary vectors

Question

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

Answer 1

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.