# How can I reduce this problem to classification?

I have data X with rows which are features associated to a whole "grid". A grid is full of training points that have (x,y) coordinates inside the grid and a classification from {0,1,2}. Given many grids, our task is to be able to label points in a new grid as 0, 1, or 2.

We are solving this problem now by drawing bounding polygons around areas containing points labeled as 1 or 2 and performing regression to find their centroids and several radii. But this seems unsatisfying and may break down in unforeseen complicated cases.

We considered building many classifiers that each take X plus the (x,y) of a point as features and are trained to output {0,1,2} specifically for this (x,y) in the grid, but there are too many points in the grid to train so many classifiers, and beside that we can not guarantee that our training points will be at regularly-placed (x,y) in the future.

Is there a clever way to reduce the problem to standard classification?

• This does not sound like a machine learning problem to me, but maybe I didn't quite get it. Could you explain how a point/cell in the grid is mapped to 0,1 or 2? Sep 5, 2017 at 20:05
• The grid is a map, and points in the grid are used as parameters in simulations. Depending upon the outcome of the simulation, the point gets a label. It is an ML problem: X is a set of other features associated with each grid (independent of the "map" aspect), and the output we are using now is a 38 dimensional Y: [x coordinate of centroid, y coordinate of centroid, one radius every 10 degrees around]. Sep 5, 2017 at 20:07
• To clarify, you have a series of grids which each have NX columns and NY rows, and also for each grid you have a set of covariates, which I'll call Z, of length NZ. Your task is to train on a set of grids and their corresponding Z's, and then given a new Z to predict values for each of the NX*NY points in the new grid? Sep 26, 2017 at 20:23
• Affirmative, yes Sep 27, 2017 at 16:28

Okay, I came up with a few ideas:

Idea 1: Assume the training points are arranged in a regular grid or that if they are irregularly-spaced, we can make some transformation to a grid by choosing the closest point's classification for grid-points or something. Train independent classifiers on every grid point. Advantages: Highly parallelizeable. Disadvantages: Doesn't take advantage of spatial correlations because no learner is aware of the others. You have to keep a lot of classifiers around to build your model. And you lose a little information in the transformation to a grid if points are not already regularly-spaced. Points must be regularly spaced for this, because each classifier has to correspond to a particular (x,y) location in the grid for training to work.

Idea 2: Join (x,y) with X data to generate a larger training matrix, and train one classifier on this. Advantages: The classifier can learn spatial relationships and correlations very naturally. The final model only has one agent. Disadvantages: Not so naturally parallelizeable. Each row of X, corresponding to many (x,y) points, will be duplicated over and over in the join. Training is slow, meaning we would need some kind of data reduction on the grid points to make the join less explosively large.

Idea 3: The Label Powerset transformation, where one "create[s] one binary classifier for every label combination attested in the training set" and then at query-time selects the answer to be the label combination belonging to the binary classifier with highest confidence. Advantages: None in this context that I can think of. Disadvantages: The number of possible combinations in the output space is huge, so we almost certainly don't have enough data to train each binary classifier, and the number of these classifiers in the final model would be huge. And what about cases where the answer should really be something not seen in the training data? This can't handle that.

Idea 4: True multi-label classification to find all y labels for all grid-points in a grid simultaneously as a one multi-dimensional output from a single agent. Advantages: Single agent. Disadvantages: Only a few kinds of learners support this functionality: AdaBoost.MH, AdaBoost.MR, ML-kNN, Decision Trees, Neural Nets (BP-MLL), and some vector-valued kernel methods (possibly some SVM?). Of these, only Decision Trees (and associated types) and kNN have this multi-output functionality built in in scikit-learn.

Idea 5: Do some kind of stochastic ensemble on joined data (as used for Idea 2). Advantages: Parallelizeable. Agents and the ensemble get some notion of spatial relationships between points. Disadvantages: Many agents.

Idea 6: Train one classifier on Idea-2-like joined data, but do data reduction to reduce the total number of points. Possibilities: clustering, only training on points around boundaries, using representative subsets.