2
$\begingroup$

I have an imbalanced data set consisting of some 10's of millions text strings, each with thousands of features created by uni- and bigrams, and additionally I have also the string length and entropy of string as features.

It is a multiclass data set (40-50 classes), but it is imbalanced. Some classes can be 1000x smaller compared to the largest class. I have restricted the data to 1 million strings per class as maximum, otherwise the imbalance could be even larger.

Because of this I want to use over-sampling to improve the data for the underrepresented classes. I have looked into ADASYN and SMOTE from the python imblearn package. But when I run it the process eats up all my RAM in the swap memory, and soon after the process gets killed. I assume because the memory is not enough.

My question is now how to best proceed. Obviously my data is too large to be over-sampled as it is. I have thought of two options, but I cannot make out which is the most "correct".

  • I sent in only one underrepresented class and the largest class, and repeated this for each underrepresented class. I am not sure if this could mean that classes might start to overlap though.

  • I instead under-sample the data, maybe down to 100k samples per class. This might reduce the data enough such that I can run oversampling on the less represented classes (with 1k-10k samples).

Any other options that are more appropriate that I have missed?

$\endgroup$
4
$\begingroup$

There are multiple options, depending on your problem and the algorithms you want to use. The most promising (or closest to your original plan) is to use a generator to prepare batches of training data. This is only useful for models that allow for partial fits, like neural networks. Your generator can just stratify examples by for example generating a batch that includes exactly one of each target. One epoch would be when you served all the samples from the biggest class.

Downsampling is not a bad idea but it depends on the difficulty of your task, because you do end up throwing away information. You could look at some curves depending on the amount of samples for your model, if it looks relatively capped this wouldn't be a big issue.

A lot of models allow for weighting classes in your loss function. If we have 10,000 of class A and 1,000 of class B, we could weight class B 10x, which means mistakes that way count much harder and it will focus relatively more on samples from class B. You could try this but I could see this going wrong with extreme imbalances.

You can even combine these methods, downsample your biggest classes, upsample your smaller classes and use weights to balance them perfectly.

EDIT: Example of the batch options:

We have 4x A, 2x B and 1x C, so our set is:

A1 A2 A3 A4 B1 B2 C1

Regular upsampling would go to:

A1 A2 A3 A4 B1 B2 B1 B2 C1 C1 C1 C1

But this will not fit in our memory in a big data setting. What we do instead is only store our original data in memory (could even be on disk) and keep track where we are for each class (so they are seperated on target).

A: A1 A2 A3 A4 B: B1 B2 C: C1

Our first batch takes one of each class:

A1 B1 C1

Now our C class is empty, which means we reinitialize it, shuffle them (in this case it's only one example).

A: A2 A3 A4 B: B2 C: C1

Next batch:

A2 B2 C1

B and C are empty, reinitialize them and shuffle:

A: A3 A4 B: B2 B1 C: C1

Next batch is:

A3 B2 C1

And our last one of the epoch would be A4 B1 C1

As you can see, we have the same distribution as the full memory option, but we never keep more in memory than our original ones, and the model always gets balanced, stratified batches.

$\endgroup$
  • $\begingroup$ If I understand you right, you suggest to split the data into multiple batches, and then run the oversampling on each of these separately? Does that mean I should keep the class ratios the same in each batch, or can it be random as long as all classes are present? Because that could mean less than 10 samples per batch for some classes. I will try also the downsampling. I have tried weighting the classes, but that option is not available in all the model algorithms. $\endgroup$ – Tobias Jul 20 '17 at 11:57
  • $\begingroup$ I will add a section with an example, but even less models can deal with this I think. $\endgroup$ – Jan van der Vegt Jul 20 '17 at 12:06
  • $\begingroup$ Thank you very much for the educational example of the batch option. In your case you reuse current data over and over. Can this not have the effect that the model becomes overfitted for the smallest classes? Instead of resampling the data I have, can I instead split my data into batches and feed it into a oversampling method, like SMOTE? $\endgroup$ – Tobias Jul 24 '17 at 7:19
  • $\begingroup$ Well, normally your small class would still have a significant amount of samples of course. My example is just classical oversampling without needing to replicate everything in memory. You could downsample your bigger classes for big batches and apply SMOTE to that, that might be a good way as well. In the end, it just comes down to trying some methods that fit in memory and evaluating them on your test set. $\endgroup$ – Jan van der Vegt Jul 24 '17 at 7:23
0
$\begingroup$

I suspect the validity of the selected answer since the given example completely ignores the fact that the sampling process does not simply generate more copies of less frequent examples but use something more complicated e.g. finding the nearest neighbor.

I think it likely that it is the latter computationally expensive process (nearest neighbor calculations) which is causing the memory problems. I don't think that the simple process of making multiple copies will produce the same effect as intended by the original algorithms.

$\endgroup$

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.