# What should I use if I have millions of possible values for a feature in a sklearn predictive model?

I am trying to create a large model. One of the features is categorical, and it has almost 100 million entries.

I have looked at sklearn LabelEncoder, but I am concerned that it will still create an ordering in my labels which I would like to avoid. If I use one hot encoding I would end up with really large vectors with 100 million dimensions. What are my options?

• Please clarify, 100 million responses or 100 million levels?? It makes a huge difference. 100 million responses is normal, 100 million levels sound crazy. – HelloWorld Jan 25 '17 at 3:16
• I mean that I have a feature that can assume 100 million categorical values. – user Jan 25 '17 at 3:21
• 100m levels... Can you briefly describe what it is? – HelloWorld Jan 25 '17 at 3:22
• I cannot go into the details, but say for example you create a dictionary with all the different words in every different language including their variations (so you would have go, goes, gone, going, etc.). But you still need to keep them separate (so go and gone should be considered as dissimilar as go and any other word). – user Jan 25 '17 at 3:26
• word2vec does this so it is feasible. So one option is to just do it. Another option is to use the hashing trick with a fixed-length input as wide as the cardinality of the data set, if you do not expect to encounter every element. – Emre Jan 25 '17 at 4:00

Unfortunately, AFAIK no sklearn model supports categorical variables.

For instance, sklearn decision trees only support rules such as X<n, not X==n which would be desirable here.

Also, the decision tree algorithm they implement only produces local one-look-ahead optimization. What this means is that, it may not produce rules such as X<n followed by X>n-1, even if such rule would be highly desirable.

In the end you will end up with non-sense things like: Car > 1 and then Car < 6 where 1 is Volkswagen and 6 is Ferrari.

The typical workaround is to use one-hot encoding, which might be a pain in the ass in your case. And then, it might not: sklearn decision tree supports sparse matrices, so the memory penalty would be low. You can use scipy for this. (Sparse matrices stores data differently than regular matrices. Instead of requiring $n\times m$ size, the memory requirement is proportional to the number of non-zeros in your matrix.) In terms of speed, it should not be any different than if the algorithm natively supported categorical variables.

This being said, your data may not allow for use of sparse, if the rest of the features are non-sparse. I don't think scipy has support for a sparse-dense hybrid matrix.

Another workaround I can think of would be to produce an Euclidean distance matrix between observations of the various categories (you may want to normalize first). Then group categories that are close together. Then build a hierarchical model, where you predict the final category for each category. In python, this is easier than it seems. You can create a class for your model using sklearn base classes.

I love Python and sklearn. But I believe in using the right tool for each job. I would use R which has native support for categorial variables (they call them factors) and has a plethora of decision tree packages. (Note: xgboost for R does not support categorial variables, it ignores the factor class-type.) Weka could also be a good tool, which also has very powerful decision tree algorithms.

You can use sklearn.preprocessing.OneHotEncoder with sparse=True. It will return a a scipy.sparse matrix some models can work with. Your matrix will indeed be 100e6 columns wide, but not densely populated won't take a lot of RAM.

An elastic net (also known as L1 and L2 regression) model can be an effective technique for dealing with very high dimensional problems. It's often used for dealing with genomic data. Elastic net documentation for sklearn can be found here. Elastic net differentiates between variables that have predictive value and those that don't, and it often sets useless variables' coefficients to zero. This can dramatically reduce the number of categories in your problem.

You can take advantage of sklearn by creating "dummy" variables out of your categories. If one of your levels/columns were "color", and your categories were red, green and blue, then you would make two columns, e.g. for one for red and another for green (blue is not necessary by process of elimination).