11
$\begingroup$

I'd like to calculate the similarity between two sets using Jaccard but temper the results using the relative frequency of each item within a corpus.

Jaccard is defined as the magnitude of the intersection of the two sets divided by the magnitude of the union of them both.

$jaccard(A, B) = \frac{|A \bigcap B|}{ |A\bigcup B|}$

If I use inverse document frequency (the log of the number of documents divided by the frequency of the item) ...

$idf(i) = log\frac{| D |}{f(i)+1}$

$|D|$ is the number of documents

$|f(i)|$ is the frequency of the item in the documents.

... can I define my weighted Jaccard similarity function as the sum of the IDFs of the items in the intersections divided by the sum of the IDFs of the union? (Sorry describing this in LaTeX reaches the limits of my knowledge of notation.) Will this scale the similarity appropriately? Are a collection of weights better suited to a cosine similarity?

Improve this question
$\endgroup$
2
  • $\begingroup$ Hi Tom---mathoverflow might not be the correct site for your question---you might get more feedback from math.stackexchange or the stats stackexchange etc. $\endgroup$
    – Suvrit
    Commented Mar 2, 2013 at 3:30
  • $\begingroup$ @TomMartin does it work? $\endgroup$
    – neouyghur
    Commented Sep 11, 2017 at 4:40

2 Answers 2

Reset to default
9
$\begingroup$

The following paper from experts at Google:

http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/36928.pdf

Defines Weighted Jaccard between two vectors with non-negative entries as:

enter image description here

Using the Inverse Document Frequency is interesting, but I am not sure you could really call this a weighted Jaccard?

Here is another paper on a related topic as well:

http://theory.stanford.edu/~sergei/papers/soda10-jaccard.pdf

Hope this helps!

Improve this answer
$\endgroup$
3
$\begingroup$

Yes! There's a paper that does exactly that using exponentially distributed hashes for idf weighting.

https://www.robots.ox.ac.uk/~vgg/publications/2008/Chum08a/chum08a.pdf

If your hash function maps to (0,1], then apply the transformation $\frac{-\log(h(x))}{w_i}$ where $w_i$ is the weight of item i.

Then apply the original minhash algorithm using these biased hashes instead of the uniform ones, and it has the properties you desire.

Check out the section on "probability distributions" in this article for a derivation of how it works. https://moultano.wordpress.com/2018/11/08/minhashing-3kbzhsxyg4467-6/

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .