Jaccard Index
en.wikipedia.org
Jaccard Index
1–10 of 46 posts
Re: Jaccard Index
#2This is one of my favorite distance metrics* to show people!
For example, perhaps one person likes Reddit and HN, while someone else likes HN and SO.
Then their Jaccard Index would be 1/3, since they have one thing in common out of three.
* Technically it computes "similarity" (larger number == more similar), but `1 - Jaccard Index` is a distance (smaller number == more similar).
Re: Jaccard Index
#3I recently used Jaccard similarity as a measurement of distance between two sets of online articles. It’s amazing how versatile it is for all sorts of weird tasks.
Re: Jaccard Index
#4The name may be an example of this: https://en.m.wikipedia.org/wiki/Stigler%27s_law_of_eponymy
It was developed by Grove Karl Gilbert in 1884 as his ratio of verification (v)[1] and now is frequently referred to as the Critical Success Index in meteorology.[2] It was later developed independently by Paul Jaccard…
Re: Jaccard Index
#5I recently used Jaccard similarity as a measurement of distance between two sets of online articles. It’s amazing how versatile it is for all sorts of weird tasks.
I uses to use Jaccard similarity combined with w-shingling at the character level to detect clusters of fraud sites. It was surprisingly effective, because it was able to pick up common patterns in the code even if they used completely different styles and text.
Re: Jaccard Index
#6didnt know there was a name for it
Re: Jaccard Index
#7Jaccard my Dice please.
Re: Jaccard Index
#8Jaccard my Dice please.
Jests asside, I've mostly used the closely related Dice coefficient when measuring segmentation reliability
Re: Jaccard Index
#9Quoting myself from a while ago[0]
At reddit many moons ago before machine learning was a buzzword one early iteration of recommendations was based on Jaccard distance using the number of co-voters between subreddits. But with one twist: divide by the size of the smaller subreddit.
relatedness a b =
numerator = | voters on(a) ∩ voters on(b) |
denominator = | voters on(a) ∪ voters on(b) |
weight = min(|voters on(a)|, |voters on(b)|)
numerator / (weight*denominator)
The great thing is that it’s actually more actionable as far as recommendations go! Everybody has already heard of the bigger version of this subreddit, but they probably haven’t heard of the smaller versions. And it’s self-correcting: as a subreddit gets bigger we are less likely to recommend it, which is great because it needs our help less.
It's also easy to compute this because it lends itself to one giant SQL query that postgres or even sqlite[2] optimises reasonable well. It has some discontinuities around very tiny subredddits, so there was also a hack to just exclude them with a hack heuristic. It does get fairly static so once we've picked 3 subreddits to recommend if you're on subreddit A, if you don't like them we'll just keep showing them anyway. I had a hack in mind for that (use the computed values as random weights so we'll still occasionally show lower-scoring ones) but by this time people much smarter than I took over recommendations with more holistic solutions to the problem we were trying to solve in the first place. Still, as a first pass it worked great and based on my experience I'd recommend simple approaches like this before you break out the the linear algebra.
Side note, I tried co-commenters in addition to co-voters. The results tended more accurate in my spot tests but the difference fell away in more proper cross-validation testing and I didn't look into where the qualitative difference was. But since there are more votes than comments on small subreddits the number of recommendable subreddits was higher with votes. I reasoned that co-submitters (of posts) should be even more accurate but it was thrown off by a small number of spammers and I didn't want to mess with combining those tasks at the time.
[0]: https://news.ycombinator.com/item?id=22178517
[1]: that votes are distributed according to a power law, meaning that everybody has voted on the largest subreddits so most clustering approaches recommend askreddit to everybody. That's okay for product recommendations where "you should buy the most popular CPU, it's most popular for a reason" but for subreddits you already know that so we want a way to bias to the most "surprising" of your votes.
[2]: I prototyped it on sqlite on my laptop and even with close to the production amount of data it ran reasonable well. Not fast, but fine. This was on considerably less traffic to today, mind.
Re: Jaccard Index
#10The name may be an example of this: https://en.m.wikipedia.org/wiki/Stigler%27s_law_of_eponymy It was developed by Grove Karl Gilbert in 1884 as his ratio of verification (v)[1] and now is frequently referred to as the Critical Success Index in meteorology.[2] It was later developed independently by Paul Jaccard…
In my field, cheminformatics, we refer to it as "Tanimoto similarity" because it was (quoting Wikipedia) "independently formulated again by T. Tanimoto."
It's an odd set of linkages to get there. First, "Dr. David J. Rogers of the New York Botanical Gardens" proposed a problem to Tanimoto, who published the writeup in an internal IBM report in 1958. (I understand there was a lot of mathematical research in taxonomy at the time.) In 1960 Rogers and Tanimoto published an updated version in Science.
In 1973 Adamson and Bush at Sheffield University developed a method for the automatic classification of chemical structures. They tried Dice, phi, and Sneath as their comparison methods but not Tanimoto. In their updated 1975 publication write "Several coefficients have been proposed based on this criterion", with a list of citations, including the Rogers and Tanimoto paper as citation 14.
In 1986, Peter Willett at Sheffield revisits this work and finds that Tanimoto gives overall better results when applied to what are now called cheminformatics "fingerprints". He uses "Tanimoto", with no direct citation for the source of that definition.
This similarity method is easy to implement, and many organizations already have pre-computed fingerprints (they are used as pre-filters for graph queries), so the concept and nomenclature takes off almost immediately, with "Tanimoto" as the preferred named.
It's not until 1991 that can find a paper in my field referring to the earlier work by Jaccard (the paper uses "Tanimoto (Jaccard)").
I have found some papers in related fields (eg, in IR and mass spectra analysis) which reference Tanimoto similarity, but nothing to the extent that my field uses it.