4
$\begingroup$

The Jaccard similarity of two sets, $A$ and $B$, is defined as: $Jaccard(A,B)=\frac{A\cap{B}}{A\cup{B}}$.

Say that I only have a sample of $P\%$ of each of the sets: $A'$ and $B'$. What would be a good estimator for the Jaccard similarity of the original sets $A$ and $B$?

I'm especially interested in the case of small $P$s, say ~ 1%

EDIT - some more details and context in response to comments:

In my specific scenario the groups A and B are external data, which is inaccessible to me directly. However, the party hosting the data is able to sample the data and transfer the resulting samples to me.

A motivational example: say there are two websites, each keeping a set of all visitors at a given day (assume each user has a unique id which is common to both websites). These sets of user ids are A and B above. I do not have access to the entire data-set, but each website samples its data and sends over the resulting sample - these are A' and B'. The goal here is to estimate the amount of user overlap between the websites based on the samples.

The samples are generated by taking each element of the sampled group with a probability of P (so sampling without replacement, and sample size is not fixed); Sampling choices are independent.

The value of P is known and identical for both A and B, but the sizes of the original sets A and B are not directly known.

Typical set sizes in my case - before sampling - are between 10K to 1M.

(end of EDIT)

Numerical Example

Say that $A = \{1..1000\}, B = \{500..2500\}$. Then $Jaccard(A,B) =\frac{500}{2500}=0.2$.

Now we sample $P=10\%$ of each set, resulting with $A'$ with an expected size of $100$, and $B'$ with an expected size of $200$.

Based on simulations, $Jaccard(A',B')\approx0.017$, i.e. much lower than $0.2$

What I've tried

Naively, I thought that a reasonable estimator may be $\frac{1}{P}{\times}Jaccard(A',B')$. For the example above, it gives: $10*0.017=0.17$, which is pretty close.

However looking closely at this estimation (using simlations), it seems biased - the estimation is consistently lower than the actual value, and more so as P nears zero:

enter image description here

