What should I use if I have millions of possible values for a feature in a sklearn predictive model?
Unfortunately, AFAIK no sklearn model supports categorical variables.

For instance, sklearn decision trees only support rules such as X&lt;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&lt;n followed by X&gt;n-1, even if such rule would be highly desirable.

In the end you will end up with non-sense things like: Car &gt; 1 and then Car &lt; 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.