3
$\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$
  • $\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 '18 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 '18 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 '18 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 '18 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 '18 at 16:15

Your Answer

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

Browse other questions tagged or ask your own question.