What approach for creating a multi-classification model based on all categorical features (1 with 5,000 levels)?
Personally, I think that building a predictor on such user Ids is not that efficient neither useful. Can you change your problem in a different manner? 

When we do any analysis we drop those ids as they are of no use they are only the incidents in a large population and we try to group them in categories which describe their features. For example, users which have good eyesight will play basketball even if it rains.

So try to think like that.