Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Let's say I have a large set of $S$ values which sometimes repeat. I wish to estimate the total number of unique values in the large set.

If I take a random sample of $T$ values, and determine that it contains $T_u$ unique values, can I use this to estimate the number of unique values in the large set?

share|improve this question
    
Can you also keep count of the number of copies of each unique value in the sample? Strikes me that might help. –  onestop Nov 27 '11 at 19:40
    
@onestop, yes I could do that –  sanity Nov 30 '11 at 16:25
add comment

migrated from stackoverflow.com Nov 27 '11 at 16:51

This question came from our site for professional and enthusiast programmers.

2 Answers

Here is a whole paper about the problem, with a summary of various approaches. It's called Distinct Value Estimation in the literature.

If I had to do this myself, without having read fancy papers, I'd do this. In building language models, one often has to estimate the probability of observing a previously unknown word, given a bunch of text. A pretty good approach at solving this problem for language models in particular is to use the number of words that occurred exactly once, divided by the total number of tokens. It's called the Good Turing Estimate.

Let u1 be the number of values that occurred exactly once in a sample of m items.

P[new item next] ~= u1 / m.

Let u be the number of unique items in your sample of size m.

If you mistakenly assume that the 'new item next' rate didn't decrease as you got more data, then using Good Turing, you'll have

total uniq set of size s ~= u + u1 / m * (s - m) 

This has some nasty behavior as u1 becomes really small, but that might not be a problem for you in practice.

share|improve this answer
add comment

The simulation strategy

Collect m random samples of size n from the set S. For each of the m samples, compute the number u of unique values and divide by n to normalize. From the simulated distribution of normalized u, compute summary statistics of interest (e.g., mean, variance, interquartile range). Multiply the simulated mean of normalized u by the cardinality of S to estimate the number of unique values.

The greater are m and n, the more closely your simulated mean will match the true number of unique values.

share|improve this answer
1  
Isn't this solution kind of lame? It doesn't take into account saturation effects at all. –  rrenaud Nov 28 '11 at 21:36
    
@rrenaud Compared to your solution, I agree that mine appears inferior. –  Brash Equilibrium Nov 28 '11 at 22:21
    
@rrenaud I do still advocate a simulation strategy whereby you calculate the probability of unique items using the GTFE on as many-as-feasible large-as-feasible samples to get some sense of sampling error for the probability of unique items. Or is there an explicit formula to calculate all of the moments? I wouldn't think it is the negative binomial since the binomial distribution, according to the Wikipedia reference, does not characterize the distribution of the number of unique items. But awesome! I'll file this away for later. –  Brash Equilibrium Nov 28 '11 at 22:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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