Return to Revisions

If the problem is memory, then you should try using sparse data structures, that are designed for such cases. In python you have scipy.sparse matrices that are handled e.g. by scikit-learn.

The simple solution is simply to drop the uncommon features, since they wouldn't be useful for the vast majority of problems. What people usually do is they choose some cutoff, say features that are relevant for less then 1% of the samples and then, they simply drop them. This should be done with caution, since it might be the case that with unbalanced classes, or with multiclass classification, those rare features may be great predictors for some rare classes.

You can also try hashing trick (Weinberger et al, 2009). The idea is use a hash functions that maps $n$ categories to a prespecified number of $m$ hashes (where $m \ll n$). There is a number of such functions, but we are looking for such that (a) are deterministic and (b) map the inputs uniformly to the outputs. Hopefully, this is the case for the high-quality hash functions (e.g. MD5 or xxHash). Obviously, we end up with hash collisions (different inputs get mapped to same outputs), but nonetheless, as described by Weinberger et al (2009), this seems to work remarkably well in machine learning and gives decent results (sometimes reported to be better then with raw data). Comparing to more advanced approaches, this is a very cheap trick (extremely fast, can be applied out-of-the-box, to any data, no matter what it is), but that is exactly the reason why people use it when the number of categories is really large (e.g. words in natural language).

Another alternative is to get a machine with more RAM memory, nowadays the cloud solutions are easily available and cheap, so this may be worth considering. You can easily rent a machine with hundreds of gigabytes of RAM with paying just for the computation time.

When you handle the memory problems, you can try models that handle large numbers of features by design, e.g. a neural network using categorical embeddings. What embeddings do, is they learn how to reduce dimensional of categorical data. The modern deep learning frameworks like TensorFlow are designed to handle large amounts of data efficiently. Deep learning is currently a hype and it doesn't always catch up with the what the marketing guys tell you about it, but the most basic neural network is basically a regression. If you want to use regression, then you can define a two-layer network, where first you learn the embeddings and then just use them as features for regression in second layer. Additionally, you can (and probably should) use regularization (e.g. $L_1$, $L_2$, dropout, batch normalization etc.). If you want to make the model deeper, you can always extend it.