0
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ttnphns Nov 8 '16 at 16:52
  • $\begingroup$ @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. $\endgroup$ – zkurtz Nov 8 '16 at 18:08
  • $\begingroup$ I'll edit the question to clarify this distinction. $\endgroup$ – zkurtz Nov 8 '16 at 18:09
  • $\begingroup$ 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/… $\endgroup$ – zkurtz Oct 29 '18 at 13:03
  • $\begingroup$ 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. $\endgroup$ – ttnphns Oct 29 '18 at 13:08
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.