Distance Metrics For Binary Vectors

Question

I have vectors of same length consisting of 1 and 0. I am trying to find out how similar they are. So far I am using hamming distance that I calculate sum of one vector then sum of second vector and the difference between this is the difference of the days. With 1 and 0 it works pretty well.

My problem is that it doesn't reflect in any way where is the difference in the vectors and what is the variance of the error. I have thought of counting of how many 1 been misplaced to 1 of the next vector and how many 0 have been misplaced. It gives little bit more of information but still doesn't tell anything about the variance of the error.

The vectors are used to represent occupancy of house in time, with every 1 indicating that house is occupied and 0 that it is not. From this I am trying to predict how next day will look.

Answer 1

Seems like you're looking for either the Jaccard distance or the Dice dissimilarity.

Jaccard distance:

$1 - \frac{|A \cap B|}{|A \cup B|}$

Dice dissimilarity:

$1 - \frac{2|A \cap B|}{|A| + |B|}$

These both are equal to zero if $A$ and $B$ are exactly the same, and one if they are completely different. However, Jaccard will "punish" differences more severely. Also note, Dice is not really a metric (doesn't satisfy triangle inequality) so it may not satisfy your needs.

The appropriate distance likely depends on the origin of the data and what you are trying to achieve, but those two are likely a good start.

Jaccard index

Sorensen-Dice index

Answer 2

In addition to Jaccard and Dice, I've had success with:

• Cosine Similarity: $\text{cos}(\theta) = \frac{{\bf u} \cdot {\bf v}}{||{\bf u}|| \times ||{\bf v}||}$
  • Not a metric, only a similarity measure. See Angular similarity if metric is needed.
• Rajski's distance: $1 - \frac{H(u;v)}{H(u,v)} $
  • H(u;v)=mutual information; H(u,v)=Joint Entropy

See this article for a good survey of binary similarity measures and distances.

Answer 3

Quick summary of metrics I used for a similar problem. Jaccard distance is also useful, as previously cited. Distance metric are defined over the interval [0,+∞] with 0=identity, while similarity metrics are defined over [0,1] with 1=identity.

a = nb positive bits for vector A

b = nb positive bits for vector B

c = nb of common positive bits between vector A and B

S = similarity

D = distance

Dice and Tanimoto metrics are monotonic (which means you will get the exact same ordering/ranking of the vectors ([B,C,D,..]) you will compare to a reference vector (A) by using these two metrics, although similarity values may differ). Manhattan and Euclidian metrics are monotonic. Cosine and Tanimoto metrics are always highly correlated but not strictly monotonic.

Tanimoto is the reference metric used in the field of drug discovery for problems that can be framed like yours. Its only issue is it is biased towards low values when your vectors contains very few positive bits.