I have a general question on reservoir sampling. When I use this method to sample a very large dataset for training machine learning classification algorithms, I am curious as to how to make my pipeline robust to fluctuations in class distribution across samples.

For example, suppose I am working on a binary classification problem. I want to sample a relatively small subset of data on which to evaluate my algorithms, so I used reservoir sampling. However, it seems to me (thought I could be wrong) that by chance I may draw a sample wherein the class distribution is significantly different from that seen in the larger population of data. If this is a correct inference, can anybody tell me how to remedy the situation? If reservoir sampling is not the answer, what other procedure are out there that I can leverage in this case (apart from using distributed environment)?

I am learning, so some explanation, hint, and direction would be greatly appreciated.

  • $\begingroup$ For binary classification I don't understand why you do this instead of simply counting elements from each of the classes. If you have many classes, it might make sense - it is easy to prove that algorithm R in en.wikipedia.org/wiki/Reservoir_sampling gives you a uniformly random sample. $\endgroup$ – Valentas Sep 11 '15 at 20:29

Consider the class to be the variable that you are sampling.

Your "reservoir sample" should still be as good as uniformly drawn from your data.

Yes, there may be fluctuations, in particular if you have small samples. If you sample a single observation, the class distribution in that sample will be 100% of one class, there is no way around that. ;-)


If you evaluate the effectiveness of your classifier using a ROC curve, you don't have to worry so much about class skew:

ROC curves have an attractive property: they are insensitive to changes in class distribution. If the proportion of positive to negative instances changes in a test set, the ROC curves will not change.

If you are using R, the ROCR package is excellent for constructing ROC curves (and many other metrics, too).


Your Answer

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

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