Choosing a method to solve a many-to-one mapping problem

Question

Problem description

To predict a list of values associated with a set of variables.

Trainset

Trainset has a set of variables X1, X2, X3, ... Xn. In the simplest form, each variable is of type numeric with different ranges. The largest range being 1-100000 and the smallest range being 1-10. Target is a list of numbers(Y) whose range is again 1-100000. The list is of variable length so each observation has varying number of targets. Could assume that the target list is a list of item IDs.

Example of the train subset (X1, X2, X3... Xn => {Y})

Observation1: 2345, 23, 8, ... 99399 => {2345, 98755}

Observation2: 45276, 3, 1, ... 80001 => {7865, 98675, 78954}

and so on...

Prediction

So, prediction is a list of numbers that can vary depending on the variable values.

My thoughts

---

1. Looks like a multi label classification problem with each label corresponding to a single value in the prediction list.
2. But because the range of the labels is large (i.e. 1-100000), cannot use a classification method.
3. Probably can use multi target regression method to predict a list of targets for an observation in the test set.

4. Assuming Ym is the maximum length of the prediction list in the training set. Could fill the prediction list in Observation1 of the training set as:

   Observation1: 2345, 23, 8, ... 99399 => {2345, 98755, 0 , ... 0} (0 representing empty value which is repeated Ym-2 times)

5. Might be worth normalizing all the variables and values in the prediction list.

Questions

1. Am I missing something ? Is this method appropriate for this kind of problem ?
2. The values in the prediction list are identifiers so they do not have a direct correlation with other values & variables in the observation. And this is a concern that worries me. Will it be a major concern if I use a multi target regression ?
3. What kind of methods can I use ? neural network or linear regression ?
4. Because the complete set of targets is known during training, could a clustering method be used as I am trying to predict a cluster of items that correspond to an observation ?

Answer 1

One possible approach is to assume that, conditional on a device's features, each cookie appears independently. In that case, you can fit a SVM or decision tree or some other classifier (I don't recommend logistic regression for classification), with the appearance of each cookie being a binary outcome. This means you have one model for each cookie. Yes, this means you are training 100,000 separate classifiers, each on who-knows-how-many data points. But the theoretical framework is straightforward and the computational challenge is not insurmountable