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.