Handling large imbalanced data set

Question

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?

Answer 1

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.

Answer 2

What is the purpose of the analysis? What are the criteria of primary interest (accuracy)?

The class imbalance problem stems from having insufficient data from the minority class to adequately characterise it's distribution. This means imbalance is only a problem if you have a small dataset, if you have lots of data, the imbalance problem generally resolves itself and resampling the dataset is likely to make things worse rather than better.

Answer 3

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.