(Note that despite the linear trend I've added, the bias does not always look linear)

I had a feeling this may be related to the hypergeometric distribution (as there's some similarity to the capture/recapture problem), but couldn't substantiate that.

So, I'm looking for a better estimator. For extra karma, explain where the bias above arises from.

EDIT

Found a better (though not perfect) estimator:

The difference between this question and the classic capture/recapture problem, is that in the classical setting both samples are done from the same population, while here the first one samples some elements in A which do not exist in B, and vice versa. However, there is a subset of the data on which this assumption does hold: the overlapping part.

Denote $L=|A{\cap}B|$, which would be our "population" in a capture/recapture setting. The first sample ($P\%$ out of $A$) sampled $P\%$ of $L$ - and so did the second sample ($P\%$ out of $B$). Using the naive estimator (Lincoln–Petersen (see here)) for this setting, $L\approx\frac{mn}{k}=\frac{(PL)(PL)}{|A'{\cap}B'|}$, i.e. $L\approx\frac{|A'{\cap}B'|}{P^2}$.

Since the size of $A$ and $B$ can be derived from the size of the samples $|A'|, |B'|$ by dividing in $P$, and using the estimate for the overlap, we can estimate $A{\cup}B=|A|+|B|-L\approx\frac{|A'|}{P}+\frac{|B'|}{P}+L$, and the estimator would be: $est\_jaccard(A',B')=\frac{L}{\frac{|A'|}{P}+\frac{|B'|}{P}+L}$.

Comparing with the previous estimator, this looks much better - although still seems to underestimate close to zero:

enter image description here

EDIT 2: I've also tried another estimator (Chapman) but didn't get better results; so for now I'm using this one.

Still, better / other estimators would be appreciated, as well as any insights regarding the problem and its analysis, which may lead to better estimation.

$\endgroup$
6
  • $\begingroup$ Your description is overly vague: the details matter. In particular, (1) do you know the sizes of $A$ and $B$? (2) Are your samples with or without replacement? (3) Do the samples have fixed sizes? By referring to "expected" sizes you imply they do not, so what is the probability distribution of the sample sizes? (4) Are the two samples independent? (5) What quantitative criteria can you offer for evaluating the "goodness" of an estimator? (6) Values of $P$ as proportions are irrelevant, so what are the typical sizes of $A$ and $B$? $\endgroup$
    – whuber
    Feb 7, 2018 at 14:51
  • $\begingroup$ Thanks for your comment. (1) No, I only know the size of the samples, A' and B', and the proportion sampled, P (so I can estimate the sizes) (2) without replacement (3) The samples are generated by adding each element of the sampled group with a probability P (uniform). (4) Yes, samples are independent (5) as a criterion, I 'd like to minimize the error in the jaccard index (in relative terms), in an unbiased way (so that the average across many experiments would be around the true value) (6) Typical sizes of A, B - 10K to 1M $\endgroup$
    – etov
    Feb 7, 2018 at 15:33
  • $\begingroup$ Thank you. Could you clear just one more thing up: if you know the probability $P$ of sampling any individual element from a group, then the group size must be $1/P$. How is that consistent with not knowing the sizes of the groups themselves? I am concerned that your efforts to simplify and abstract the question may be leading to inconsistencies or even incorrect representations of what you're trying to do. $\endgroup$
    – whuber
    Feb 7, 2018 at 15:59
  • $\begingroup$ Your concern is certainly a valid one! What I meant is that each element has an independent P% probability of being in the sample. Technically a sample is generated by iterating over the group, and taking each element if rand() < P. I think this means that the original group size can be estimated to be (sample size)/P - does this clarify the point? or am I missing something? $\endgroup$
    – etov
    Feb 7, 2018 at 16:12
  • $\begingroup$ If you can "iterate over the group," then doesn't that imply you know the size of the group? My larger concern was expressed in the preceding comment: your description relies heavily on abstract accounts and thereby might not reflect what's really going on. I think it would help if you could provide some context. $\endgroup$
    – whuber
    Feb 7, 2018 at 16:15

1 Answer 1

1
$\begingroup$

I see this is an old thread, but for the benefit of others who run into this question, I found a good analysis in a paper titled "Estimating Set Intersection using Small Samples" by Henning Kohler published in Proc. 33rd Australasian Computer Science Conference (ACSC 2010), Brisbane, Australia. The paper is available here https://dl.acm.org/doi/pdf/10.5555/1862199.1862207.

Just to provide a quick summary: the author considers a generalized problem where the random samples $A'$ and $B'$ may be of different sizes and proportions. The first question is the probability of drawing the 2 samples with $x$ common items, $a$ items from A and $b$ items from B (so that A' has $a + x$ items and B' has $b + x$ items), given X = $|A \bigcap B|$. This is:

$$p(a, b, x | X) = \frac {\begin{pmatrix} {|A| - X}\cr a \end{pmatrix} \begin{pmatrix} {|B| - X}\cr b \end{pmatrix} \begin{pmatrix} {X}\cr x \end{pmatrix} } { \begin{pmatrix} {|A| + |B| - X}\cr {a + b + x} \end{pmatrix} } $$

The problem of estimating X is then solved using 2 different ways. Firstly, by minimizing the standard error $\sqrt {E((\hat X - X)^2)}$, which is the square root of: $$ \sum^{min(|A|, |B|)}_{X=0} {p(X).\sum_{a,b,x} p(a,b,x|X).(\hat X - X)^2} $$ The result of minimization (after a simplifying assumption that $p(X)$ is a constant) is:

$$ \hat X = \frac { \sum^{min(|A| - a, |B| - b}_{X=x} {p(a, b, x|X)*X} } { \sum^{min(|A| - a, |B| - b}_{X=x} {p(a, b, x|X)} } $$

Unfortunately this is expensive to compute. The author also provides a second way to estimate X - an MLE estimate based on maximizing $p(a, b, x | X)$ which has a closed form:

$C_1 = x.(|A| + |B| + 1 - (a + b + x))$

$C_2 = |A|.b.(|A|-a) + |B|.a.(|B|-b)$

$C_3 = |A|.b + |B|.a - a.b$

$a_0 = |A|.|B|.C_1 - C_2$

$a_1 = C_3 - C_2 - (|A| + |B|).C_1$

$a_2 = C_1 + C_3$

$\hat X = \frac {-a_1 \pm \sqrt {a_1^2 - 4.a_0.a_2}} {2.a_2}$

$\endgroup$
2
  • 2
    $\begingroup$ If that link went dead your answer would lose its value so can you edit it to include the salient points from the material you link to? $\endgroup$
    – mdewey
    May 11, 2021 at 16:16
  • $\begingroup$ This is indeed a good pointer. Reading through the paper, it seems that the suggested methods rely on sampling the original groups in a specific (synchronized) way, an element which is absent the question (i.e. as the question is presented, the sampling method - uniform % selection - is a given.). However in my opinion this would be a valuable addition here. As others have noted, you should edit the answer to include the relevant details. $\endgroup$
    – etov
    May 13, 2021 at 8:28

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.