# Similarity between n >> 2 binary vectors

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

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

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.