Multiclass Classification with large number of categories

I am making a recommendation system (kind of) and I have to recommend the item a user is most likely to buy in his next purchase. Doesn't matter if he already bought this item.

Given this, I'm treating this problem as a multiclass-classification problem with 4000 categories (number of different items users can buy).

Searching in Wikipedia I found this link and decided to use the One vs -rest method. So I decided to train one random forest for each item using as covariates flags if the user bought each item before (so I have around 4000 covariates). Then I will decide a rule to decide the recommended item (something like the one which has the largest probability to be bought or the largest lift.)

My problem is that it's taking too long to train (5 to 10 min per item):

> 5*4000
[1] 20000
> 20000/60
[1] 333.3333
> 333.3333/24
[1] 13.88889


So in the best case it would take 2 weeks to train.

I would like to know if the method i'm using is right, and if there's another faster method to achieve this.

You might have more luck with a Naive Bayes Classifier. It can handle a large number of target classes, and is relatively fast to train, since you largely just calculate a bunch of univariate stats to plug into at prediction time. It won't capture fancy interactions as much as a random forest though, so if you are concerned about "they only buy shoelaces if they bought shoes but NOT shoeshine" vs "they often buy shoelaces if they've bought shoes" then it may disappoint. You may also want to incorporate a time component, but I'm not sure what you're doing.

https://en.wikipedia.org/wiki/Association_rule_learning may also be relevant.

• I managed to reduce the number of variables using some simple rules and I could train all random forests. Like you said, naive bayes was less accurate but was faster to train. Thanks for your answer! – Daniel Falbel Jul 28 '16 at 14:49