# One-hot-encoding gives untractable amount of classes

I'm performing regression on the price of bycicles based on their brand, model and submodel. These features are hierarchical: one model belongs only to one brand but one brand can have many models. Similarly, one submodel belongs only to a model but the model can have many submodels.

I tried one-hot encoding the combination of [brand-model-submodel] but I get almost 45k classes. Ironically, the resulting matrix is so big that I can't even apply pca because I run out of memory. Many machine learning models also run out of memory when they try to fit the data, so I really need to reduce the dimensionality somehow.

I was thinking of there is a way to only branch out a class if the prices are really different from those of their siblings. Other than that, how would you solve it? What alternatives do I have? I'm using python by the way, in case you can point me to concrete resources.

• Many ideas here, and look at the tag many-categories. – kjetil b halvorsen Jan 19 '19 at 11:46
• Possible duplicate of Principled way of collapsing categorical variables with many levels? – kjetil b halvorsen Jan 19 '19 at 11:46
• @kjetilbhalvorsen I don't agree with this close vote. This question seem to focus more on something more basic, i.e. representing and storing the data, while the linked thread discusses situation what to do when you already managed this. That is why I provided answer that discusses both the engineering and modelling solutions (with using parts my old answer that actually didn't fit well to the linked thread). – Tim Jan 19 '19 at 11:54
• Your answer is good, but with so many levels the "representation" and analysis aspects of the problem will be intertwined. – kjetil b halvorsen Jan 19 '19 at 11:57
• Just a suggestion, but are there 45k submodels of bicycles in the world? Are you sure you are using a hierarchical classification and not just crossing factors? That is, you might be making a class for every brand combined with every model of all brands. – Pere Jan 19 '19 at 12:11

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.

When you handle the issues with efficiently storing the data, you can also check the Principled way of collapsing categorical variables with many levels? thread for some more hints on modelling it.

Weinberger, K., Dasgupta, A., Attenberg, J., Langford, J., & Smola, A. (2009). Feature hashing for large scale multitask learning. [In:] Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, pages 1113–1120, 2009.