Response variable with very high number of class levels in R
Cluster your n response classes into m clusters, where m &lt; 1,000. With an incoming instance i assign it to one of the m clusters using your favorite classification algorithm. Once the instance has been assigned to a specific cluster, you just need to run it through a classifier trained on the classes that comprise that particular cluster.

I've used this particular architecture to assign texts to one of n possible "emotions", which I illustrate below. The incoming text was first scored with a binary classifier trained on positive &amp; negative texts. Given the text's probability of being positive (as predicted by the classifier), the text was then routed to either a series of all positive or a series of all negative emotion classifiers where it was a assigned a specific emotion. 



This same sort of design should work your case. First you assign your instance a cluster. Given that assignment, send your instance to the next stage - where the final classification occurs.