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,
- $SetSim(A, B) \leq 1$ with equality holding iff A = B
- $SetSim(A, B) \geq Jaccard(A, B)$ with equality if $ElementSim(a,b) = I(a == b)$, the indicator of exact equality.