Multiclass classification with large number of classes but for each user the set of target classes is known

Question

Hi Data Science Stack Exchange! I'm new here but I'm familiar with some machine learning theory (took some courses in school) and my question is more about how to apply ML in a practical setting.

I have this project where I'm trying to design a system to predict which "store" a user is going to buy a given item from. However, the set of stores a user can potentially buy from is already known for each user (because this promotion only works at limited stores they signed up for). On average, the set of stores the average user can buy from is around 3 but the # of distinct stores across all users is about 10000.

In theory, for a single user this seems like a simple classification problem. We have historical information such as the time/day/month the user bought item Y from store X along with other features such as location (postal code) where the user lives and features related to the type of item they are buying (cost, weight, brand).

However, the issue is that there's currently around 6000 users so going with this approach seems like I would need a separate model for each user but that doesn't seem like an efficient solution to me or at least not how I've generally seen ML algorithms used. Unfortunately, I don't see any other way I could take into account the fact that the set of stores a user can already buy from is known for each user already. I suppose I could have a categorical variable for each buy-able store as a feature but then that would be equivalent to adding 10000 features and I'm not sure if this would scale as the number of distinct stores increases.

It would be really helpful if anyone has any insight on how to apply machine learning techniques to this kind of problem in general as this is sort my first time working on a "real" problem. Thanks!

Answer 1

so it sounds like you have historical transaction data. If you do, you probably want to train a model using store label as your dependent variable, and all the others independent variables.

set.seed(100)
items <- c("milk", "cheese", "steak", "apple", "eggs")    
df <- data.frame(trans_id = 1:100, 
                       cust_id = sample(1:10, 100, replace = TRUE),
                       item = sample(items, 100, replace = TRUE)
                       )

df$store <- as.factor(sapply(df$cust_id, function(x) {
    sample(letters[cust_id:(cust_id+2)],1)
  }))

head(df)
##  trans_id cust_id   item store
##1        1       4 cheese     e
##2        2       3 cheese     f
##3        3       6   milk     f
##4        4       1 cheese     f
##5        5       5  steak     d
##6        6       5  apple     f

#train General linear model
glm(formula = store ~., family = binomial(link = "logit"), 
     data = df)

##all:  glm(formula = store ~ ., family = binomial(link = "logit"), data = df)
##
##Coefficients:
##(Intercept)     trans_id      cust_id   itemcheese  
##   1.320095    -0.007399    -0.066363     0.024632  
##   itemeggs     itemmilk    itemsteak  
##   0.084018     0.047022     1.069399  

library("e1071")
#train naive bayes
naiveBayes(formula = store ~., data = df)

Depending on business constraints you may or may not want to include customer id as a predictor variable (include if you will only be predicting stores for a finite known pool of customers; don't include if your model needs to generalize across customers). Similarly, if this were a real data set, you probably wouldn't include a transaction id as a predictor variable, because it won't generalize to new cases (transaction ids are unique)

Answer 2

To add to what @Brandon has said: you can add another set of variables like customer ID* other predictors ( product of one hot customer IDs with other predictors). These additional predictors will implicitly capture the fact that different customers have different set of candidate stores. A cleaner approach is to build customer level models if you have enough data Note: you'll have #customers*#predictors additional variables and will need to regularize using L1 penalty

Answer 3

Another approach would be to add a feature that captures which stores the customer was eligible to avail discounts at. A classification model given a large enough dataset would probably figure out that connection:)