How often to subsample for classification? It is often recommended to subsample randomly if class sizes are unbalanced in classification - especially when classification accuracy is used. My question however: How often should the subsampling be done? For instance, if I subsample 10 times and then average classification accuracy over these 10 repeated classifications, the accuracy is quite variable comparing results from different instances of this 10-times repeated classification, whereas when subsampling is done say 1000 times, it seems to stabilize. Hence the reduced variability seems to be a useful criteria - is there any more precise benchmark? 
 A: I feel that your understanding of subsampling is not quite correct or your problem is too complex. For two classes subsampling is basically throwing away majority of samples from the larger class, so the remaining amount will be approximately the same to the amount of samples from the smaller class. If, as you write, subsampling lead you to unstable results, then the majority class is not represented well by the subsample (with regards to your model), and you are overfitting your model. 
If your model is good, then even trained on a subsample, it will classify well the unseen samples, at least for the majority class.  
Subsampling is just one of many techniques that can be applied to the unbalanced classes problem. To overcome the (unbalanced dataset) problem, one can also:


*

*Adjust the decision threshold.

*Adjust the underrepresented class weight.

*Oversample/synthesize new samples of the underrepresented classes.

*Throw away examples of underrepresented class and switch to an anomaly detection framework.


As a rule of thumb, you should start worrying when you classes representation ratio grows beyond 1:10, which is basically majority of the real world scenarios. When you do subsampling, you need to make sure that all your resulting classes will have sufficient samples regarding your model complexity and training procedure. It is also relevant to the test procedure, as you need enough samples to have some confidence level in your results.
Also, Accuracy is not very good measure of goodness of the model. When evaluating a model performance you should also consider Precision and Recall (this also depends on the specific task).
You might be interested to read this survey on the subj.
