Jaccard Similarity
Jaccard similarity is the ratio of the common items of two sets to the total of distinct items in those two sets.
Two titles are first converted into a set of words. The number of common words is divided by the total of distinct words appearing in the two sets. The result is a number between 0 and 1: 0 means no common words at all, 1 means the two sets are exactly the same. The measurement does not look at the order of the words, it only looks at which words are present. Its calculation is cheap; it can be run among thousands of titles.
Example: In the
{earthquake, region, damage}and{earthquake, region, team}sets, the common word count is 2, the total distinct word count is 4. Jaccard = 2 / 4 = 0.50.
Go deeper
Formula: J(A,B) = |A∩B| / |A∪B|.
Since the measurement runs on sets, word order and repetition count do not change the result. “Earthquake in region” and “In region earthquake” yield the same set.
It has two known limits. First: two titles telling the same event with completely different words receive a low ratio — the measurement sees the word, not the meaning. Second: conjunction and preposition type words appearing in every text artificially raise the ratio. The second problem is reduced by eliminating these words (stopwords) and very short words before comparison. The first one cannot be solved with this method; it is an accepted limit.
In a naive implementation, every title is compared with every title and the cost grows with the square of the item count. An inverted index — taking as candidates only pairs carrying a common word — reduces this cost.
1.4.1 M1: Similarity Lab
M1Test the limits of the Jaccard measure. Does word order change the result? What do stop words do?