# Computing Jaccard Similarity between two documents

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 = jeﬀ typed the quick brown dog jumps over the lazy fox by mistake

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

• This looks a lot like a homework question. Can you show what you have done so far? or say which part you don't understand? – Erwan Oct 1 '19 at 23:01
• It is not a homework question. I actually found this online while researching. I started off by breaking down the words into 2 sets, "the quick" "quick brown" "brown fox" "fox jumps" "jumps over" "over the" "the lazy" "lazy dog" "jeff typed" "typed the" "the quick" "quick brown" "brown dog" "dog jumps" "lazy fox" "fox by" "by mistake" etc. – Danniy Oct 1 '19 at 23:05
• Not sure where to go from there. I was not sure if I split the sets up right either. – Danniy Oct 1 '19 at 23:08
• Ok, I wrote an answer, let me know if anything unclear – Erwan Oct 1 '19 at 23:28

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$$

• This helps a lot. It makes sense now. Thank you so much. – Danniy Oct 1 '19 at 23:47