Computing Jaccard Similarity between two documents

Question

Data Mining:

Compute the Jaccard similarity of D1 and D2 on 2-shingles is. Sim(D1,D2) =

D1 = the quick brown fox jumps over the lazy dog

D2 = jeff typed the quick brown dog jumps over the lazy fox by mistake

Could you explain how to reach the conclusion, step-by-step? Thanks.

Answer 1

You forgot a few 2-shingles (bigrams but without duplicates) in the second set but you got the idea right:

$S_1$ = { "the quick", "quick brown", "brown fox", "fox jumps", "jumps over", "over the", "the lazy", "lazy dog" }

$S_2$ = { "jeff typed", "typed the", "the quick", "quick brown", "brown dog", "dog jumps", "jumps over", "over the", "the lazy", "lazy fox", "fox by", "by mistake" }

Remark: For this particular example, in each of these two sets every sequence of 2 words appears only once, so there's no need to remove duplicates to obtain the set. In the general case this might be necessary (see the Wikipedia example).

To calculate Jaccard similarity we need to count:

• The intersection $S_1 \cap S_2$, i.e. the 2-shingles in common: | { "the quick", "quick brown", "jumps over", "over the", "the lazy" } | = 5
• The union $S_1 \cup S_2$, i.e. all the distinct 2-shingles: | { "the quick", "quick brown", "brown fox", "fox jumps", "jumps over", "over the", "the lazy", "lazy dog", "jeff typed", "typed the", "brown dog", "dog jumps", "lazy fox", "fox by", "by mistake" } = 15

Jaccard similarity:

$$\frac{S_1 \cap S_2}{S_1 \cup S_2} = \frac{5}{15} = 0.33$$