Techniques for Handling Incomplete/Missing Data

My question is directed to techniques to deal with incomplete data during the classifier/model training/fitting.

For instance, in a dataset w/ a few hundred rows, each row having let's say five dimensions and a class label as the last item, most data points will look like this:

[0.74, 0.39, 0.14, 0.33, 0.34, 0]

A few might look something like this:

[0.21, 0.68, ?, 0.82, 0.58, 1]

So it's those types of data points that are the focus of this Question.

My initial reason for asking this question was a problem directly in front of me; however, before posting my Question, i thought it might be more useful if i re-phrased it so the answers would be useful to a larger portion of the Community.

As a simple heuristic, let's divide these data-handling techniques based on when during the processing flow they are employed--before input to the classifier or during (i.e., the technique is inside the classifier).

The best example i can think of for the latter is the clever 'three-way branching' technique used in Decision Trees.

No doubt, the former category is far larger. The techniques i am aware of all fall into one of the groups below.

While recently reviewing my personal notes on "missing data handling" i noticed that i had quite an impressive list of techniques. I just maintain these notes for general peace of mind and in case a junior colleague asks me how to deal with missing data. In actual practice, i don't actually use any of them, except for the last one.

1. Imputation: a broad rubric for a set of techniques which whose common denominator (i believe) is that the missing data is supplied directly by the same data set--substitution rather than estimation/prediction.

2. Reconstruction: estimate the missing data points using an auto-associative network (just a neural network in which the sizes of the input and output layers are equal--in other words, the output has the same dimension as the input); the idea here is to train this network on complete data, then feed it incomplete patterns, and read the missing values from the output nodes.

3. Bootstrapping: (no summary necessary i shouldn't think, given it's use elsewhere in statistical analysis).

4. Denial: quietly remove the data points with missing/corrupt elements from your training set and pretend they never existed.

-
There's also "reduced-model" approach where you train a classifier for every pattern of missing values encountered during testing. IE, to make prediction for x where i'th attribute is missing, remove i'th attribute from all instances of training data and train on that. jmlr.csail.mit.edu/papers/v8/saar-tsechansky07a.html –  Yaroslav Bulatov Aug 10 '10 at 1:27
I believe your definition of Imputation is incorrect in the modern context. Imputation now involves modeling the missing data based on other variables from the data set. The currently-favored Imputation method is Multiple Imputation, which generates multiple alternatives for each missing value (based on the model), processes each alternative completed data set, and then combines the answers reflecting the variability between the results. (In the "old days", people did things like substitute the value from a similar record, or the mean, etc, but not now.) –  Wayne Feb 19 '12 at 14:56

I gave this answer to another question, but it might apply here too.

"There is a reasonably new area of research called Matrix Completion, that probably does what you want. A really nice introduction is given in this lecture by Emmanuel Candes"

Essentially, if your dataset has low rank (or approximately low rank) i.e. you have 100 rows, but the actual matrix has some small rank, say 10 (or only 10 large singular values), then you can use Matrix Completion to fill the missing data.

-

If you have a reasonable hunch about the data generating process that is responsible for the data in question then you could use bayesian ideas to estimate the missing data. Under the bayesian approach you would simply assume that the missing data are also random variables and construct the posterior for the missing data conditional on the observed data. The posterior means would then be used as a substitute for the missing data.

The use of bayesian models may qualify as imputation under a broad sense of the term but I thought of mentioning it as it did not appear on your list.

-