Jaccard similarity of sets with approximate element matching

Question

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.

Answer 1

You may want to try to represent your items as a bag (or set) of N-Grams on the character level. For example, "hello" could be represented as {"hel", "ell", "llo"}. And you may apply this transformation to all the elements of your original set. Once you've done it, you can compute the Jaccard similarity on this representaion.

Even though this is not exactly what you ask (and the other answer points you in the right direction), I still believe it can solve your problem in a computationally cheaper way.

Answer 2

Jaccard works with a label system, so if you want that make happen you need to do use a distance measure, like Levenshtein distance.

If you want to use Jaccard anyway, try to normalize to lowercase letters and atleast you would have a match in cases like the example.