SubSampling data such that at least K classes are selected from a huge dataset containing N classes
It seems that you have a simple combinatorics problem.
Assume you have M red marbles and N green marbles in a box. You pull out K marbles randomly. What is the expected values of a ratio of red to green in your sample? Furthermore, what is the variance? Lets define "representative" as extreme values in 95% confidence interval of the ratio (expected-2*std, expected+2*std) been no more than 10% wide relative to the expected value of the ratio. It as straightforward to express it as a function of K (in fact you can do it with pencil and paper for 2 classes). For three classes you can say that the highest variance of the ratio between any two classes should be no more than 10%.
I have a dataset containing 1.3 Million records categorized into 109 classes. Obviously there is class imbalance with highest class being 18% in the data and lowest class being less than 1%
Now, my task is to devise a general forumula/technique/code for sampling from these reords such that: What is the minimum number of records we need to select such that it contains records from K classes (where K can vary from 1 to 109) and is representetive of the original data for these classes. Obviuosly tehre cant be an exact solution so we can deal with 'high confidence' solution