1
$\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$
6
  • $\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, 2016 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, 2016 at 18:08
  • $\begingroup$ I'll edit the question to clarify this distinction. $\endgroup$
    – zkurtz
    Nov 8, 2016 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, 2018 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, 2018 at 13:08

2 Answers 2

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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