12
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ How about edit distance? $\endgroup$
    – ziggystar
    May 11, 2013 at 11:51
  • $\begingroup$ any suggestion which distance would be more useful? $\endgroup$
    – totpiko
    May 11, 2013 at 11:52
  • $\begingroup$ Do you have the "correct" data to CV with? $\endgroup$
    – N. McA.
    May 11, 2013 at 12:01
  • 1
    $\begingroup$ You seem to have defined Hamming distance incorrectly. It is not the sum of one minus the sum of the other it is the sum of the differences. $\endgroup$
    – Peter Flom
    May 11, 2013 at 12:34
  • 1
    $\begingroup$ @Peter Actually, it's not that either. Assuming you mean sum of absolute values of the differences (without which you cannot have a distance at all), you have described the L1 distance. The Hamming distance is the number of places in which the two vectors differ. $\endgroup$
    – whuber
    Oct 31, 2016 at 20:13

3 Answers 3

14
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ +1 for the link to the article! $\endgroup$
    – Dataman
    Jan 15, 2019 at 12:42
  • 1
    $\begingroup$ The link is dead but the linked article was titled "A Survey of Binary Similarity and Distance Measures" by Choi et al 2010 and published in SYSTEMICS, CYBERNETICS AND INFORMATICS, ISSN 1690-4524, VOLUME 8 - NUMBER 1 - YEAR 2010 $\endgroup$
    – krassowski
    Sep 15, 2021 at 20:18
2
$\begingroup$

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.

enter image description here

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.

$\endgroup$

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.