# Jaccard similarity of sets with approximate element matching

Consider two sets like this: A = {'hello', 'world'} and B = {'Hello', 'helo', 'goodbye'}.

I want to measure the similarity between these two sets. There are two levels to this problem:

• Comparing set elements: How similar are "hello" and "Hello"? This is not the subject of my question; let's assume that we have a satisfactory function $ElementSim()$ that returns a similarity between any two strings.
• Comparing sets: How similar are A and B? The Jaccard similarity provides one solution to this problem. Implicitly, the Jaccard similarity uses a binary $ElementSim()$; two elements $a \in A, b \in B$ are in the intersection $A \cap B$ iff $a$ and $b$ are exactly the same.

The basic Jaccard similarity of A and B is 0, but obviously you could be unhappy with this if your preferred element similarity is very not binary, like $1 >>ElementSim(hello, Hello) >> 0$.

I'm looking for a generalization $SetSim()$ of Jaccard similarity that accepts an arbitrary $ElementSim()$ function for comparing elements. Requirements for such a similarity include, for any sets A,B,

1. $SetSim(A, B) \leq 1$ with equality holding iff A = B
2. $SetSim(A, B) \geq Jaccard(A, B)$ with equality if $ElementSim(a,b) = I(a == b)$, the indicator of exact equality.
• I don't think the question is about "a variant of Jaccard similarity". It actually is about how to measure partial match between words, a totally idependent theme. – ttnphns Nov 8 '16 at 16:52
• @ttnphns, you are correct that there are two independent components here. One is the set-level similarity. The other is the element-level similarity. A partial match between words is an element-level similarity in my application above. My question is about the set-level similarity, not the word-level part. It's easy enough to normalize Levenshtein distance into a word-level similarity. – zkurtz Nov 8 '16 at 18:08
• I'll edit the question to clarify this distinction. – zkurtz Nov 8 '16 at 18:09
• Sides 28-32 present a soft set similarity that gives intuitive results, although it does not readily scale well to large sets, and it lacks peer review or other formal validation: first.org/resources/papers/conf2017/… – zkurtz Oct 29 '18 at 13:03
• As I know, extension of Jaccard similarity from binary data to quantitative data case is called Ruzicka similarity (which is also = 1-Soergel distance). If you are interested you can find formulas in "Various proximities" docx on my web page. – ttnphns Oct 29 '18 at 13:08