[HN Gopher] Jaccard Index
___________________________________________________________________
Jaccard Index
Author : dedalus
Score : 240 points
Date : 2023-03-19 19:33 UTC (1 days ago)
(HTM) web link (en.wikipedia.org)
(TXT) w3m dump (en.wikipedia.org)
| hbcondo714 wrote:
| I think a good example of the Jaccard Index is from the paper
| Lazy Prices[1] in which the authors use it to measure diffs in a
| company's annual and quarterly reports. They also use other
| similarity measures (cosine, minimum edit, simple) so you get a
| better understanding of how each applies to textual similarity as
| a whole.
|
| [1] https://papers.ssrn.com/sol3/papers.cfm?abstract_id=1658471
| SubiculumCode wrote:
| Jaccard my Dice please.
| SubiculumCode wrote:
| Jests asside, I've mostly used the closely related Dice
| coefficient when measuring segmentation reliability
| tpoacher wrote:
| they are effectively equivalent, theres a one to one mapping
| between the two
| pfdietz wrote:
| I've used this to find similarity between terms in a
| specification document and identifiers in a program. The index is
| computed on the bag of bigrams from the two strings.
|
| If one has a set of pairs that are similar, one can look for
| common bag differences in the matches. These can correspond to
| extra characters inserted in the identifier names for that
| particular program (for example, prefixes or suffixes related to
| module name or variable types.) Once these are found they can be
| used to tweak the similarity score.
| psyklic wrote:
| This 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).
| aquafox wrote:
| Very useful indeed. I used it to compute the similarity of
| patients with different diseases, e.g. if patient1 has 3
| diseases and patient2 has 2 of those three, they should be
| treated more similar than if patient1 has only 1 disease and
| patient2 has another one. Euclidean distance would assign the
| same value in both cases.
| startup_eng wrote:
| I just used this at work the other day to calculate similarities
| between different data models that had overlapping children
| models. One of our teams was going to go through manually to
| check these overlaps and consolidate, but by using this
| clustering algo based on Jaccard distance we were able to give
| them clusters to consolidate up front. Super cool stuff!
| sonofaragorn wrote:
| what is a children model? I'm curious but can't really follow
| what you wrote, can you add a bit more context?
| [deleted]
| BenoitP wrote:
| As an aside if you find yourself having to compute them on the
| fly, know that the Roaring Bitmaps libraries is the way to go
| [1]. The bitmaps are compressed, and can be streamed directly
| into SIMD computations (batching boolean transformations and
| popcnts 256 bits wide!). The Jaccard index is just
| intersection_len / union_len [2] away
|
| Of note: the author of that library is none other than Daniel
| Lemire [3], whose articles pop up quite often on HN
|
| [1] https://roaringbitmap.org/
|
| [2]
| https://roaringbitmap.readthedocs.io/en/latest/#roaringbitma...
|
| [3] https://lemire.me/blog/
| b_mc2 wrote:
| I've used this recently to do some fuzzy matching of column names
| in datasets, I also added it to a small python one-liner library
| I've been making for practice. p.s. don't give me flack, I know
| this isn't an efficient way to do things.
|
| jaccard = lambda A, B: len(set(A).intersection(set(B))) /
| len(set(A).union(set(B)))
|
| https://github.com/b-mc2/MiniMath
| coeneedell wrote:
| I 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.
| paulgb wrote:
| 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.
|
| https://en.m.wikipedia.org/wiki/W-shingling
| jethkl wrote:
| Interesting - I also used Jaccard similarity to classify
| clusters of malicious ad traffic schemes. The idea worked
| well. It was unclear if the similarity was due to mimicry or
| authorship, but that did not matter for our use.
| unethical_ban wrote:
| What is the predicted bounding and the ground truth bounding, as
| related by a stop sign? I have no idea what's happening there.
| [deleted]
| montroser wrote:
| The "predicted" box there would be a best guess from a
| statistical model powered by AI or computer vision, answering,
| "where is the stop sign in this image?". The "ground truth"
| would be an annotation by a human answering the same question.
| The jaccard similarity metric would say that these bounding
| boxes are highly similar, and so the prediction could be
| evaluated as high quality.
| john-titor wrote:
| this is well-known to people working in cheminfornatics as the
| tanimoto similarity, used to calculate the similarity of two
| chemical structures based on their (folded) fingerprint
| pallas_athena wrote:
| I used this for a project re: similarity between two strings.
|
| The Jaccard similarity between sets of uni- and bi-grams was a
| surprising effective metric.
|
| DOG -> {d, o, g, do, og}
|
| GOD -> {g, o, d, go, od}
|
| intersection = {d, g, o}
|
| union = {d, g, o, do, go, od, og}
|
| J = 3 / 7 = ~43%
| bitshiftfaced wrote:
| One of the weaknesses with Jaccard similarity is how it focuses
| on matches/true positives. It neglects the importance of
| "negative space."
|
| I was happy to see Matthew's correlation coefficient (MCC) used
| in the recent "1st and Future - Player Contact Detection" Kaggle
| competition. MCC balances the eight confusion matrix ratios, and
| I've gotten excellent results when using it in the past.
| tpoacher wrote:
| It's not a weakness; it's a feature.
|
| One that makes it the better choice in situations where
| negative space should in fact be ignored. (comparing chest
| xrays are a typical example in medical imaging)
| bitshiftfaced wrote:
| It's unclear to me why they should be ignored.
| samscully wrote:
| The book Mining of Massive Datasets [1] has useful information on
| building an efficient similarity index using Jaccard/minhash. I
| would also recommend Otmar Ertl's papers on extensions of minhash
| that approximate Jaccard better in certain situations, e.g.
| superminhash [2].
|
| [1] http://www.mmds.org/ Chapter 3 [2]
| https://arxiv.org/abs/1706.05698
| pncnmnp wrote:
| I recently wrote a fun blog post
| (https://pncnmnp.github.io/blogs/odd-sketches.html) about how to
| estimate Jaccard Similarity using min hashing, what b-bit min
| hashing is, and how to improve upon its limitations using a 2014
| data structure called odd sketches.
|
| Jaccard Similarity's history is also quite interesting. From my
| blog:
|
| > In the late 19th century, the United States and several
| European nations were focused on developing strategies for
| weather forecasting, particularly for storm warnings. In 1884,
| Sergeant John Finley of the U.S. Army Signal Corps conducted
| experiments aimed at creating a tornado forecasting program for
| 18 regions in the United States east of the Rockies. To the
| surprise of many, Finley claimed his programs were 95.6% to 98.6%
| accurate, with some areas even achieving a 100% accuracy rate.
| Upon publishing his findings, Finley's methods were criticized by
| contemporaries who pointed out flaws in his verification
| strategies and proposed their solutions. This sparked a renewed
| interest in weather prediction, which is now referred to as the
| "Finley Affair."
|
| > One of these contemporaries was Grove Karl Gilbert. Just two
| months after Finley's publication, Gilbert pointed out that,
| based on Finley's strategy, a 98.2% accuracy rate could be
| achieved simply by forecasting no tornado warning. Gilbert then
| introduced an alternative strategy, which is now known as Jaccard
| Similarity.
|
| > So why is it named Jaccard Similarity? As it turns out, nearly
| three decades after Sergeant John Finley's tornado forecasting
| program in the 1880s, Paul Jaccard independently developed the
| same concept while studying the distribution of alpine flora.
| B0073D wrote:
| Recently I wanted to try and use this to filter out logs I
| don't care about, but it seemed a lot more involved than I
| initially thought.
|
| I essentially wanted to use this as a way to flexibly filter
| out items without having to come up with a regex for every line
| item.
|
| I wonder if anyone has done this before...
| zamadatix wrote:
| Could always rely on the Levenshtein distance. You have to be
| careful with similarity approaches though as you may end up
| filtering important messages because they are structurally
| similar to the unimportant message.
| voldacar wrote:
| Maybe you could use a language model embedding to define
| some kind of semantic distance.
| dopidopHN wrote:
| I often feel modern tools should offer that
| ta988 wrote:
| Bayesian filters like for emails? You mark them as important
| or noise and over time it will learn. These are extremely
| easy to put in place and you don't have to preannotate as it
| learns as you go.
| nl wrote:
| Yes Bayesian filters work well for this.
|
| I had an idea Splunk had them built in? But it's about 5
| lines of Python anyway.
| funkylisp wrote:
| Just filter out logs by the file, line that generated it
| (i.e. that had the log statement). Even if the actual log
| entry changes (e.g. because of a formatted str with vars)
| they will always have the same source.
| charliejuggler wrote:
| My colleague Nate wrote about using Jaccard for search engine
| regression testing:
| https://opensourceconnections.com/blog/2021/07/23/jaccard-in...
| If you make changes to a search algorithm and the order of
| results changes too much this can alarm users, so this is a good
| way to reduce risk.
| stygiansonic wrote:
| The 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..._
| jszymborski wrote:
| Another example of this sort of thing (that is vaguely related
| in that it's commonly used as a metric) is (what I call) the
| Matthew's Correlation Coefficient
| https://en.wikipedia.org/wiki/Phi_coefficient
|
| > In machine learning, it is known as the Matthews correlation
| coefficient (MCC) ... introduced by biochemist Brian W.
| Matthews in 1975.[1] Introduced by Karl Pearson,[2] and also
| known as the Yule phi coefficient from its introduction by Udny
| Yule in 1912
| dalke wrote:
| 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.
| hughw wrote:
| Looks like a "reflection coefficient for sets."
|
| Reflection coefficient in electrical or acoustic (or elastic)
| transmission across two media is the difference of their
| impedances over the sum of them.
|
| Difference over sum is a pattern you see a lot.
| ketralnis wrote:
| Quoting 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)
|
| That gives you a directional relatedness, that is
| programming->python but not necessarily python->programming. Used
| this way you account for the giant subreddit problem[1]
| automatically but now the results are less "amitheasshole is
| related to askreddit" and more like "linguisticshumor is a more
| niche version of linguistics".
|
| 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.
| reichardt wrote:
| Super interesting! I'm currently writing my master thesis on
| analyzing relationships between subreddits based on user and
| semantic similarity. For user similarity I use the Jaccard
| similarity between the unique set of authors of each subreddit.
|
| Can I send you a message and quote you in my thesis? You can
| shoot me a short message as well: violets.parr-0c@icloud.com
| ketralnis wrote:
| Yeah sure, you can message me on reddit too. Same username
| seydor wrote:
| didnt know there was a name for it
___________________________________________________________________
(page generated 2023-03-20 23:03 UTC)