Classification with millions of records, thousands of categories - keep memory use efficient? I have about 20 categorical variables to predict another categorical variable. One of the variables can have as many as 12000 levels (O/P will be one of the 12000) and another one can have about 8000 levels. Rest will have less than 100 levels. Random Forest was the first thing that came to my mind, but Python’s Random Forest implementation doesn’t support categorical variables. If I one-hot encoded all these variables, then I will end up with thousands of variables for Millions of records which will throw me into memory issues.

What are my options?
I assume you are using the sklearn implementation of random forests. If you are not bound to use sklearn, you could try another implementation, like the one from h2o, that supports enum categorical variables.

Alternatively, you could first determine if all of the 12000 levels are relevant: for each of the 12000 levels, you could compute something like information gain, which will tell you if that level provides any information relevant to predicting the class. You may then use a threshold on the information gain to discard all levels that provide no information, reducing the number of levels and, perhaps, allowing you to use one-hot encoding.

Basically, if $H$ is the entropy (of the class label) for a set of examples, given a dataset $D$, you could discard any level $v$ of an attribute $a$ for which the following is below a certain threshold (to be determined given how many levels you want to keep):

$$
H(D) - \frac{|D_v|}{|D|} \cdot H(D_v)
$$

where $D_v = \{x \in D|value(x, a) = v\}$